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

Question

看看这段代码摘录:

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

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

foo 将:

• 移除it，并再次插入一个与*it相同值的元素，返回false；
• 删除它并返回 true。

我的问题:

运行这个循环安全吗？

在调用 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(取自以下链接):

When calling a function (whether ornot the function is inline), everyvalue computation and side effectassociated with any argumentexpression, or with the postfixexpression designating the calledfunction, is sequenced beforeexecution of every expression orstatement in the body of the calledfunction. (Note: Value computationsand side effects associated with thedifferent argument expressions areunsequenced.)

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