代码之家 › 专栏 › 技术社区 › Alok Save

迭代器失效规则[重复]

invalidation iterator stl c++

5

Alok Save · 技术社区 · 15 年前

在STL容器类(Vector、Dequeue、list、map、multimap、set、multiset)上操作时,迭代器失效的常见规则是什么。是否有可能对C++的STL程序员在处理容器及其迭代器时必须知道的一些一般规则/准则进行分类和总结?

2 回复 | 直到 15 年前

1

6

Björn Pollex 15 年前

这些规则是特定于容器的。事实上,这些是决定使用哪个容器的重要标准。

例如,迭代器 std::vector std::list 没有这个问题。插入和移除对象(迭代器指向的对象除外)不会使迭代器失效。

SGI提供良好的 documentation

2

3

rwong 15 年前

无效规则的灵感来自于 数据结构和算法 用于实现这些容器。如果您不打算学习基础知识,那么您需要记住迭代器文档。

iterator 在某种程度上用简单的C指针实现。它并不要求库实际使用指针;它只是使这样做成为可能。

基本上,如果操作导致底层存储元素(在 vector ,在 list map 或 set )被释放或转移到不同的内存位置。

一个通常通过从动态内存(堆)分配数组来实现。为了减少重新分配的次数,数组总是分配一些空闲空间,即最初未使用的空间。当元素被添加到数组中时,空闲空间将被耗尽。当所有空闲空间都被占用并且需要插入新元素时,将分配一个更大的新数组。这将导致指向旧数组的所有迭代器失效。

矢量 ,这将导致所有后续元素被向前复制。指向移位元素的迭代器仍将引用数组中的同一索引,但该索引现在包含不同的元素。这也是一个无效的例子。

为了 列表 , 设置 ,树节点或列表节点在其包含的元素被删除之前保持有效。注意,指向无效节点的迭代器不能用于任何事情;甚至不能用于迭代器增量/减量。这是因为在链表或树实现中,迭代器依赖于存储在节点本身中的子指针。