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

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);
}

(这假设范围有效且不重叠.)