插入/擦除std :: map中的元素会修改迭代序列吗？

Question

说我有以下代码:

typedef std::map< int, std::string >::iterator Iterator;
Iterator iter = myMap.begin();

while (iter != myMap.end())
{
    Iterator current = iter;
    ++iter;

    maybeDeleteElement( current ) // may call erase.
}

鉴于它std::map是作为红黑树实现的,是否保证地图中的每个元素都只被访问一次？或者修改地图会导致树重新平衡,从而改变迭代序列？

注意:这不是关于任何迭代器是否将被无效的问题.但是迭代器仍然有效并不一定意味着递增它将为您提供与之前相同的下一个元素.

Answer 1

在一个std::map元素将按顺序访问.

如果存储引用未删除元素的迭代器,因此迭代器仍将引用同一元素.(如果它是结束迭代器,它仍然是结束迭代器,因为它没有失效).

当您前进该迭代器时,它将在您引用的元素之后按顺序前进到下一个元素.

对于您的特定示例,是的,每个元素将被访问一次,因为元素的所有删除都是在循环的当前迭代器状态之前的元素.

如果您在用于迭代的任何迭代器之前插入元素,那么当您使用迭代器向前迭代时,最终会到达它们.如果您在用于迭代的任何迭代器之前删除元素,那么如果您使用该迭代器进行迭代,它们将不再是您将要访问的未来元素的一部分.

如果插入或删除迭代器当前位置之前的元素,除非您开始调用--或类似函数,否则当前迭代将继续,而不会注意到它们消失了.

这是因为++在有序容器中的有效迭代器上保证返回顺序中的下一个元素,而在其他迭代器上对迭代器无效的操作不会改变迭代器的不变量(就像它们引用的元素一样).