在向量中移动项目的最有效方法是什么？ [英] What is the most effective way to move items within a vector?

问题描述

我已经看到一些特殊情况，其中可以使用 std :: rotate 或与一种搜索算法结合使用，但是通常：当一个向量的向量为N时项并想要编写如下代码的函数：

I've seen some special cases where std::rotate could be used or a combination with one of the search algorithms but generally: when one has a vector of N items and wants to code function like:

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

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

I've been thinking about creation of a new vector + std::copy or combination of insert/erase but I can't say I ended up with some nice and elegant solution.

推荐答案

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

It's always important to profile before jumping to any conclusions. The contiguity of vector's data memory may offer significant caching benefits that node-based containers don't. So, perhaps you could give the direct approach a try:

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 。

In C++11, you'd wrap the iterators in the first and third line into std::make_move_iterator.

（要求是 dst 不在 [start，start + length）之内，否则该问题的定义不明确。）

(The requirement is that dst not lie within [start, start + length), or otherwise the problem is not well-defined.)

这篇关于在向量中移动项目的最有效方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！