迭代器失效规则
在 STL 容器类（Vector、Dequeue、list、map、multimap、set、multiset）上操作时，迭代器失效的常用规则是什么。是否可以对 C++ STL 程序员在使用容器及其迭代器时必须了解的一些通用规则/指南进行分类和总结？
What are the usual rules for Iterator invalidation when operating over STL container classes(Vector,Dequeue,list,map,multimap,set,multiset). Is it possible to categorize and sum up some general rules/guidelines that a C++ STL programmer must be aware of while working with containers and their Iterators?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这些规则是特定于容器的。事实上，这些是决定使用哪个容器的重要标准。
例如，插入对象时，
std::vector的迭代器可能会失效（取决于插入对象的位置以及是否发生重新分配），并且在之前删除对象时，迭代器也会失效。迭代器。std::list不存在这个问题。插入和删除对象（迭代器指向的对象除外）不会使迭代器失效。SGI 对此提供了很好的文档。
These rules are container specific. In fact, these are important criteria for deciding which container you use.
For instance, iterators to an
std::vectorcan get invalidated when an object is inserted (depends in where the object is inserted and if reallocation takes place), and they get invalidated when an object is removed before the iterator. Anstd::listdoes not have this problem. Inserting and removing objects (except for the object the iterator points to) does not invalidate the iterator.SGI provides good documentation on this.
失效规则的灵感来自用于实现这些容器的非常基本的数据结构和算法。如果您不打算学习基础知识，那么您将需要记住迭代器文档。
C++ 标准定义了迭代器的行为，使得使用简单的 C 指针实现成为可能。它不需要库实际使用指针；它只是使这样做成为可能。
基本上，如果操作导致底层存储元素（
向量中使用的堆数组、列表中使用的链表节点或树），迭代器就会失效。map或set中使用的节点）将被释放，或转移到不同的内存位置。向量通常通过从动态内存（堆）分配数组来实现。为了减少重新分配的次数，数组总是分配一些闲置空间，即最初未使用的空间。当元素被添加到数组中时，空闲空间就会被用完。当所有闲置空间都被占用并且需要插入新元素时，将分配一个更大尺寸的新数组。这将导致所有指向旧数组的迭代器失效。同样，当从
向量中删除一个元素时，这将导致所有后续元素被向前复制。指向移位元素的迭代器仍将引用数组中的相同索引，但该索引现在包含不同的元素。这也是无效的一个例子。对于
list、map和set，树节点或列表节点保持有效，直到它包含的元素被删除。请注意，指向无效节点的迭代器不能用于任何用途；甚至对于迭代器递增/递减也不适用。这是因为在链表或树实现中，迭代器依赖于存储在节点本身中的子指针。为了始终保证正确的操作，该标准的措辞比使用简单的数据结构更具限制性（矛盾的是，这为库实现者提供了更多的自由来使用更高级的数据结构）。例如，请参阅 http://c2.com/cgi/wiki?IteratorInvalidationProblem 和 http://www.threadingbuildingblocks.org/codesamples.php 。
The invalidation rules are inspired from the very fundamental Data Structures and Algorithms used to implement these containers. If you do not plan to learn the fundamentals, then you will need to remember the iterator documentation by heart.
The C++ standard defines the behaviors of
iteratorin a way that makes it possible to implement with simple C pointers. It does not require the library to actually use pointers; it simply makes it possible to do so.Basically, an iterator is invalidated if an operation causes an underlying storage element (a heap array used in a
vector, a linked-list node used in alist, or a tree node used in amaporset) to be deallocated, or shifed into a different memory location.A
vectoris usually implemented by allocating an array from the dynamic memory (heap). In order to reduce the number of reallocations, the array is always allocated with some slack, i.e. initially unused space. As elements are added to the array, the slack space is being used up. When all slack space has been taken up and a new element needs to be inserted, then a new array with a bigger size will be allocated. This will cause the invalidation of all iterators pointing to the old array.Likewise, when an element is erased from a
vector, this will cause all subsequent elements to be copied forward. An iterator pointing to the shifted elements will still reference the same index in the array, but that index now contains a different element. This is also an example of invalidation.For
list,mapandset, the tree-node or list-node remains valid until the element it contains is erased. Note that an iterator pointing to an invalidated node cannot be used for anything; not even for iterator increment/decrement. This is because in a linked-list or tree implementation, the iterator depends on child pointers that are stored in the node itself.In order to always guarantee correct operation, the standard is worded in a more restrictive way than if simple data structures are used (which, paradoxically gives more freedom to library implementers to use more advanced data structures). For example, see http://c2.com/cgi/wiki?IteratorInvalidationProblem and http://www.threadingbuildingblocks.org/codesamples.php .