c++ 17(所有参考文献均来自CPP17 - n4659的最终工作草案)

---

插入

顺序容器

vector: The functions insert, emplace_back, emplace, push_back cause reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation happens, all the iterators and references before the insertion point remain valid. [26.3.11.5/1] With respect to the reserve function, reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity(). [26.3.11.3/6] deque: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. [26.3.8.4/1] list: Does not affect the validity of iterators and references. If an exception is thrown there are no effects. [26.3.10.4/1]. The insert, emplace_front, emplace_back, emplace, push_front, push_back functions are covered under this rule. forward_list: None of the overloads of insert_after shall affect the validity of iterators and references [26.3.9.5/1] array: As a rule, iterators to an array are never invalidated throughout the lifetime of the array. One should take note, however, that during swap, the iterator will continue to point to the same array element, and will thus change its value.

关联容器

所有关联容器:insert和emplace成员不应影响迭代器和容器引用的有效性[26.2.6/9]

无序关联容器

All Unordered Associative Containers: Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. [26.2.7/9] The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. [26.2.7/14] The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor. [26.2.7/15] All Unordered Associative Containers: In case of a merge operation (e.g., a.merge(a2)), iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid. (Table 91 — Unordered associative container requirements)

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

擦除

顺序容器

vector: The functions erase and pop_back invalidate iterators and references at or after the point of the erase. [26.3.11.5/3] deque: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque. [ Note: pop_front and pop_back are erase operations. —end note ] [26.3.8.4/4] list: Invalidates only the iterators and references to the erased elements. [26.3.10.4/3]. This applies to erase, pop_front, pop_back, clear functions. remove and remove_if member functions: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements [26.3.10.5/15]. unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.10.5/19] forward_list: erase_after shall invalidate only iterators and references to the erased elements. [26.3.9.5/1]. remove and remove_if member functions - Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). Invalidates only the iterators and references to the erased elements. [26.3.9.6/12]. unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.9.6/16] All Sequence Containers: clear invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator (Table 87 — Sequence container requirements). But for forward_list, clear does not invalidate past-the-end iterators. [26.3.9.5/32] All Sequence Containers: assign invalidates all references, pointers and iterators referring to the elements of the container. For vector and deque, also invalidates the past-the-end iterator. (Table 87 — Sequence container requirements)

关联容器

所有关联容器:erase成员只能使被擦除元素的迭代器和引用无效[26.2.6/9] 所有关联容器:extract成员只使被移除元素的迭代器失效;指向被移除元素的指针和引用仍然有效[26.2.6/10]

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

与迭代器失效相关的一般容器需求:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [26.2.1/12] no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ] [26.2.1/(11.6)]

作为上述要求的例子:

变换算法:op和binary_op函数不能使迭代器或子范围失效，也不能修改范围中的元素[28.6.4/1] 在[first, last]范围内，binary_op既不能修改元素，也不能使迭代器或子范围失效[29.8.2/1] Reduce算法:binary_op既不能使迭代器或子范围失效，也不能修改范围[first, last]中的元素。(29.8.3/5)

等等……

c++ 03(来源:迭代器失效规则(c++ 03))

---

插入

顺序容器

vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.2.4.3/1] deque: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.2.1.3/1] list: all iterators and references unaffected [23.2.2.3/1]

关联容器

[multi]{set,map}:所有迭代器和引用不受影响[23.1.2/8]

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

擦除

顺序容器

Vector:擦除点之后的每个迭代器和引用都无效[23.2.4.3/3] Deque:所有迭代器和引用都无效，除非被擦除的成员位于Deque的末尾(前面或后面)(在这种情况下，只有被擦除的成员的迭代器和引用无效)[23.2.1.3/4] 列表:只有迭代器和被擦除元素的引用是无效的[23.2.2.3/3]

关联容器

[multi]{set,map}:只有被擦除的元素的迭代器和引用无效[23.1.2/8]

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

调整

向量:根据插入/擦除[23.2.4.2/6] Deque: as per insert/erase [23.2.1.2/1] 列表:按插入/擦除[23.2.2.2/1]

---

注1

除非另有规定(either 显式地或通过定义函数 对于其他函数)，调用 一个容器成员函数或传递 类的参数 图书馆的功能不应失效 的值的迭代器，或更改 该容器中的对象。 (23.1/11)

注2

在c++ 2003中，“end”迭代器是否服从上述规则还不清楚;无论如何，您应该假设它们是(正如实际情况一样)。

注3

指针无效的规则与引用无效的规则相同。

c++ 11(来源:迭代器失效规则(c++ 0x))

---

插入

顺序容器

vector: all iterators and references before the point of insertion are unaffected, unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated) [23.3.6.5/1] deque: all iterators and references are invalidated, unless the inserted member is at an end (front or back) of the deque (in which case all iterators are invalidated, but references to elements are unaffected) [23.3.3.4/1] list: all iterators and references unaffected [23.3.5.4/1] forward_list: all iterators and references unaffected (applies to insert_after) [23.3.4.5/1] array: (n/a)

关联容器

[multi]{set,map}:所有迭代器和引用不受影响[23.2.4/9]

未排序的关联容器

Unordered_ [multi]{set,map}:当重散列发生时，所有迭代器无效，但引用不受影响[23.2.5/8]。如果插入没有导致容器的大小超过z * B(其中z是最大负载因子，B是当前桶数)，则不会发生重散列。(23.2.5/14)

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

擦除

顺序容器

vector: every iterator and reference at or after the point of erase is invalidated [23.3.6.5/3] deque: erasing the last element invalidates only iterators and references to the erased elements and the past-the-end iterator; erasing the first element invalidates only iterators and references to the erased elements; erasing any other elements invalidates all iterators and references (including the past-the-end iterator) [23.3.3.4/4] list: only the iterators and references to the erased element is invalidated [23.3.5.4/3] forward_list: only the iterators and references to the erased element is invalidated (applies to erase_after) [23.3.4.5/1] array: (n/a)

关联容器

[multi]{set,map}:只有被擦除的元素的迭代器和引用无效[23.2.4/9]

无序关联容器

Unordered_ [multi]{set,map}:只有迭代器和被擦除元素的引用是无效的[23.2.5/13]

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

调整

向量:根据插入/擦除[23.3.6.5/12] Deque: as per insert/erase [23.3.3.3/3] 列表:按插入/擦除[23.3.5.3/1] Forward_list: as per insert/erase [23.3.4.5/25] :数组(n / a)

---

注1

除非另有规定(either 显式地或通过定义函数 对于其他函数)，调用 一个容器成员函数或传递 类的参数 图书馆的功能不应失效 的值的迭代器，或更改 该容器中的对象。 (23.2.1/11)

注2

没有swap()函数会使任何函数失效 引用、指针或迭代器 元素的元素 正在交换集装箱。[注: End()迭代器不指向任何对象 元素，因此它可能无效。 -end note] [23.2.1/10]

注3

除了上面关于swap()的警告之外，不清楚“end”迭代器是否受上述列出的每个容器规则的约束;不管怎样，你应该假设它们是。

注意4

vector and all unordered associative containers support reserve(n) which guarantees that no automatic resizing will occur at least until the size of the container grows to n. Caution should be taken with unordered associative containers because a future proposal will allow the specification of a minimum load factor, which would allow rehashing to occur on insert after enough erase operations reduce the container size below the minimum; the guarantee should be considered potentially void after an erase.

这是cppreference.com网站上的一个很好的汇总表:

这里，插入指的是向容器中添加一个或多个元素的任何方法，擦除指的是从容器中删除一个或多个元素的任何方法。

可能值得添加的是，任何类型的插入迭代器(std::back_insert_iterator, std::front_insert_iterator, std::insert_iterator)只要所有插入都通过该迭代器执行，并且没有发生其他独立的迭代器失效事件，就保证保持有效。

例如，当您使用std::insert_iterator对std::vector执行一系列插入操作时，这些插入操作很可能会触发vector重分配，这将使所有“指向”该vector的迭代器失效。但是，所讨论的插入迭代器保证是有效的，也就是说，您可以安全地继续插入序列。完全没有必要担心触发向量重新分配。

同样，这只适用于通过插入迭代器本身执行的插入。如果容器上的某个独立操作触发了迭代器失效事件，则插入迭代器也会按照一般规则失效。

例如，这段代码

std::vector<int> v(10);
std::vector<int>::iterator it = v.begin() + 5;
std::insert_iterator<std::vector<int> > it_ins(v, it);

for (unsigned n = 20; n > 0; --n)
  *it_ins++ = rand();

保证执行对向量的有效插入序列，即使向量“决定”在此过程中间重新分配。迭代器it显然会失效，但it_ins将继续有效。

c++ 17(所有参考文献均来自CPP17 - n4659的最终工作草案)

---

插入

顺序容器

vector: The functions insert, emplace_back, emplace, push_back cause reallocation if the new size is greater than the old capacity. Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. If no reallocation happens, all the iterators and references before the insertion point remain valid. [26.3.11.5/1] With respect to the reserve function, reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. No reallocation shall take place during insertions that happen after a call to reserve() until the time when an insertion would make the size of the vector greater than the value of capacity(). [26.3.11.3/6] deque: An insertion in the middle of the deque invalidates all the iterators and references to elements of the deque. An insertion at either end of the deque invalidates all the iterators to the deque, but has no effect on the validity of references to elements of the deque. [26.3.8.4/1] list: Does not affect the validity of iterators and references. If an exception is thrown there are no effects. [26.3.10.4/1]. The insert, emplace_front, emplace_back, emplace, push_front, push_back functions are covered under this rule. forward_list: None of the overloads of insert_after shall affect the validity of iterators and references [26.3.9.5/1] array: As a rule, iterators to an array are never invalidated throughout the lifetime of the array. One should take note, however, that during swap, the iterator will continue to point to the same array element, and will thus change its value.

关联容器

所有关联容器:insert和emplace成员不应影响迭代器和容器引用的有效性[26.2.6/9]

无序关联容器

All Unordered Associative Containers: Rehashing invalidates iterators, changes ordering between elements, and changes which buckets elements appear in, but does not invalidate pointers or references to elements. [26.2.7/9] The insert and emplace members shall not affect the validity of references to container elements, but may invalidate all iterators to the container. [26.2.7/14] The insert and emplace members shall not affect the validity of iterators if (N+n) <= z * B, where N is the number of elements in the container prior to the insert operation, n is the number of elements inserted, B is the container’s bucket count, and z is the container’s maximum load factor. [26.2.7/15] All Unordered Associative Containers: In case of a merge operation (e.g., a.merge(a2)), iterators referring to the transferred elements and all iterators referring to a will be invalidated, but iterators to elements remaining in a2 will remain valid. (Table 91 — Unordered associative container requirements)

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

擦除

顺序容器

vector: The functions erase and pop_back invalidate iterators and references at or after the point of the erase. [26.3.11.5/3] deque: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements. An erase operation that erases the first element of a deque but not the last element invalidates only iterators and references to the erased elements. An erase operation that erases neither the first element nor the last element of a deque invalidates the past-the-end iterator and all iterators and references to all the elements of the deque. [ Note: pop_front and pop_back are erase operations. —end note ] [26.3.8.4/4] list: Invalidates only the iterators and references to the erased elements. [26.3.10.4/3]. This applies to erase, pop_front, pop_back, clear functions. remove and remove_if member functions: Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value, pred(*i) != false. Invalidates only the iterators and references to the erased elements [26.3.10.5/15]. unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version of unique with no arguments) or pred(*i, *(i - 1)) (for the version of unique with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.10.5/19] forward_list: erase_after shall invalidate only iterators and references to the erased elements. [26.3.9.5/1]. remove and remove_if member functions - Erases all the elements in the list referred by a list iterator i for which the following conditions hold: *i == value (for remove()), pred(*i) is true (for remove_if()). Invalidates only the iterators and references to the erased elements. [26.3.9.6/12]. unique member function - Erases all but the first element from every consecutive group of equal elements referred to by the iterator i in the range [first + 1, last) for which *i == *(i-1) (for the version with no arguments) or pred(*i, *(i - 1)) (for the version with a predicate argument) holds. Invalidates only the iterators and references to the erased elements. [26.3.9.6/16] All Sequence Containers: clear invalidates all references, pointers, and iterators referring to the elements of a and may invalidate the past-the-end iterator (Table 87 — Sequence container requirements). But for forward_list, clear does not invalidate past-the-end iterators. [26.3.9.5/32] All Sequence Containers: assign invalidates all references, pointers and iterators referring to the elements of the container. For vector and deque, also invalidates the past-the-end iterator. (Table 87 — Sequence container requirements)

关联容器

所有关联容器:erase成员只能使被擦除元素的迭代器和引用无效[26.2.6/9] 所有关联容器:extract成员只使被移除元素的迭代器失效;指向被移除元素的指针和引用仍然有效[26.2.6/10]

容器适配器

堆栈:从底层容器继承 队列:从底层容器继承 Priority_queue:从底层容器继承

---

与迭代器失效相关的一般容器需求:

Unless otherwise specified (either explicitly or by defining a function in terms of other functions), invoking a container member function or passing a container as an argument to a library function shall not invalidate iterators to, or change the values of, objects within that container. [26.2.1/12] no swap() function invalidates any references, pointers, or iterators referring to the elements of the containers being swapped. [ Note: The end() iterator does not refer to any element, so it may be invalidated. —end note ] [26.2.1/(11.6)]

作为上述要求的例子:

变换算法:op和binary_op函数不能使迭代器或子范围失效，也不能修改范围中的元素[28.6.4/1] 在[first, last]范围内，binary_op既不能修改元素，也不能使迭代器或子范围失效[29.8.2/1] Reduce算法:binary_op既不能使迭代器或子范围失效，也不能修改范围[first, last]中的元素。(29.8.3/5)

等等……