Правила инвалидации итератора

Эти правила зависят от контейнера. На самом деле, это важные критерии для принятия решения о том, какой контейнер вы используете.

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

SGI предоставляет хорошую документацию по этому вопросу.

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

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

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

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

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

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

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