将向量元素移动到向量的末尾

Question

有没有比擦除元素并重新添加到最后更好的方法（速度更快或代码符号更少）？

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
   T tmp(v[itemIndex]);
   v.erase(v.begin() + itemIndex);
   v.push_back(tmp);
}

- Violet Giraffe

---

不是很好...Vector 不是一种非常有效的存储需要从开头删除的东西的方式。看看 std::queue 或 std::dequeue。 - IdeaHat

@MadScienceDreams：在这里std::dequeue也不好用，我需要随机访问。 - Violet Giraffe

那么使用的高效结构是制作自己的环形缓冲区。 - IdeaHat

@MadScienceDreams：我没有问哪个容器最适合这个任务，我问的是用“向量”做到最好的可能方式是什么。为什么要踩我？.. - Violet Giraffe

抱歉，我没有给你的问题点踩（不幸的是，我发现很多堆栈溢出会在“初学者”问题上投下负分）。我没有直接回答你的问题，这就是为什么我在评论中的原因。环形缓冲区将利用向量，执行此操作的时间是常数时间（这回答了“更快”的部分）。 - IdeaHat

你也可以尝试使用std::rotate。它会实现你想要的功能，但我不确定它是否比push_back/erase更快或更慢。 - Blastfurnace

Answer 1

你可以使用标准库中的std::rotate来实现此功能。由于它不会改变向量的大小，因此也不会触发重新分配内存。你的函数将类似于这样：

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
    auto it = v.begin() + itemIndex;
    std::rotate(it, it + 1, v.end());
}

- Blastfurnace

---

这是Stepanov（STL的设计者）推荐的：http://www.stepanovpapers.com/notes.pdf，第154页。 - Max Lybbert

只是一点提醒：如果我理解正确的话，这个程序的时间复杂度为O(n)。下面的std::swap解决方案的时间复杂度为O(1)。 - geometrian

@imallett 没错。这个答案确实保留了移动项以外的元素顺序，而另一个答案则没有。问题本身并没有明确说明这是一个要求。保留顺序的代价更高。 - Blastfurnace

Answer 2

可能最快的方法是将其与最后一个元素交换。

template <typename T>
void moveItemToBack(std::vector<T>& v, size_t itemIndex)
{
   std::swap(v[itemIndex], v.back()); // or swap with *(v.end()-1)
}

一个操作！当然，std::swap必须与T一起使用。

- Nikos Athanasiou

---

这是一个显而易见的解决方案，但它改变了物品的排序方式，不仅仅是将一个移到最后。 - Violet Giraffe

@VioletGiraffe 旋转不行吗？ - Nikos Athanasiou

@VioletGiraffe 好的，现在我明白你的意思了。只要相对顺序不变，旋转是可以的。我只是对问题“将一个元素移到后面”给出了一个字面上的答案。 - Nikos Athanasiou

当然，这是我的错误，我没有在我的问题中表达所有的要求。根据我目前所述的问题，你的答案适合。 - Violet Giraffe

Answer 3

您可以避免使用额外的变量。

v.push_back(v[itemIndex]);
v.erase(v.begin() + itemIndex);

如果你需要频繁从向量中间删除元素，并且能够重写代码以不需要随机访问，那么使用链表 (std::list) 可能可以提高效率。

- Brian Bi

---

啊，当然，整洁！谢谢。顺便问一下，在这里使用emplace_back有什么好处吗？ - Violet Giraffe

@VioletGiraffe，如果 T 很小，那么 emplace_back 不太可能比 push_back 更快。如果 T 很大，那我其实不确定。 - Brian Bi

@Brian emplace_back 实际上调用类的构造函数，这将在此调用中减少到复制构造函数...所以在这种情况下，我认为对于任何一种方式都不会有影响。您可以使用 v.push_back(std::move(v[itemIndex)) 来触发在 C++11 中使用移动构造函数。 - IdeaHat

@MadScienceDreams，你是对的，我刚才有点傻，以为push_back按值传递它的参数。 - Brian Bi

这种做法可能会影响性能。在执行erase之前进行push_back操作会暂时增加向量的大小，可能导致重新分配内存。 - Blastfurnace