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

Coyote

In C++11 you can use range-based for-loop with reverse adapter, see here – Villeneuve

theoretically, on a 32 bit machine, for the second solution, if the vector size is larger than 2,147,483,647 + 1 it will overflow (vector::size() is unsigned), but currently chances are that you will never hit that limit (also current vector limit on 32 bit machines is 1,073,741,823). – Hippocras

@StefanRogin overflow issue becomes real when instead of "int i" in the for loop someone uses size_t (or maybe auto) in their quest to avoid compiler warnings (due to size() assignment to int). With this, and for a single element vector, the second iteration overflows auto i and the loop executes with the overflown "i" resulting in all sorts of crashes. – Upmost

Answer 1

One way is:

for (vector<my_class>::reverse_iterator riter = my_vector.rbegin();
     riter != my_vector.rend(); ++riter) 
{ 
    // do stuff
} 

rbegin()/rend() were especially designed for that purpose. (And yes, incrementing a reverse_iterator 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 iter = my_vector.end();
while (iter != my_vector.begin())
{
     --iter;
    /*do stuff */
}

Lydgate

I just realized that --i will cause a big problem if container is empty... Before going into do - while loop it makes sense to check (my_vector.begin() != my_vector.end()). – Rolland

Why are you using a do-while loop instead of just a while loop? Then you wouldn't need any special check for empty vectors. – Curzon

Could you update the answer to use auto for better readability? – Ellette

Answer 2

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

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

Varien

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

Barthol

I am confused with this line for(auto& i : vec | views::reverse). How does it work? What does the | do here? – Derrek

@DinoSaric This is a new feature in C++20 that allows composing operations on ranges. See this tutorial for example: hannes.hauswedell.net/post/2019/11/30/range_intro – Barthol

@DinoSaric I was confused, too, since it doesn't look like C++ anymore! :/ – Gretchengrete

This seems to work fine with VS 2022. 👍 for(auto& i : vec | views::reverse). – Frayda

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
}

Millsaps

cppreference.com says, accessing the element at end() "results in undefined behavior", so I think, the loops should start at --end() – Wabble

@ThomasSchmid These loops never attempt to access at end(). Even though they seem to start at end(), they always make sure to decrement the iterator before the first access. – Millsaps

This is so much nicer then rbegin/rend because you can loop the other way at runtime (no template) 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; } – Allseed

@Allseed Egads! that ugly!. You are testing reversed four times -- two of them inside a loop. Of course, testing a boolean is very fast, but still, why to work you don't have to? Especially, since the only purpose seems to be to make the code unreadable. how 'bout we use two separate loops? if (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);} – Lydgate

Actually you missed my point. You are absolutely right to split it into two ifs but I wanted to get rid of the template on the doStuff(). Still doable though with the two ifs you have by looping the other way round on the first one. – Allseed

That's the code I'm using because I need an iterator and not a reverse_iterator. – Infrared

Answer 5

User rend() / rbegin() iterators:

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

Rolland

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.

Lylalyle

Answer 7

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

Eavesdrop

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
}

Equiprobable

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.

Pileate

Indeed, boost::adaptors::reverse is very useful! – Depew

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

Hovercraft

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

Umbelliferous

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

Blabbermouth

This code fails terribly, if vec refers to an empty vector! – Depew

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

Starch

This code fails terribly, if arr refers to an empty vector! – Depew