При добавлении нового элемента в std::list почему указатель на уже существующий элемент не инвалидируется?
Указатель на существующий элемент std::list сохраняет действительность после вставки других элементов, потому что элементы списка размещаются в отдельных узлах, а вставка изменяет связи между узлами, не перемещая сами объекты. Это гарантируется правилами инвалидирования контейнера: вставка в std::list не делает недействительными указатели, ссылки и итераторы на уже существующие элементы.
Гарантия действует, пока сам элемент не удалён и время жизни контейнера не завершилось.
Контейнеры узлового типа предназначены для ситуаций, где важны стабильные адреса элементов и предсказуемая вставка в середину. В отличие от непрерывного массива, списку не требуется перемещать соседние элементы при добавлении нового узла.
За эту стабильность платят дополнительными выделениями памяти, расходом памяти на связи между узлами и худшей локальностью доступа по сравнению с std::vector.
Если программа сохраняет указатель на элемент контейнера, последующая модификация контейнера может сделать этот указатель недействительным. Разыменование такого указателя приводит к неопределённому поведению, даже если по старому адресу случайно осталось похожее значение.
Для std::vector расширение вместимости может переместить все элементы, поэтому указатели на них становятся недействительными. Для std::list вставка нового элемента не требует перемещения существующих объектов, и этот конкретный риск отсутствует.
std::list хранит каждый элемент в отдельном узле. Узел содержит объект элемента и служебные ссылки на соседние узлы. При вставке создаётся новый узел, после чего обновляются ссылки нескольких соседей; объекты в уже существующих узлах не перемещаются и не пересоздаются.
Поэтому указатель продолжает указывать на тот же объект, а его время жизни не изменяется. Это относится не только к указателям, но также к ссылкам и итераторам на существующие элементы.
Однако стабильность не является бессрочным владением. Указатель становится недействительным после удаления соответствующего элемента через erase, clear или уничтожение контейнера. После удаления время жизни объекта заканчивается, даже если память узла ещё физически не возвращена аллокатору.
Следует различать стабильность адреса и владение. Обычный указатель не удерживает элемент живым и не предотвращает его удаление. Если требуется гарантировать время жизни независимо от контейнера, нужно отдельно спроектировать владение ресурсом, например хранить объект через std::unique_ptr или std::shared_ptr с учётом их семантики.
Сервис хранит заказы в std::list и передаёт другим подсистемам указатели на выбранные заказы. Добавление новых заказов не ломает такие указатели, что удобно для долгоживущих связей между объектами.
Вариант с std::vector обычно обеспечивает лучшую производительность обхода и меньший расход памяти, но расширение контейнера может инвалидировать указатели. Можно заранее вызвать резервирование, однако это лишь снижает вероятность перемещения и не решает проблему при превышении зарезервированной ёмкости.
Выбор std::list оправдан, если действительно нужна стабильность ссылок при вставках и допустимы накладные расходы узлов. Если важнее компактность и быстрый последовательный доступ, лучше выбрать std::vector, а вместо указателей хранить устойчивые идентификаторы элементов и находить элементы по ним.
Нет. Вставка не инвалидирует итераторы, указатели и ссылки на уже существующие элементы. Итератор на новый элемент, конечно, появляется только после получения результата операции вставки.
Это не означает, что любой итератор списка бессрочен: итератор, относящийся к удалённому элементу, использовать нельзя. Также нельзя использовать итераторы после завершения времени жизни самого контейнера.
При перемещении контейнера сами узлы обычно передаются новому контейнеру без перемещения объектов. Стандартные гарантии для перемещающего конструктора сохраняют действительность указателей, ссылок и итераторов на элементы; они начинают обозначать элементы нового контейнера.
Перемещающее присваивание требует большей осторожности: его результат зависит, в частности, от свойств аллокаторов, а элементы контейнера-получателя могут быть уничтожены. Поэтому долгожившие указатели нельзя безопасно оценивать только по названию операции — нужно учитывать конкретную операцию и требования стандарта к аллокатору.
erase завершает время жизни объекта элемента. После этого старый указатель больше не обозначает живой объект требуемого типа, поэтому его разыменование недопустимо независимо от того, сохранились ли байты в памяти.
Аллокатор может позднее переиспользовать тот же участок под другой объект. Внешне адрес останется тем же, но это уже другой объект, а старый указатель не превращается автоматически в корректную ссылку на него. Безопасный код должен удалить или заменить указатель одновременно с удалением элемента.