A pointer problem from a high school programming contest

[kolistivra]

Hi experts,

The code below is from a programming contest, the answer must be given without using a compiler(this test is on paper).


The problem: How many '*' does that piece of code prints?
a) 20
b) 25
c) 33
d) 50
e) 100

#include<cstdio>
void f(int i){i--;}
void g(int i){int*p;p=&i;*p--;}
void h(int*p){*p--;}
void i(int*p){int i;i=*p;i--;}
int main()
{
int index=100;
for(;index>0;index--)
{ printf("*"); f(index); g(index); h(&index); i(&index); }
}

I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?

thanks in advance!

[brewbuck]

I found out 50, but when i put it in compiler i saw that i'm mistaken, the answer seems 100. How can it be? shouldn't function h decrease index too?

Look carefully at an operator precedence table. *p-- isn't doing what you think it is.

[robatino]

If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100% correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).

[brewbuck]

If I'm not mistaken, each of the *p--'s is generating a bad pointer by decrementing p, then dereferencing the result, either of which generates undefined behavior. So there is no 100% correct answer (though if you assume that *p-- is equivalent to a noop, then it's 100).

It's postfix decrement, so it decrements after the dereference. This is a funny example because although the decrement binds first, its operation happens second.

You typically see this kind of thing in loops which copy data (usually with increment, not decrement):

type *src, *dst, *end;
...
while(src < end)
    *dst++ = *src++;

[robatino]

> It's postfix decrement, so it decrements after the dereference.
You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).

[brewbuck]

> It's postfix decrement, so it decrements after the dereference.
You're right, I don't know what I was thinking since I do this all the time. So it's just the decrement that generates the undefined behavior (though the conclusion is the same).

I don't think there's any undefined behavior. The decrement turns the pointer into something undefined, but the function returns immediately so the bogus pointer is never used.

If merely being in possession of an undefined pointer could lead to undefined behavior, then pretty much every program in the universe is undefined, because whenever you declare a pointer there is a brief period of time before it is initialized:

void nuclear_explosion()
{
    int *kaboom;

    printf("I explode now because kaboom is undefined!\n");
    kaboom = NULL;
}

Any platform or compiler where that blows up is just ridiculous. Even if the standard implies it.

[Daved]

Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer. That is a special case, though, so kaboom is not undefined behavior but decrementing p is.

The part of the standard I was looking at was not specifically related to this, though, so it is possible that the actual wording is different.

[laserlight]

Actually, I think I remember reading in the standard that there is only one case where you can have a pointer that points to an undefined location, and that is the case of an uninitialized pointer.

There is at least one other case, that of a pointer that points one past the end of an array.

[dwks]

What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.

[robatino]

I believe the undefined behavior only occurs when the pointer is actually _assigned_ a bad value. I found the following (http://gcc.gnu.org/onlinedocs/libstd...ors/howto.html) though I don't have an exact reference in the Standard:

1. You can point anywhere in the array, or to the first element past the end of the array. A pointer that points to one past the end of the array is guaranteed to be as unique as a pointer to somewhere inside the array, so that you can compare such pointers safely.
2. You can only dereference a pointer that points into an array. If your array pointer points outside the array -- even to just one past the end -- and you dereference it, Bad Things happen.
3. Strictly speaking, simply pointing anywhere else invokes undefined behavior. Most programs won't puke until such a pointer is actually dereferenced, but the standards leave that up to the platform.

Edit: Here's a link to the exact part of the Standard that mentions the undefined behavior (see 1161).

http://c0x.coding-guidelines.com/6.5.6.html

[brewbuck]

There is at least one other case, that of a pointer that points one past the end of an array.

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should. There's no legitimate reason to prevent people from processing an array backwards instead of forwards.

This is one area where I feel perfectly safe disregarding the standard.

[laserlight]

What about pointers to out-of-scope variables? Or NULL pointers. Or pointers to freed memory.

As I understand it, null pointers do not point to any location, so they do not point to any undefined location. The other two look like good examples too.

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.

I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.

[brewbuck]

I have been searching the C++ standard for a word on this, but it seems to only deal with one past the end pointers explicitly.

The C and C++ standards irritate me because they were written under the assumption that a computer could be ANYTHING at all. A computer might work via millions of tiny clowns on unicycles. So the standard ends up disallowing tons of completely reasonable code.

Any platform where that nuclear_explosion() function blows up is a platform you'll never see me writing code for. At least not in C/C++.

[robatino]

I'm not sure if it also includes a pointer to a position immediately before the beginning of an array as well... But if it doesn't, it should.

It doesn't. I don't remember the details, but there was a reason involving much more wasted memory if one-past access was allowed at both ends. In any case, it's possible to write loops so they only require it at one end (of course the choice of which end is arbitrary).

[robatino]

Here's a long and detailed thread on the subject:

http://groups.google.com/group/comp....18f6cccd56427d