Как осуществляется перевыделение памяти у контейнера std::vector в C++?

При добавлении элементов в std::vector, если его текущая вместимость (capacity()) недостаточна для хранения новых элементов, происходит перевыделение памяти:

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

Этот процесс может быть относительно затратным по времени, особенно при большом количестве элементов, так как включает выделение новой памяти, перемещение/копирование данных и освобождение старой памяти.

Вместимость вектора можно узнать с помощью метода capacity(), а количество элементов - size(). Перевыделение происходит, когда size() становится равным capacity().

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

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec;
    std::cout << "Initial capacity: " << vec.capacity() << std::endl;

    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
        // Каждый раз проверяем вместимость
        std::cout << "After adding " << i << ", size: " << vec.size() << ", capacity: " << vec.capacity() << std::endl;
    }

    return 0;
}

Вывод этой программы покажет, как capacity() увеличивается по мере добавления элементов, демонстрируя точки перевыделения. Точная стратегия увеличения вместимости (на сколькоfactor) зависит от реализации стандартной библиотеки.

Для оптимизации производительности при известном заранее количестве элементов рекомендуется использовать метод reserve(), чтобы заранее выделить необходимый объем памяти и избежать множественных перевыделений.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> vec;
    // Заранее выделяем память для 100 элементов
    vec.reserve(100);
    std::cout << "Capacity after reserve(100): " << vec.capacity() << std::endl; // Будет >= 100

    for (int i = 0; i < 10; ++i) {
        vec.push_back(i);
        // Вместимость не меняется, пока не превысим зарезервированное
        std::cout << "After adding " << i << ", size: " << vec.size() << ", capacity: " << vec.capacity() << std::endl;
    }

    return 0;
}

Использование reserve() может значительно повысить производительность операций вставки, особенно при добавлении большого количества элементов.