Что происходит с элементом при реаллокации?

Процесс реаллокации элементов в контейнерах

При реаллокации (перераспределении памяти) контейнера (например, std::vector) происходит следующее:

Основные этапы реаллокации

1. Выделение новой памяти — создаётся новый буфер больших размеров (обычно в 1.5-2 раза больше текущего)
2. Перемещение элементов — все элементы копируются (или перемещаются, если поддерживаются move-семантика) из старого буфера в новый
3. Освобождение старой памяти — деаллокация исходного буфера
4. Обновление внутренних указателей — указатели контейнера теперь указывают на новый буфер

Влияние на итераторы и ссылки

При реаллокации все итераторы, указатели и ссылки становятся невалидными. Это критический момент:

std::vector<int> vec = {1, 2, 3};
int* ptr = &vec[0];  // Указатель на первый элемент
vec.push_back(4);    // Может вызвать реаллокацию!
// ptr теперь "висячий указатель" (dangling pointer) — использовать нельзя!

Оптимизация с reserve()

std::vector<int> vec;
vec.reserve(1000);  // Выделяем память для 1000 элементов
for (int i = 0; i < 1000; ++i) {
    vec.push_back(i);  // Без реаллокаций!
}

Move vs Copy семантика

С C++11 используется move-семантика, что снижает затраты:

struct Heavy {
    std::vector<int> data;  // Дорогой объект
    Heavy(Heavy&&) = default;  // Move конструктор (быстро)
};

std::vector<Heavy> vec;
vec.push_back(Heavy());  // Перемещение, не копирование

Когда происходит реаллокация

• std::vector — при push_back(), insert() если размер превышает capacity
• std::string — при добавлении символов сверх capacity
• std::deque — обычно не реаллоцирует (использует блоки), но может
• std::map, std::set — не реаллоцируют (tree-based)
• std::unordered_map — реаллоцирует при превышении load factor

Практические последствия

1. Производительность — O(n) операция, может быть узким местом
2. Исключения — если при копировании/перемещении выбросится исключение, вектор может остаться в несогласованном состоянии
3. Memory fragmentation — старый буфер может оставить "дыру" в памяти
4. Cache misses — новый буфер может быть в другом месте памяти

Защита от проблем

// 1. Предварительно выделяем память
vec.reserve(needed_size);

// 2. Проверяем capacity перед операциями
if (vec.size() == vec.capacity()) {
    // Скоро будет реаллокация
}

// 3. Используем move-семантику
std::vector<Heavy> result;
result.push_back(std::move(expensive_object));

Понимание реаллокации критично для написания эффективного C++ кода, особенно при работе с контейнерами и управлением памятью.