Итераторы STL гарантируют действительность после изменения коллекции?

Question

Предположим, у меня есть какая-то коллекция, и я получил итератор для его начала. Теперь предположим, что я модифицировал коллекцию. Могу ли я использовать итератор безопасно, независимо от типа коллекции или итератора?

Чтобы избежать путаницы, здесь порядок операций я говорю о:

1. Получить итератор коллекции.
2. Изменить коллекцию (очевидно не элемент в ней, а сама коллекция).
3. Используйте итератор, полученный на шаге 1. Является ли он действительным в соответствии со стандартом STL ?!

Answer 1

Зависит от контейнера. например если это vector, после изменения контейнера все итераторы могут быть аннулированы. Однако, если это list, итераторы, не имеющие отношения к модифицированному месту, останутся действительными.

• итераторы вектора, являются недействительными, если его память перераспределяется. Кроме того, вставка или удаление элемента в середине вектора аннулирует все итераторы, указывающие на элементы, следующие за точкой вставки или удаления. Из этого следует, что вы можете помешать итераторам вектора быть недействительными, если вы используете reserve() для предопределения столько памяти, сколько будет использоваться вектором, и если все вставки и удаления находятся на конце вектора. [1]

• Семантика недействительности итератора для deque заключается в следующем. Insert (включая push_front и push_back) аннулирует все итераторы, ссылающиеся на deque. Erase в середине deque аннулирует все итераторы, ссылающиеся на deque. Erase в начале или конце deque (включая pop_front и pop_back) аннулирует итератор, только если он указывает на стертый элемент. [2]

• List s имеют важное свойство, что вставка и сплайсинг не аннулирует итераторы в список элементов, и даже удаление аннулирует только итераторы, которые указывают на элементы, которые будут удалены. [3]

• Map имеет важное свойство, вставляя новый элемент в map не аннулирует итераторы, которые указывают на существующие элементы. Стирание элемента с карты также не отменяет никаких итераторов, за исключением, конечно, для итераторов, которые фактически указывают на стираемый элемент. [4] (то же самое для set, multiset и multimap)

Answer 2

Нет, итераторы хороши только тогда, когда итерированный контейнер не изменяется. Если коллекция изменена, итератор должен быть получен заново.

Answer 3

Это зависит от коллекции под вопросом. Например, изменение std::vector (например, добавление элемента) может привести к недействительности всех итераторов в этом векторе.Напротив, с std::list, итераторы остаются в силе, когда вы добавляете в список еще один элемент. В некоторых случаях правила еще сложнее (например, если память работает с std::deque, добавление к началу или концу оставляет существующие итераторы действительными, но добавление где-либо еще может привести к их недействительности - но моя память достаточно бедна, проверьте до этого в зависимости от этого).