Iterating over a vector in reverse direction

Question

I need to iterate over a vector from the end to the beginning. The "correct" way is

for(std::vector<SomeT>::reverse_iterator rit = v.rbegin(); rit != v.rend(); ++rit)
{
    //do Something
}

When //do Something involves knowing the actual index, then some calculations need to be done with rit to obtain it, like index = v.size() - 1 - (rit - v.rbegin)

If the index is needed anyway, then I strongly believe it is better to iterate using that index

for(int i = v.size() - 1; i >= 0; --i)
{
    //do something with v[i] and i; 
}

This gives a warning that i is signed and v.size() is unsigned. Changing to

for(unsigned i = v.size() - 1; i >= 0; --i) is just functionally wrong, because this is essentially an endless loop :)

What is an aesthetically good way to do what I want to do which

• is warning-free
• doesn't involve casts
• is not overly verbose

Gelya

loop condition i != std::numeric_limits<unsigned>::max() ... or use UINT_MAX if you think its to verbose. – Clue

So far, I think doing a cast is looking like the cleanest solution :-) – Suit

just set an upper bound on i, i.e. v.size(). – Boogeyman

@Downvoter: Would you be kind to explain the downvote? This was a precise question and I finally got the answer thanks to @Nim. – Gelya

@Steve: Suppose the value of the element must be multiplied with its index or something like that :) – Gelya

In that case, I think my answer works well, because there's never a need to use indexing. The arithmetic in maintaining dual loop counters ought to be less costly. – Yost

for (size_t i = v.size(); i --> 0; ) – Titre

for(unsigned i : boost::counting_range(v) | boost::adaptors::reversed) – Temuco

Answer 1

As you've noted, the problem with a condition of i >= 0 when it's unsigned is that the condition is always true. Instead of subtracting 1 when you initialize i and then again after each iteration, subtract 1 after checking the loop condition:

for (unsigned i = v.size(); i-- > 0; )

I like this style for several reasons:

• Although i will wrap around to UINT_MAX at the end of the loop, it doesn't rely on that behavior — it would work the same if the types were signed. Relying on unsigned wraparound feels like a bit of a hack to me.
• It calls size() exactly once.
• It doesn't use >=. Whenever I see that operator in a for loop, I have to re-read it to make sure there isn't an off-by-one error.
• If you change the spacing in the conditional, you can make it use the "goes to" operator.

Blanketyblank

shoulnd't it be size_t than unsigned ? – Picket

That could be better if you really anticipate having more items than will fit in an unsigned, @Yes123, but the formally correct type would be std::vector<SomeT>::size_type, or, nowadays, simply auto. – Blanketyblank

Answer 2

There's nothing to stop your reverse_iterator loop also using the index as described in multiple other answers. That way you can use the iterator or index as needed in the // do the work part, for minimal extra cost.

size_t index = v.size() - 1;
for(std::vector<SomeT>::reverse_iterator rit = v.rbegin(); 
    rit != v.rend(); ++rit, --index)
{
  // do the work
}

Though I'm curious to know what you need the index for. Accessing v[index] is the same as accessing *rit.

Yost

This is actually the only correct answer for any underlying type that's not random access. Assuming std::vector<SomeT> is typedef'd away somewhere I'd prefer to use the correct iterator in case I later decided to use a list, multiset, map, etc. – Gelman

use auto to reduce verbosity. – Phox

Answer 3

to be aesthetically pleasing! ;)

for(unsigned i = v.size() - 1; v.size() > i; --i)

Boogeyman

@Armen, hmm, but unsigned (by default int) could be smaller than the size_type of vector, as to why you could have more than 4bn entries in your vector, that's a different question... :).. okay, okay... I give in... – Boogeyman

And what if v.size() == UINT_MAX ? I know this never happens in practice, but it is a theoric flaw – Nic

@JB: vector::size_type is not unsigned int is also a theoretic flaw. But I honestly don't care about theoretic flaws as long as there is really no practical chance it's gonna backfire – Armen Tsirunyan 7 secs ago edit – Gelya

I don't know if it's me not using the wrapping around efficiently, but I usually do it with for (i = v.size(); i > 0; --i) and then use i-1 as the actual index. Matter of preference I guess. – Aintab

this piece of code is hard to understand at first sight: it looks like causing "underflow" if v is empty, which is compensated with alternative for-condition. I guess, calling v.size() in each loop may affect performance if compiler can't optimize it. – Conduit

Answer 4

In C++20 one can use ranges (#include <ranges>)

//DATA
std::vector<int> vecOfInts = { 2,4,6,8 };

//REVERSE VECTOR 
for (int i : vecOfInts | std::views::reverse)
{
     std::cout << i << "  ";
} 

or if it is required to save in a different variable.

//SAVE IN ANOTHER VARIABLE
auto reverseVecOfInts = std::views::reverse(vecOfInts);

//ITERATION
for (int i : reverseVecOfInts)
{
    std::cout << i << "  ";
}

Propensity

though this approach looks nice, it has performance implications - reverse will do exactly (last - first) / 2 swaps , which in certain cases may be a notable overhead – Conduit

@AntonK: I think you are talking about std::ranges::reverse in algorithms. This post is about std::ranges::views::reverse. I believe views are light, just like iterators. – Jevons

Answer 5

I would prefer the reverse iterator variant, because it's still easy to interpret and allows to avoid index-related errors.

Sometimes you can simply use the BOOST_REVERSE_FOREACH, which would make your code look the following way:

reverse_foreach (int value, vector) {
   do_something_with_the_value;
}

---

Actually speaking, you can always use foreach statements for these kinds of loops, but then they become a bit unobvious:

size_t i = 0;

foreach (int value, vector) {
   do_something;
   ++i;
}

Defrock

Answer 6

Try out a do while :

std::vector<Type> v;
// Some code 
if(v.size() > 0)
{
    unsigned int i = v.size() - 1;
    do
    {
        // Your stuff
    }
    while(i-- > 0);
}

Nic

Okay, no problem ;). I tested the do while and it works. I don't say it is the best solution, but it is one available. – Nic

Answer 7

Hi i think better way use iterator as you use in first sample and if you need get iterator index you can use std::distance to calculate it, if i understand your question

Perionychium

Answer 8

loop condition i != std::numeric_limits<unsigned>::max() ... or use UINT_MAX if you think its to verbose. or another way:
for(unsigned j=0, end=v.size(), i=end-1; j<end; --i, ++j)
or
for(unsigned end=v.size(), i=end-1; (end-i)<end; --i)

Clue

Answer 9

You can cast the size to an int if your vector is not huge

for (int i = int(v.size()) - 1; i >= 0; --i) {
    //do something with v[i] and i; 
}

Availability

Answer 10

I think that:

for(unsigned i = v.size() - 1; i >= 0; --i)

is fine if you check

!v.empty()

earlier.

Dialectic

@HardCoder1986: Think again :) – Gelya

the code won't work properly because of underflow error. It's better to get rid of subtracting 1 initially, and instead compare for greater this way for(unsigned i = v.size(); i > 0; --i) { ... }, but you'll have then use v[i-1] to access current element by an index within the loop. – Conduit

Answer 11

for (it = v.end()-1; it != v.begin()-1; --it)
{
}

The "goes to" operator definitely messes with my head.

Pedicle

@Floella AFAIK, this doesn't work (subtracting integers is not supported for iterators). To iterate in reverse, I think you have to use std::vector<T>::reverse_iterator a la https://mcmap.net/q/379375/-iterating-over-a-vector-in-reverse-direction, or use std::distance if you really insist on using subtraction. – Humus