std:container c ++移到前面

Question

我正在寻找像std :: list这样的std容器,它可以有效地将元素移动到前面:

a-b-c-d-e

将"b"移到前面:

a-c-d-e-b

std容器中没有这样的功能.因此,我认为我必须结合使用remove和push_front函数,但任何人都可以找到更好的主意吗？

预先感谢.

Answer 1

在std::vector,您可以使用std::rotate,具有线性复杂性

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>

std::vector<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   // swap ranges [1, 2) and [2, 5)
   auto it = std::next(v.begin(), 1); // O(1)
   auto rb = std::next(it);
   auto re = v.end();
   std::rotate(it, rb, re); // O(N)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));   
   std::cout << "\n";
}

在一个std::list你可以使用成员函数splice,它(给定迭代器)具有恒定的复杂性

#include <algorithm>
#include <iostream>
#include <iterator>
#include <list>

std::list<int> v = { 0, 1, 2, 3, 4 };

int main()
{
   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ",")); 
   std::cout << "\n";

   auto it = std::next(v.begin(), 1); // O(N)
   auto rb = std::next(it);
   auto re = v.end();   
   v.splice(it, v, rb, re); // O(1)

   std::copy(v.begin(), v.end(), std::ostream_iterator<int>(std::cout, ","));
   std::cout << "\n";   
}

注意:最后一个元素通常表示为backSTL容器,第一个元素表示为front.因为std::vector,获取某个元素的迭代器是恒定时间,交换是线性时间.因为std::list,获取迭代器是线性时间,但拼接到同一列表是恒定时间.然而,正如Stroustrup的这个基准所示,矢量更好的内存缓存行为也很重要.

更新:几个评论者提到简单交换元素:这仅适用于您想要转换a-b-c-d-e为a-e-c-d-b.在这种情况下,请使用std::iter_swap您喜欢的任何容器.对于改造a-b-c-d-e成a-c-d-e-b使用std::rotate或list::splice.

Answer 2

如果您不必维护其他元素的顺序,那么最简单的解决方案无疑只是将您想要的元素与容器中的第一个元素交换.这对所有容器都很有效.

否则,std::list提供splice可以使用的操作.我认为如下:

void
moveToFront( 
    std::list<MyType>& list,
    std::list<MyType>::iterator element )
{
    if ( element != list.begin() ) {
        list.splice( list.begin(), list, element, std::next( element ) );
    }
}

这应该只有几个指针操作,而 不是副本.另一方面,std::list一般来说可能非常慢(因为它的地方不好); 我会非常谨慎地对待天真的实施std::vector,以确保它在全球范围内取得胜利.如果迭代找到你想要移动到前面的元素,那么消除这里的所有副本可能不是一个胜利.(这很大程度上取决于MyType复制的成本,以及它sizeof(MyType)的大小.如果接近页面大小,或访问MyType最终访问大量间接分配的对象,则locality参数将不成立.)

有了std::vector,而不是显而易见的erase/insert

void
moveToFront( 
    std::vector<MyType>& list,
    std::vector<MyType>::iterator element )
{
    MyType tmp( *element );
    std::copy_backwards( list.begin(), std::prev( element ), element );
    *list.begin() = tmp;
}

这将导致比较少拷贝erase(其复制所有以下元素组成)insert(其也将所有下列元素内,这意味着所有的元素,因为我们在开始插入的)图案.