标准库：C++容器移动到前端

Question

我在寻找一个像std::list这样的标准容器，可以高效地将元素移动到前面：

a-b-c-d-e

将 "b" 移到前面：

a-c-d-e-b

标准容器中没有这样的功能。因此，我认为我必须结合 remove 和 push_front 函数，但是否有更好的想法？

提前致谢。

- Jav

---

"efficiently" 的意思是什么？ - Jon

好问题...我的意思是比将其删除并在前面创建更好。 如果我必须从头开始实现它（用C语言），我可以简单地使a.next指向“c”，c.prev指向“a”，b.prev指向“e”，b.next指向NULL，front指向“b”和e.next指向“b”...那将是有效的；但重新实现一个容器有点太耗时了;) - Jav

“快速”列表解决方案会在可能未被缓存的内存中随机更改许多指针（在64位代码中每个指针占用8个字节）。像示例中的五个元素的向量可能适合于单个缓存行，并且非常快。 - Bo Persson

Answer 1

如果您不必维护其他元素的顺序，那么最简单的解决方案无疑就是将要交换的元素与容器中的第一个元素进行交换。这对于所有容器都是高效的。

否则，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 通常会非常慢（因为其局部性很差）；我会非常仔细地测量，以确保在全局上获得优胜。如果迭代以查找要移动到前面的元素的成本比较高，则消除所有副本可能并不是一个优势。（这在很大程度上取决于复制 MyType 的成本以及它有多大。如果 sizeof(MyType) 接近一页的大小，或访问 MyType 导致访问了许多间接分配的对象，则局部性论点将无力回天。）

使用 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（它也复制所有接下来的元素 - 这意味着所有元素，因为我们是在开头插入）模式产生更少的副本。

- James Kanze

---

有什么理由不使用 list.begin() = tmp 而是使用 *list.begin() = tmp？ - mallwright

Answer 2

在 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";   
}

注意: 在STL容器中，最后一个元素通常表示为back，第一个元素表示为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。

- TemplateRex

---

那样比对单个元素进行删除和插入更高效吗？ - Lieuwe

@MichaelWild但是由于一个常数因素的影响，可能会变得更慢。 （当然，这取决于容器的大小和正在移动的类型。） - James Kanze

从std::list中删除一个链接并将其插入到其他位置实际上非常便宜。除了病态情况，如果使用std::vector实现更快，我会感到非常惊讶。 - Michael Wild

@MichaelWild 谢谢，看到更新的答案了。还要注意一下Stroustrup的演讲，它给出了在std::vector上进行插入操作的惊人结果。 - TemplateRex

@MichaelWild 准备惊喜吧。从 std::list 中删除一个元素，然后将其插入到头部，涉及两个元素的复制，_加上_一个释放和一个分配。释放和分配内存很容易比复制几百个 int 或 double 花费更多的时间。对于少于一千个 int 的集合，std::vector 在此操作中可能会胜过 std::list。即使涉及到 splicing 的解决方案也可能会触及几个不同的页面，而对于较小的数据集，使用 vector 的解决方案可能永远不会有缓存未命中。 - James Kanze