STL 迭代器是否保证集合更改后的有效性?
假设我有某种集合，并且我获得了它开头的迭代器.现在假设我修改了集合.无论集合类型或迭代器如何，我仍然可以安全地使用迭代器吗?
Let's say I have some kind of collection and I obtained an iterator for the beginning of it. Now let's say I modified the collection. Can I still use the iterator safely, regardless of the type of the collection or the iterator?
为了避免混淆，以下是我所说的操作顺序:
To avoid confusion, here is the order of operations I talk about:
- 获取集合的迭代器.
- 修改集合(显然不是其中的元素，而是集合本身).
- 使用在步骤 1 中获得的迭代器.根据 STL 标准它仍然有效吗?！
推荐答案
取决于容器.例如如果是vector，修改容器后所有迭代器都可以失效.但是，如果是list，则与修改位置无关的迭代器将保持有效.
Depends on the container. e.g. if it's a vector, after modifying the container all iterators can be invalidated. However, if it's a list, the iterators irrelevant to the modified place will remain valid.
当重新分配内存时，向量的迭代器失效.此外，在向量中间插入或删除元素会使所有指向插入或删除点之后的元素的迭代器失效.因此，如果您使用
reserve()预分配向量将使用的尽可能多的内存，并且如果所有插入和删除都在向量的末尾，则可以防止向量的迭代器失效.[1]
A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point. It follows that you can prevent a vector's iterators from being invalidated if you use
reserve()to preallocate as much memory as the vector will ever use, and if all insertions and deletions are at the vector's end. [1]
deque 的迭代器失效语义如下.Insert(包括push_front 和push_back)使所有引用deque 的迭代器无效.在 deque 中间的 Erase 使所有引用 deque 的迭代器无效.Erase 在 deque(包括 pop_front 和 pop_back)的开头或结尾，仅当它指向时才使迭代器无效到被擦除的元素.[2]
The semantics of iterator invalidation for deque is as follows. Insert (including push_front and push_back) invalidates all iterators that refer to a deque. Erase in the middle of a deque invalidates all iterators that refer to the deque. Erase at the beginning or end of a deque (including pop_front and pop_back) invalidates an iterator only if it points to the erased element. [2]
Lists 有一个重要的特性，即插入和拼接不会使列表元素的迭代器失效，即使移除也只会使指向被移除元素的迭代器失效.[3]
Lists have the important property that insertion and splicing do not invalidate iterators to list elements, and that even removal invalidates only the iterators that point to the elements that are removed. [3]
Map 具有一个重要的特性，即将新元素插入到 map 中不会使指向现有元素的迭代器失效.从映射中擦除元素也不会使任何迭代器失效，当然，实际上指向被擦除元素的迭代器除外.[4](set 相同，multiset 和 multimap)
Map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators, except, of course, for iterators that actually point to the element that is being erased. [4] (same for set, multiset and multimap)
相关文章