6

假设我有以下代码：

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是作为红黑树实现的，是否可以保证地图中的每个元素都将被访问一次？或者修改地图会导致树重新平衡，从而改变迭代顺序？

注意：这不是关于任何迭代器是否会失效的问题。但是保持有效的迭代器并不一定意味着增加它会给你提供与之前相同的下一个元素。

4

5 回答 5

5

在 astd::map中，元素将按顺序访问。

如果您存储的迭代器引用了未删除的元素，因此未失效，则迭代器仍将引用同一元素。（如果它是结束迭代器，它仍然是结束迭代器，因为它没有失效）。

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

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

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

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

这是因为++在有序容器中的有效迭代器上保证返回顺序中的下一个元素，并且不会使迭代器无效的其他迭代器上的操作不会更改该迭代器的不变量（例如它们引用的元素）。

于 2013-05-30T03:39:21.703 回答
2

是的，插入/擦除可以修改迭代顺序。在您的示例中不会发生这种情况，因为您擦除了已经通过的迭代器，但是如果您擦除/插入位于当前迭代器之前的元素，那么它将修改序列的其余部分。

这是显示此类行为的简短代码：

int main (){
    map<int,int> mapa;
    for(int i = 0; i < 5; ++i) mapa[i] = i;
    bool add = false;
    for(auto it = mapa.begin(); it != mapa.end(); ++it){
        int x = it->second;
        printf("%d\n", x);
        if(add) mapa.erase(x+1);
        add = !add;
    }
    return 0;
}

上面的示例将打印0 1 3 4（而不是0 1 2 3 4）。此外，如果您擦除当前迭代器，它对下一个元素的引用将失效，并且您的程序将在下一次迭代时崩溃。

或者，您也可以通过将if(add)上述内容替换为以下内容来测试插入：

if(add) mapa[x+5] = x+5;
else mapa[x-20] = x-20;

该示例将打印额外的元素 {6, 8, 11, 16}，而不打印负数，因为它们被插入到当前元素之前的位置。

于 2013-05-30T03:23:21.693 回答
1

从 a 中删除元素map不会使迭代器无效，因此我希望它能够继续正确迭代。

见https://stackoverflow.com/a/6438087/5987

于 2013-05-30T02:49:41.517 回答
0

尽管您有注释，但对于这种erase情况，这个问题正是关于迭代器失效的，因为如果没有迭代器失效，则顺序必然保持不变。这是因为map它是一个排序的容器，所以无论内部表示可能发生什么变化，迭代顺序都必须保持完全相同。

为了具体解决您的示例，它将仅遍历每个元素一次，因为您保存了迭代器以检查和增加您的遍历迭代器。

在插入的情况下，如果您在当前迭代点之前插入，则不会访问该元素。在当前迭代器之后插入将导致遍历新项目。

于 2013-05-30T03:46:34.230 回答
0

是的，迭代顺序发生了变化。这是由于 §23.2.4.1/10 和 /11：

(p10) 关联容器迭代器的基本特性是它们以键的非降序遍历容器，其中非降序由用于构造它们的比较定义。对于任何两个可解引用的迭代器 i 和 j 使得从 i 到 j 的距离为正，

value_comp(*j, *i) == false

(p11) 对于具有唯一键的关联容器，更强的条件成立，

value_comp(*i, *j) != false.

如果在插入之后，无论元素的顺序如何，都在迭代序列的开头添加新元素（以免在任何现有迭代器位置之前修改序列），则将违反上述要求。

于 2013-05-30T03:21:55.950 回答