迭代器失效规则

Question

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

优选地以摘要列表格式.

_{(注意:这是Stack Overflow的C++常见问题解答的一个条目.如果你想批评在这种形式下提供常见问题解答的想法,那么发布所有这些的元数据的发布将是这样做的地方.这个问题在C++聊天室中受到监控,其中FAQ的想法一开始就出现了,所以你的答案很可能被那些提出想法的人阅读.)}

Answer 1

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

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

Answer 2

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,其中z为最大负载因数和B桶的当前数目.[23.2.5/14]

容器适配器

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

Answer 3

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

插入

序列容器

• vector:功能insert,emplace_back,emplace,push_back造成再分配如果新的大小比原来容量更大.重新分配使引用序列中元素的所有引用,指针和迭代器无效.如果没有重新分配,插入点之前的所有迭代器和引用仍然有效.[26.3.11.5/1]
  关于reserve函数,重新分配使引用序列中元素的所有引用,指针和迭代器无效.在调用之后发生的插入期间不应进行重新分配,reserve()直到插入将使向量的大小大于值的值为止capacity().[26.3.11.3/6]

• deque:deque中间的插入使所有迭代器和对deque元素的引用无效.在deque两端的插入使deque的所有迭代器无效,但对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:insert和emplace成员不应影响迭代器的有效性和对容器的引用[26.2.6/9]

无序关联容器

• All Unordered Associative Containers:Rehashing使迭代器无效,元素之间的顺序更改以及桶元素出现的更改,但不会使指针或对元素的引用无效.[26.2.7/9]
  的insert和emplace成员不应影响到容器元素的引用的有效性,但可能违反所有迭代器在容器上.[26.2.7/14]
  的insert和emplace成员不应影响迭代器的有效性,如果(N+n) <= z * B,在这里N是在之前的插入操作的容器中的元素的数量,n是插入的元素的数量,B是容器的桶计数,以及z是容器的最大负载系数.[26.2.7/15]

• All Unordered Associative Containers:在合并操作(例如,a.merge(a2))的情况下,引用传递的元素和引用的所有迭代器的迭代器a将无效,但是剩余的元素的迭代器a2将保持有效.(表91 - 无序关联容器要求)

容器适配器

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

擦除

序列容器

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

• deque:删除操作的擦除操作deque只会使过去的迭代器和所有迭代器以及对已擦除元素的引用无效.擦除操作但擦除最后一个元素的第一个元素的擦除操作deque仅使迭代器和对擦除元素的引用无效.擦除操作既不擦除第一个元素也不擦除最后一个元素,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 == valuefor remove()),pred(*i)为true(for remove_if()).仅使迭代器和对已擦除元素的引用无效.[26.3.9.6/12.
  unique成员函数 - 删除迭代器i在[first + 1,last]范围内引用的每个连续的相等元素组中的第一个元素*i == *(i-1)(对于没有参数的版本)或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使引用容器元素的所有引用,指针和迭代器无效.for vector和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]

• no swap()函数使任何引用,指针或迭代器无效,引用被交换的容器的元素.[注意:end()迭代器不引用任何元素,因此它可能无效. - 尾注] [26.2.1 /(11.6)]

作为上述要求的例子:

• transformalgorithm:op和binary_op函数不应使迭代器或子范围无效,或修改范围中的元素[28.6.4/1]

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

• reducealgorithm:binary_op既不会使迭代器或子范围无效,也不会修改[first,last]范围内的元素.[29.8.3/5]

等等...

Answer 4

这可能是值得补充说,任何一种(中插入迭代std::back_insert_iterator,std::front_insert_iterator,std::insert_iterator)是保证保持有效,只要插入所有通过此迭代进行,没有其他独立的迭代器无效的事件发生.

例如,当您std::vector使用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会继续有效.

Answer 5

由于这个问题吸引了如此多的选票而且变成了常见问题解答,我想最好写一个单独的答案来提及C++ 03和C++ 11关于std::vector插入操作对其影响的一个显着差异.迭代器和引用相对的有效性reserve()和capacity(),其中最upvoted答案没有注意到.

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中,一旦a insert()导致向量的大小达到前一次reserve()调用中指定的值(可能小于当前值,capacity()因为reserve()可能导致capacity()大于请求的值),任何后续操作insert()都可能导致重新分配并使其无效所有迭代器和引用.在C++ 11中,这不会发生,您可以始终相信capacity(),在确定大小超越之前不会发生下一次重新分配capacity().

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

Answer 6

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

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