c++ - 迭代器失效规则

Question

在 STL 容器类（Vector、Dequeue、list、map、multimap、set、multiset）上操作时迭代器失效的通常规则是什么。是否可以对 C++ STL 程序员在使用容器及其迭代器时必须注意的一些一般规则/指南进行分类和总结？

score 7 · Accepted Answer

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

例如，std::vector当插入对象时，迭代器可能会失效（取决于插入对象的位置以及是否发生重新分配），并且当在迭代器之前删除对象时它们会失效。安std::list没有这个问题。插入和删除对象（迭代器指向的对象除外）不会使迭代器失效。

SGI 在这方面提供了很好的文档。

score 3 · Accepted Answer

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

C++ 标准以一种可以用简单的 C 指针实现iterator的方式定义的行为。它不需要库实际使用指针；它只是使这样做成为可能。

基本上，如果操作导致底层存储元素（a 中使用的堆数组vector、a 中使用的链表节点list或 a 中使用的树节点）被释放map或set转移到不同的内存中，则迭代器无效地点。

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

同样，当从 a 中删除一个元素时vector，这将导致所有后续元素被向前复制。指向移位元素的迭代器仍将引用数组中的相同索引，但该索引现在包含不同的元素。这也是失效的一个例子。

对于list，map和set，树节点或列表节点保持有效，直到它包含的元素被擦除。请注意，指向无效节点的迭代器不能用于任何事情；甚至对于迭代器递增/递减也不行。这是因为在链表或树实现中，迭代器依赖于存储在节点本身中的子指针。

为了始终保证正确操作，该标准的措辞比使用简单数据结构更严格（矛盾的是，这为库实现者提供了使用更高级数据结构的更多自由）。例如，请参阅http://c2.com/cgi/wiki?IteratorInvalidationProblem和http://www.threadingbuildingblocks.org/codesamples.php。

2 回答 2