Reverse iteration with an unsigned loop variable

Question

Hi all,

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

Cheers,

Dan

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

size_t i = n-1;

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

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

Answer 6

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

Answer 7

Unsigned integers are guaranteed to wrap around nicely. They just implement arithmetic modulo 2^N. 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.

Answer 8

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.