Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Iterating C++ vector from the end to the beginning

People also ask

How do you iterate a vector backwards?

So, to iterate over a vector in reverse direction, we can use the reverse_iterator to iterate from end to start. vector provides two functions which returns a reverse_iterator i.e. vector::rend() –> Returns a reverse iterator that points to the virtual element before the start of vector.

What should begin () and end () do for a container?

vector::begin() function is a bidirectional iterator used to return an iterator pointing to the first element of the container. vector::end() function is a bidirectional iterator used to return an iterator pointing to the last element of the container.

What is vector end () C++?

The C++ function std::vector::end() returns an iterator which points to past-the-end element in the vector container. The past-the-end element is the theoretical element that would follow the last element in the vector.


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


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

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

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
}

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