首页 文章

迭代器失效规则

提问于
浏览
456

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

优选地以摘要列表格式 .

(注意:这是Stack Overflow的C FAQ的一个条目 . 如果你想批评在这个表单中提供常见问题解答的想法,那么发布所有这些的meta上的帖子就是这样做的地方 . 这个问题在C聊天室中受到监控,其中FAQ的想法首先出现在那里,所以你的答案很可能被那些提出这个想法的人阅读 . )

4 回答

  • 396

    C++03 (来源:Iterator Invalidation Rules (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

    It's not clear in C++2003 whether "end" iterators are subject to the above rules;无论如何,你应该假设它们是(在实践中就是这种情况) .

    注3

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

  • 335

    C++11 (来源:Iterator Invalidation Rules (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()it's not clear whether "end" iterators are subject to the above listed per-container rules的上述警告除外;无论如何,你应该假设它们是 .

    注4

    vector 和所有无序关联容器都支持 reserve(n) ,这可以保证至少在容器大小增长到 n 之前不会发生自动调整大小 . 应该注意无序的关联容器,因为未来的提议将允许指定最小负载因子,这将允许在足够的 erase 操作将容器大小减小到最小值之后在 insert 上进行重新散列;在 erase 之后,保证应视为可能无效 .

  • 37

    可能有必要补充一点,任何类型的插入迭代器( std::back_insert_iteratorstd::front_insert_iteratorstd::insert_iterator )都保证有效,只要所有插入都是通过此迭代器执行的,并且不会发生其他独立的迭代器无效事件 .

    例如,当您使用 std::insert_iteratorstd::vector 执行一系列插入操作时,很可能这些插入将触发向量重新分配,这将使"point"进入该向量的所有迭代器无效 . 但是,有问题的插入迭代器保证保持有效,即您可以安全地继续插入序列 . 根本不需要担心触发向量重新分配 .

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

    例如,这段代码

    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();
    

    保证在向量中执行有效的插入序列,即使向量"decides"在此过程中间的某处重新分配 . 迭代器 it 显然会变为无效,但 it_ins 将继续有效 .

  • 20

    由于这个问题吸引了如此多的选票而且变成了常见问题解答,我想最好写一个单独的答案来提及C03和C11之间关于 std::vector 的插入操作对迭代器有效性的影响之间的一个显着差异以及关于 reserve()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) " as mentioned in the other answer, instead, it should be " greater than the size specified in the most recent call to reserve() ” . 这是C 03与C 11的不同之处 . 在C 03中,一旦 insert() 导致向量的大小达到前一个 reserve() 调用中指定的值(可能小于当前的 capacity() ,因为 reserve() 可能会导致比要求的更大的 capacity() ),任何后续的 insert() 都可能导致重新分配并使所有迭代器和引用无效 . 在C 11中,这不会发生,您可以始终信任 capacity() 以确定在大小超越 capacity() 之前不会发生下一次重新分配 .

    总之,如果你正在使用C 03向量,并且你想确保重新分配赢得't happen when you perform insertion, it' s你之前传递给 reserve() 的参数的值,你应该检查大小,而不是调用 capacity() 的返回值,否则你可能会对“过早”的重新分配感到惊讶 .

相关问题