596

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

（注意：这个问答是Stack Overflow 的 C++ FAQ中的一个条目。关于问题本身的元讨论应该发布在开始所有这些的元问题上，而不是在这里。）
4

6 回答 6

423

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

插入

序列容器

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

关联容器

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

容器适配器

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

擦除

序列容器

  • vector：擦除点之后的每个迭代器和引用都无效 [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]
  • list：根据插入/擦除 [23.2.2.2/1]

注1

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

笔记2

在 C++2003 中不清楚“结束”迭代器是否受上述规则的约束；无论如何，您应该假设它们是（实际上就是这种情况）。

注3

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

于 2011-06-22T10:01:57.873 回答
367

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

插入

序列容器

  • vector：插入点之前的所有迭代器和引用不受影响，除非新容器大小大于以前的容量（在这种情况下，所有迭代器和引用都无效）[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：（不适用）

关联容器

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

未排序的关联容器

  • unordered_[multi]{set,map}：当重新散列发生时，所有迭代器都失效，但引用不受影响 [23.2.5/8]。如果插入不会导致容器的大小超过最大负载因子和当前桶数，z * B则不会发生重新散列。[23.2.5/14]zB

容器适配器

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

擦除

序列容器

  • vector：在擦除点或之后的每个迭代器和引用都无效 [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]
  • array：（不适用）

关联容器

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

无序关联容器

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

容器适配器

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

调整大小

  • vector：根据插入/擦除 [23.3.6.5/12]
  • deque：根据插入/擦除 [23.3.3.3/3]
  • list：根据插入/擦除 [23.3.5.3/1]
  • forward_list：根据插入/擦除 [23.3.4.5/25]
  • array：（不适用）

注1

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

笔记2

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

注3

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

注4

vector并且所有无序关联容器都支持reserve(n)，它保证至少在容器大小增长到n. 对无序关联容器应谨慎，因为未来的提案将允许指定最小负载因子，这将允许insert在足够的erase操作将容器大小减小到最小值以下后进行重新散列；担保应被视为在erase.

于 2011-06-22T15:53:12.653 回答
169

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

插入

序列容器

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

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

  • list：不影响迭代器和引用的有效性。如果抛出异常，则没有任何影响。[26.3.10.4/1]。
    此规则涵盖insert, emplace_front, emplace_back, emplace, push_front,函数。push_back

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

  • array：通常，数组的迭代器在数组的整个生命周期内都不会失效。然而，应该注意的是，在交换期间，迭代器将继续指向同一个数组元素，因此会改变它的值。

关联容器

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

无序关联容器

  • All Unordered Associative Containers: 重新散列使迭代器无效，更改元素之间的顺序，并更改元素出现在哪些桶中，但不会使指针或对元素的引用无效。[26.2.7/9] and成员不应影响对容器元素的引用的有效性，但可能会使容器的所有迭代器无效
    。[26.2.7/14] and成员不应影响迭代器的有效性，如果 ，其中是插入操作之前容器中的元素数，是插入的元素数，是容器的桶数，并且是集装箱的最大装载系数。[26.2.7/15]insertemplace
    insertemplace(N+n) <= z * BNnBz

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

容器适配器

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

擦除

序列容器

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

  • deque：擦除 a 的最后一个元素的擦除操作deque仅使过去的迭代器和所有迭代器以及对被擦除元素的引用无效。擦除 a 的第一个元素但不擦除最后一个元素的擦除操作deque只会使迭代器和对被擦除元素的引用无效。既不擦除 a 的第一个元素也不擦除最后一个元素的擦除操作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 == value, pred(*i) != false. 仅使迭代器和对已擦除元素的引用无效 [26.3.10.5/15]。成员函数 - 从迭代器引用的每个连续
    unique的相等元素组中擦除除第一个元素之外的所有元素（对于不带参数的唯一版本）或i[first + 1, last)*i == *(i-1)pred(*i, *(i - 1))（对于带有谓词参数的唯一版本）成立。仅使迭代器和对已擦除元素的引用无效。[26.3.10.5/19]

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

  • All Sequence Containers:clear使所有引用 a 元素的引用、指针和迭代器无效，并可能使过去的迭代器无效（表 87 — 序列容器要求）。但是对于forward_list,clear不会使过去的迭代器无效。[26.3.9.5/32]

  • All Sequence Containers:assign使所有引用容器元素的引用、指针和迭代器无效。对于vectorand deque，也使过去的迭代器无效。（表 87——序列容器要求）

关联容器

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

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

容器适配器

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

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

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

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

作为上述要求的示例：

  • transform算法：opandbinary_op函数不应使迭代器或子范围无效，或修改范围 [28.6.4/1] 中的元素

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

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

等等...

于 2019-01-02T10:44:35.680 回答
44

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

std::vector例如，当您通过使用对 a 执行一系列插入操作std::insert_iterator时，这些插入很可能会触发向量重新分配，这将使所有“指向”该向量的迭代器无效。但是，有问题的插入迭代器保证保持有效，即您可以安全地继续插入序列。根本不需要担心触发向量重新分配。

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

例如，这段代码

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会继续保持有效。

于 2012-07-04T23:36:24.350 回答
22

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

C++ 03：

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

C++11：

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

所以在 C++03 中，它不是unless the new container size is greater than the previous capacity (in which case all iterators and references are invalidated)另一个答案中提到的“”，而是应该是“ greater than the size specified in the most recent call to reserve()”。这是 C++03 与 C++11 不同的一件事。在 C++03 中，一旦 aninsert()导致向量的大小达到上一次reserve()调用中指定的值（这很可能小于当前值capacity()，因为 areserve()可能导致capacity()大于要求的值），任何后续insert()都可能导致重新分配和无效所有的迭代器和引用。在 C++11 中，这不会发生，您始终可以capacity()确信在 size overpasses 之前不会发生下一次重新分配capacity()。

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

于 2014-03-08T02:24:59.837 回答
8

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

在此处输入图像描述

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

于 2020-04-24T10:44:46.413 回答