C++ 的迭代器失效规则容器

Question

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

_{(Note: This Q&A is an entry in Stack Overflow's C++ FAQ. Meta-discussion about the question itself should be posted on the Meta question that started all of this, not here.)}

Answer 1

C++03 （来源：迭代器失效规则 ( C++03))

---

插入

序列容器

• 向量：插入点之前的所有迭代器和引用不受影响，除非新容器大小大于先前的容量（在这种情况下，所有迭代器和引用都无效）[23.2.4.3/1]
• deque：所有迭代器和引用都无效，除非插入的成员位于末尾（前面或后面）双端队列的（在这种情况下，所有迭代器都无效，但对元素的引用不受影响）[23.2.1.3/1]
• list：所有迭代器和引用不受影响[23.2.2.3/1]

关联容器

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

容器适配器< /em>

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

---

擦除

序列容器

• 向量：擦除点之后的每个迭代器和引用都无效[23.2.4.3/3]
• deque：所有迭代器和引用都无效，除非已擦除成员位于双端队列的末尾（前面或后面）（在这种情况下，只有迭代器和对已擦除成员的引用无效）[23.2.1.3/4]
• list：仅迭代器并且对已擦除元素的引用无效 [23.2.2.3/3]

关联容器

• [multi]{set,map}：仅迭代器和对已擦除元素的引用无效[23.1.2/8]

容器适配器

• stack：从底层容器继承
• queue：从底层容器继承
• priority_queue：继承自底层容器

---

调整

• vector大小：根据插入/擦除[23.2.4.2/6]
• deque：根据插入/擦除[ 23.2.1.2/1]
• 列表：按照插入/擦除[23.2.2.2/1]

---

注释1

除非另有说明（或者
显式或通过定义函数
就其他功能而言），调用
容器成员函数或传递
一个容器作为 a 的参数
库函数不得无效
迭代器或更改其值，
该容器内的对象。
[23.1/11]

注 2

C++2003 中尚不清楚“end”迭代器是否受以上规则；无论如何，你应该假设它们是（因为实践中就是这种情况）。

注3：

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

Answer 2

C++11（来源：迭代器失效规则 (C++0x))

---

插入

序列容器

• 向量：插入点之前的所有迭代器和引用不受影响，除非新容器size 大于先前的容量（在这种情况下，所有迭代器和引用都无效） [23.3.6.5/1]
• deque：所有迭代器和引用都无效，除非插入的成员位于末尾（双端队列的前面或后面）（在这种情况下，所有迭代器都无效，但对元素的引用不受影响）[23.3.3.4/1]
• list：所有迭代器和引用不受影响[23.3.5.4/1]
• forward_list：所有迭代器和引用不受影响（适用于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]

容器适配器

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

---

擦除

序列容器

• 向量：擦除点或擦除点之后的每个迭代器和引用都无效[23.3.6.5/3]
• deque：删除最后一个元素只会使迭代器以及对被删除元素和尾后迭代器的引用无效；擦除第一个元素只会使迭代器和对已擦除元素的引用无效；删除任何其他元素会使所有迭代器和引用无效（包括末尾迭代器）[23.3.3.4/4]
• list：只有对已删除元素的迭代器和引用无效[23.3.5.4 /3]
• forward_list：只有迭代器和对被擦除元素的引用无效（适用于erase_after) [23.3.4.5/1]
• 数组：（n/a）

关联容器

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

无序关联容器

• unordered_[multi]{set,map}：只有迭代器和对已擦除元素的引用无效[23.2.5/13]

容器适配器

• 堆栈：从底层容器继承
• queue：从底层容器继承
• priority_queue：从底层容器继承

---

调整

• vector大小：根据插入/擦除[23.3.6.5/12]
• deque：按照插入/擦除 [23.3.3.3/3]
• list：按照插入/擦除 [23.3.5.3/1]
• < code>forward_list：按照插入/擦除 [23.3.4.5/25]
• array：（n/a）

---

注释 1

除非另有说明（或者
显式或通过定义函数
就其他功能而言），调用
容器成员函数或传递
一个容器作为 a 的参数
库函数不得无效
迭代器或更改其值，
该容器内的对象。
[23.2.1/11]

注2

没有任何 swap() 函数会使任何
引用、指针或迭代器
提及的元素
容器正在交换。 [注：
end()迭代器不引用任何
元素，因此它可能会失效。
——尾注] [23.2.1/10]

Note 3

除了上述关于 swap() 的警告之外，尚不清楚“结束”迭代器是否受上面列出的每个容器规则的约束；无论如何，你应该假设它们是。

注 4

vector 和所有无序关联容器都支持 reserve(n)，这保证至少在容器大小达到之前不会自动调整大小增长到n。应谨慎对待无序关联容器，因为未来的提案将允许指定最小负载因子，这将允许在足够的擦除后在插入上进行重新哈希 操作将容器大小减小到最小值以下；在擦除后，该保证应被视为可能无效。

Answer 3

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

---

插入

序列容器

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

• deque：在双端队列中间插入会使所有迭代器和对双端队列元素的引用无效。在双端队列任一端插入都会使双端队列的所有迭代器无效，但不会影响对双端队列元素的引用的有效性。 [26.3.8.4/1]

• list：不影响迭代器和引用的有效性。如果抛出异常，则不会产生任何影响。 [26.3.10.4/1].
  插入、emplace_front、emplace_back、emplace、push_front、push_back 函数涵盖在该规则中。

• forward_list：insert_after 的任何重载都不会影响迭代器和引用的有效性 [26.3.9.5/1]

• array：< a href="https://en.cppreference.com/w/cpp/container/array#Iterator_invalidation" rel="noreferrer">通常，数组的迭代器永远不会失效在阵列的整个生命周期中。然而，应该注意的是，在交换过程中，迭代器将继续指向同一个数组元素，从而改变其值。

关联容器

• 所有关联容器：insert 和 emplace 成员不应影响迭代器和对容器 [26.2.6/9]

无序关联容器

• 所有无序关联容器：重新哈希无效迭代器，更改元素之间的顺序，并更改元素出现在哪些存储桶中，但不会使元素的指针或引用无效。 [26.2.7/9]
  insert 和 emplace 成员不应影响对容器元素的引用的有效性，但可能会使容器的所有迭代器无效。 [26.2.7/14]
  如果 (N+n) <= z * B，则 insert 和 emplace 成员不会影响迭代器的有效性，其中 N 是插入操作之前容器中的元素数量，n 是插入的元素数量，B 是容器的存储桶计数，< code>z 是集装箱的最大负载系数。 [26.2.7/15]

• 所有无序关联容器：在合并操作（例如，a.merge(a2)）的情况下，迭代器引用转移的元素和所有引用 a 的迭代器都将失效，但指向 a2 中剩余元素的迭代器将保持有效。 （表 91 — 无序关联容器要求）

容器适配器

• stack：从底层容器继承
• queue：从底层容器继承
• priority_queue code>：继承自底层容器

---

擦除

序列容器

• vector：函数erase和pop_back无效擦除点或擦除点之后的迭代器和引用。 [26.3.11.5/3]

• deque：擦除 deque 最后一个元素的擦除操作仅使尾后迭代器以及所有迭代器和对已擦除元素的引用。擦除双端队列的第一个元素但不擦除最后一个元素的擦除操作只会使迭代器和对已擦除元素的引用无效。既不删除双端队列的第一个元素也不删除最后一个元素的擦除操作会使尾后迭代器以及对双端队列所有元素的所有迭代器和引用无效。
  [注：pop_front和pop_back是擦除操作。 ——尾注] [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))< /code> （对于带有谓词参数的 unique 版本）成立。仅使迭代器和对已擦除元素的引用无效。 [26.3.10.5/19]

  


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

• 所有序列容器：clear 使引用 a 元素的所有引用、指针和迭代器无效，并可能使过去的-end 迭代器（表 87 — 序列容器要求）。但对于 forward_list 来说，clear 不会使尾后迭代器失效。 [26.3.9.5/32]

• 所有序列容器：分配使所有引用、指针和
  引用容器元素的迭代器。对于vector和deque，也会使尾后迭代器无效。 （表 87 — 顺序容器要求）

关联容器

• 所有关联容器：erase 成员应仅使迭代器和对已擦除对象的引用无效元素[26.2.6/9]

• 所有关联容器：extract 成员仅使已删除元素的迭代器无效；指向已删除元素的指针和引用仍然有效[26.2.6/10]

容器适配器

• 堆栈：从底层容器继承
• 队列：从底层继承容器
• priority_queue：继承自底层容器

---

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

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

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

作为上述要求的示例：

• transform 算法：op 和binary_op 函数不得使迭代器或子范围无效，或修改范围 [28.6.4/1]

  中的元素

• < 中的元素。 p>accumulate 算法：在范围 [first, last] 中，binary_op 既不会修改元素，也不会使迭代器或子范围无效[29.8.2/1]

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

等等...

Answer 4

可能值得补充的是，任何类型的插入迭代器（std::back_insert_iterator、std::front_insert_iterator、std::insert_iterator）都是只要通过此迭代器执行所有插入并且没有其他独立的迭代器无效事件发生，就保证保持有效。

例如，当您使用 std::insert_iterator 对 std::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 将继续保持有效。

Answer 5

这是来自 cppreference.com 的一个很好的汇总表：

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

Answer 6

由于这个问题吸引了如此多的选票，并且有点成为常见问题解答，我想最好写一个单独的答案来提及 C++03 和 C++11 之间关于 std:: 影响的一个显着差异。 vector 对迭代器和引用相对于 reserve() 和 capacity() 有效性的插入操作，这是最多支持的答案未能注意到的。

C++ 03：

重新分配会使所有引用、指针和迭代器失效
引用序列中的元素。保证不会
重新分配发生在调用后发生的插入期间
Reserve() 直到插入的大小达到
向量大于最近调用中指定的大小
保留（）。

C++11：

重新分配会使所有引用、指针和迭代器失效
引用序列中的元素。保证不会
重新分配发生在调用后发生的插入期间
Reserve() 直到插入的大小达到
向量大于capacity()的值。

因此，在 C++03 中，它不是另一个答案中提到的“除非新容器大小大于以前的容量（在这种情况下所有迭代器和引用都无效）”，而是，它应该“大于最近一次调用reserve()时指定的大小”。这是 C++03 与 C++11 的不同之处之一。在 C++03 中，一旦 insert() 导致向量的大小达到先前 reserve() 调用中指定的值（该值很可能小于当前的capacity()，因为reserve()可能会导致比要求的更大的capacity())，任何后续的insert( ) 可能会导致重新分配并使所有迭代器和引用。在 C++11 中，这种情况不会发生，您始终可以相信 capacity() 可以确定地知道，在大小超过 capacity()< 之前不会进行下一次重新分配。 /代码>。

总之，如果您正在使用 C++03 向量，并且希望确保执行插入时不会发生重新分配，那么它就是您之前传递给 reserve() 您应该检查大小，而不是调用 capacity() 的返回值，否则您可能会对“过早”重新分配感到惊讶。