Краткий ответ

Если вставка вызвала перераспределение памяти, все ранее полученные итераторы становятся недействительными. Если память не перераспределялась, действительными остаются только итераторы, указывающие на элементы до позиции вставки; итераторы от позиции вставки и дальше, включая прежний итератор конца, недействительны.

Исторический контекст

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

Для std::vector приоритетом являются непрерывное хранение и быстрый доступ по индексу. Перемещение элементов внутри такого массива или выделение нового массива неизбежно влияет на адреса элементов и, следовательно, на связанные с ними итераторы.

Постановка проблемы

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

Использование недействительного итератора приводит к неопределённому поведению. Ошибка может проявиться не сразу: адрес иногда выглядит доступным, но уже не относится к нужному элементу или вообще указывает на освобождённую память.

Подробное решение

У std::vector действуют два основных случая:

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

Проверка только факта изменения размера недостаточна. Нужно учитывать ёмкость: если после вставки размер не превышает текущую capacity(), перераспределение обычно не требуется, но сдвиг элементов всё равно инвалидирует итераторы от позиции вставки.

#include <vector>

int main() {
    std::vector<int> values{1, 2, 3};
    values.reserve(4);

    auto before = values.begin();
    auto at = values.begin() + 1;
    values.insert(values.begin() + 1, 9);

    (void)*before; // допустимо: итератор указывает до позиции вставки
    // at недействителен и разыменовывать его нельзя
}

Вызов reserve заранее оставляет место для вставки, поэтому в примере перераспределения не происходит. Однако это не сохраняет итератор at: элемент в этой позиции и последующие были сдвинуты.

Если итератор должен использоваться после вставки, его следует получить заново, например начиная от нового begin() или от результата insert. Нельзя полагаться на численное значение старого итератора или на то, что память физически осталась по прежнему адресу.

Ситуация из практики

Сервис обрабатывает большой вектор задач и вставляет приоритетную задачу в середину. Одновременно другой код хранит итератор на текущую задачу для последующего обновления.

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

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

Что кандидаты часто упускают

1. Достаточно ли вызвать reserve, чтобы все итераторы пережили вставку?

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

2. Что произойдёт с итератором на первый элемент при вставке в середину без перераспределения?

Он остаётся действительным, потому что элементы до позиции вставки не перемещаются. Это правило относится именно к итератору, указывающему на элемент до точки вставки; прежний end() всё равно недействителен, поскольку изменился конец диапазона.

3. Отличаются ли правила для ссылок и указателей на элементы?

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