Каковы обычные правила для недействительности Iterator при работе над классами контейнеров STL (Vector, Dequeue, list, map, multimap, set, multiset). Можно ли классифицировать и подытожить некоторые общие правила/рекомендации, которые должен знать программист C++ STL во время работы с контейнерами и их итераторами?Правила для Iterator Invalidation
ответ
Эти правила специфичны для контейнеров. Фактически, это важные критерии для определения того, какой контейнер вы используете.
Например, итераторы до std::vector
могут быть признаны недействительными, когда объект вставлен (зависит от того, где объект вставлен и происходит перераспределение), и они становятся недействительными, когда объект удаляется перед итератором. std::list
не имеет этой проблемы. Вставка и удаление объектов (за исключением объекта, на который указывает итератор) не отменяет итератора.
SGI обеспечивает хорошее documentation на этом.
Хорошо, может, пожалуйста, добавить некоторые из них. –
Предпочитаете стандарт для документов SGI (которые предназначены для старого оригинального STL, а не для стандартных библиотек). Я использую документы SGI для быстрой справки, но если вы хотите быть уверенными, то всегда есть шанс, что стандарт изменил что-то. –
@Steve: Вы правы, только некоторые из нас не имеют доступного стандарта. –
Правила недействительности основаны на самом фундаментальном Структуры данных и алгоритмы, используемые для реализации этих контейнеров. Если вы не планируете изучать основы, то вам нужно будет запомнить документацию итератора наизусть.
Стандарт 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.
Примечание: в то время как элементы в deque не перемещаются из-за push_back(), push_front(), emplace_back() или emplace_front(), эти операции могут по-прежнему отменять итераторы. – Nevin
Цитата: «В общем, простые мутации, которые не меняют« форму »контейнера (например, заменяют третий элемент массива новым значением), не создают проблем». http://c2.com/cgi/wiki?IteratorInvalidationProblem – rwong
[Правила недействительности итератора] (http://kera.name/articles/2011/06/iterator-invalidation-rules/) –
@Tomalak Geret'kal: Это хороший ! Могу ли я предложить добавить его в качестве записи 'C++ faq'. –