c++ - 标准 : container c++ move to front

Question

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

a-b-c-d-e

将“b”移到前面:

a-c-d-e-b

标准容器中没有这样的功能。因此，我认为我必须结合 remove 和 push_front 函数，但有没有人能找到更好的主意？

提前致谢。

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 可能非常慢 一般(因为它的位置差)；我会衡量非常 小心反对使用 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(也复制所有 以下元素的——这意味着所有元素， 因为我们在开头插入)模式。