3

I got into the habit of declaring for loop indices with size_t instead of int. That however already bit me multiple times when I was iterating an array backwards, i.e. checking for the index to be greater or equal to zero:

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

When the body has been run for i == 0, it gets decremented and wraps around, to SIZE_T_MAX probably. That makes the break condition a tautology. There might be some clever bit manipulations to check for possible underflows, but wouldn't it be simpler to use ptrdiff_t instead?

What is the proper idiomatic C way to solve this? size_t plus bit twiddling or ptrdiff_t and feeling uncomfortable about semantics?

Sebastian Graf
  • 3,602
  • 3
  • 27
  • 38
  • @haccks Then, on several common platforms, you're restricted to array sizes which are quite a lot smaller than the array sizes that can reasonably be supported by the amount of physical memory. Worse, the compiler will optimize based on `int` overflow being undefined (giving quite strange behavior when it does overflow), and since it requires rather extreme inputs any problem related to this will be hard to find and reproduce. –  May 31 '14 at 15:06
  • 1
    My GCC 4.7 doesn't appear to notice the tautology (edit: with `-Wextra` it does), but my Clang 3.2 warns about it at `-Wall`. So I guess "enable warnings" is another solution? –  May 31 '14 at 15:11
  • Might be, I was just wondering if I'm 'doing it the right way'. – Sebastian Graf May 31 '14 at 15:13

2 Answers2

3

A backwards loop should look like this:

for (size_t i = 0; i != n; ++i) {
    arr[n - i - 1] = foo();
}

The n - i - 1 is the "reverse iterator" corresponding to i, if you will.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
0

Here is a safer way to write your downward loop:

  • it works with both signed or unsigned index types,
  • it uses the array length unmodified just once. You could also write i = sizeof(arr) / sizeof(*arr) if arr is defined as an array.
  • i takes all valid index values in decreasing order.
for (size_t i = n; i-- > 0;) {
    arr[i] = compute_value(i);
}

One could write i --> 0 as an eye catcher idiom, but some experts seem to disagree on this alternative.

chqrlie
  • 131,814
  • 10
  • 121
  • 189
  • 1
    I disagree that this is idiomatic, it is just obscure. The version posted by Kerrek is close to idiomatic, except it should be `i – Lundin Jan 13 '22 at 14:52
  • "Being funny" in your source isn't. – DevSolar Jan 13 '22 at 14:54
  • @Lundin: if you do not like `i --> 0`, you can write `i-- > 0`. It is a matter of personal choice. I have been using this idiom for a while and it has proven quite effective. – chqrlie Jan 13 '22 at 14:54
  • Or you can use the [i slides down to zero operator](https://stackoverflow.com/a/8909176/584518)... – Lundin Jan 13 '22 at 14:57
  • @Lundin: which is by far the most upvoted question with the [c] tag and the tenth most upvoted question of all time on stack overflow :) – chqrlie Jan 13 '22 at 15:00
  • 1
    People like seeing posts about weird funny crap, that's why. Out of the top 10 most up-voted questions, 3 are about obfuscation, including the famous `!ErrorHasOccured() ??!??! HandleError();`. If funny cat pictures were on topic, those would have even more votes... – Lundin Jan 13 '22 at 15:05
  • Well, disregarding the aesthetics of whitespace which has now been fixed in the answer, this code will work and is perhaps less confusing and easier to get right than writing `n - i - 1` everywhere (or even just once). The only drawback is that it will occupy one more register for the back jump: https://godbolt.org/z/h6b73sfT6 On the other hand, https://stackoverflow.com/a/23971533/388010 will likewise need another register to store `n - i - 1`, just not between loop iterations (which presumably makes it easier to optimise). – Sebastian Graf Jan 18 '22 at 10:01
  • 1
    Perhaps interestingly, clang is able to optimise this program to use `jb`, which is the C equivalent of `i < (size_t) -1` if that wasn't UB in C. But it isn't UB in x86_64, hence this optimisation is sound! Very nice. So the above piece of code generates optimal code there: https://godbolt.org/z/4Wo884zrG. On the other hand, the other answer does generate optimal code, too: https://godbolt.org/z/eaW4af3bc. Bottom line: As far as efficiency is concerned, it doesn't matter. – Sebastian Graf Jan 18 '22 at 10:05