从末尾开始迭代C++向量

Question

如何逆序遍历vector？

for (vector<my_class>::iterator i = my_vector.end();
        i != my_vector.begin(); /* ?! */ ) {
}

还是只有像这样的东西才能做到：

for (int i = my_vector.size() - 1; i >= 0; --i) {
}

- user

---

在C++11中，你可以使用带有反向适配器的范围for循环，详见这里。 - M.M

理论上，在32位机器上，对于第二种解决方案，如果向量大小大于2,147,483,647 + 1，则会溢出（vector :: size（）为无符号），但目前的机会是您永远不会达到该限制（也当前向量限制在32位机器上为1,073,741,823）。 - Stefan Rogin

当在for循环中使用size_t（或可能是auto）以避免由于将size()赋值给int而导致的编译器警告时，就会出现溢出问题。对于只有一个元素的向量，第二次迭代会导致auto i溢出，并且循环将执行具有溢出的“i”，从而导致各种崩溃。 - Neelabh Mam

Answer 1

一种方法是：

for (vector<my_class>::reverse_iterator i = my_vector.rbegin(); 
        i != my_vector.rend(); ++i ) { 
} 

rbegin()/rend() 是专门为此目的设计的。(而且是的，对于 reverse_iterator来说，递增操作会将它向后移动)

理论上讲，您的方法（使用 begin()/end() 和 --i）也可以工作，因为 std::vector 的迭代器是双向的，但请记住，end() 不是最后一个元素——它在最后一个元素之后，所以您必须先减小迭代器，当达到 begin() 时就完成了——但你仍然需要进行处理。

vector<my_class>::iterator i = my_vector.end();
while (i != my_vector.begin())
{
     --i;
    /*do stuff */

} 

更新：我在将for()循环改写为while()循环时显然过于激进。(重要的是--i在开头。)

- James Curran

---

我刚意识到如果容器为空，--i 会导致一个大问题... 在进入 do-while 循环之前，检查 (my_vector.begin() != my_vector.end()) 是有意义的。 - a1ex07

为什么你使用 do-while 循环而不是 while 循环呢？这样你就不需要对空向量进行特殊检查了。 - jamesdlin

请使用auto以提高可读性更新答案。 - LNJ

Answer 2

如果您使用的是C++11，您可以使用auto

for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it)
{
}

- Akavall

Answer 3

从 C++20 开始，您可以使用 std::ranges::reverse_view 和范围基于 for 循环：

#include<ranges>
#include<vector>
#include<iostream>

using namespace std::ranges;

std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

for(auto& i :  views::reverse(vec)) {
    std::cout << i << ",";
}

甚至可以

for(auto& i :  vec | views::reverse)

很遗憾，在撰写本文时（2020年1月），没有主要的编译器实现了范围库，但您可以使用Eric Niebler的ranges-v3：

#include <iostream>
#include <vector>
#include "range/v3/all.hpp"

int main() {

    using namespace ranges;

    std::vector<int> const vec{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(auto& i :  views::reverse(vec)) {
        std::cout << i << ",";
    }

    return 0;
}

- florestan

---

我对这行代码 for(auto& i : vec | views::reverse) 感到困惑。它是如何工作的？这里的 | 是什么意思？ - Dino Saric

这是C++20中的一个新功能，允许在范围上组合操作。参见此教程以获取示例：https://hannes.hauswedell.net/post/2019/11/30/range_intro/ - florestan

@DinoSaric 我也很困惑，因为它看起来不像C++了！ :/ - Alex D

Answer 4

逆向遍历半开区间的常用“模式”如下所示

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator-- != begin; ) {
  // Process `*iterator`
}

或者，如果您更喜欢的话，

// Iterate over [begin, end) range in reverse
for (iterator = end; iterator != begin; ) {
  --iterator;
  // Process `*iterator`
}

这个模式很有用，例如，可以使用无符号索引来反向索引数组

int array[N];
...
// Iterate over [0, N) range in reverse
for (unsigned i = N; i-- != 0; ) {
  array[i]; // <- process it
}

对于这种模式不熟悉的人经常会坚持使用带符号的整数类型来进行数组索引，特别是因为他们错误地认为无符号类型在反向索引时某种程度上是“不能用的”

它可以用于使用“滑动指针”技术来迭代数组

// Iterate over [array, array + N) range in reverse
for (int *p = array + N; p-- != array; ) {
  *p; // <- process it
}

或者它可以用于使用普通（非反向）迭代器对向量进行反向迭代。

for (vector<my_class>::iterator i = my_vector.end(); i-- != my_vector.begin(); ) {
  *i; // <- process it
}

- AnT stands with Russia

---

cppreference.com表示，访问end()处的元素会导致“未定义的行为”，因此我认为循环应该从--end()开始。 - Thomas Schmid

@ThomasSchmid 这些循环从不尝试访问 end()。即使它们似乎从 end() 开始，它们总是在第一次访问之前确保递减迭代器。 - AnT stands with Russia

这比rbegin/rend好多了，因为你可以在运行时反向循环（无需模板）。auto a = vector<int>{0,1,2}; bool reversed = 0; auto it = (!reversed?a.begin():a.end()); auto end = (reversed?a.begin():a.end());while(it != end) { if(reversed)--it; cout << *it << endl; if(!reversed)++it; } - colin

@colin 哎呀！好丑啊！你在测试 reversed 四次 -- 其中两次在循环内。当然，测试布尔值非常快，但是，为什么要做不必要的工作呢？特别是因为唯一的目的似乎是让代码难以阅读。我们怎么样使用两个单独的循环呢？如果 (reversed) for (auto it = my_vector.rbegin(); it != my_vector.rend(); ++it) {doStuff(*it);} else for (auto it = my_vector.begin(); it != my_vector.end(); ++it) {doStuff(*it);} - James Curran

实际上你误解了我的意思。把它分成两个 if 是完全正确的，但我想要摆脱 doStuff() 上的模板。不过即使有这两个 if，你可以通过在第一个 if 中反向循环来实现。 - colin

这是我使用的代码，因为我需要一个迭代器而不是反向迭代器。 - Octo Poulos

Answer 5

用户可使用rend() / rbegin()迭代器：

for (vector<myclass>::reverse_iterator it = myvector.rbegin(); it != myvector.rend(); it++)

- a1ex07

Answer 6

template<class It>
std::reverse_iterator<It> reversed( It it ) {
  return std::reverse_iterator<It>(std::forward<It>(it));
}

然后：

for( auto rit = reversed(data.end()); rit != reversed(data.begin()); ++rit ) {
  std::cout << *rit;

在 C++14 中可以采用以下方式：

for( auto rit = std::rbegin(data); rit != std::rend(data); ++rit ) {
  std::cout << *rit;

在C++03/11中，大多数标准容器都有.rbegin()和.rend()方法。

最后，您可以按照以下方式编写范围适配器backwards：

namespace adl_aux {
  using std::begin; using std::end;
  template<class C>
  decltype( begin( std::declval<C>() ) ) adl_begin( C&& c ) {
    return begin(std::forward<C>(c));
  }
  template<class C>
  decltype( end( std::declval<C>() ) ) adl_end( C&& c ) {
    return end(std::forward<C>(c));
  }
}

template<class It>
struct simple_range {
  It b_, e_;
  simple_range():b_(),e_(){}
  It begin() const { return b_; }
  It end() const { return e_; }
  simple_range( It b, It e ):b_(b), e_(e) {}

  template<class OtherRange>
  simple_range( OtherRange&& o ):
    simple_range(adl_aux::adl_begin(o), adl_aux::adl_end(o))
  {}

  // explicit defaults:
  simple_range( simple_range const& o ) = default;
  simple_range( simple_range && o ) = default;
  simple_range& operator=( simple_range const& o ) = default;
  simple_range& operator=( simple_range && o ) = default;
};
template<class C>
simple_range< decltype( reversed( adl_aux::adl_begin( std::declval<C&>() ) ) ) >
backwards( C&& c ) {
  return { reversed( adl_aux::adl_end(c) ), reversed( adl_aux::adl_begin(c) ) };
}

现在你可以这样做：

for (auto&& x : backwards(ctnr))
  std::cout << x;

我认为这相当漂亮。

- Yakk - Adam Nevraumont

Answer 7

使用反向迭代器，从rbegin()循环到rend()

- Steve Townsend

Answer 8

我喜欢Yakk - Adam Nevraumont的回答中的反向迭代器，但对于我的需求来说似乎有些复杂，因此我写了以下代码：

最初的回答

template <class T>
class backwards {
    T& _obj;
public:
    backwards(T &obj) : _obj(obj) {}
    auto begin() {return _obj.rbegin();}
    auto end() {return _obj.rend();}
};

最初的回答：我能够使用普通迭代器，就像这样：

for (auto &elem : vec) {
    // ... my useful code
}

将其更改为以下内容以进行反向迭代：

并将其更改为以下内容以进行反向迭代：

for (auto &elem : backwards(vec)) {
    // ... my useful code
}

- John Stephen

Answer 9

如果您可以使用 Boost 库，可以通过包含以下内容来使用 reverse range adapter 提供的 Boost.Range ：

#include <boost/range/adaptor/reversed.hpp>

然后，结合 C++11 的范围for循环，您可以只需编写以下内容：

for (auto& elem: boost::adaptors::reverse(my_vector)) {
   // ...
}

由于这个代码比使用迭代器对的代码更简短，因此它可能更易读，更不容易出错，因为需要注意的细节更少。

- JFMR

---

确实，boost::adaptors::reverse非常有用！ - Kai Petzke

Answer 10

这是一个非常简单的实现，允许使用 for each 结构，并仅依赖于 C++14 标准库：

namespace Details {

    // simple storage of a begin and end iterator
    template<class T>
    struct iterator_range
    {
        T beginning, ending;
        iterator_range(T beginning, T ending) : beginning(beginning), ending(ending) {}

        T begin() const { return beginning; }
        T end() const { return ending; }
    };

}

/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// usage:
//  for (auto e : backwards(collection))
template<class T>
auto backwards(T & collection)
{
    using namespace std;
    return Details::iterator_range(rbegin(collection), rend(collection));
}

这适用于提供rbegin()和rend()的事物，以及静态数组。

std::vector<int> collection{ 5, 9, 15, 22 };
for (auto e : backwards(collection))
    ;

long values[] = { 3, 6, 9, 12 };
for (auto e : backwards(values))
    ;

- Mordachai