Правила для Iterator Invalidation

Question

Каковы обычные правила для недействительности Iterator при работе над классами контейнеров STL (Vector, Dequeue, list, map, multimap, set, multiset). Можно ли классифицировать и подытожить некоторые общие правила/рекомендации, которые должен знать программист C++ STL во время работы с контейнерами и их итераторами?

Answer 1

Эти правила специфичны для контейнеров. Фактически, это важные критерии для определения того, какой контейнер вы используете.

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

SGI обеспечивает хорошее documentation на этом.

Answer 2

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

Стандарт C++ определяет поведение iterator таким образом, что позволяет реализовать с помощью простых указателей C. Это не требует, чтобы библиотека фактически использовала указатели; это просто позволяет это сделать.

В основном, итератор становится недействительным, если операция вызывает основной элемент хранения (массив кучи, используемый в vector, узел связанного списка, используемом в list, или узел дерева, используемый в map или set) быть освобождается или перераспределяется в другое место памяти.

A vector обычно реализуется путем выделения массива из динамической памяти (кучи). Чтобы уменьшить количество перераспределений, массив всегда выделяется с некоторой задержкой, т. Е. Изначально неиспользуемого пространства. Когда элементы добавляются к массиву, пространство ожидания уменьшается. Когда все свободное пространство занято, и нужно добавить новый элемент, тогда будет выделен новый массив с большим размером. Это приведет к недействительности всех итераторов, указывающих на старый массив.

Аналогичным образом, когда элемент стирается от vector, это приведет к копированию всех последующих элементов вперед. Итератор, указывающий на сдвинутые элементы, по-прежнему будет ссылаться на один и тот же индекс в массиве, но этот индекс теперь содержит другой элемент. Это также пример недействительности.

Для list, map и set узел дерева или список-узел остается действительным до тех пор, пока содержащийся в нем элемент не будет удален. Обратите внимание, что итератор, указывающий на недействительный узел, не может использоваться ни для чего; даже для увеличения и уменьшения итератора. Это связано с тем, что в реализации связанного списка или дерева итератор зависит от дочерних указателей, которые хранятся в самом узле.

Для обеспечения правильной работы стандарт формулируется более строгим образом, чем при использовании простых структур данных (что, как ни парадоксально, дает больше возможностей библиотечным разработчикам использовать более сложные структуры данных). Например, см. http://c2.com/cgi/wiki?IteratorInvalidationProblem и http://www.threadingbuildingblocks.org/codesamples.php.