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

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

Основная архитектура

std::vector реализует динамический массив, основанный на трёх указателях:

template<typename T>
class vector {
private:
    T* _begin;        // Указатель на начало выделенной памяти
    T* _end;          // Указатель на конец используемых элементов
    T* _capacity_end; // Указатель на конец выделенной памяти
};

_begin — указатель на первый элемент в выделенной памяти

_end — указатель сразу после последнего элемента (size() = _end - _begin)

_capacity_end — указатель сразу после выделенной памяти (capacity() = _capacity_end - _begin)

Хранение в памяти

Элементы хранятся в смежном блоке памяти в heap в порядке их добавления. Это отличает vector от linked list и обеспечивает:

• O(1) доступ к элементу по индексу
• Cache-friendly поведение (пространственная локальность)
• Минимальные издержки на хранение (без overhead на указатели)

vector<int> v = {1, 2, 3};
// Память: [1][2][3][???]...
//          ^               ^
//       _begin        _capacity_end
//              ^
//            _end

Динамическое расширение

Когда size() == capacity(), происходит реаллокация:

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

vector<int> v;
v.reserve(2);     // Выделит память на 2 элемента
v.push_back(1);   // size=1, capacity=2
v.push_back(2);   // size=2, capacity=2
v.push_back(3);   // Реаллокация! capacity станет 4
                  // Старые элементы переместятся

Важные моменты

Инвалидация итераторов: реаллокация инвалидирует все итераторы и ссылки на элементы

Move семантика: в C++11+ используется std::move для перемещения элементов при реаллокации, что дешевле чем копирование

Гарантии исключений: операции имеют strong guarantee (если исключение, vector остаётся без изменений)

Пустой vector: занимает память только для трёх указателей, не выделяет место под элементы

Практические последствия

Для оптимизации производительности:

• Используй reserve() если заранее знаешь размер
• Избегай бесконечного цикла с push_back на больших данных
• Помни о реаллокации при работе с итераторами
• Для очень частых изменений рассмотри std::deque или std::list

Сравнение с другими контейнерами

std::deque: похож, но с двойной индирекцией, поддерживает O(1) push_back и push_front

std::array: фиксированный размер, хранится на stack (если локальная переменная)

std::list: связный список, O(1) вставка/удаление, но O(n) доступ по индексу