在向量内移动项目的最有效方法是什么？

Question

我见过一些特殊情况，可以使用 std::rotate 或与其中一种搜索算法结合使用，但通常：当一个人有 N 个项目的向量并想要编写如下函数时

void move( int from, int count, int to, std::vector<int>& numbers );

：一直在考虑创建一个新的向量+ std::copy 或插入/擦除的组合，但我不能说我最终得到了一些漂亮而优雅的解决方案。

Answer 1

在得出任何结论之前先进行分析总是很重要的。 vector 数据内存的连续性可能会提供基于节点的容器所没有的显着缓存优势。因此，也许您可​​以尝试直接方法：

void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
  const size_t final_dst = dst > start ? dst - length : dst;

  std::vector<T> tmp(v.begin() + start, v.begin() + start + length);
  v.erase(v.begin() + start, v.begin() + start + length);
  v.insert(v.begin() + final_dst, tmp.begin(), tmp.end());
}

在 C++11 中，您可以将第一行和第三行中的迭代器包装到 std::make_move_iterator 中。

（要求 dst 不能位于 [start, start + length) 范围内，否则问题无法明确定义。）

Answer 2

根据向量的大小和涉及的范围，这可能比执行复制/擦除/插入更便宜。

template <typename T>
void move_range(size_t start, size_t length, size_t dst, std::vector<T> & v)
{
    typename std::vector<T>::iterator first, middle, last;
    if (start < dst)
    {
        first  = v.begin() + start;
        middle = first + length;
        last   = v.begin() + dst;
    }
    else
    {
        first  = v.begin() + dst;
        middle = v.begin() + start;
        last   = middle + length;
    }
    std::rotate(first, middle, last);
}

（这假设范围有效并且不重叠。）

Answer 3

C++11 之前的版本（尽管以下内容仍然有效），对于专门化/重载 std::swap 的包含类型，您可以获得更高效的“移动”。要利用这一点，您需要执行类似的操作

std::vector<Foo> new_vec;
Foo tmp;

for (/* each Foo&f in old_vec, first section */) {
    swap (f, tmp);
    new_vec .push_back (tmp);
}

for (/* each Foo&f in old_vec, second section */) {
    swap (f, tmp);
    new_vec .push_back (tmp);
}

for (/* each Foo&f in old_vec, third section */) {
    swap (f, tmp);
    new_vec .push_back (tmp);
}

swap (new_vec, old_vec);

。如果 Foo 有移动运算符但没有专门的 swap，那么上面的内容也可能为 C++11 提供良好的结果。

如果Foo一些巧妙的序列类型可能效果更好> 没有移动语义或其他优化的 swap

另请注意，如果上述内容在函数中

std::vector<Foo> move (std::vector<Foo> old_vec, ...)`

，那么您可能能够执行整个操作 无需复制任何内容，即使在 C++98 中要实现此功能，您需要经过value 和 not 通过引用，这违背了传统的首选通过引用传递的智慧。