logo标签列表

在std::map中插入/删除元素是否会修改迭代顺序？

c++iteratorstdmapred-black-tree
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 实现为红黑树，是否可以保证地图中的每个元素都恰好被访问一次？或者修改地图会导致树重新平衡，从而改变迭代顺序？
注意：这不是关于迭代器是否会失效的问题。但迭代器仍然有效并不一定意味着将其递增会给出与之前相同的下一个元素。
1
可能是迭代器失效规则的重复问题。 - Anthony
修改后，这不再是上述建议问题的重复。 - jogojapan
1
你的例子和标题中的问题只有轻微的关联。你是在问标题中的问题，还是在询问你的例子？ - Yakk - Adam Nevraumont
一个指向标准的红黑树 std::map 的迭代器本质上是一个指向包含某个元素的节点的指针，而不是什么“根节点左边然后右边的节点”。因此，未失效的迭代器在树重新平衡时仍然指向相同的元素。但我找不到标准引用来证明所有这些都是保证的。 - aschepler
5个回答
5
在 std::map 中，元素将按顺序访问。
如果您存储的迭代器指向未被删除（因此未失效）的元素，则迭代器仍将指向该元素。 （如果它是 end 迭代器，则仍为 end 迭代器，因为它未失效）。
当您推进该迭代器时，它会在您引用的元素之后按顺序推进到下一个元素。
对于您特定的示例，是的，每个元素将仅被访问一次，因为所有已删除元素都位于循环的当前迭代器状态之前。
如果您在要使用进行迭代的迭代器之前插入元素，则在使用迭代器向前迭代时最终将到达它们。 如果您在要使用进行迭代的迭代器之前删除元素，则它们将不再是您使用该迭代器迭代时到达的未来元素的一部分。
如果您插入或删除在迭代器当前位置之前的元素，除非开始调用 -- 或类似的函数，否则当前迭代将继续而不注意它们消失了。
这是因为有序容器中有效迭代器上的 ++ 保证返回按顺序的下一个元素，并且对不使迭代器失效的其他迭代器的操作不会更改该迭代器的不变性（例如它所指向的元素）。
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}，而不打印负数，因为这些负数被插入到当前位置之前。
你的例子和原帖中的例子不同。原帖中的例子是在迭代器可能被删除之前先将其推进了。而你的例子是在迭代器被推进之前就已经删除了一个元素。 - Yakk - Adam Nevraumont
是的，但问题涉及插入/删除元素，而不仅仅是示例。在OP的代码中，它将正常运行，因为过去的元素不会影响未来元素的顺序，就像我的插入示例所示。 - i Code 4 Food
@Yakk 我特别是在讲在删除之前推进迭代器，但是在这里提到这个警告仍然很有用。 - Dominic Gurto
1
这实际上取决于std::map迭代器的实现方式：它是使用树的结构还是键的排序（似乎是后者）。 - Dominic Gurto
@DominicGurto，它并不取决于实现 - 如果标准保证了它，那么实现就别无选择，只能符合标准。 - Mark Ransom
如果标准没有明确规定，那么实现可以随意处理... - Dominic Gurto
@DominicGurto，如果不清楚的话，那就是我的观点 - 在这种情况下，标准确实有规定。 - Mark Ransom
0

是的，迭代序列会发生变化。这是由于§23.2.4.1/10和/11所致：

(p10) The fundamental property of iterators of associative containers is that they iterate through the containers in the non-descending order of keys where non-descending is defined by the comparison that was used to construct them. For any two dereferenceable iterators i and j such that distance from i to j is positive,

value_comp(*j, *i) == false

(p11) For associative containers with unique keys the stronger condition holds,

value_comp(*i, *j) != false.
如果在插入后，新元素无论元素的排序如何都被添加到迭代序列的开头（以不修改任何现有迭代器位置前面的序列），那么上述要求将被违反。
我认为当你说“迭代序列改变”时，完全不同于OP在询问迭代序列是否改变时所考虑的。因此，你的回答会令人困惑，并且似乎是矛盾的。 - Benjamin Lindley
@BenjaminLindley 上面的意思是，当你前进一个迭代器时，你将按顺序得到下一个元素（由value_comp定义）。因此，如果您进行插入操作，然后再前进迭代器，那么您所获得的元素可能与没有插入操作时不同。这不是OP想知道的吗？如果我理解错误，请原谅。 - jogojapan
直接阅读OP代码后的段落。请注意，有两个命题，OP认为它们是相互矛盾的。第一个命题似乎很清楚。 “地图中的每个元素是否保证只访问一次？” - 答案显然是肯定的。第二个命题，“或者修改地图会导致...迭代序列改变吗？” - 不清楚OP的意思是什么，但如果它与第一个命题相矛盾，则必须为假。我不是说你的答案是错误的，但我认为措辞很令人困惑。 - Benjamin Lindley
0
尽管您的注释，对于erase情况，这个问题确切地涉及到迭代器失效，因为如果没有迭代器失效，顺序必然保持不变。这是因为map是一个排序容器，所以无论发生什么内部表示变化，迭代顺序都必须完全相同。
针对您的示例，它将恰好遍历每个元素一次，因为您保存了迭代器来检查和增加遍历迭代器。
在插入的情况下，如果您在当前迭代点之前插入元素，则不会访问该元素。在当前迭代器之后插入将导致新项目被遍历。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接