size_t len = strlen(some_c_str);
size_t i;
for (i = 0; i < len; ++i) {
  /* Do stuff with each char of some_c_str
  */
}

/* Warning: buggy code!
*/
size_t len = strlen(some_c_str);
size_t i;
for (i = len - 1; i >= 0; --i) {
  /* Do stuff with each char of some_c_str, backwards
  */
}

/* Warning: buggy code!
*/
size_t len = strlen(some_c_str);
size_t i;
for (i = 0; i < len - 1; ++i) {
  /* Do stuff with some_c_str[i] and some_c_str[i+1].
  */
}

32 Responses to “The perils of unsigned iteration in C/C++”

1. and Says:
   June 11th, 2010 at 08:51

   i use

   [const] char *end = some_c_str + strlen(some_c_str);
   for ([const] char *ptr = some_c_str; ptr != end; ptr++) {
     /* Do stuff with each char of some_c_str
         using *ptr
     */
   }

2. Ben Bass Says:
   June 11th, 2010 at 09:56

   It really only makes sense for equal / not equal comparisons with zero for unsigned variables, which gives your second example a bad smell – perhaps compilers could include this as a warning…?

   In general of course this is what C++’s STL iterators and algorithms are for… but beside that (and for C code), I’d probably tend to use pointer equality comparison rather than indexing into an array, and avoid the index altogether (this is effectively what the relevant STL algorithms do anyway);

   char* ptr;
   for (ptr = some_c_str; ptr != some_c_str+len; ptr++) {
   /* do stuff with *ptr */
   }

   maybe this is a bit of a hack, but I think often introducing an index variable at all causes problems (personally I hate C arrays, but probably more people hate pointers…)

3. Thomas Guest Says:
   June 11th, 2010 at 10:44

   The usual form for iterating backwards would be:

   size_t const len = strlen(some_c_str);
   size_t i = len;
   while (i-- != 0) {
     /* Do stuff with each char of some_c_str, backwards */
   }

   In the second case, when you want to process some_c_str[i] and some_c_str[i+1], you need to check that makes sense before entering the loop, so check the length of the string first.

4. Mr.T Says:
   June 11th, 2010 at 10:52

   size_t len = strlen(some_c_str);
   // warning: correct code follows
   for (size_t i = len; i–;) {
   /* Do stuff with each char of some_c_str, backwards
   */
   }
   // i not longer accessible outside the for loop

5. Antoine Says:
   June 11th, 2010 at 11:58

   The signed version of size_t is ssize_t, not int. It can make a big difference (literally) on 64-bit machines

6. Francesco Says:
   June 11th, 2010 at 12:45

   Since you mention C++, in many cases you can use iterators which shield you from these gotchas. I agree, static_cast would be a code smell
   Obviously iterators have their own costs/quirks it may or may not be applicable to your specific case / codebase.

7. eliben Says:
   June 11th, 2010 at 13:35

   @and and @Ben Bass,

   This won’t help cleanly access a char and the next char. Simple iteration is not a problem, especially over a string where I could simply use:

   char* ptr = some_c_str;
   while (*ptr) {
      // do something with *ptr
      ptr++;
   }

   @Thomas & @Mr. T,

   Thanks, an interesting approach. I must admit I haven’t seen a lot of real code that uses this idiom, and on first sight it raises an eyebrow as your subconscience battles with the fact that it indeed never makes you point outside the string.

   @Francesco,

   Yes, using a reverse iterator with rbegin() and rend() would help. But not for the second problem

8. tbp Says:
   June 11th, 2010 at 14:02

   for (size_t i=std::strlen(some_c_str); i; i--) {
   	// dereference i-1
   }

   If you need to abstract that into iterators because it’s too sharp a tool, maybe it’s time for you to reconsider your choice of language.
   The only peril of unsigned loop counters is, possibly, making impossible for the compiler to prove their boundedness.

9. John Says:
   June 11th, 2010 at 14:14

   For the first, why not take into account that len?

   size_t len = strlen(some_c_str);
   size_t i;
   for (i = len - 1; i < len; --i) {
     /* Do stuff with each char of some_c_str, backwards
     */
   }

   For the second I think you’ll just have to make sure len isn’t zero.

   size_t len = strlen(some_c_str);
   size_t i;
   for (i = 0; len > 0 && i < len - 1; ++i) {
     /* Do stuff with some_c_str[i] and some_c_str[i+1].
     */
   }

10. John Says:
    June 11th, 2010 at 14:16

    That should read:

    For the first, why not take into account that less-than zero is the same as greater-than len?

11. Matt Edlefsen Says:
    June 11th, 2010 at 14:29

    Your loop invariant is that both i and i+1 must be valid indexes into some_c_str. It doesn’t make sense to talk about negative sizes so just work in positives.

    for (i = 0; (i  + 1) < len; ++i) {
         // do stuff
    }

12. Brian Bloniarz Says:
    June 11th, 2010 at 14:31

    One cool way to make these bugs less subtle IMHO is to use an integer class that won’t silently overflow.

    I’ve used the SafeInt library from microsoft before, it works great: http://blogs.msdn.com/b/david_leblanc/archive/2008/09/30/safeint-3-on-codeplex.aspx

    SafeInt<size_t> is just like a size_t, except that it
    (a) throws on overflow
    (b) disallows implicit conversions to other integer types
    It also works fine on GCC.

13. Laurie Cheers Says:
    June 11th, 2010 at 15:53

    In this case the simplest fix is:

    size_t len = strlen(some_c_str);
    size_t i;
    for (i = 0; i+1 < len; ++i) {
    /* Do stuff with some_c_str[i] and some_c_str[i+1].
    */
    }

14. Duncan Beevers Says:
    June 11th, 2010 at 16:46

    JavaScript doesn’t have an unsigned type, so the initial problem affect that dialect of ECMAScript, though I have been bitten by this in ActionScript, which does support unsigned types.

    Although most ECMAScript implementations offer forEach-equivalents, the while-loop, length-down-to-zero pattern is becoming more popular in the JavaScript community as that construct performs slightly faster in most implementations.

    var i = collection.length;
    while(i--) {
      doSomething(collection[i]);
    }

    The main caveat here, which is not just limited to this approach, is that JavaScript only has function-local, and not block-local scope.

15. Paul Says:
    June 11th, 2010 at 17:15

    Couldn’t you replace i < len-1 by i+1 < len?

16. antti Says:
    June 11th, 2010 at 17:38

    for(char const* b = str, * e = str + strlen(str); b != e && (b + 1) != e; ++b) {
      f(b[0], b[1]);
    }

    equivalently

    for(char const* b = str, * b1 = str + 1, * e = str + strlen(str); b != e && b1 != e; ++b) {
      f(*b, *b1);
    }

17. antti Says:
    June 11th, 2010 at 17:39

    Oops, forgot ++b1 from the second one

18. Segher Says:
    June 11th, 2010 at 18:00

    You write an unsigned down-count loop like:

    for (i = len – 1; i < len; i–)

    and your second example should use:

    for (i = 0; i+1 < len; i++)

    In unsigned, "a < b" is not equivalent to "a-c < b-c".

19. Segher Says:
    June 11th, 2010 at 18:05

    You write an unsigned down-count loop like:

    for (i = len - 1; i < len; i--)

    and your second example should use:

    for (i = 0; i+1 < len; i++)

    The actual condition you need is “i<len && i+1 < len", but that simplifies to just
    "i+1 < len". In unsigned arithmetic, "a < b" is not equivalent to "a-c < b-c", so
    this is not the same condition as "i < len-1".

20. R Samuel Klatchko Says:
    June 11th, 2010 at 18:51

    Here’s a clean way to write that code without changing to signed or adding lots of extra checks:

    for (i = 0; i + 1 < len; ++i) {

21. meh Says:
    June 11th, 2010 at 18:57

    size_t len = strlen(some_c_str);
    size_t i;
    for (i = 0; i < len; i++) {
    /* Do stuff with some_c_str[i] and some_c_str[i+1].
    */
    }

22. Ashutosh Mehra Says:
    June 11th, 2010 at 19:33

    One way to “solve” the problem might be to do use “i + 1″ instead of “len – 1″ in the comparison:

    size_t len = strlen(some_c_str);
    size_t i;
    for (i = 0; i + 1 < len; ++i) {
      /* Do stuff with some_c_str[i] and some_c_str[i+1]. */
    }

    This may cause extra move/increment instructions, unless they can be optimized away.

23. Brian Hurt Says:
    June 11th, 2010 at 20:11

    Don’t use int’s as loop iterator variables! This introduces a rather bad 32-bit limitation in your code, were it ever to run on 64-bit machines. On 64-bit machines, it is quite likely already you will encounter arrays with more than 2 billion elements- and on most 64-bit C/C++ compilers, ints are still 32 bits. Java is hitting this problem hard (see all the blog posts on how hard it is to write a correct binary search- almost all the problems they talk about are due to very large array indicies that overflow 32-bit arithmetic). It’s only when counting down are unsigned values a problem.

24. Joseph Garvin Says:
    June 11th, 2010 at 20:28

    If you used a signed loop variable instead, would the bugs be any better? Looping 2 billion times or not looping at all still leaves a bug. At least if it’s looping you have plenty of time to break into the debugger and see where it’s stuck.

25. mos Says:
    June 11th, 2010 at 20:58

    I also prefer using the beginning and end of the string as my iterator bounds.

    const char *e = some_str[strlen(some_str)];
    for(char *c = some_str[0]; c != e; ++c)
    {
       ...
    }

26. Roger Pate Says:
    June 11th, 2010 at 22:06

    @eliben: When using iterators instead of indexes (as ‘and’ and Ben Bass comment), you just use p[1] instead of s[i+1] to access the next element.

27. Daniel Says:
    June 11th, 2010 at 23:04

    I write your last example

    for (i = 0; i+1 < len; ++i) ...
    when i is unsigned. I don’t like to use the postfix operators.

28. eliben Says:
    June 12th, 2010 at 06:17

    @Roger Pate,

    But then you can’t iterate until end itself, but must iterate until end - 1.

    @Matt, Laurie and others,

    Using i + 1 < len is an interesting approach – I didn’t think about it at all. You must admit that it’s not an idiomatic way to loop, however.

29. Sean Hsien Says:
    June 13th, 2010 at 10:16

    Rather than using i + 1 < len, why not sanitize len before the loop, which saves you an increment each loop as well? For readability, you can store sanitized value in another variable if you like.

    size_t len = strlen(some_c_str);
    if (len > 0)
        --len;
    size_t i;
    for (i = 0; i < len; ++i) {
        /* Do stuff with some_c_str[i] and some_c_str[i+1]. */
    }

    Alternatively, you can loop by referring to the 2nd value of the pair:

    size_t len = strlen(some_c_str);
    size_t i;
    for (i = 1; i < len; ++i) {
        /** note the difference here... **/
        /* Do stuff with some_c_str[i-1] and some_c_str[i]. */
    }

30. Sean Hsien Says:
    June 13th, 2010 at 11:08

    Sorry my first example won’t work, but the 2nd should

31. Marco Says:
    June 14th, 2010 at 19:07

    Just error out of the function early before the loop:

    if (len == 0) return;

32. Marc van Leeuwen Says:
    March 19th, 2012 at 17:13

    I almost always loop using unsigned variables if that is appropriate. For decreasing loops over the interval [a,b) I use the following idiom, which curiously I have never seen used by others:
    for (unsigned i=b; i-->a; )
{ // stuff using i here
}
    This works well for any possible a,b, including a=0. If a<=b, then it is equivalent to a version with i-- != a that I saw in the comments above, but i --> a (I often use spacing like that) just look so cute.

Leave a Reply