在删除和重新插入元素时遍历树

Question

看看这段代码摘录：

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

it 和 it_end 是 std::set（RB 树）的有效迭代器。

foo 将：

删除it，并再次插入一个具有相同值*it的元素，返回false；
删除 it 和 return 为真。

我的问题：

运行这个循环安全吗？

在调用 foo 之前，it 将是树的下一个元素的有效迭代器，但是我担心 std::set 中的某些内部魔法会使该迭代器无效，比如RB树的自平衡算法。

Answer 1

这似乎是安全的，因为你正在使用 std::set

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

增量将在调用 foo() 之前发生，即在元素被删除之前发生。换句话说，增量是在迭代器有效时完成的，因此它是安全的。注意 - foo() 仍然使用迭代器在增量之前的值调用。

增量发生在之前的事实来自于：

引用 [C++ 标准][1] 1.9.16（取自下面的 link）：

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

更多信息可以在这里找到：Is it legal to use the increment operator in a C++ function call?

在删除和重新插入元素时遍历树

Iterating over a tree while removing and reinserting an element

c++

tree

red-black-tree