CODEWITHSUNDEEP
c++for-loop
Daniel Paull
Daniel Paull

Reputation: 6843

Reverse iteration with an unsigned loop variable

I've been discussing the use of size_t with colleagues. One issue that has come up is loops that decrement the loop variable until it reaches zero.

Consider the following code:

for (size_t i = n-1; i >= 0; --i) { ... }

This causes an infinite loop due to unsigned integer wrap-around. What do you do in this case? It seems far to easy to write the above code and not realise that you've made a mistake.

Two suggestions from our team are to use one of the following styles:

for (size_t i = n-1; i != -1 ; --i) { ... }

for (size_t i = n; i-- > 0 ; ) { ... }

But I do wonder what other options there are...

Upvotes: 76

Views: 20452

Answers (11)

cigien
cigien

Reputation: 60228

From C++20, you can use ranges, and views, like this:

namespace sv = std::views;
    
for (unsigned i : sv::iota(0u, n) | sv::reverse)
    std::cout << i << "\n";

Here's a demo.

The code is very readable, and it completely avoids any issues with unsigned wrap-around behavior, since i only has values in the range [0,n).

Upvotes: 6

Corentor
Corentor

Reputation: 769

Another solution (available on POSIX compliant systems) that I found to be simple and effective is to replace size_t with ssize_t:

for (ssize_t i = n-1; i >= 0; --i) { ... }

On non-POSIX systems, ssize_t is not difficult to typedef: Alternative to ssize_t on POSIX-unconformant systems

Upvotes: 1

boni
boni

Reputation: 253

Yet another way (no signed/unsigned comparisons):

for (size_t i = n-1; i + 1 > 0; i--)

since

(i + 1 > 0) === (i > -1)

Upvotes: 1

joshperry
joshperry

Reputation: 42227

Are you using standard library containers? If so I like reverse_iterator

   vector<int> ivect;

   // push, push, push...

   vector<int>::reverse_iterator riter;
   for(riter=riter.rbegin(); riter!=ivect.rend(); ++riter)
   {
       //...
   }

For a raw array you can just use a std::reverse_iterator the key to this is that a pointer is an iterator:

int i[] = {1, 2, 3, 4};

typedef std::reverse_iterator<const int*> irevit;

irevit iter(i+4);
irevit end(i);
for(; iter != end; ++iter) {
    cout << *iter;
}

// Prints 4321

Noncontiguous object iteration can be done by storing the object pointers in a container or array:

struct Foo {
    Foo(int i) I(i) { }
    int I;
}

vector<Foo*> foos;
for(int i = 0; i < 10; ++i)
    foos.push_back(new Foo(i));

typedef vector<Foo*>::const_reverse_iterator frevit;

frevit iter(foos.rbegin());
for(; iter != foos.rend(); ++iter) {
    cout << (*iter)->I;
}

// Prints 9876543210

If you really want to use a naked size_t then why use all of this implicitly confusing -1 trickery in the other answers? The max value of size_t is explicitly available to use as your termination value:

int is[] = {1, 2, 3, 4};
int n = 3;

for (size_t i = n; i != std::numeric_limits<size_t>::max(); --i) {
    cout << is[i] << endl;
}

// prints 4321

Upvotes: 5

visitor
visitor

Reputation: 8834

Personally I have come to like:

for (size_t i = n; i --> 0 ;)

It has a) no funny -1, b) the condition check is mnemonic, c) it ends with a suitable smiley.

Upvotes: 118

Jens Gustedt
Jens Gustedt

Reputation: 78923

Unsigned integers are guaranteed to wrap around nicely. They just implement arithmetic modulo 2N. So an easy to read idiom is this one:

for (size_t i = n-1; i < n ; --i) { ... }

this sets the variable to the initial value that you want, shows the sense of the iteration (downward) and gives precisely the condition on the values that you want to handle.

Upvotes: 73

caf
caf

Reputation: 239071

If you're worried about accidentally writing a loop like that, some compilers will warn about such things. For example, gcc has a warning enabled by the -Wtype-limits option (also enabled by -Wextra):

x.c:42: warning: comparison of unsigned expression >= 0 is always true

Upvotes: 5

D&#233;j&#224; vu
D&#233;j&#224; vu

Reputation: 28840

size_t i = n-1;

do  { 
  ...
} while ( i-- != 0);

You may wrap that with a if (n > 0) if necessary.

Upvotes: 2

Arun
Arun

Reputation: 20383

Here is a pointer to a good discussion on this topic.

I would try:

for( size_t i = n; i != 0; i-- ) {
  // do stuff with array[ i - 1 ]
}

Upvotes: 1

Alex Martelli
Alex Martelli

Reputation: 881805

i != -1 relies on the -1 being silently cast to a size_t, which seems fragile to me, so, of the alternatives you present, I'd definitely go with the post-decrement one. Another possibility (esp. if you don't actually need i in the loop body but just need to iterate on an array in reverse order) would be to wrap the array in a std::-like container and use an iterator on the wrapper, with the rbegin and rend methods. E.g., Boost.Array would support the latter choice.

Upvotes: 3

Jerry Coffin
Jerry Coffin

Reputation: 490178

  1. Replace the loop with an algorithm.
  2. Use a reverse iterator instead of an integer.
  3. Count down from n to 1, but inside the loop use i-1 instead of i.

Upvotes: 13

Related Questions