Что происходит при добавлении в vector элемента сверх изначального capacity?

Что происходит при добавлении в vector элемента сверх изначального capacity?

Краткий ответ

Когда добавляешь элемент в vector и размер превышает текущий capacity:

1. Выделяется новый, больший буфер (обычно в 1.5x или 2x раза больше)
2. Все существующие элементы копируются в новый буфер (или перемещаются, если доступен move конструктор)
3. Старый буфер освобождается
4. Новый элемент добавляется в новый буфер
5. Все итераторы и ссылки на старый буфер становятся невалидными

Процесс с примером

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    
    std::cout << "Начальный capacity: " << v.capacity() << "\n";
    
    for (int i = 0; i < 10; i++) {
        int old_capacity = v.capacity();
        v.push_back(i);
        
        if (v.capacity() > old_capacity) {
            std::cout << "Переаллокация! Размер: " << v.size() 
                      << ", Новый capacity: " << v.capacity() << "\n";
        }
    }
    
    return 0;
}

// Вывод (обычно на системах с gcc/clang):
// Начальный capacity: 0
// Переаллокация! Размер: 1, Новый capacity: 1
// Переаллокация! Размер: 2, Новый capacity: 2
// Переаллокация! Размер: 3, Новый capacity: 4
// Переаллокация! Размер: 5, Новый capacity: 8
// Переаллокация! Размер: 9, Новый capacity: 16

Стратегия роста буфера

Разные реализации выбирают разные стратегии:

// Strategy 1: Goldmine ratio (1.5x) — libstdc++ (GCC)
// Новый capacity = old capacity * 1.5

// Strategy 2: Doubling (2x) — MSVC
// Новый capacity = old capacity * 2

// Strategy 3: Golden ratio φ ≈ 1.618 — некоторые реализации
// Новый capacity = old capacity * φ

Почему не просто +1? Потому что это привело бы к O(n) аллокациям при построении вектора размером n.

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

std::vector<int> v = {1, 2, 3};
auto it = v.begin();

// Используем итератор
std::cout << *it << "\n";  // OK: 1

v.push_back(4);  // Если произойдёт переаллокация...

// Теперь *it указывает на удалённую память!
std::cout << *it << "\n";  // UB!

Проблема 2: Производительность

std::vector<std::string> v;

// Плохо: много переаллокаций
for (const auto& s : large_list) {
    v.push_back(s);  // Копирует + возможные переаллокации
}

// Хорошо: предварительное выделение
std::vector<std::string> v;
v.reserve(large_list.size());
for (const auto& s : large_list) {
    v.push_back(s);  // Без переаллокаций
}

Проблема 3: Стоимость копирования объектов

class HeavyObject {
    std::vector<int> data;  // Много памяти
public:
    HeavyObject() {
        data.resize(1000000);
    }
};

std::vector<HeavyObject> v;
for (int i = 0; i < 1000; i++) {
    v.push_back(HeavyObject());  // Копирует весь объект с его вектором!
}

Решение: используй move семантику:

std::vector<HeavyObject> v;
for (int i = 0; i < 1000; i++) {
    v.push_back(std::move(HeavyObject()));  // Перемещает, не копирует
}

// Или используй emplace_back:
for (int i = 0; i < 1000; i++) {
    v.emplace_back();  // Создаёт объект прямо на месте
}

Оптимизация: Reserve vs Resize

// reserve(n) — выделяет память, но size остаётся 0
std::vector<int> v1;
v1.reserve(1000);
std::cout << v1.size() << "\n";   // 0
std::cout << v1.capacity() << "\n"; // >= 1000

// resize(n) — выделяет память и инициализирует n элементов
std::vector<int> v2;
v2.resize(1000);
std::cout << v2.size() << "\n";     // 1000
std::cout << v2.capacity() << "\n"; // >= 1000

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

Move vs Copy при переаллокации

class MoveableObject {
    int* data;
public:
    // Move конструктор — просто копирует указатель
    MoveableObject(MoveableObject&& other) noexcept 
        : data(other.data) {
        other.data = nullptr;
    }
    
    // Copy конструктор — копирует данные
    MoveableObject(const MoveableObject& other) {
        data = new int(*other.data);
    }
};

std::vector<MoveableObject> v;
// Если в объектах есть move конструктор —
// переаллокация будет быстрой (просто копирование указателей)
// Без move — копирование всех данных = медленно!

Выводы

• Переаллокация копирует ВСЕ элементы в новый буфер
• Стратегия роста обычно 1.5x или 2x для амортизированной O(1) вставки
• Reserve заранее если знаешь размер
• Используй move для тяжёлых объектов
• Храни в vector легкие объекты или указатели на тяжёлые данные
• Итераторы инвалидируются при переаллокации