Case for post-increment/decrement

17 views
Skip to first unread message

dave

unread,
May 31, 2001, 10:28:47 AM5/31/01
to
I am searching for a situation when an algorithm absolutely requires
post-increment/decrement behavior and cannot be re-written in terms of
pre-increment/decrement.

For example a coworker wrote the following loop.

while (i--)
{
//do some stuff
}

The pseudocode for what happens with i-- to me then appears to be:

copy i
decrement i
return the copy

I told my coworker to rewrite his loop as:

do
{
//so some stuff
} while (--i);

That way I know he won't be making copies and throwing them away on each
iteration of the loop.

This made me think that there is probably no occasion where
post-increment/decrement couldn't always be re-written in terms of
pre-increment/decrement.

So the challenge is to refute my claim that all post-inc/dec can be
re-written in terms of pre-inc/dec.


Dave Leimbach

NOTE:
I realize the compiler "can" re-write most of these so pre gets called
instead of post but I think people should understand what they are asking
the compiler to do to begin with.
I have seen far too much code with the following in a for loop:

for (i=0; i < SIZE; i++)

what will really end up happening <I would hope> is:

for (i=0; i < SIZE; ++i)

otherwise worthless copies are created and destroyed at the bottom
of each for loop. :)

I am a firm believer in "write what you mean" code.

[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]

Neil Butterworth

unread,
May 31, 2001, 3:46:26 PM5/31/01
to
"dave" <dlei...@earthlink.net> wrote in message
news:87hey2w...@mutt.home.net...

> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.
>
> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
> The pseudocode for what happens with i-- to me then appears to be:
>
> copy i
> decrement i
> return the copy
>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);

Well, I hope he told you where to go! The two loops do not have the same
behaviour; consider the case where i is an integer containing zero. The
first loop will not be executed at all, while the second loop will be
execute a large number of times (until i cycles back round to being zero).

> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.

It's nice to be efficient, but it's nicer to be correct.

[snip]

NeilB

Maciej Sobczak

unread,
May 31, 2001, 3:54:02 PM5/31/01
to
Hi,

"dave" <dlei...@earthlink.net> wrote in message
news:87hey2w...@mutt.home.net...
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.

Probably there is no such one. If we agree that every post- ++ and -- can be
written *in terms of* pre- ++ and --, then post- operators seem to be only
convenience wrappers around their pre- forms. Those wrappers could have been
useful in old C days, when the overhead of creating the temporary (for
example) integer wasn't a bottleneck (of course, there are very tight loops
where even this can shave few % off the performance). Today (when we can
overload operators for our own, often heavy classes) - this convenience
becomes a problem.

> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
> The pseudocode for what happens with i-- to me then appears to be:
>
> copy i
> decrement i
> return the copy
>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);

Wrong.
The first "some stuff" can be *never* executed if i happens to have value
zero at the entry.
The second "some stuff" executes *at least once*, whatever i's value. This
is a difference.
The first loop could be rewritten to this:
while (i)
{
--i;
// do some stuff
}
without changes in semantics.

> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.

Sure.

> This made me think that there is probably no occasion where
> post-increment/decrement couldn't always be re-written in terms of
> pre-increment/decrement.

Well, see above.

> So the challenge is to refute my claim that all post-inc/dec can be
> re-written in terms of pre-inc/dec.

I don't take it up - I claim the same.

> NOTE:
> I realize the compiler "can" re-write most of these so pre gets called
> instead of post but I think people should understand what they are asking
> the compiler to do to begin with.
> I have seen far too much code with the following in a for loop:
>
> for (i=0; i < SIZE; i++)
>
> what will really end up happening <I would hope> is:
>
> for (i=0; i < SIZE; ++i)
>
> otherwise worthless copies are created and destroyed at the bottom
> of each for loop. :)
>
> I am a firm believer in "write what you mean" code.

And this is a problem. People use post- operators just because they "write
what they mean". The example is the first while loop in your post. Rewriting
it for performance is: "write what is better than what you mean".

Maciej Sobczak, http://www.cern.ch/Maciej.Sobczak
"in theory, there is no difference between theory and practice - but in
practice, there is"

Dennis Yelle

unread,
May 31, 2001, 3:57:44 PM5/31/01
to
dave wrote:
>
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.
>
> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }

[...]



> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);

A friend of mine had a rubber stamp made that said:

Does Not Work For N Equals 0.

Dennis Yelle
--
I am a computer programmer and I am looking for a job.
There is a link to my resume here:
http://table.jps.net/~vert/

Ernest Friedman-Hill

unread,
May 31, 2001, 4:50:18 PM5/31/01
to
dave wrote:
>
> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
...

>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);
>

You've introduced a serious bug into your coworker's code. The body of the
first loop won't be executed if i is 0; the second loop will execute
about 2^32 times (assuming 32 bit ints) because i will decrement to -1,
then to -2, then wrap around through all positive numbers before finally
coming back to 0.

The proper rewrite might be

while (--i > 0) {
}

which is probably as cheap as your first version, and more explicit -- but
inarguably longer to type.

And yes, I know the original is broken for negative values -- but at least it
worked for 0.


---------------------------------------------------------
Ernest Friedman-Hill
Distributed Systems Research Phone: (925) 294-2154
Sandia National Labs FAX: (925) 294-2234
Org. 8920, MS 9012 ejf...@ca.sandia.gov
PO Box 969 http://herzberg.ca.sandia.gov
Livermore, CA 94550

Tom Plunket

unread,
May 31, 2001, 4:54:44 PM5/31/01
to
dave wrote:

> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
> The pseudocode for what happens with i-- to me then appears to be:
>
> copy i
> decrement i
> return the copy
>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);
>
> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.

Have you looked at the generated code? "Throwing away" the copy
means nothing; there's still going to be one write to memory
unless the compiler is *really* dumb. It's likely that both of
those decrement to another register anyway, the "write" just
happens from a different source.

Anyway- if you're worried about performance or overhead or
whatever, then look at what gets generated. As far as "The
Standard" requires, I can't imagine that it says anything about
copying or returning anything anywhere, it just says what the
order of operations are...

-tom!

--
Tom Plunket to...@fancy.org
PlayStation2/3D Studio geek
You seem familiar. Have you been in Halas lately?

Francis Glassborow

unread,
May 31, 2001, 4:56:47 PM5/31/01
to
In article <87hey2w...@mutt.home.net>, dave <dlei...@earthlink.net>
writes

>So the challenge is to refute my claim that all post-inc/dec can be
>re-written in terms of pre-inc/dec.

The only case I can think of where even thought would be needed is where
only one of increment and decrement were possible, i.e. there is no
going back. Even then you would also need to be unable to copy the value
in question. Even then I find it difficult to conceive of a case where
it was still impossible to delay your pre-increment until after you had
used the original.


Francis Glassborow ACCU
64 Southfield Rd
Oxford OX4 1PA +44(0)1865 246490
All opinions are mine and do not represent those of any organisation

John Potter

unread,
May 31, 2001, 4:58:30 PM5/31/01
to
On 31 May 2001 10:28:47 -0400, dave <dlei...@earthlink.net> wrote:

> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.

> For example a coworker wrote the following loop.

int i(0); // loop does not execute

> while (i--)
> {
> //do some stuff
> }

> I told my coworker to rewrite his loop as:

int i(0); // loop executes a bunch of times.

> do
> {
> //so some stuff
> } while (--i);

For the other cases, the value of i within the two loops is different
by one.

> So the challenge is to refute my claim that all post-inc/dec can be
> re-written in terms of pre-inc/dec.

First, turn your counter example into an example. ;-)

John

Homer Meyer

unread,
May 31, 2001, 5:00:11 PM5/31/01
to
"dave" <dlei...@earthlink.net> wrote in message
news:87hey2w...@mutt.home.net...
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.

I won't argue that you cannot always rewrite code to use pre-increment
instead of post-increment, because you can. However, sometimes you have to
make the copy anyway, and it can be quite a bit more convienent to use
post-increment instead of explicitly creating a variable and making the copy
yourself.

Consider the pop() function for a simple array based stack. (Error handling
has been left out to keep the code as simple as possible.)

struct stack {
int array[MAX];
size_t top;
};

int pop( stack* pstack ) {
return pstack->array[pstack->top--];
}

Sure you can rewrite this in terms of preincrement, but you are going to
have to make an extra copy of either the index or the value.

int pop( stack* pstack ) {
int old_top = pstack->top;
--pstack->top;
return pstack->array[old_top];
}

or

int pop( stack* pstack ) {
int result = pstack->array[pstack->top];
--pstack->top;
return result;
}

> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
> The pseudocode for what happens with i-- to me then appears to be:
>
> copy i
> decrement i
> return the copy
>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);
>
> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.

The two loops are not equivalent. What happens if i == 0 on the first
iteration?

Answer:
The while(i--) {...} loop exits immediately, but the do {...} while(--i)
loop goes through a very large number of iterations.

And what if the loop were something like this:

while( i-- && some_condition ) {
// do some stuff
}

It can be rewritten using pre-decrment, but it's not nearly as succinct.

<SNIP>

> I am a firm believer in "write what you mean" code.

So am I, but sometimes post-increment/decrement says what I mean a lot
better than pre-increment/decrement.

Jeff Claar

unread,
May 31, 2001, 5:08:53 PM5/31/01
to

"dave" <dlei...@earthlink.net> wrote in message
news:87hey2w...@mutt.home.net...
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.
>
> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }
>
<SNIP>

>
> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);
>
> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.
>

There are a few problems with your rewrite. (For purposes of this message,
I'll assume i is an integer.)

1 - Consider the problem where the initial condition of i is 0. In the first
case, the loop will never execute. In the rewritten case, the do loop will
execute 2^32 times (assuming 32 bit, 2's complement representations).

2 - The value of i after the while loop is different in both cases. In the
first, it will be -1. In the second, it will be 0.

3 - The value of i during the while loop is different. This could require
the rewritten code to be less efficient:
int i = 4;
int buff[4];
while (i--)
{
buff[i] = 0;
}

The equivalent do loop is:
int i = 4;
int buff[4];
do
{
buff[i-1] = 0;
} while (--i);

This requires the additional computation of i-1 each time through the loop,
which is probably as expensive as a post-increment.

> I am a firm believer in "write what you mean" code.

I agree. :-)

Jeff Claar

Drew Eckhardt

unread,
Jun 1, 2001, 8:05:34 AM6/1/01
to
In article <3B167BC1...@alum.mit.edu>,

Ernest Friedman-Hill <ejf...@alum.mit.edu> wrote:
>The proper rewrite might be
>
>while (--i > 0) {
>}
>
>which is probably as cheap as your first version, and more explicit -- but
>inarguably longer to type.

It's also wrong when i is unsigned.

while (i) {
--i;
}

--
<a href="http://www.poohsticks.org/drew/">Home Page</a>
For those who do, no explanation is necessary.
For those who don't, no explanation is possible.

Sean Kelly

unread,
Jun 1, 2001, 8:44:52 AM6/1/01
to
"dave" <dlei...@earthlink.net> wrote in message
news:87hey2w...@mutt.home.net...
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.

It doesn't exist. You can always add a line of code or move bits around to
avoid the need for either pre or post operators. However post-increment
might produce the most succinct code in some situations.


> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }

....


> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);
>
> That way I know he won't be making copies and throwing them away on each
> iteration of the loop.

Certainly, however these two loops are not strictly the same. If i = 0, the
first loop will never be entered at all while the second will run for N
iterations. Also, i will be decremented before the while loop in the first
case, so if you use i inside the loop anywhere you will get different
effects.

Still, why use either situation when you can get the benefit of both with a
for loop?

for( ; i; --i ) {
....
}

As for "write what you mean" -- C/C++ has a ton of unneccessary constructs.
A "pure" language need only the capability for recursion OR a single loop
idiom (LISP, for example) -- C++ has at least 3 types of loops plus the
capability to recurse functions. Personally, I like it, but it also allows
you to represent an algorithm using a number of syntactically different
methods.


Sean

dave

unread,
Jun 1, 2001, 8:50:22 AM6/1/01
to
dave <dlei...@earthlink.net> writes:

I would first like to mention that the code from my previous post
does the job it is supposed to when applied to the context in which
it is used.
That situation is that i is not allowed to be <= 0. There is an assertion
of sorts to prevent the loop from ever executing on the case which makes

do {
} while(--i);

different from

while (i--)
{}

I know someone out there will say this isn't necessarily thread safe.
Give me SOME ground for establishing an argument. :)

Anyway I apologize for not mentioning that before.

Now for a related discussion.

Many authors write the following in their learning programming books:

for (i=0; i < SIZE; i++)

;

This may confuse the C/C++ newbie as to what parts of the for loop control
[the part in (;;)] are executed at what point during the loop iteration.

The same behavior is exhibited whether i++ is executed before or after
the "meat" of the loop just as:

while (i--)
{
}

and

while (i)
{
//loop meat here
i--
}
are identical.

I know when I was learning C/C++ I had trouble seeing that the part that
increments the i value was not executed at the top of each loop iteration
due to this very issue. It's likely I was not the only one.

If the for loop had been written:


for (i=0; i < SIZE; ++i)

{}
I think I would have understood this better.

There is the counter argument that "compilers will optimize this...".
That may be true but I have seen some really strange behavior in some
commericial compilers.. Someone put VC++ in an infinite loop with
perfectly legal C++ code. <John Potter I am looking in your direction> :)
Thusly I don't trust compilers.

I also try to code by a rule:
"If the semantics of the code I key in do not do mean what I am
trying to express then I should re-write the code so it does."

I would clearly be in violation if I ever wrote for (i=0;i<n;i++);

In some cases the compiler can/should not optimize my code.

It's possible my class's implementation of post-increment does more than
the one used on built in types. (It may violate my rule above to have
such a non-standard post-increment operator but I may have a special
exception).

I truly feel postincrement and postdecrement could have been and probably
should have been left out of C/C++. I feel post-increment and decrement
are only there to make programmers feel clever about writing one line of
code that could have been more clearly or just as clearly expressed in
two lines.

#include <iostream>
using namespace std;
//clever one line function
int f (int & val)
{
return val++;
}
//what is really happening [sort-of]
int g (int & val)
{
int copy=val;
++val;
return copy;
}
int main () {
int num=10;
cout << f(num) << endl;
cout << num << endl;
cout << g(num) << endl;
cout << num << endl;
}


And just for fun here is a quiz for you:
Why is ++i++ illegal and (++i)++ not?

[I know the answer I just want to see the replies]

David Suarez de Lis

unread,
Jun 1, 2001, 9:11:37 AM6/1/01
to
Hi,

Homer Meyer wrote:

> Consider the pop() function for a simple array based stack. (Error handling
> has been left out to keep the code as simple as possible.)
>
> struct stack {
> int array[MAX];
> size_t top;
> };
>
> int pop( stack* pstack ) {
> return pstack->array[pstack->top--];
> }

Problem is you have left exception-handling as well... There's no way
to be sure this pop() function will work, for in the case the
assigment operator throws an exception, the Stack has been changed but
the pop()ed value has been lost forever...

That's why STL pop_*() functions are always declared to be void pop().
When you need the value, you can use a non modifying 'T top()' (for
example) and once you have the value, you 'void pop()' it. Another way
is having 'void pop( T& result )'

Considering that exception-handling affects *both* implementation and
design (not just error-handling), I considered necessary to point this
out.. There's a GoTW on this, and more on _Exceptional C++_ by Herb
Sutter... Item 10 on the book, GoTW #8 Challenge Edition.

best regards,
david

Thomas Kunert

unread,
Jun 1, 2001, 10:16:27 AM6/1/01
to
dave wrote:
>
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.
>


//*****************************************************

static unsigned int i = 0;

struct A {
const unsigned int number;
A() : number( i++ ){}
};

struct B {
const unsigned int number;
A a;
B() : number( i++ ){}
};


#include <iostream>

int main()
{
B b;
std::cout << b.number << " " << b.a.number << std::endl;
}

//*******************************************************

Every object of type A and B get's numbered in the order of
construction.
Try this without postincrement and without the introduction of new
functions!

--
Thomas Kunert

Maciej Sobczak

unread,
Jun 1, 2001, 4:04:04 PM6/1/01
to
Hi,
"Drew Eckhardt" <dr...@revolt.poohsticks.org> wrote in message
news:4dg6f9....@revolt.poohsticks.org...

> In article <3B167BC1...@alum.mit.edu>,
> Ernest Friedman-Hill <ejf...@alum.mit.edu> wrote:
> >The proper rewrite might be
> >
> >while (--i > 0) {
> >}
> >
> >which is probably as cheap as your first version, and more explicit --
but
> >inarguably longer to type.
>
> It's also wrong when i is unsigned.
>
> while (i) {
> --i;
> }

To be exact to the limits, this is yet another bug. (Yeah - I've posted the
same. I found the bug after clicking "Send", as always happens.)
This:

while (i--)
{
// abc
}

leaves the i with the value -1 after completion (or "a bit more" if i is
unsigned).
Your code (yeah, yeah - mine too) leaves i with the value 0.
Normally nobody cares, because i is no longer needed, or if needed - it's
reinitialized anyway.
But to be *really* exact (which can matter when the oparator--(int) is
overloaded for our own class and/or has some side-effects) it should be:

while (i)
{
--i;
// abc
}
--i; // NOTE THIS LITTLE EVIL HERE

(it can become a lot more complicated, with more evils, if "abc" can break
the loop)

Which can be the reason why post- operators are still (and remain) in the
language. They are just more intuitive is some situations.

Maciej Sobczak, http://www.cern.ch/Maciej.Sobczak
"in theory, there is no difference between theory and practice - but in
practice, there is"

Allan W

unread,
Jun 1, 2001, 9:11:32 PM6/1/01
to
dave <dlei...@earthlink.net> wrote:
> I am searching for a situation when an algorithm absolutely requires
> post-increment/decrement behavior and cannot be re-written in terms of
> pre-increment/decrement.

This can happen with non-primitive types. The best example that
I have seen is using an STL iterator. Suppose you want to remove
selected elements from a list:

list<myclass>::iterator i = mylist.begin();
while (i != mylist.end()) {
if ( /* complicated condition */ ) {
// Remove the element and move to the next element
mylist.erase(i++);
} else {
// Leave it alone, just move to next
++i;
}
}

You probably want to argue that this is equivalent:

list<myclass>::iterator i = mylist.begin();
while (i != mylist.end()) {
if ( /* complicated condition */ ) {
// Remove the element
mylist.erase(i);
}
// Now move to next element
++i;
}

But this is NOT equivalent -- once you erase the
element, the iterator that points to it becomes
invalid. The only legal way to handle this without
postincrement is to start the loop over again:

list<myclass>::iterator i = mylist.begin();
while (i != mylist.end()) {
if ( /* complicated condition */ ) {
// Remove the element
mylist.erase(i);

// Make i valid again by resetting to
// the beginning. Hopefully the
// "complicated condition" returns the
// same results for the same data...
i = mylist.begin();
} else {
// Leave the element alone, move to next element
++i;
}
}

> For example a coworker wrote the following loop.
>
> while (i--)
> {
> //do some stuff
> }

[snip]


> I told my coworker to rewrite his loop as:
>
> do
> {
> //so some stuff
> } while (--i);

I notice that a lot of people pointed out what happens when the
loop starts with i=0. But there is one other potentially-important
difference.

int i=5;
while (i--) {
std::cout << i << ' ';
}
std::cout << '*' << i << std::endl;
// Output is: 4 3 2 1 0*-1

int j=5;
do {
std::cout << '*' << j << ' ';
} while (--j);
std::cout << j << std::endl;
// Output is: 5 4 3 2 1* 0

The value inside the loop is off by 1, and the value when the
loop completes is off by 1. Sometimes benign, but other times
a fatal difference. Think about it.

Allan W

unread,
Jun 1, 2001, 9:12:08 PM6/1/01
to
> dave wrote:
> > I am searching for a situation when an algorithm absolutely requires
> > post-increment/decrement behavior and cannot be re-written in terms of
> > pre-increment/decrement.

Thomas Kunert <kun...@physik.tu-dresden.de> wrote:
> //*****************************************************
>
> static unsigned int i = 0;
>
> struct A {
> const unsigned int number;
> A() : number( i++ ){}
> };
>
> struct B {
> const unsigned int number;
> A a;
> B() : number( i++ ){}
> };
>
>
> #include <iostream>
>
> int main()
> {
> B b;
> std::cout << b.number << " " << b.a.number << std::endl;
> }
>
> //*******************************************************
>
> Every object of type A and B get's numbered in the order of
> construction.
> Try this without postincrement and without the introduction of new
> functions!

Okay.

//*****************************************************

static unsigned int i = 1;

struct A {
const unsigned int number;

A() : number( ++i ){}
};

struct B {
const unsigned int number;
A a;

B() : number( ++i ){}
};


#include <iostream>

int main()
{
B b;
std::cout << b.number << " " << b.a.number << std::endl;
}

//*******************************************************

What do I win?

Homer Meyer

unread,
Jun 1, 2001, 11:14:25 PM6/1/01
to
"dave" <dlei...@earthlink.net> wrote in message
news:87wv6x8...@mutt.home.net...
> dave <dlei...@earthlink.net> writes:
<SNIP>

> And just for fun here is a quiz for you:
> Why is ++i++ illegal and (++i)++ not?
>
> [I know the answer I just want to see the replies]

Obviously, you don't know the answer as well as you think you do, because it
depends on what type i is. If i is a user defined type, then the pre and
post increment operators can be defined so that the first is just as legal
as the second.

struct foo {
foo& operator++() { return *this; }
foo& operator++(int) { return *this; }
};

int main() {
foo i;
++i++;

Homer Meyer

unread,
Jun 1, 2001, 11:14:50 PM6/1/01
to

"David Suarez de Lis" <dsua...@massdt.es.lucent.com> wrote in message
news:3B175834...@massdt.es.lucent.com...

> Hi,
>
> Homer Meyer wrote:
>
> > Consider the pop() function for a simple array based stack. (Error
handling
> > has been left out to keep the code as simple as possible.)
> >
> > struct stack {
> > int array[MAX];
> > size_t top;
> > };
> >
> > int pop( stack* pstack ) {
> > return pstack->array[pstack->top--];
> > }
>
> Problem is you have left exception-handling as well... There's no way
> to be sure this pop() function will work, for in the case the
> assigment operator throws an exception, the Stack has been changed but
> the pop()ed value has been lost forever...

I know this, and I knew someone would bring it up. That's why I explictly
stated error handling had been left out. In this case no exceptions are
possible, however, because assignment of int's never raises an exception.

> That's why STL pop_*() functions are always declared to be void pop().
> When you need the value, you can use a non modifying 'T top()' (for
> example) and once you have the value, you 'void pop()' it. Another way
> is having 'void pop( T& result )'

Again, I know this. This code was not an example of how to write a stack
class. It was an example of why post-increment/decrement is sometimes more
useful/convenient/expressive than pre-increment/decrement.

<SNIP>

John Potter

unread,
Jun 2, 2001, 2:36:06 PM6/2/01
to
On 1 Jun 2001 21:11:32 -0400, all...@my-dejanews.com (Allan W) wrote:

> dave <dlei...@earthlink.net> wrote:
> > I am searching for a situation when an algorithm absolutely requires
> > post-increment/decrement behavior and cannot be re-written in terms of
> > pre-increment/decrement.
>
> This can happen with non-primitive types. The best example that
> I have seen is using an STL iterator. Suppose you want to remove
> selected elements from a list:
>
> list<myclass>::iterator i = mylist.begin();
> while (i != mylist.end()) {
> if ( /* complicated condition */ ) {
> // Remove the element and move to the next element
> mylist.erase(i++);

This also works for associatives but not for other sequences.

> } else {
> // Leave it alone, just move to next
> ++i;
> }
> }

There are at least two ways to write that without postfix. The postfix
is nothing more than a convenience.

// also works for associatives but not other sequences
list<myclass>::iterator j = i;
++ i;
mylist.erase(j);

or

// also works for other sequences but not associatives
i = mylist.erase(i);

The postfix is a nice convenience, but let's not claim a necessity.

John

Thomas Thiriez

unread,
Jun 2, 2001, 2:40:02 PM6/2/01
to
Allan W wrote:
> dave <dlei...@earthlink.net> wrote:
>> I am searching for a situation when an algorithm absolutely requires
>> post-increment/decrement behavior and cannot be re-written in terms
>> of pre-increment/decrement.
>
> This can happen with non-primitive types. The best example that
> I have seen is using an STL iterator. Suppose you want to remove
> selected elements from a list:
>
> list<myclass>::iterator i = mylist.begin();
> while (i != mylist.end()) {
> if ( /* complicated condition */ ) {
> // Remove the element and move to the next element
> mylist.erase(i++);
> } else {
> // Leave it alone, just move to next
> ++i;
> }
> }
[...]

> The only legal way to handle this without
> postincrement is to start the loop over again:

The post-increment operator does a copy of the iterator before
performing the increment. Therefore, it is possible to repalce the
post-increment by doing a copy, like this:

list<myclass>::iterator i = mylist.begin();
while (i != mylist.end()) {
if ( /* complicated condition */ ) {
// Remove the element and move to the next element

list<myclass>::iterator j = i;
++i;
mylist.erase(j);

} else {
// Leave the element alone, move to next element
++i;
}
}

Thomas

Drew Hall

unread,
Jun 2, 2001, 6:51:04 PM6/2/01
to
Thomas Kunert <kun...@physik.tu-dresden.de> wrote in message
news:<3B17986A...@physik.tu-dresden.de>...

>
> static unsigned int i = 0;
>
> struct A {
> const unsigned int number;
> A() : number( i++ ){}
> };
>
> struct B {
> const unsigned int number;
> A a;
> B() : number( i++ ){}
> };
>
>
> #include <iostream>
>
> int main()
> {
> B b;
> std::cout << b.number << " " << b.a.number << std::endl;
> }
>
> Every object of type A and B get's numbered in the order of
> construction.
> Try this without postincrement and without the introduction of new
> functions!

Okay, I'll bite. How about:

//***************************************


static unsigned int i = 0;

struct A {
const unsigned int number;

A() : number( ++i - 1 ){ }
};

struct B {
const unsigned int number;
A a;

B() : number( ++i - 1 ){ }
};


#include <iostream>

int main()
{
B b;
std::cout << b.number << " " << b.a.number << std::endl;

return 0;
}

//***********************************

Now, I won't make any claim that that's a _better_ way to write it,
but it is equivalent :)

<<<Waiting nervously for inevitable disproof of my claim :) >>>>

Cheers,

Drew

dave

unread,
Jun 2, 2001, 7:57:15 PM6/2/01
to
Comments below.

> > Why is ++i++ illegal and (++i)++ not?

> > [I know the answer I just want to see the replies]
>
> Obviously, you don't know the answer as well as you think you do, because it
> depends on what type i is. If i is a user defined type, then the pre and
> post increment operators can be defined so that the first is just as legal
> as the second.
>
> struct foo {
> foo& operator++() { return *this; }
> foo& operator++(int) { return *this; }
> };
>
> int main() {
> foo i;
> ++i++;
> }
>

You are of course absoultely correct.

Again I have not specified part of the problem.
That is that i is of a built-in type.
Perhaps I should have posed the question to comp.lang.c.moderated...
where you cannot overload operators. :)
(I don't know what the C99 standard says but I am sure someone would correct
me here... )

To finish this up for you you cannot have ++i++ on a built-in type because
of precedence and return value.

The precedence rules state that postfix is evaluated before prefix.
Postfix increment and decrement return RVALUEs and prefix requires an
LVALUE to work on.

So for:

int i;
++i++; is illegal and (++i)++; is not.

One of these days I will pose a question so clearly there will be no doubt
as to what I was thinking at the time. :)

Most of you have been very patient with me and I appreciate it.

Of course the moderators help too... I hope I haven't been keeping
them to busy filtering flames out.

Dave (flamebait) Leimbach

James Dennett

unread,
Jun 2, 2001, 9:53:47 PM6/2/01
to
dave wrote:

[snip]

> That is that i is of a built-in type.
> Perhaps I should have posed the question to comp.lang.c.moderated...
> where you cannot overload operators. :)
> (I don't know what the C99 standard says but I am sure someone would correct
> me here... )
>
> To finish this up for you you cannot have ++i++ on a built-in type because
> of precedence and return value.
>
> The precedence rules state that postfix is evaluated before prefix.
> Postfix increment and decrement return RVALUEs and prefix requires an
> LVALUE to work on.
>
> So for:
>
> int i;
> ++i++; is illegal and (++i)++; is not.

That last one is illegal because it tries to modify i twice
between sequence points.

-- James Dennett

dave

unread,
Jun 3, 2001, 12:21:29 AM6/3/01
to
James Dennett <jden...@acm.org> writes:


> > int i;
> > ++i++; is illegal and (++i)++; is not.
>
> That last one is illegal because it tries to modify i twice
> between sequence points.
>
> -- James Dennett

Where can I find the definition of a sequence point?
Is the standard clear on what this means?

Dave

dave

unread,
Jun 3, 2001, 11:32:53 AM6/3/01
to
dave <dlei...@earthlink.net> writes:

commentary below..


>
>
> > > int i;
> > > ++i++; is illegal and (++i)++; is not.
> >
> > That last one is illegal because it tries to modify i twice
> > between sequence points.
> >
> > -- James Dennett
>
> Where can I find the definition of a sequence point?
> Is the standard clear on what this means?
>
> Dave

Someone was kind enough to refer me to sections of the standard. I do not
own a copy and hesitate to get one as I understand a new standard may be
underway soon...

"... Between the previous and next sequence point a scalar object shall
have its stored value modified at most once by the evaluation of an
expression. Furthermore, the prior value shall be accessed only to
determine the value to be stored. The requirements of this paragraph
shall be met for each allowable ordering of the subexpressions of a
full expression; otherwise the behavior is undefined."

++i++ is clearly undefined here but I think there is still a problem
<most likely with my understanding of sequence points>.

"...the prior value shall be accessed only to determine the value to
be stored."

Ok, so i+=1 or i/=3 are obviously defined but this doesn't seem to leave room
for the postfix operators at all:

So is this then defined?

++i = i++;

And if so this must be defined also.

int a, i;
a = i++;

The only way I understand this to be defined by the standard is if the
expressions on either side of the operator = are in this case seperate
sequence points. Is this always true that operator = is a sequence point
boundary?

So is there an "object-oriented" analogy to sequence points?

I am thinking something along the lines of:

Expressions have sequence points and certainly not that
sequence points have Expressions....

Maybe I will get that standard anyway... :)

Dave Leimbach

PS:
I appreciate everyone's help so far to alleviate my ignorance.

John Potter

unread,
Jun 3, 2001, 11:33:23 AM6/3/01
to
On 2 Jun 2001 21:53:47 -0400, James Dennett <jden...@acm.org> wrote:

> dave wrote:
> > int i;
> > ++i++; is illegal and (++i)++; is not.
>
> That last one is illegal because it tries to modify i twice
> between sequence points.

It's perfectly legal, just undefined behavior. It might format your
hard drive, but usually adds 2 to i returning i + 1.

John

Sef Campstein

unread,
Jun 3, 2001, 12:57:49 PM6/3/01
to
The code your coworker wrote can not be 'simplified' /optimized using
pre-decrement without loosing its semantics.

>
> So the challenge is to refute my claim that all post-inc/dec can be
> re-written in terms of pre-inc/dec.
>
>

Your claim is NOT valid, as one can implement pre-inc/dec and post-inc/dec
for classes in such a way that even i++; and ++i; do not have the same
effect.

Groenten

John Potter

unread,
Jun 3, 2001, 3:30:50 PM6/3/01
to
On 3 Jun 2001 11:32:53 -0400, dave <dlei...@earthlink.net> wrote:

> dave <dlei...@earthlink.net> writes:

> Someone was kind enough to refer me to sections of the standard. I do not
> own a copy and hesitate to get one as I understand a new standard may be
> underway soon...

Standards are changed roughly every ten years. You will get lots of use
from the 1998 standard. A new standard may be underway now, but it will
be a long time before it becomes an approved standard.

> "...the prior value shall be accessed only to determine the value to
> be stored."
>
> Ok, so i+=1 or i/=3 are obviously defined but this doesn't seem to leave
> room for the postfix operators at all:

> So is this then defined?

> ++i = i++;

No, the only sequence point in that expression is the ;. Remember that
the assignment operator is an operator just like +.

Other undefined examples: i = ++i; i = i++; ++i = 5; (i += 1) += 1;
j = ++ i + ++ i;

Sequence points are introduced by && || ?: , (). Where comma is the
comma operator, not the token that seperates parameters in a function
call and () is function call, not the tokens that change the order of
evaluation in an expression. Since user defined operators are
functions, UDTs have well defined behavior in many places where the
builtins have undefined behavior. The last example above would have
unspecified behavior for UDT because + might see i+1, i+2 or i+2, i+1,
assuming normal definition of the operators.

> And if so this must be defined also.
>
> int a, i;
> a = i++;

Nothing is modified more than once, nor accessed for reasons other than
to determine its new value. Because there are no sequence points, the
compiler might generate load i, sto a, inc reg, sto i. I is accessed
to determine its new value, the old value from the access happens to
also be the value of the expression. The expression i + ++ i is an
example of access for purposes other than to determine the new value.

The purpose of sequence points is to allow compilers to retain values
in registers delaying the stores until a sequence point without any
invocation of the as if rule. The as if rule allows delaying longer
if your program can not tell.

John

James Dennett

unread,
Jun 3, 2001, 3:49:42 PM6/3/01
to
John Potter wrote:
>
> On 2 Jun 2001 21:53:47 -0400, James Dennett <jden...@acm.org> wrote:
>
> > dave wrote:
> > > int i;
> > > ++i++; is illegal and (++i)++; is not.
> >
> > That last one is illegal because it tries to modify i twice
> > between sequence points.
>
> It's perfectly legal, just undefined behavior.

I don't consider code which invokes "undefined behavior" to
be legal. I don't think the C++ Standard defines the term
"legal" so this is just a difference of the meaning we give
the term.

Would you say that the code
int *p;
*p = 3;
was legal? I would not, although syntactically it is fine.

> It might format your
> hard drive, but usually adds 2 to i returning i + 1.

In my book, legal code doesn't accidentally format my hard
drive. Code which invokes undefined behavior might do so
to help me avoid the trouble of taking it to a code review.

-- James Dennett

dave

unread,
Jun 3, 2001, 3:50:54 PM6/3/01
to
I am convinced now that my claim is incorrect and even flawed.

Thanks to all who participated in this thread.

It was at least enlightening to me and possibly to those anonymous readers
who didn't chime in with their $.02.

I have seen a counter example already to my claim which I could not refute.

Again thanks...

This newsgroup seems to be one of the best resources for clarifying such
issues.

Dave Leimbach

Dietmar Kuehl

unread,
Jun 3, 2001, 4:03:41 PM6/3/01
to
Hi,

dave wrote:
> I do not own a copy and hesitate to get one as I understand a new
> standard may be underway soon...

Although the C++ standardization commitee decided to work on library
extension and will start thinking about language changes and extensions,
too, the next standard will not be available prior to 2003. Actually, I
would be pretty surprised if it will be available prior to 2005. Since
the standard costs $18 in electronic form at ANSI, I think it is
reasonable to get the standard... (actually, even if the next revision
of the standard become available in one year, I would consider the $18
to be a good investment).
--
<mailto:dietma...@yahoo.com> <http://www.dietmar-kuehl.de/>
Phaidros eaSE - Easy Software Engineering: <http://www.phaidros.com/>

John Potter

unread,
Jun 3, 2001, 10:55:07 PM6/3/01
to
On 3 Jun 2001 15:49:42 -0400, James Dennett <jden...@acm.org> wrote:

> John Potter wrote:
> >
> > On 2 Jun 2001 21:53:47 -0400, James Dennett <jden...@acm.org> wrote:
> >
> > > dave wrote:
> > > > int i;
> > > > ++i++; is illegal and (++i)++; is not.
> > >
> > > That last one is illegal because it tries to modify i twice
> > > between sequence points.
> >
> > It's perfectly legal, just undefined behavior.
>
> I don't consider code which invokes "undefined behavior" to
> be legal. I don't think the C++ Standard defines the term
> "legal" so this is just a difference of the meaning we give
> the term.
>
> Would you say that the code
> int *p;
> *p = 3;
> was legal? I would not, although syntactically it is fine.

Ok. They are both well formed. It is an old arguement whether a
compiler is allowed to issue a diagnostic without proving that the
code will be executed. An implementation is also permitted do
anything with any undefined behavior, including define it.

So, we agree that it is neither illegal nor legal.

John

John Potter

unread,
Jun 3, 2001, 10:55:27 PM6/3/01
to
On 3 Jun 2001 15:50:54 -0400, dave <dlei...@earthlink.net> wrote:

> I am convinced now that my claim is incorrect and even flawed.

> I have seen a counter example already to my claim which I could not refute.

Which one was that?

General statements are usually wrong. This group is good at coming up
with counter examples. It is also good at destroying those counter
examples.

John

Mark Williams

unread,
Jun 4, 2001, 11:49:55 AM6/4/01
to
jpo...@falcon.lhup.edu (John Potter) wrote in message news:<3b1a5e4c...@news.csrlink.net>...

> On 3 Jun 2001 11:32:53 -0400, dave <dlei...@earthlink.net> wrote:
>
> > dave <dlei...@earthlink.net> writes:
>
>
> > "...the prior value shall be accessed only to determine the value to
> > be stored."

>

> > And if so this must be defined also.
> >
> > int a, i;
> > a = i++;
>
> Nothing is modified more than once, nor accessed for reasons other than
> to determine its new value.

Seems to me that the prior value of i is used both to determine the
new value of i _AND_ to determine the new value of a.

Now I personally dont see a problem with that, because I read the
above sentence to mean "the prior value shall not be accessed unless
it is used to determine the value to be stored", rather than "the


prior value shall be accessed only to determine the value to be stored

and for no other purpose", but there was a ridiculously long thread
here (or maybe on comp.std.c) a year or so ago, where the overwhelming
majority view was for the latter interpretation.

What I never understood was how a person could hold that view, and
simultaneously see no problem with the expression "a = i++".


Mark Williams

dave

unread,
Jun 4, 2001, 11:54:43 AM6/4/01
to
jpo...@falcon.lhup.edu (John Potter) writes:


>
> Which one was that?

I believe it was this:

static int i =0;

struct A {
int count;
A () : count(i++) {};
};

struct B {
A a;
int count;
B () : count(i++) {};
};

int main () {
B b;
cout << b.a.count << ' ' << b.count << endl;
}

basically you get 0 1.

Of course since I am clueless as to what a sequence point is yet I am
sure there must be something wrong with the above code.


>
> General statements are usually wrong. This group is good at coming up
> with counter examples. It is also good at destroying those counter
> examples.

Sure. But I have yet to re-write this in terms of prefix or anything else
that behaves the same way this does. Does it violate some section of the
standard... I don't know. I don't have it.. Neither to 1000's of other
C++ programmers I bet. :)

Thomas Kunert

unread,
Jun 4, 2001, 5:29:37 PM6/4/01
to
Allan W wrote:
//*******************************************************
>
> What do I win?
>

Sorry, there is a difference visible: `i' is alway too big using your
code.

Regards,
Thomas

Thomas Kunert

unread,
Jun 4, 2001, 5:30:07 PM6/4/01
to
Drew Hall wrote:
>
> but it is equivalent :)
>
> <<<Waiting nervously for inevitable disproof of my claim :) >>>>
>

I can't find anything wrong :-(
Even in case overflow it seems to be equivalent.

Thanks,
Thomas

Michiel Salters

unread,
Jun 5, 2001, 12:45:02 PM6/5/01
to
In article <87hey2w...@mutt.home.net>, dave says...

>
>I am searching for a situation when an algorithm absolutely requires
>post-increment/decrement behavior and cannot be re-written in terms of
>pre-increment/decrement.

>
>For example a coworker wrote the following loop.
>
>while (i--)
>{

[ SNIP ]

>So the challenge is to refute my claim that all post-inc/dec can be
>re-written in terms of pre-inc/dec.
>

>Dave Leimbach

Try naming this language/newsgroup without using post-incerement :-)

Regards,
Michiel Salters

--
Michiel Salters
Consultant Technical Software Engineering
CMG Trade, Transport & Industry
Michiel...@cmg.nl

John Potter

unread,
Jun 5, 2001, 2:37:24 PM6/5/01
to
On 4 Jun 2001 11:54:43 -0400, dave <dlei...@earthlink.net> wrote:

> I believe it was this:
>
> static int i =0;
>
> struct A {
> int count;
> A () : count(i++) {};
> };
>
> struct B {
> A a;
> int count;
> B () : count(i++) {};
> };

You must have missed Drew Hall's rewrite of this one. I think it is
a general proof of your claim.

For built-in types, any use of x++ may be replaced by ++x-1 with
identical semantics. It also solves your original problem with
while (--i+1).

Of course, that does nothing to support your motivation for wanting
to remove postfix for efficiency reasons. Compilers are much better
at that.

dave

unread,
Jun 5, 2001, 4:46:50 PM6/5/01
to

Comment below:

> Try naming this language/newsgroup without using post-incerement :-)
>

So then C++ is really a copy of C but after you use C++ its one more than C?
:)

Dave


> Regards,
> Michiel Salters

Reply all
Reply to author
Forward
0 new messages