11

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

a-b-c-d-e

将“b”移到前面：

a-c-d-e-b

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

预先感谢。

4

2 回答 2

17

开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的这个基准所示，vector 更好的内存缓存行为也很重要。

更新：几位评论者提到简单地交换元素：这仅适用于您想转换a-b-c-d-e为a-e-c-d-b. 在这种情况下，std::iter_swap请在您喜欢的任何容器上使用。对于 into 的a-b-c-d-e转换a-c-d-e-b，使用std::rotateor list::splice。

于 2013-01-29T09:51:41.777 回答
15

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

否则，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（它也复制所有以下元素——这意味着所有元素，因为我们在开头插入）模式的副本更少。

于 2013-01-29T10:30:58.733 回答