c++ c++迭代器失效 - 迭代器失效规则




如下stl容器中哪些在增加或者删除节点时指向其它节点的iterator不会失效 (5)

可能值得添加的是,只要所有插入操作都是通过此迭代器执行的,并且没有其他迭代器无效事件,则任何类型的插入迭代器( std::back_insert_iteratorstd::front_insert_iteratorstd::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();

保证在向量中执行有效的插入序列,即使向量“决定”在此过程中的某个地方重新分配也是如此。

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

最好以摘要列表格式。

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


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

插入

序列容器

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

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


由于这个问题吸引了太多的投票,并且成为常见问题解答,我想最好是写一个单独的答案来提及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()的调用的返回值,否则您可能会对“ 过早 ”重新分配感到惊讶。


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后应该认为保证可能无效。


似乎值得重复我的答案中的列表“任何理由来重载全局新的和删除?” 在这里 - 有关更详细的讨论,参考和其他原因,请参阅该答案(或该问题的其他答案 )。 这些原因通常适用于本地操作符重载以及默认/全局重载,以及C malloc / calloc / realloc / free重载或挂钩。

我们工作的全局new和delete运算符超载的原因有很多:

  • 汇集所有小的分配 - 减少开销,减少碎片,可以提高小型重型应用程序的性能
  • 使用已知生命周期划分分配 - 在此期间结束之前忽略所有释放,然后将所有释放一起释放(诚然,我们使用本地运算符重载而不是全局执行此操作)
  • 对齐调整 - 到高速缓存行边界等
  • alloc fill - 帮助揭示未初始化变量的使用情况
  • 免费填充 - 帮助揭示以前删除的内存的使用情况
  • 延迟自由 - 提高自由填充的效率,偶尔提高性能
  • 哨兵fenceposts - 帮助暴露缓冲区溢出,欠载和偶尔的狂野指针
  • 重定向分配 - 考虑NUMA,特殊内存区域,甚至在内存中保持独立的系统(例如嵌入式脚本语言或DSL)
  • 垃圾收集或清理 - 对于那些嵌入式脚本语言也很有用
  • 堆验证 - 您可以在N个alloc / frees中遍历堆数据结构,以确保一切正常
  • 会计 ,包括泄漏跟踪使用快照/统计 (堆栈,分配年龄等)






c++ c++11 iterator c++03 c++-faq