1

Take a look at this code excerpt:

while( *it <= *it_end and it != myset.end() )
    if(foo(*it++))
        return true;

it and it_end are valid iterators of std::set (an RB tree).

foo will either:

  • Remove it, and insert again an element with the same value of *it, returing false;
  • Remove it and return true.

My question:

Is it safe to run this loop?

Before calling foo, it will be a valid iterator to the next element of the tree, however I'm afraid that some inner magic inside std::set makes that iterator invalid, like the self-balancing algorithms of the RB tree.

Kira
  • 463
  • 4
  • 12

1 Answers1

0

It seems to be safe because your are using std::set

See http://www.cplusplus.com/reference/set/set/erase

Iterator validity:

Iterators, pointers and references referring to elements removed by the function are invalidated. All other iterators, pointers and references keep their validity.

The increment will happen before foo() is called, i.e. before the element is removed. In other words the increment is done while the iterator is valid and consequently it is safe. Note - that foo() is still called with the value the iterator had before the increment.

The fact that the increment happens before comes from this:

Quoth the [C++ standard][1] 1.9.16 (taken from the link below):

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.)

Much more can be found here: Is it legal to use the increment operator in a C++ function call?

Community
  • 1
  • 1
Support Ukraine
  • 42,271
  • 4
  • 38
  • 63
  • 1
    It is funny how your answer is strictly wrong because your are confusing the difference between post and pre-increment. `it` is incremented before calling `foo`. However the excerpt that you have pasted actually does answer the question, which is "yes, it is safe". I think I should accept your answer and also downvote it, hehehe. – Kira Nov 30 '15 at 19:19
  • @Kira - yes, my first answer was wrong. Not due to a confusion of pre/post increment but due to a confusion of whether the increment was done before or after execution of foo. Answer updated. – Support Ukraine Dec 01 '15 at 08:59