Коротко и по делу.
1) Почему в примере указатель может стать недействителен
- std::vector хранит элементы в одном непрерывном буфере. При вставке, если текущая вместимость (capacity) недостаточна, контейнер выделяет новый буфер побольше и копирует/перемещает элементы — это называется реаллокация. После реаллокации все указатели, ссылки и итераторы на элементы векторa становятся недействительными.
- Если реаллокации НЕ происходит (вместимость достаточна), то существующие указатели/ссылки/итераторы остаются действительными (за исключением итератора end()).
Применяя к вашему коду:
- v.push_back(1); int *p = &v[0]; v.push_back(2);
— p станет недействителен только если второй push_back вызвал реаллокацию (т.е. если до него было $\text{size}=\text{capacity}$). Если вместимость была достаточна, p останется валидным.
2) Правила инвалидации для распространённых контейнеров (кратко)
- std::vector, std::string: реаллокация — инвалидирует все указатели/ссылки/итераторы. Вставка/удаление в середине — инвалидирует итераторы/ссылки начиная с места вставки/удаления и дальше.
- std::deque: правила сложнее (внутренний "map" блоков). Вставка/удаление в середине обычно инвалидирует итераторы; операции на концах могут не инвалидировать ссылки на существующие элементы в большинстве реализаций, но итераторы — часто инвалидируются. Для точного поведения смотрите cppreference.
- std::list, std::forward_list: вставка/удаление не инвалидируют указатели/ссылки/итераторы на другие элементы; только удаление конкретного элемента инвалидирует итератор/ссылку на этот элемент.
- Ассоциативные (std::set/std::map): вставка не инвалидирует итераторы/ссылки; удаление инвалидирует только итераторы на удалённые элементы.
- Неупорядоченные (std::unordered_map/set и др.): реhash (автоматический при вставках) инвалидирует все итераторы/ссылки; вставка без реhash — обычно не инвалидирует. Используйте reserve, чтобы избежать реhash.
- Замечание: vector — специальная оптимизация, поведение ссылок/итераторов отличается.
3) Практические приёмы для безопасного кода
- Предотвратить реаллокации: заранее выделяйте память: v.reserve($n$). Тогда указатели на элементы будут валидны при push_back до тех пор, пока size $\le$ reserved capacity.
Пример: v.reserve($100$); int *p = v.data(); /* безопасно, пока не превысите capacity */
- Не храните сырой указатель/итератор через операцию, которая может изменить контейнер; после операций, которые могут инвалидацию, всегда заново получать итератор/указатель.
- Храните индексы вместо указателей, если работаете с vector: индекс остаётся валиден (пока вы не удаляете элементы раньше этого индекса и не хотите переносить порядок).
- Используйте контейнеры со «стабильными ссылками», если нужны постоянные ссылки: std::list или std::forward_list (вставки не рушат ссылки на другие элементы). Для случайного доступа они медленнее.
- Для хранения объектов с «неприкосновенными» адресами — храните умные указатели на динамические объекты: std::vector<std::unique_ptr> — сам вектор может реаллокацию переносить указатели, но указатель на heap-объект остаётся валидным.
- Для unordered_* контейнеров избегайте реhash, вызвав reserve заранее.
- После любых операций, которые могут реаллокацию или инвалидацию, пересоздавайте/обновляйте все кешированные итераторы/указатели/ссылки.
4) Простые шаблоны кода
- Гарантировать валидность указателя на data():
v.reserve($N$);
// теперь v.data() и &v[0] валидны при добавлении элементов до достижения capacity
- Безопасное использование указателя:
int *p = nullptr;
v.push_back(x);
p = &v[0]; // брать указатель только после всех потенциальных реаллокаций
// или после каждой модификации: p = &v[0];
Итого: главный принцип — помнить про реаллокацию; либо предотвращать её (reserve), либо не держать указатели/итераторы дольше, чем гарантировано безопасно, либо использовать контейнеры/приёмы с гарантированной стабильностью ссылок (list, хранение в куче и т.д.).