如何对C++向量进行反转？

Question

在C++中是否有内置的向量函数可以原地翻转向量？

还是必须手动完成？

- Dollarslice

Answer 1

这个目的可以使用头文件中的std::reverse函数来实现。

#include <vector>
#include <algorithm>

int main() {
  std::vector<int> a;
  std::reverse(a.begin(), a.end());
  return 0;
}

- Ivaylo Strandjev

---

你能解释一下如何反转向量的向量吗？我想要将v[0]与v[v.size()-1]交换，并且保持v[0][i]元素的顺序不变。这类似于更改行的顺序（如果将向量视为矩阵）。如果一个向量被定义为：vector<vector<int>> v; reverse(v.begin(), v.end())不能反转它。谢谢！ - Coder

@VikasGoel，实际上你建议的代码片段应该可以工作。也许有其他问题？ - Ivaylo Strandjev

你也可以保持元素顺序相反，但需要倒序迭代：for(auto i=a.end(); i!=a.begin();i--) {...} 尽管由于误差可能会产生困难。因此，像其他人建议的那样使用rbegin()和rend()更好。 - mo FEAR

Answer 2

所有容器都提供使用 rbegin() 和 rend() 反转其内容的“视图”。这两个函数返回所谓的“反向迭代器”，可以像正常迭代器一样使用，但它看起来就像容器实际上被翻转了一样。

#include <vector>
#include <iostream>

template<class InIt>
void print_range(InIt first, InIt last, char const* delim = "\n"){
  --last;
  for(; first != last; ++first){
    std::cout << *first << delim;
  }
  std::cout << *first;
}

int main(){
  int a[] = { 1, 2, 3, 4, 5 };
  std::vector<int> v(a, a+5);
  print_range(v.begin(), v.end(), "->");
  std::cout << "\n=============\n";
  print_range(v.rbegin(), v.rend(), "<-");
}

在 Ideone 上的实时示例。输出：

1->2->3->4->5
=============
5<-4<-3<-2<-1

- Xeo

---

这并不会直接原地翻转向量。你可以使用 std::vector<T> v2( v1.rbegin(), v1.rend() ); v2.swap(v1); 创建一个新向量，从而有效地使用您的解决方案。但是我不认为这比使用 std::reverse 更优雅或更有优势。 - CashCow

@CashCow：首先，它是一个无操作（no-op），时间复杂度为O(1)。相反地，反转操作就不是了。大多数时候，你并不需要一个真正的倒序容器，你只需要把它看做是倒序的即可。事实上，我想不出任何需要一个真正的倒序容器的情况，这些情况都可以用反向迭代器来解决。 - Xeo

@CashCow：优雅并不总是真正的优雅。在我的职业生涯中，大多数情况下我只需要一个反向视图，而不是一个反向向量。在所有这些情况中，如果您创建更多的副本或转换排序，性能将会完全不必要地受到影响。如果您只需要未指定顺序的前10个元素，您是否也会使用std::sort来对1000个元素的向量进行排序，因为这比std::partition更优雅？这就是那种思想流派，它使我的PC体验今天像15年前一样受到破坏，不同之处在于浪费的周期更多了，达到了数十亿个。 - Sebastian Mach

print_range 不正确：当传递一个空范围时，它将无法工作。 - Nawaz

@Xeo 实际需要计算反向向量的一个例子是当您使用无法更改其实现的 API 时。 - billx

Answer 3

您可以像这样使用 std::reverse

std::reverse(str.begin(), str.end());

- Chuck Norris

Answer 4

通常反转向量的原因是你将所有项目推送到末尾进行填充，但实际上是按相反顺序接收它们。在这种情况下，您可以使用 deque 并直接将它们推到前面来，在遍历容器时反转容器。(或者您可以使用vector :: insert() 将项目插入到前面，但当有大量项目时，这样做会很慢，因为每次插入都必须移动所有其他项目。) 因此，与以下方式不同：

std::vector<int> foo;
int nextItem;
while (getNext(nextItem)) {
    foo.push_back(nextItem);
}
std::reverse(foo.begin(), foo.end());

您可以选择这样做：

std::deque<int> foo;
int nextItem;
while (getNext(nextItem)) {
    foo.push_front(nextItem);
}
// No reverse needed - already in correct order

- Arthur Tacca

---

缺点是元素不再像向量一样在内存中连续，因此您无法使用.data()。 - mo FEAR

Answer 5

你也可以使用std::list代替std::vector。 list有一个内置函数list::reverse用于反转元素。

- Hello W

---

如果需要在序列的任意位置插入许多元素，应该优先选择std::list而不是vector。仅因为你将反转序列而使用std::list而不是vector在性能上是个坏主意。 - eozd