Iterating C++ vector from the end to the beginning

Question

Is it possible to iterate a vector from the end to the beginning?

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

Or is that only possible with something like that:

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

Answer 1

One way is:

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

rbegin()/rend() were especially designed for that purpose. (And yes, incrementing a reverse_interator moves it backward.)

Now, in theory, your method (using begin()/end() & --i) would work, std::vector's iterator being bidirectional, but remember, end() isn't the last element — it's one beyond the last element, so you'd have to decrement first, and you are done when you reach begin() — but you still have to do your processing.

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

} 

UPDATE: I was apparently too aggressive in re-writing the for() loop into a while() loop. (The important part is that the --i is at the beginning.)

Answer 2

If you have C++11 you can make use of auto.

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

Answer 3

Starting with c++20, you can use a std::ranges::reverse_view and a range-based for-loop:

#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 << ",";
}

Or even

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

Unfortunately, at the time of writing (Jan 2020) no major compiler implements the ranges library, but you can resort to Eric Niebler's 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;
}

Answer 4

The well-established "pattern" for reverse-iterating through closed-open ranges looks as follows

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

or, if you prefer,

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

This pattern is useful, for example, for reverse-indexing an array using an unsigned index

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

(People unfamiliar with this pattern often insist on using signed integer types for array indexing specifically because they incorrectly believe that unsigned types are somehow "unusable" for reverse indexing)

It can be used for iterating over an array using a "sliding pointer" technique

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

or it can be used for reverse-iteration over a vector using an ordinary (not reverse) iterator

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

Answer 5

User rend() / rbegin() iterators:

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

Answer 6

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

Then:

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

Alternatively in C++14 just do:

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

In C++03/11 most standard containers have a .rbegin() and .rend() method as well.

Finally, you can write the range adapter backwards as follows:

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

and now you can do this:

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

which I think is quite pretty.

Answer 7

Use reverse iterators and loop from rbegin() to rend()

Answer 8

I like the backwards iterator at the end of Yakk - Adam Nevraumont's answer, but it seemed complicated for what I needed, so I wrote this:

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

I'm able to take a normal iterator like this:

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

and change it to this to iterate in reverse:

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

Answer 9

If you can use The Boost Library, there is the Boost.Range that provides the reverse range adapter by including:

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

Then, in combination with a C++11's range-for loop, you can just write the following:

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

Since this code is briefer than the one using the iterator pair, it may be more readable and less prone to errors as there are fewer details to pay attention to.

Answer 10

Here's a super simple implementation that allows use of the for each construct and relies only on C++14 std library:

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

This works with things that supply an rbegin() and rend(), as well as with static arrays.

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

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

Answer 11

can try this one (only for --i):

std:vector<int> vec = {1, 2, 3};
size_t i{ vec.size() - 1 };
while (i < size_t(-1))
{
    auto& el = vec[i];
    --i;
}

Answer 12

use this code

//print the vector element in reverse order by normal iterator.
cout <<"print the vector element in reverse order by normal iterator." <<endl;
vector<string>::iterator iter=vec.end();
--iter;
while (iter != vec.begin())
{
    cout << *iter  << " "; 
    --iter;
}

Answer 13

As I don't want to introduce alien-like new C++ syntax, and I simply want to build up on existing primitives, the below snippets seems to work:

#include <vector>
#include <iostream>

int main (int argc,char *argv[])
{
    std::vector<int> arr{1,2,3,4,5};
    std::vector<int>::iterator it;

    // iterate forward
    for (it = arr.begin(); it != arr.end(); it++) {
        std::cout << *it << " ";
    }

    std::cout << "\n************\n";
 
    if (arr.size() > 0) {
        // iterate backward, simple Joe version
        it = arr.end() - 1;
        while (it != arr.begin()) {
            std::cout << *it << " ";
            it--;
        }
        std::cout << *it << " ";
    } 

    // iterate backwards, the C++ way
    std::vector<int>::reverse_iterator rit;
    for (rit = arr.rbegin(); rit != arr.rend(); rit++) {
        std::cout << *rit << " ";
    }

    return 0;
}