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

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

  • 回答 (2)
  • 关注 (0)
  • 查看 (19)

我见过一些特殊情况std::rotate可以使用,也可以与其中一种搜索算法结合使用,但一般情况下:当一个有N个项的向量并且想要编码函数时,如下所示:

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

我一直在考虑创建一个新的向量+std::copy或者是INSERT/ERASE的组合。

提问于
用户回答回答于

在得出任何结论之前,首先要描述一下情况,这是很重要的。毗连性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),否则问题就没有得到很好的定义。)

用户回答回答于

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

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

扫码关注云+社区