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

1️⃣ Как кратко ответить

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

2️⃣ Подробное объяснение темы

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

Зачем нужна реаллокация

Реаллокация необходима, чтобы vector мог динамически увеличивать свой размер по мере добавления новых элементов. Поскольку vector хранит элементы в непрерывном блоке памяти, когда текущий блок памяти заполняется, требуется выделить новый, более крупный блок, чтобы вместить дополнительные элементы.

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

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

2. Копирование элементов: Все существующие элементы копируются из старого блока памяти в новый. Это может быть затратной операцией, особенно если элементы имеют сложные конструкторы копирования.

3. Освобождение старого блока памяти: После успешного копирования всех элементов старый блок памяти освобождается.

4. Обновление указателей и метаданных: Указатели и метаданные vector обновляются, чтобы указывать на новый блок памяти и его новую емкость.

Пример кода

#include <iostream>
#include <vector>
​
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 << "Added element " << i << ", capacity: " << vec.capacity() << std::endl;
    }
​
    return 0;
}

Объяснение кода

• std::vector<int> vec; — создается пустой вектор vec для хранения элементов типа int.
• vec.capacity() — возвращает текущую емкость вектора, то есть количество элементов, которые он может хранить без необходимости реаллокации.
• Цикл for добавляет 10 элементов в вектор. При каждом добавлении элемента вызывается push_back, который добавляет элемент в конец вектора.
• vec.capacity() внутри цикла показывает, как изменяется емкость вектора. При добавлении элементов емкость увеличивается, когда текущая емкость исчерпана, что свидетельствует о произошедшей реаллокации.

Применение и важные моменты

• Эффективность: Реаллокация может быть дорогой операцией, так как требует копирования всех элементов. Поэтому vector старается минимизировать количество реаллокаций, увеличивая емкость в два раза.
• Итераторы: После реаллокации все существующие итераторы, указатели и ссылки на элементы вектора становятся недействительными.
• Ручное управление емкостью: Для оптимизации можно использовать методы reserve и shrink_to_fit. reserve позволяет заранее выделить память для определенного количества элементов, чтобы избежать частых реаллокаций. shrink_to_fit уменьшает емкость до текущего размера, освобождая неиспользуемую память.

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