Что происходит, когда мы вставляем элемент в вектор?

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

Понимание внутреннего механизма работы вектора критично для написания производительного кода. Вставка элемента в std::vector — это не просто добавление в конец, а сложный процесс управления памятью и данными.

Вставка в конец (push_back)

Сценарий 1: Есть свободное место в буфере

std::vector<int> v;
v.reserve(10);  // capacity = 10, size = 0
v.push_back(42); // size = 1, capacity остаётся 10

• Вектор проверяет, есть ли свободное место (size < capacity)
• Если есть, копирует элемент в конец массива: *(buffer + size) = 42
• Увеличивает size на 1
• Сложность: O(1)

Сценарий 2: Буфер полон (size == capacity)

std::vector<int> v;
v.push_back(1); // capacity = 1, size = 1
v.push_back(2); // Нужна переаллокация!

Здесь происходит:

1. Выделение новой памяти — новый буфер большего размера (обычно multiplier × 1.5 или 2)
2. Копирование старых элементов — перемещение всех существующих элементов в новый буфер
3. Удаление старого буфера — освобождение старой памяти (если нужны деструкторы)
4. Копирование нового элемента — добавление нового элемента

// Визуально:
// До:   [1] (capacity=1, size=1)
// После: [1, 2, _, _, _] (capacity=4-5, size=2)

Сложность: O(n) в худшем случае, но амортизированная сложность O(1).

Вставка в середину (insert)

Вставка элемента не в конец намного дороже:

std::vector<int> v = {1, 3, 4}; // [1, 3, 4]
v.insert(v.begin() + 1, 2);     // [1, 2, 3, 4]

Что происходит:

1. Поиск позиции — проверяется, где вставлять
2. Сдвиг элементов — все элементы после позиции сдвигаются на одно место вправо
3. Копирование нового элемента — вставляется новый элемент
4. Переаллокация (если нужна) — если нет место, выполняется вся процедура переаллокации

// Визуально процесс сдвига:
// До:     [1, 3, 4]
// Сдвиг:  [1, 3, 4, _]
// После:  [1, 2, 3, 4]

Сложность: O(n) — нужно сдвинуть все элементы после позиции вставки.

Детали управления памятью

Множитель роста capacity

Разные компиляторы используют разные множители:

• GCC/libstdc++: обычно 1.5x
• MSVC: обычно 1.5x
• Clang/libc++: обычно 2x

std::vector<int> v;
for (int i = 0; i < 5; i++) {
    std::cout << "size: " << v.size() 
              << ", capacity: " << v.capacity() << std::endl;
    v.push_back(i);
}
// Выведет примерно:
// size: 0, capacity: 0
// size: 1, capacity: 1 (или больше)
// size: 2, capacity: 2 (или 3)
// ...

Конструкторы и деструкторы

При переаллокации для типов с нетривиальными конструкторами:

struct Heavy {
    Heavy(int val) : value(val) { 
        std::cout << "Construct " << val << std::endl; 
    }
    Heavy(const Heavy& other) : value(other.value) { 
        std::cout << "Copy " << value << std::endl; 
    }
    ~Heavy() { 
        std::cout << "Destruct " << value << std::endl; 
    }
    int value;
};

std::vector<Heavy> v;
v.push_back(Heavy(1)); // Construct, Copy, Destruct, Destruct

Можно оптимизировать через emplace_back:

v.emplace_back(1);  // Construct один раз

Move-семантика (C++11+)

Модерный C++ использует move вместо copy при переаллокации:

std::vector<std::string> v;
v.push_back("hello"); // move, не copy (если перемещение возможно)

Это критично для performance:

std::vector<std::vector<int>> matrix;
matrix.push_back(std::vector<int>{1, 2, 3});
// Move semantics избегает копирования всего вектора

Оптимизации

reserve() предварительное выделение

std::vector<int> v;
v.reserve(1000); // Выделить место сразу
for (int i = 0; i < 1000; i++) {
    v.push_back(i); // Все вставки O(1), без переаллокаций
}

shrink_to_fit() освобождение лишней памяти

std::vector<int> v(1000);
v.resize(100);
v.shrink_to_fit(); // Уменьшить capacity с 1000 до 100

Рекомендации для production

1. Используй push_back/emplace_back вместо insert в контексте конца
2. Предварительно выделяй память через reserve(), если знаешь примерный размер
3. Избегай частых вставок в середину — это O(n) операция
4. Используй emplace_back вместо push_back для сложных объектов
5. Профилируй переаллокации — они могут быть узким местом