1

Is the following code, safe to iterate an array backward?

for (size_t s = array_size - 1; s != -1;  s--)
    array[s] = <do something>;

Note that I'm comparing s, which is unsigned, against -1;

Is there a better way?

Bite Bytes
  • 1,455
  • 8
  • 24

3 Answers3

3

This code is surprisingly tricky. If my reading of the C standard is correct, then your code is safe if size_t is at least as big as int. This is normally the case because size_t is usually implemented as something like unsigned long int.

In this case -1 is converted to size_t (the type of s). -1 can't be represented by an unsigned type, so we apply modulo arithmetic to bring it in range. This gives us SIZE_MAX (the largest possible value of type size_t). Similarly, decrementing s when it is 0 is done modulo SIZE_MAX+1, which also results in SIZE_MAX. Therefore your loop ends exactly where you want it to end, after processing the s = 0 case.

On the other hand, if size_t were something like unsigned short (and int bigger than short), then int could represent all possible size_t values and s would be converted to int. In other words, the comparison would be done as (int)SIZE_MAX != -1, which would always return false, thus breaking your code. But I've never seen a system where this could happen.

You can avoid any potential problems by using SIZE_MAX (which is provided by <stdint.h>) instead of -1:

for (size_t s = array_size - 1; s != SIZE_MAX;  s--)
    ...

But my favorite solution is this:

for (size_t s = array_size; s--; )
    ...
melpomene
  • 84,125
  • 8
  • 85
  • 148
  • 1
    Good point about the relative sizes. There have actually been implementations with 4-byte `int` with 2-byte `size_t` . – M.M Aug 21 '17 at 21:59
  • See also [What is the --> operator?](https://stackoverflow.com/questions/1642028/what-is-the-operator-in-c) – M.M Aug 21 '17 at 22:00
  • In C89 there is no SIZE_MAX constant, what if I used `size_t SIZE_MAX = -1;` would that be correct? – Bite Bytes Aug 21 '17 at 22:56
  • 1
    @BiteBytes Yes, that would work. Or `#define SIZE_MAX ((size_t)-1)`. – melpomene Aug 21 '17 at 23:00
0

Well, s will never be -1, so your ending condition will never happen. s will go from 0 to SIZE_MAX, at which point your program will probably segfault from a memory access error. The better solution would be to start at the max size, and subtract one from everywhere you use it:

for (size_t s = array_size; s > 0; s--)
    array[s-1] = <do something>;

Or you can combine this functionality into the for loop's syntax:

for (size_t s = array_size; s--;)
    array[s] = <do something>;

Which will subtract one before going into the loop, but checks for s == 0 before subtracting 1.

Felix Guo
  • 2,700
  • 14
  • 20
  • SIZE_MAX = -1 (at the binary level), isn't? – Bite Bytes Aug 21 '17 at 21:43
  • @BiteBytes I am not sure that for example for the sign and magnitude representation the operation s-- will give -1 when s is equal to 0. – Vlad from Moscow Aug 21 '17 at 21:49
  • It seems to work in C++11 (https://repl.it/KTS1/0) (albeit it's a bad practice) but I don't know how much of it is compiler specific vs standard defined. – Felix Guo Aug 21 '17 at 21:51
  • @VladfromMoscow, Felix sayd **s will never be -1**, which is incorrect. – Bite Bytes Aug 21 '17 at 22:49
  • 2
    @BiteBytes-- it is correct that `size_t s` can never be -1: `s` is an `unsigned` value, after all, and `-1` is a `signed` integer value. But in the expression `s != -1`, the `-1` is converted to a `size_t` (so long as `size_t` is a wider type than an `int`, and this conversion is well-defined as a wrap-around value, so the comparison "works", but not exactly as might be expected. Where this answer goes wrong is with "so your ending condition will never happen." – ad absurdum Aug 21 '17 at 23:21
0

IMO in the iterations use large enough signed value. It ss easier to read by humans.

0___________
  • 60,014
  • 4
  • 34
  • 74