Будут ли валидны сохранённые итераторы после добавления большого количества элементов в std::vector

Что проверяют

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

Как отвечать

Ответ зависит от ёмкости, поэтому фразу «добавили много элементов» стоит сразу перевести на язык size() и capacity().

• перераспределение: если после вставки size() превышает capacity(), вектор выделяет новый блок, переносит туда элементы и освобождает старый. Недействительными становятся все итераторы, указатели и ссылки на элементы, включая end() и результат data();
• без перераспределения: push_back и emplace_back портят только end(), а insert в середину портит итераторы начиная с точки вставки. Всё, что левее, остаётся валидным;
• рост ёмкости: геометрический, множитель стандартом не задан. В libstdc++ и libc++ он равен 2, в MSVC 1,5. При большом числе вставок перераспределение практически гарантировано;
• перенос элементов: при росте вектор перемещает элементы, только если конструктор перемещения помечен noexcept, иначе копирует ради строгой гарантии безопасности исключений.

Как защититься: вызвать reserve(n) заранее, тогда до превышения n перераспределений не будет и итераторы проживут. Хранить индексы вместо итераторов. Если нужна стабильность адресов при росте, выбрать другой контейнер: у std::list итераторы переживают любые вставки, а у std::deque вставка в начало или конец портит итераторы, но не ссылки на элементы.

Где спотыкаются

Думают, что недействительный итератор бросит исключение или предсказуемо вернёт мусор. Это неопределённое поведение: код может месяцами работать и упасть на другом компиляторе. Ловят такое AddressSanitizer и отладочные режимы вроде _GLIBCXX_DEBUG.

Вызывают push_back внутри цикла по тому же вектору, в том числе в range-based for. Скрытые begin() и end() цикла инвалидируются на первом же перераспределении.

Забывают, что reserve() сам перераспределяет память, если запрошено больше текущей ёмкости, так что итераторы, полученные до этого вызова, тоже становятся недействительными.