c++容器的迭代器失效规则

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

这个问答是Stack Overflow的c++ FAQ中的一个条目。关于问题本身的元讨论应该张贴在正是这个元问题引发了这一切上，而不是这里。)
161126 次浏览
小开

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: as per insert/erase [23.2.4.2/6]
  • deque: as per insert/erase [23.2.1.2/1]
  • list: as per insert/erase [23.2.2.2/1]

注1

< p > # EYZ0 ( 显式地或通过定义函数 对于其他函数)，调用 一个容器成员函数或传递 容器作为 A的参数 图书馆的功能不应失效 迭代器到或改变的值， 该容器中的对象。 [23.1/11] < / p >

注2

# EYZ0;无论如何，您应该假设它们是(正如实际情况一样)。

注3

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

小开

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]
  • # EYZ0: # EYZ1

关联容器

  • [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]
  • # EYZ0: # EYZ1

关联容器

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

无序关联容器

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

容器适配器

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

调整

  • vector: as per insert/erase [23.3.6.5/12]
  • deque: as per insert/erase [23.3.3.3/3]
  • list: as per insert/erase [23.3.5.3/1]
  • forward_list: as per insert/erase [23.3.4.5/25]
  • # EYZ0: (n / a)

注1

< p > # EYZ0 ( 显式地或通过定义函数 对于其他函数)，调用 一个容器成员函数或传递 容器作为 A的参数 图书馆的功能不应失效 迭代器到或改变的值， 该容器中的对象。 (23.2.1/11) < / p >

注2

no swap()函数使任何无效 引用、指针或迭代器 元素的元素 正在交换集装箱。[注:The End () iterator不指向任何对象 元素，所以它是可能无效。 -end note] [23.2.1/10]

注3

除了上述关于swap()， 不清楚“end”迭代器是否服从上面列出的每个容器规则的警告;不管怎样，你应该假设它们是。

注意4

vector和所有无序关联容器支持reserve(n)，这保证至少在容器大小增长到n之前不会自动调整大小。应该谨慎对待无序关联容器，因为未来的提案将允许最小负载因子的规范，这将允许在足够的erase操作将容器大小减小到最小值以下后，在insert上进行重散列;在erase之后，该担保应被视为潜在无效。

小开

可能值得补充的是，只要所有插入都通过该迭代器执行，并且没有发生其他独立的使迭代器失效的事件，任何类型的插入迭代器(std::back_insert_iterator， std::front_insert_iterator， std::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();

保证执行对向量的有效插入序列，即使向量“决定”在此过程中间重新分配。迭代器it显然将无效，但it_ins将继续有效。

小开

由于这个问题获得了如此多的投票，并成为了一个常见问题，我想最好单独写一个答案，以提及c++ 03和c++ 11之间关于std::vector的插入操作对迭代器和引用的有效性的影响的一个重要区别，而投票最多的答案没有注意到这一点。

c++ 03:

重新分配将使所有的引用、指针和迭代器无效 指序列中的元素。这是可以保证的 重新分配发生在调用后发生的插入期间 的大小直到插入时为止 Vector ，大于最近调用中指定的大小 储备()< /强>。< / p >

c++ 11:

重新分配将使所有的引用、指针和迭代器无效 指序列中的元素。这是可以保证的 重新分配发生在调用后发生的插入期间 的大小直到插入时为止 向量# EYZ0。< / p >

所以在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()可以确定地知道，在size超过capacity()之前，下一次重新分配不会发生。

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

小开
最佳答案

c++ 17(所有参考资料均来自CPP17的最终工作草案- n4659)

插入

顺序容器

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

  • 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函数包含在此规则中

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

  • array: 一般来说，数组的迭代器在数组的整个生命周期中永远不会失效。但是，应该注意，在交换过程中，迭代器将继续指向相同的数组元素，因此将改变其值。

关联容器

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

无序关联容器

  • All Unordered Associative Containers:重散列使迭代器无效，改变元素之间的顺序，改变元素出现在哪个桶中，但不会使指向元素的指针或引用无效。[26.2.7/9]
    insert和emplace成员不影响容器元素引用的有效性，但可以使容器的所有迭代器失效。[26.2.7/14]
    insert和emplace成员不应该影响迭代器的有效性，如果(N+n) <= z * B，其中N是插入操作之前容器中的元素数量，n是插入的元素数量，B是容器的桶数，z是容器的最大装载系数。(26.2.7/15) < / p >

  • 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的最后一个元素的擦除操作将使遍历结束迭代器以及对deque的所有元素的所有迭代器和引用失效。 [注:pop_front和pop_back是擦除操作。-end note] [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)(用于不带参数的unique版本)或pred(*i, *(i - 1))(用于带有谓词参数的unique版本)所包含的元素。仅使被擦除的元素的迭代器和引用失效。(26.3.10.5/19) < / p >

  • forward_list: erase_after将只使被擦除的元素的迭代器和引用无效。[26.3.9.5/1]。
    remove和remove_if成员函数——删除列表迭代器i引用的所有元素，其中包含以下条件:*i == value(对于remove())， pred(*i)为真(对于remove_if())。仅使被擦除的元素的迭代器和引用失效。[26.3.9.6/12]。
    unique成员函数——从迭代器i所引用的[first + 1, last)范围内的[first + 1, last]中删除除第一个元素以外的所有连续相等元素组，其中*i == *(i-1)(对于没有参数的版本)或pred(*i, *(i - 1))(对于有谓词参数的版本)所包含的范围。仅使被擦除的元素的迭代器和引用失效。(26.3.9.6/16) < / p >

  • All Sequence Containers: clear使指向a元素的所有引用、指针和迭代器失效，并可能使过尾迭代器失效(表87 -序列容器要求)。但是对于forward_list， clear不会使过尾迭代器失效。(26.3.9.5/32)

  • All Sequence Containers: assign使所有引用，指针和 指向容器元素的迭代器。对于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()迭代器不指向任何元素，因此可能会失效。-end note] [26.2.1/(11.6)]

作为上述要求的例子:

  • op和binary_op函数不能使迭代器或子范围失效，也不能修改范围内的元素[28.6.4/1]

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

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

等等……

小开

下面是来自cppreference.com的一个漂亮的汇总表:

enter image description here

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


提交答案