为什么从地图擦除操作不invalide迭代

我不知道为什么从地图根据谓词在循环中的擦除操作保持在一个状态的Valide迭代器，而不是一个向量为什么从地图擦除操作不invalide迭代

2011-05-29 Guillaume07

erm ...因为该标准指定它必须符合该行为。如果你想知道_how_在树上（avl，rb）阅读（也许从链表开始）。 – sehe 2011-05-29 10:28:00

Vector::erase使迭代器无效到所有元素之后被清除的第一个元素。这是有道理的，因为矢量将数据存储在数组中。当一个元素被删除时，它之后的所有元素都需要被移动，例如，

int test[] = {0, 1, 2, 3, 4, 5}; 
          ^

在我们指着值5，这是我们想要的迭代器上面，然而，元件1被擦除，我们现在有：

0, 2, 3, 4, 5 
      ^

的迭代器指向过去的结束的阵列，一个问题。

随着std::map，数据存储在二叉树，所以当一个元素被删除，一些节点的左/右指针被修改，但他们在内存中的位置不会改变。因此，任何指向尚未被擦除的元素的现有迭代器仍然有效。

来源

2011-05-29 10:33:08 Node

我认为你的例子通过删除最后一个元素来歪曲事情。从数组中间删除一个元素也是一样（因为（假设平凡的指针迭代器）可达性保证被违反了（你会不小心跳过下一个条目），并且允许实现使用非平凡的迭代器类型，例如用于调试，并且这些被允许在从矢量删除后调用更多未定义的行为） – sehe 2011-05-29 10:40:03

@sehe，我选择了最后一个元素来做一个简单易懂的例子，但这是关于中间元素的一个好点。 – Node 2011-05-29 10:42:13

见http://www.sgi.com/tech/stl/Map.html

地图具有将新元素插入地图的重要属性不会使指向现有元素的迭代器无效。从地图擦除元素也不会使任何迭代器失效，当然，除了实际指向正在被擦除的元素的迭代器。

它实际上是一个功能。它并不会使它们失效，因为它不需要。对于矢量而言，你至少必须去除所有被删除元素的所有元素，并且指针会改变。

来源

2011-05-29 10:32:32

呃...简单的回答：

因为标准需要这种行为。

如果你想知道如何上树（AVL，RB）阅读（可能是用链表开始）

您可以轻松地在想，当你从中间删除一个项目发生了什么想象它在你的心中（即C风格的数组;后来的项目被移动），而不是从列表/树中移除（没有项目被移动，只有链接指针被更新）。

请注意，遍历可以使向量安全（通过使用序号索引而不是迭代器），但这不是重点：迭代器接口要求增量会导致下一个有效的迭代器。这不是真的（即使在实现中使用T *的'简单'迭代器）也不是这样。

来源

2011-05-29 10:32:36 sehe

为什么从地图擦除操作不invalide迭代

回答

相关问题