Как std::vector хранит элементы

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

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

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

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

Структура хранения

1. Непрерывная память: Элементы std::vector хранятся в непрерывном блоке памяти. Это означает, что если у вас есть вектор из n элементов, то они расположены последовательно в памяти, как в обычном массиве. Это позволяет эффективно использовать кэш процессора и обеспечивает быстрый доступ к элементам по индексу.

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

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

Пример кода

#include <iostream>
#include <vector>
​
int main() {
    std::vector<int> numbers; // Создаем пустой вектор для хранения целых чисел
​
    numbers.push_back(1); // Добавляем элемент 1 в вектор
    numbers.push_back(2); // Добавляем элемент 2 в вектор
    numbers.push_back(3); // Добавляем элемент 3 в вектор
​
    // Выводим элементы вектора
    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << numbers[i] << " "; // Доступ к элементам по индексу
    }
    std::cout << std::endl;
​
    return 0;
}

• std::vector<int> numbers; — создается пустой вектор для хранения целых чисел.
• numbers.push_back(1); — добавляет элемент 1 в конец вектора. Если емкость вектора недостаточна, выделяется новый блок памяти.
• for (size_t i = 0; i < numbers.size(); ++i) — цикл для доступа к элементам вектора по индексу.
• std::cout << numbers[i] << " "; — выводит каждый элемент вектора. Доступ по индексу осуществляется за постоянное время O(1).

Применение

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