Коротко — суть и последствия
- Проблема: при вызове `vector.push_back` при нехватке текущей capacity происходит реаллокация внутреннего буфера: выделяется новый блок, элементы копируются/переносятся, старый блок освобождается. После такой реаллокации все итераторы, указатели и ссылки на элементы вектора становятся висячими (dangling) — дальнейшее их разыменование даёт неопределённое поведение.
- Если же реаллокации не было (достаточная capacity), то `push_back` не инвалидирует существующие итераторы и ссылки, но всегда меняет `end()`.
Пример проявления (необнаружимая ошибка)
```cpp
#include #include
int main() {
std::vector v;
v.push_back($1$); // v: {1}
v.push_back($2$); // v: {1, 2}
auto it = v.begin(); // указывает на элемент с индексом $0$ v.push_back($3$); // может вызвать реаллокацию -> it становится висячим
std::cout << *it << std::endl; // неопределённое поведение: может вывести $1$, мусор или упасть
}
```
Почему ошибка часто «необнаружима»: на некоторых реализациях реаллокация может скопировать данные в новый блок, и при первом выводе вы ещё увидите ожидаемое значение; на другой платформе/сборке — мусор или крах. Потому это — UB, а не ловимая ошибка времени выполнения.
Безопасные альтернативы и рекомендации
1) reserve — предотвратить реаллокации заранее
- Вызвать `v.reserve(n)` до серий вставок, чтобы гарантировать отсутствие реаллокации при добавлении до $n$ элементов. Итераторы останутся валидными, пока число элементов ≤ зарезервированной capacity.
- Пример: `v.reserve($100$);` — безопасно добавить до $100$ элементов.
2) Использовать индексы вместо итераторов/указателей
- Храните индекс (`size_t idx`) вместо `iterator`. Индексы остаются корректными при реаллокации (поскольку элементы физически перемещаются, но порядковый номер не меняется), пока не выполняется удаление/вставка в середину, меняющая порядок.
- Доступ: `v[idx]`.
3) Контейнеры со стабильными итераторами (невалидируются при вставке)
- std::list, std::forward_list: вставка/удаление не инвалидирует итераторы на другие элементы (только итератор на удаляемый элемент теряет валидность). Подходят, если нужна стабильность ссылок и итераторов, но операции доступа по индексу стоят дорого.
- Ассоциативные контейнеры (std::map, std::set и т.д.): вставки не инвалидируют существующие итераторы; удаление инвалидирует только удалённые элементы.
- Внимание: std::deque и unordered_* имеют свои правила (deque может инвалидировать итераторы при некоторых перераспределениях внутренной структуры; unordered_* может реhash-ить при вставке и инвалидировать итераторы). Проверяйте cppreference для конкретного контейнера.
4) Пересоздавать/обновлять итераторы после потенциально изменяющих операций
- Не сохраняйте итератор дольше, чем гарантия его валидности; после `push_back` при неопределённости — получить новый итератор (`it = v.begin() + idx`).
5) Использовать специализированные структуры для стабильности ссылок
- boost::stable_vector и т.п. обеспечивают стабильность ссылок/итераторов при вставках (за счёт внутренней организации) — полезно, если нужен контейнер с эффективным случайным доступом и стабильностью ссылок.
Дополнительное замечание: перенос/копирование элементов при реаллокации вызывает вызовы конструкторов/перемещений — это может иметь побочные эффекты для типов с немаковыми семантиками, учитывайте это при проектировании.
Вывод: если вы храните итераторы/указатели на элементы std::vector и выполняете вставки, всегда думайте о возможной реаллокации: используйте `reserve`, индексы или контейнеры с гарантиями стабильности, чтобы избежать UB.