Как работает реаллокация в vector?

Как работает реаллокация в vector

Проблема: vector растёт

std::vector динамически растет в размере при добавлении элементов. Когда текущее выделенное место заканчивается, вектор переходит на новое, большее место в памяти.

Как это работает

std::vector<int> v;
v.reserve(2);  // Выделить место для 2 элементов

v.push_back(1);  // size=1, capacity=2
v.push_back(2);  // size=2, capacity=2
v.push_back(3);  // size=3, но capacity=2! РЕАЛЛОКАЦИЯ!

Процесс реаллокации

ШАГ 1: Выделить новую память

Когда size() == capacity(), нужна реаллокация:

vector v = {1, 2};
v.push_back(3);
// РЕАЛЛОКАЦИЯ!

// Старая память:
Old: [1][2][???]

// Новая память (обычно в 1.5 или 2 раза больше):
New: [1][2][3][???][???][???][...]  // capacity = 4 или 6

Политика роста:

• GCC/libstdc++: умножает на 1.5
• MSVC: умножает на 1.5
• Clang/libc++: умножает на 1.5 или 2

Обычно в старых реализациях было 2x, теперь чаще 1.5x для экономии памяти.

ШАГ 2: Скопировать или переместить элементы

Все существующие элементы копируются (или перемещаются в C++11+) в новую память:

// C++03 и раньше: копирование
for (int i = 0; i < old_size; i++) {
    new_ptr[i] = old_ptr[i];  // Вызывает copy constructor
}

// C++11+: перемещение (если нет throw в move constructor)
for (int i = 0; i < old_size; i++) {
    new_ptr[i] = std::move(old_ptr[i]);  // Вызывает move constructor
}

Перемещение намного дешевле копирования:

std::string s1 = "Hello";
std::string s2 = s1;           // Copy (дорого)
std::string s3 = std::move(s1); // Move (дёшево)

ШАГ 3: Добавить новый элемент

new_ptr[size] = new_value;
size++;

ШАГ 4: Освободить старую память

delete[] old_ptr;

Пример пошагово

std::vector<int> v;

// 1. Инициализация
// size=0, capacity=0, ptr=nullptr

v.push_back(1);
// Реаллокация! capacity=1
// size=1, capacity=1, ptr=[1]

v.push_back(2);
// Реаллокация! capacity=1*1.5=1 (округлённо 2)
// Скопировать [1] -> новую память
// Добавить 2
// size=2, capacity=2, ptr=[1,2]

v.push_back(3);
// Реаллокация! capacity=2*1.5=3
// Скопировать [1,2] -> новую память
// Добавить 3
// size=3, capacity=3, ptr=[1,2,3]

v.push_back(4);
// Реаллокация! capacity=3*1.5=4 (округлённо)
// size=4, capacity=4, ptr=[1,2,3,4]

v.push_back(5);
// Реаллокация! capacity=4*1.5=6
// size=5, capacity=6, ptr=[1,2,3,4,5,???]

Видишь? Не каждый push_back вызывает реаллокацию, только когда size==capacity.

Проблема: инвалидация итераторов

Реаллокация инвалидирует все итераторы и ссылки:

std::vector<int> v = {1, 2};

int* ptr = &v[0];  // Указатель на первый элемент

v.push_back(3);  // РЕАЛЛОКАЦИЯ!

std::cout << *ptr;  // UNDEFINED BEHAVIOR!
// ptr указывает на старую, уже удалённую память

Правильно:

std::vector<int> v = {1, 2};
v.push_back(3);
int* ptr = &v[0];  // Получить указатель ПОСЛЕ реаллокации
std::cout << *ptr;  // OK

Это почему не нужно хранить указатели на элементы вектора.

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

Если знаешь сколько элементов добавишь, используй reserve():

// ПЛОХО: множественные реаллокации
std::vector<int> v;
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);  // Реаллокация ~20 раз
}

// ХОРОШО: одна реаллокация
std::vector<int> v;
v.reserve(1000000);  // Выделить место заранее
for (int i = 0; i < 1000000; i++) {
    v.push_back(i);  // Нет реаллокаций
}

Это может быть в 100x+ быстрее!

Move semantics и noexcept

Важно что move constructor имеет noexcept:

std::string s1("Hello");

// Если move может выкинуть исключение:
std::vector<std::string> v;
v.push_back(s1);  // Придётся использовать copy

// Если move не может выкинуть исключение:
v.push_back(std::move(s1));  // Безопасно использовать move при реаллокации

Поэтому для контейнеров важно, чтобы move constructor был noexcept.

Стратегии роста

1.5x стратегия:

Оригинальный capacity: 10
После 1-й реаллокации: 15
После 2-й реаллокации: 22
После 3-й реаллокации: 33

Преимущества:

• Меньше памяти тратится впустую
• Логарифмическое количество реаллокаций

2x стратегия:

Оригинальный capacity: 10
После 1-й реаллокации: 20
После 2-й реаллокации: 40
После 3-й реаллокации: 80

Преимущества:

• Проще в реализации
• Всегда степень двойки (хорошо для cache)

Как это реализовано

template<typename T>
class vector {
private:
    T* data;
    size_t size_;      // Текущее количество элементов
    size_t capacity_;  // Выделенное место
    
public:
    void push_back(const T& value) {
        if (size_ == capacity_) {
            // РЕАЛЛОКАЦИЯ
            size_t new_capacity = capacity_ == 0 ? 1 : capacity_ * 1.5;
            T* new_data = new T[new_capacity];
            
            // Переместить элементы
            for (size_t i = 0; i < size_; i++) {
                new_data[i] = std::move(data[i]);
            }
            
            delete[] data;
            data = new_data;
            capacity_ = new_capacity;
        }
        
        // Добавить новый элемент
        data[size_] = value;
        size_++;
    }
};

Производительность

Добавление N элементов в vector:

• Без reserve(): O(N) операций, но много реаллокаций и копирований. Общее время: O(N) (амортизированная сложность)
• С reserve(): O(N) операций, нет реаллокаций. Быстрее в константное число раз

Когда реаллокация дорога

std::vector<std::string> v;  // Большие объекты

// Каждая реаллокация копирует все std::string объекты
// Это дорого, потому что copy constructor для std::string выделяет новую память

// Решение:
v.reserve(1000);
for (int i = 0; i < 1000; i++) {
    v.push_back(std::string("item " + std::to_string(i)));
}

Итого

Реаллокация в vector:

1. Выделить новую память (обычно в 1.5x раза больше)
2. Переместить элементы (используя move если noexcept)
3. Освободить старую память
4. Добавить новый элемент

Оптимизация: используй reserve() если знаешь размер заранее.

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