C++ 容器的迭代器失效规则 [英] Iterator invalidation rules for C++ containers

问题描述

C++ 容器的迭代器失效规则是什么?

What are the iterator invalidation rules for C++ containers?

推荐答案

C++17 (所有参考资料均来自 CPP17 的最终工作草案 - n4659)

C++17 (All references are from the final working draft of CPP17 - n4659)

序列容器

• vector:函数insert、emplace_back、emplace、push_back 如果新容量大于旧容量，则导致重新分配.重新分配使指向序列中元素的所有引用、指针和迭代器无效.如果没有重新分配发生时，插入点之前的所有迭代器和引用仍然有效.[26.3.11.5/1]
  对于 reserve 函数，重新分配会使所有引用序列中元素的引用、指针和迭代器无效.在调用 reserve() 之后的插入过程中不会发生重新分配，直到插入会使向量的大小大于 capacity() 的值>.[26.3.11.3/6]

• 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:在双端队列中间插入会使所有迭代器和对双端队列元素的引用无效.在双端队列的任一端插入会使双端队列的所有迭代器无效，但不会影响对双端队列元素的引用的有效性.[26.3.8.4/1]

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:不影响迭代器和引用的有效性.如果抛出异常，则没有任何影响.[26.3.10.4/1].
insert、emplace_front、emplace_back、emplace、push_front、push_back 函数包含在此规则下.

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:insert_after 的任何重载都不会影响迭代器和引用的有效性 [26.3.9.5/1]

forward_list: None of the overloads of insert_after shall affect the validity of iterators and references [26.3.9.5/1]

array:作为规则，数组的迭代器在数组的整个生命周期中永远不会失效.但是需要注意的是，在交换过程中，迭代器会继续指向同一个数组元素，从而改变它的值.

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.

关联容器

• All Associative Containers:insert 和 emplace 成员不应影响迭代器的有效性和对容器的引用 [26.2.6/9]

• All Associative Containers: The insert and emplace members shall not affect the validity of iterators and references to the container [26.2.6/9]

无序关联容器

• 所有无序关联容器:重新散列会使迭代器失效，更改元素之间的顺序，并更改元素出现在哪些桶中，但不会使元素的指针或引用失效.[26.2.7/9]
  insert 和 emplace 成员不应影响对容器元素的引用的有效性，但可能会使容器的所有迭代器无效.[26.2.7/14]
  insert 和 emplace 成员不应影响迭代器的有效性，如果 (N+n) <= z * B，其中 N为插入操作前容器中的元素个数，n为插入元素个数，B为容器的bucket个数，z 是容器的最大负载因子.[26.2.7/15]

• 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:在合并操作的情况下(例如，a.merge(a2))，引用传输元素的迭代器和所有引用 a 的迭代器将失效，但指向 a2 中剩余元素的迭代器将保持有效.(表 91 — 无序关联容器要求)

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)

容器适配器

• stack:从底层容器继承
• queue:从底层容器继承
• priority_queue:从底层容器继承

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

序列容器

• vector:函数 erase 和 pop_back 在擦除点或之后使迭代器和引用无效.[26.3.11.5/3]

• 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:擦除 deque 的最后一个元素的擦除操作仅使尾后迭代器和所有迭代器以及对擦除的引用无效元素.擦除 deque 的第一个元素而不是最后一个元素的擦除操作只会使迭代器和对被擦除元素的引用无效.既不擦除 deque 的第一个元素也没有擦除最后一个元素的擦除操作会使尾后迭代器和所有迭代器以及对 deque 的所有元素的引用无效.[ 注意:pop_front 和 pop_back 是擦除操作.—尾注] [26.3.8.4/4]

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:仅使迭代器和对已擦除元素的引用无效.[26.3.10.4/3].这适用于erase、pop_front、pop_back、clear 功能.
remove 和 remove_if 成员函数:擦除列表迭代器 i 引用的列表中的所有元素，其中满足以下条件:*i == 值, pred(*i) != false.仅使迭代器和对已擦除元素的引用无效 [26.3.10.5/15].
unique 成员函数 - 从 [first + 1, last) 范围内的迭代器 i 引用的每组连续相等元素中删除除第一个元素之外的所有元素 其中 *i == *(i-1)(对于没有参数的 unique 版本)或 pred(*i, *(i - 1))(对于带有谓词参数的 unique 版本)成立.仅使迭代器和对已擦除元素的引用无效.[26.3.10.5/19]

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 应仅使迭代器和对已擦除元素的引用无效.[26.3.9.5/1].
remove 和 remove_if 成员函数 - 删除列表迭代器 i 引用的列表中的所有元素，其中满足以下条件:*i == value(对于 remove())，pred(*i) 为真(对于 remove_if()).仅使迭代器和对已擦除元素的引用无效.[26.3.9.6/12].
unique 成员函数 - 从迭代器 i 引用的每个连续的相等元素组中删除除第一个元素之外的所有元素，范围为 [first + 1, last)，其中 *i == *(i-1)(对于没有参数的版本)或 pred(*i, *(i - 1))(对于有谓词参数的版本)成立.仅使迭代器和对已擦除元素的引用无效.[26.3.9.6/16]

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 使所有引用 a 元素的引用、指针和迭代器无效，并可能使尾后迭代器 (表 87 — 序列容器要求).但是对于 forward_list，clear 不会使过去的迭代器无效.[26.3.9.5/32]

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 使所有引用、指针和引用容器元素的迭代器.对于 vector 和 deque，也使后尾迭代器无效.(表 87 — 序列容器要求)

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)

关联容器

• All Associative Containers:erase 成员应仅使迭代器和对已擦除元素的引用无效 [26.2.6/9]

• All Associative Containers: The erase members shall invalidate only iterators and references to the erased elements [26.2.6/9]

All Associative Containers:extract 成员仅使移除元素的迭代器失效；指向已删除元素的指针和引用仍然有效 [26.2.6/10]

All Associative Containers: The extract members invalidate only iterators to the removed element; pointers and references to the removed element remain valid [26.2.6/10]

容器适配器

• stack:从底层容器继承
• queue:从底层容器继承
• priority_queue:从底层容器继承

• stack: inherited from underlying container
• queue: inherited from underlying container
• priority_queue: inherited from underlying container

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

• 除非另有说明(明确地或通过根据其他函数定义函数)，调用容器成员函数或将容器作为参数传递给库函数不应使迭代器无效或更改值的，该容器内的对象.[26.2.1/12]

• 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]

没有 swap() 函数会使任何引用、指针或迭代器无效，这些引用、指针或迭代器引用了被交换的容器的元素.[ 注意:end() 迭代器不引用任何元素，因此它可能会失效.—尾注] [26.2.1/(11.6)]

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)]

作为上述要求的示例:

• transform 算法:op 和 binary_op 函数不应使迭代器或子范围无效，或修改范围内的元素 [28.6.4/1]

• transform algorithm: The op and binary_op functions shall not invalidate iterators or subranges, or modify elements in the ranges [28.6.4/1]

accumulate 算法:在 [first, last] 范围内，binary_op 不得修改元素，也不得使迭代器或子范围无效 [29.8.2/1]

accumulate algorithm: In the range [first, last], binary_op shall neither modify elements nor invalidate iterators or subranges [29.8.2/1]

reduce 算法:binary_op 不应使迭代器或子范围无效，也不应修改范围 [first, last] 中的元素.[29.8.3/5]

reduce algorithm: binary_op shall neither invalidate iterators or subranges, nor modify elements in the range [first, last]. [29.8.3/5]

等等...

这篇关于C++ 容器的迭代器失效规则的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！