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

Question

我看过一些特殊情况下可以使用std::rotate或与搜索算法之一相结合，但通常：当有一个N项的向量并希望编写如下函数时：

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

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

- Miro Kropacek

---

也许已经很明显了，但我还是想指出，移动大块内存总是比移动小引用更低效。因此，执行您所描述的操作时，使用std::list而不是std::vector等数据结构实现更加高效。请注意保持原文意思，同时使内容更加通俗易懂。 - Frerich Raabe

如果源区域和目标区域重叠，move函数是否应该正常工作？ - Frerich Raabe

@FrerichRaabe：你说得对，这就是我必须处理的。是的，源和目标可以重叠。 - Miro Kropacek

更新：嘿，这有点尴尬，我去找那个指定功能的人告诉我他们实际上不能重叠。我想这会让事情变得容易得多。 - Miro Kropacek

rotate是最好的方法：https://dev59.com/b2Uq5IYBdhLWcg3wV_Ai#14580001 - Violet Giraffe

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)之内，否则问题就没有明确定义。）

- Kerrek SB

---

我认为你的“length-start>=0”的条件不正确，否则我就不能从索引10复制2个元素了。 - Miro Kropacek

@Miro：当然，那很愚蠢，让我修复一下。我的意思是 length >= 0，但那是自动的。 - Kerrek SB

现在有意义了。我试图修复一个小错别字（final_dst行中有两个“：”），但我没有足够的权限，所以请随意修改。 - Miro Kropacek

@Miro：完成了，谢谢！我经常打错三元条件运算符，不知道为什么。 - Kerrek SB

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

（这假设范围是有效的且它们不重叠。）

- Blastfurnace

---

这个很好用。我希望它能成为标准库的一部分。也许是时候写一个提案了。 - Kuba hasn't forgotten Monica

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

上述内容对于具有移动运算符但未特化swap的C++11也可能产生良好的结果。

如果Foo没有移动语义或优化的swap，则链表或某些聪明的序列类型可能更好。

还要注意，如果上述内容在函数中。

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

那么你可能能够执行整个操作而不复制任何内容，即使在C++98中，但为了使其工作，您需要通过值传递而不是通过引用传递，这与传递引用的常规偏好相反。

- spraff

---

实际上，可能建议不要调用std::swap。将swap(Foo＆，Foo＆)放置在与Foo相同的命名空间中是正常的，并且通过请求std::swap，您无法让ADL找到正确的重载。 - visitor

你应该将自己的 swap 特化放入 std 命名空间中。 - spraff

我可能错了，但据我所知，那不是一个经验法则。你只能专门化函数，但不能部分专门化函数。任何高质量的代码（包括标准库实现）都应该使用ADL来查找适合swap的重载。顺便说一句，我完全看不出你的算法在哪里执行任何形式的旋转。它只是将所有内容复制过去，然后将所有内容交换回原来的样子。 - visitor

@spraff：特化并不是你可以随意选择放在任何地方的新声明。而且你也不允许在 std 命名空间中添加重载。正确的方法是：(a) 在与你的类相同的命名空间中提供一个 swap 重载，这样 ADL 就会选择它，以及 (b) 如果可能的话，则专门化 std::swap。如果你要处理类模板，那么 (b) 是不可能的——至少在 C++03 中是如此。至于调用 swap 函数，你应该这样做：using std::swap; swap(x,y); 这样，就会使用 ADL（这是好的），并使用 std::swap 作为后备方案。顺便说一下，这基本上就是 boost::swap 所做的。 - sellibitze

@UncleBens：您说得很对，自C++11以来，对用户定义的交换函数有了要求。 - JoeG