9.3.6. Некоторые операции с контейнерами делают итераторы недопустимыми

Функции, добавляющие и удаляющие элементы из контейнера, могут сделать некорректными указатели, ссылки или итераторы на его элементы. Некорректными считаются те указатели, ссылки и итераторы, которые больше не указывают на элемент. Использование некорректного указателя, ссылки или итератора является серьезной ошибкой, последствия которой, вероятно, будут схожи с использованием неинициализированного указателя (см. раздел 2.3.2, стр. 89).

После операции добавления элементов в контейнер возможно следующее.

• Итераторы, указатели и ссылки на элементы вектора или строки становятся недопустимыми после повторного резервирования пространства контейнера. Если повторного резервирования не было, ссылки на элементы перед позицией вставки остаются допустимыми, а на элементы после позиции вставки — нет.

• Итераторы, указатели и ссылки на элементы двухсторонней очереди становятся недопустимыми после добавления элементов в любую позицию кроме начала или конца. При добавлении в начало или в конец недопустимыми становятся только итераторы, а ссылки и указатели на существующие элементы — нет.

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

• У контейнеров list и forward_list все остальные итераторы, ссылки и указатели (включая итераторы после конца и перед началом) остаются допустимыми.

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

• У контейнеров vector и string все остальные итераторы, ссылки и указатели на элементы перед позицией удаления остаются допустимыми. При удалении элементов итератор после конца всегда оказывается недопустимым.

Использование недопустимого итератора, указателя или ссылки является серьезной ошибкой, которая проявится во время выполнения программы.

Совет. Контроль итераторов

При использовании итератора (или ссылки, или указателя на элемент контейнера) имеет смысл минимизировать ту часть программы, где итератор обязан оставаться допустимым.

Поскольку код, добавляющий или удаляющий элементы из контейнера, может сделать итераторы недопустимыми, необходимо позаботиться о переустановке итераторов соответствующим образом после каждой операции, которая изменяет контейнер. Это особенно важно для контейнеров vector, string и deque.

Создание циклов, которые изменяют контейнер

Циклы, добавляющие или удаляющие элементы из контейнеров vector, string или deque, должны учитывать тот факт, что итераторы, ссылки и указатели могут стать недопустимыми. Программа должна гарантировать, что итератор, ссылка или указатель обновляется на каждом цикле. Если цикл использует функцию insert() или erase(), обновить итератор довольно просто. Они возвращают итераторы, которые можно использовать для переустановки итератора:

// бесполезный цикл, удаляющий четные элементы и вставляющий дубликаты

// нечетных

vector<int> vi = {0,1,2,3,4,5,6,7,8,9};

auto iter = vi.begin(); // поскольку vi изменяется, используется

                        // функция begin(), а не cbegin()

while (iter != vi.end()) {

 if (*iter % 2) {

  iter = vi.insert(iter, *iter); // дублирует текущий элемент

  iter +=2;                      // переместить через элемент

 } else

  iter = vi.erase(iter); // удалить четные элементы

 // не перемещать итератор; iter обозначает элемент после

 // удаленного

}

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

После вызова функции erase() никакой необходимости в приращении итератора нет, поскольку возвращенный ею итератор обозначает следующий элемент в последовательности. После вызова функции insert() итератор увеличивается на два. Помните, функция insert() осуществляет вставку перед указанной позицией и возвращает итератор на вставленный элемент. Таким образом, после вызова функции insert() итератор iter обозначает элемент (недавно добавленный) перед обрабатываемым. Приращение на два осуществляется для того, чтобы перескочить через добавленный и только что обработанный элементы. Это перемещает итератор на следующий необработанный элемент.

Не храните итератор, возвращенный функцией end()

При добавлении или удалении элементов в контейнер vector или string либо при добавлении или удалении элементов в любую, кроме первой, позицию контейнера deque возвращенный функцией end() итератор всегда будет недопустимым. Потому циклы, которые добавляют или удаляют элементы, всегда должны вызывать функцию end(), а не использовать хранимую копию. Частично поэтому стандартные библиотеки С++ реализуют обычно функцию end() так, чтобы она выполнялась очень быстро.

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

// ошибка: поведение этого цикла непредсказуемо

auto begin = v.begin(),

 end = v.end(); // плохая идея хранить значение итератора end

while (begin != end) {

 // некоторые действия

 // вставить новое значение и переприсвоить итератор begin, который

 // в противном случае окажется недопустимым

 ++begin; // переместить begin, поскольку вставка необходима после

          // этого элемента

 begin = v.insert(begin, 42); // вставить новое значение

 ++begin; // переместить begin за только что добавленный элемент

}

Поведение этого кода непредсказуемо. На многих реализациях получится бесконечный цикл. Проблема в том, что возвращенное функцией end() значение хранится в локальной переменной end. В теле цикла добавляется элемент. Добавление элемента делает итератор, хранимый в переменной end, недопустимым. Этот итератор не указывает ни на какой элемент в контейнере v, ни на следующий после его конца.

Не кешируйте возвращаемый функцией end() итератор в циклах, которые вставляют или удаляют элементы в контейнере deque, string или vector.

Вместо того чтобы хранить итератор end, его следует повторно вычислять после каждой вставки:

// существенно безопасный: повторно вычислять end после каждого

// добавления/удаления элементов

while (begin != v.end()) {

 // некоторые действия

 ++begin; // переместить begin, поскольку вставка необходима после

          // этого элемента

 begin = v.insert(begin, 42); // вставить новое значение

 ++begin; // переместить begin за только что добавленный элемент

}

Упражнения раздела 9.3.6

Упражнение 9.31. Программа из пункта «Создание циклов, которые изменяют контейнер», удаляющая четные и дублирующая нечетные элементы, не будет работать с контейнером list или forward_list. Почему? Переделайте программу так, чтобы она работала и с этими типами тоже.

Упражнение 9.32. Будет ли допустим в указанной выше программе следующий вызов функции insert()? Если нет, то почему?

iter = vi.insert(iter, *iter++);

Упражнение 9.33. Что будет, если в последнем примере этого раздела не присваивать переменной begin результат вызова функции insert()? Напишите программу без этого присвоения, чтобы убедиться в правильности своего предположения.

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

iter = vi.begin();

while (iter != vi.end())

 if (*iter % 2)

  iter = vi.insert(iter, *iter);

 ++iter;