Что такое недействительность итератора?

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

Почему это происходит? С чем это трудно?

Ответ 1

Итераторы - прославленные указатели. Недействительность Iterator очень похожа на недействительность указателя; это означает, что он внезапно указывает на нежелательные данные.

Потому что это очень естественно, но неправильно делать такие вещи:

for(iterator it = map.begin(); it != map.end(); ++it) {
    map.erase(it->first);
    // whoops, now map has been restructured and iterator 
    // still thinks itself is healthy
}

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

Вы должны быть в режиме повышенной готовности, когда выполняете итерацию по структуре данных и сами изменяете структуру, а не просто объекты, содержащиеся в них. В этот момент вы, вероятно, должны перейти к документации и проверить, была ли операция незаконной.

Ответ 2

Недействительность Iterator - это то, что происходит, когда тип итератора (объект, поддерживающий операторы ++ и *) неправильно отражает состояние объекта, который он итерирует. Например:

int *my_array = new int[15];
int *my_iterator = &my_array[2];

delete[] my_array;

std::for_each(my_iterator, my_iterator + 5, ...); // invalid

Это приводит к поведению undefined, потому что память, на которую он указывает, была восстановлена ОС.

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

Ответ 3

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

Вставка в контейнер (в любом месте)
Удаление элемент из контейнера
Любая операция, которая изменяет ключ (в AssociativeContainer)
Любая операция, которая изменяет порядок элементов в сортированном контейнере.
Более сложная операция состоящий из одного или более из указанных выше (например, расщепления контейнера на два).

(От: http://c2.com/cgi/wiki?IteratorInvalidationProblem)

Концепция на самом деле довольно проста, но побочные эффекты могут быть весьма раздражающими. Я бы добавил, что эта проблема влияет не только на C/С++, но и на другие языки низкого или среднего уровня. (В некоторых случаях, даже если они не позволяют прямое распределение кучи)