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

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

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

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

Ответы

Ответ 1

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

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

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

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

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

Ответ 2

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

Ответ 3

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