Is it legal to use the increment operator in a C++

Question

There's been some debate going on in this question about whether the following code is legal C++:

std::list<item*>::iterator i = items.begin();
while (i != items.end())
{
    bool isActive = (*i)->update();
    if (!isActive)
    {
        items.erase(i++);  // *** Is this undefined behavior? ***
    }
    else
    {
        other_code_involving(*i);
        ++i;
    }
}

The problem here is that erase() will invalidate the iterator in question. If that happens before i++ is evaluated, then incrementing i like that is technically undefined behavior, even if it appears to work with a particular compiler. One side of the debate says that all function arguments are fully evaluated before the function is called. The other side says, "the only guarantees are that i++ will happen before the next statement and after i++ is used. Whether that is before erase(i++) is invoked or afterwards is compiler dependent."

I opened this question to hopefully settle that debate.

Answer 1

The standard says the side effect happens before the call, so the code is the same as:

std::list<item*>::iterator i_before = i;

i = i_before + 1;

items.erase(i_before);

rather than being:

std::list<item*>::iterator i_before = i;

items.erase(i);

i = i_before + 1;

So it is safe in this case, because list.erase() specifically doesn't invalidate any iterators other than the one erased.

That said, it's bad style - the erase function for all containers returns the next iterator specifically so you don't have to worry about invalidating iterators due to reallocation, so the idiomatic code:

i = items.erase(i);

will be safe for lists, and will also be safe for vectors, deques and any other sequence container should you want to change your storage.

You also wouldn't get the original code to compile without warnings - you'd have to write

(void)items.erase(i++);

to avoid a warning about an unused return, which would be a big clue that you're doing something odd.

Answer 2

It's perfectly OK. The value passed would be the value of "i" before the increment.

Answer 3

To build on Bill the Lizard's answer:

int i = 1;
foo(i++, i++);

might also result in a function call of

foo(1, 1);

(meaning that the actuals are evaluated in parallel, and then the postops are applied).

-- MarkusQ

Answer 4

Sutter's Guru of the Week #55 (and the corresponding piece in "More Exceptional C++") discusses this exact case as an example.

According to him, it is perfectly valid code, and in fact a case where trying to transform the statement into two lines:

items.erase(i);
i++;

does not produce code that is semantically equivalent to the original statement.

Answer 5

Quoth the C++ standard 1.9.16:

When calling a function (whether or not the function is inline), every value computation and side effect associated with any argument expression, or with the postfix expression designating the called function, is sequenced before execution of every expression or statement in the body of the called function. (Note: Value computations and side effects associated with the different argument expressions are unsequenced.)

So it would seem to me that this code:

foo(i++);

is perfectly legal. It will increment i and then call foo with the previous value of i. However, this code:

foo(i++, i++);

yields undefined behavior because paragraph 1.9.16 also says:

If a side effect on a scalar object is unsequenced relative to either another side effect on the same scalar object or a value computation using the value of the same scalar object, the behavior is undefined.

Answer 6

To build on MarkusQ's answer: ;)

Or rather, Bill's comment to it:

(Edit: Aw, the comment is gone again... Oh well)

They're allowed to be evaluated in parallel. Whether or not it happens in practice is technically speaking irrelevant.

You don't need thread parallelism for this to occur though, just evaluate the first step of both (take the value of i) before the second (increment i). Perfectly legal, and some compilers may consider it more efficient than fully evaluating one i++ before starting on the second.

In fact, I'd expect it to be a common optimization. Look at it from an instruction scheduling point of view. You have the following you need to evaluate:

1. Take the value of i for the right argument
2. Increment i in the right argument
3. Take the value of i for the left argument
4. Increment i in the left argument

But there's really no dependency between the left and the right argument. Argument evaluation happens in an unspecified order, and need not be done sequentially either (which is why new() in function arguments is usually a memory leak, even when wrapped in a smart pointer) It's also undefined what happens when you modify the same variable twice in the same expression. We do have a dependency between 1 and 2, however, and between 3 and 4. So why would the compiler wait for 2 to complete before computing 3? That introduces added latency, and it'll take even longer than necessary before 4 becomes available. Assuming there's a 1 cycle latency between each, it'll take 3 cycles from 1 is complete until the result of 4 is ready and we can call the function.

But if we reorder them and evaluate in the order 1, 3, 2, 4, we can do it in 2 cycles. 1 and 3 can be started in the same cycle (or even merged into one instruction, since it's the same expression), and in the following, 2 and 4 can be evaluated. All modern CPU's can execute 3-4 instructions per cycle, and a good compiler should try to exploit that.