[c++] 迭代器失效规则



Answers

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

插入

序列容器

  • vector :插入点之前的所有迭代器和引用不受影响,除非新的容器大小大于先前的容量(在这种情况下,所有迭代器和引用都将失效)[23.3.6.5/1]
  • deque :所有迭代器和引用都是无效的,除非插入的成员在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 :从底层容器继承

擦除

序列容器

  • 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(n / a)

关联容器

  • [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 :(n / a)

注1

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

笔记2

没有swap()函数会使任何引用,指针或迭代器引用正在交换的容器元素。 [注意: end()迭代器不引用任何元素,所以它可能会失效 。 - 结束] [23.2.1 / 10]

注3

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

注4

vector和所有无序的关联容器支持reserve(n) ,这保证了不会自动调整大小,至少在容器的大小增长到n 。 应该注意无序的关联容器,因为未来的提议将允许指定最小的加载因子,这将允许在足够的erase操作将容器大小减小到最小值之后insert时发生再次散列; erase后应该认为保证可能无效。

Question

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

最好以摘要列表格式。

(注意:这意味着要成为的C ++常见问题解答的入口,如果您想批评在此表单中提供常见问题解答的想法,那么启动所有这些工作的meta上的贴子将成为这样做的地方。该问题在C ++聊天室中进行监控,常见问题解决方案首先出现在C ++聊天室中,因此您的答案很可能会被提出这一想法的人阅读。)




由于这个问题吸引了太多的投票,并且成为常见问题解答,我想最好是写一个单独的答案来提及C ++ 03和C ++ 11之间关于std::vector的影响之间的一个显着区别插入操作对迭代器的有效性以及对reserve()capacity()引用,这是最有争议的答案未能注意到的。

C ++ 03:

重新分配将使所有引用序列中元素的引用,指针和迭代器无效。 保证在调用reserve()之后发生的插入过程中不发生重新分配,直到插入将使向量的大小大于最近调用reserve()时指定的大小为止。

C ++ 11:

重新分配将使所有引用序列中元素的引用,指针和迭代器无效。 确保在调用reserve()之后发生的插入过程中不发生重新分配,直到插入将使vector的大小大于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中,一旦insert()导致vector的大小达到前一个reserve()调用中指定的值(这可能小于当前capacity()因为reserve()会导致更大capacity()要求),任何后续的insert()都可能导致重新分配并使所有迭代器和引用无效。 在C ++ 11中,这种情况不会发生,您可以始终相信capacity()可以确定地知道下一次重新分配不会在大小超过capacity()之前发生。

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




Links