Is it safe to test relations between pointers for iteration?

user_3284878 0
Viewed 84

Please consider an array of Thing. It's a kind of stack.

It is pointed to by thingsBottom, and its empty end is pointed to by thingsTop.

EDIT: Every time I want push something onto the list, I do *thingsTop = newThing; thingsTop++;.

I'd like to iterate it from the end to the beginning using pointers, like so:

for (Thing* thing = thingsTop - 1; thing >= thingsBottom; thing--) {
    doSomething(*thing);
}

Is this guaranteed to always work, regardless of the specific C implementation used?

Is it safe to say thing >= thingsBottom?

pointers iteration c
2 Answers

Is this guaranteed to always work, regardless of the specific C implementation used?

Is it safe to say thing >= thingsBottom?

No, and not unconditionally.

The problem with your approach is that it produces undefined behavior to compute a pointer value that would be before the beginning of the array on which that pointer is based, and pointer comparisons are valid only for pointers into, or just past the end of, the same array. "Just before the beginning" does not have any special status or provision.

You can write such a loop; you just need to test before you decrement:

for (Thing* thing = thingsTop; thing > thingsBottom; ) {
    thing--;
    doSomething(*thing);
}
user_24022720

Given that both pointers point at the same array - and only then - it is safe to compare them with each other. However, if you go 1 item below the array, you go out of bounds and that's undefined behavior, even if you don't access that item.

To allow code such as this, C has a special rule that allows you to have a pointer point 1 item beyond the array, and it is safe, long as you don't de-reference that pointer when it is pointing 1 item beyond.

Meaning that you have to write an up-counting loop, not a down-counting one. A fairly canonical example of this would be:

thing* begin = thing_array;
thing* end   = thing_array + size; // point 1 past the last valid item

for(thing* i = begin; i != end; i++)
{
   do_stuff(i);
}

For example this is pretty much how C++ container class ::iterator work.

If you truly need to iterate from the end to the beginning, I would recommend an integer iterator instead:

for(size_t i=0; i<size; i++)
{
  do_stuff(thing_array[size-i-1]);
}
user_5845180
Related