std：container c ++ move to front [英] std: container c++ move to front

问题描述

我正在寻找一个std容器，如std :: list，可以有效地将一个元素移动到前面：

  abcde 
  

将b移到前面：

  acdeb 
  

容器。因此，我想我必须结合一个remove和push_front函数，但任何人都可以找到一个更好的主意？

提前感谢。

那么最简单的解决方案无疑只是交换
元素想要与容器中的第一个元素。

否则， std :: list 提供 splice 操作，可以使用
。像下面这样，我想：

  void 
 moveToFront（
 std :: list< MyType> & list，
 std :: list< MyType> :: iterator元素）
 {
 if（element！= list.begin（））{
 list.splice .begin（），list，element，std :: next（element））; 
} 
} 
  

这应该只有几个指针操作，和
无个副本。另一方面， std :: list 在
中可能很慢（因为它的局部性很差）;我使用 std :: vector ，
仔细地测量非常简单的实现，以确保它是一个全局的胜利。在这里消除所有副本
可能不是一个胜利如果迭代找到你想要的元素
移动到前面是十倍贵。 （很多这个
取决于多少$ MyType 是复制，以及
是多大。如果 sizeof MyType）接近页面大小，或者
访问 MyType 会导致大量间接访问
对象，局部性参数不会成立。）

使用 std :: vector erase / insert

  void 
 moveToFront（
 std :: vector< MyType>& list，
 std :: vector< MyType> :: iterator元素）
 {
 MyType tmp（* element）; 
 std :: copy_backwards（list.begin（），std :: prev（element），element）; 
 * list.begin（）= tmp; 
} 
  

这将导致比 / code>（它复制
所有以下元素） insert （它还复制以下元素的所有
元素—的元素，
，因为我们在开头插入）模式。

I'm looking for a std container like a std::list that can efficiently move an element to the front:

a-b-c-d-e

move "b" to front:

a-c-d-e-b

There is no such function in the std containers. Therefor, I think I must combine a remove and push_front function but has anyone can find a better idea?

Thank in advance.

解决方案

If you don't have to maintain the order of the other elements, then the simplest solution is doubtlessly just to swap the element you want with the first element in the container. This will be efficient with all containers.

Otherwise, std::list offers a splice operation which could be used. Something like the following, I think:

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

This should end up with only a couple of pointer operations, and no copies. On the other hand, std::list can be very slow in general (because of its poor locality); I'd measure very carefully against the naïve implementation using std::vector, to make sure it was a win globally. Eliminating all copies here may not be a win if iterating to find the element you want to move to the front is ten time more expensive. (A lot of this depends on how expensive MyType is to copy, and how large it is. If sizeof(MyType) is close to the size of a page, or accessing MyType ends up accessing a lot of indirectly allocated objects, the locality argument won't hold.)

With an std::vector, rather than the obvious 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;
}

This will result in less copies than the erase (which copies all of the following elements) insert (which also copies all of the following elements—which means all of the elements, because we are inserting at the beginning) pattern.

这篇关于std：container c ++ move to front的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！