Как устроен vector изнутри

Вопрос-крючок: «Что выведет этот код и почему capacity меняется скачками, а не плавно?»

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v;
    for (int i = 0; i < 5; i++) {
        v.push_back(i);
        std::cout << "size=" << v.size()
                   << " capacity=" << v.capacity() << std::endl;
    }
}

Вывод:

size=1 capacity=1
size=2 capacity=2
size=3 capacity=4
size=4 capacity=4
size=5 capacity=8

Большинство новичков ждут, что capacity будет расти вместе с size на единицу. На деле она скачет: 1, 2, 4, 8. Это и есть тот самый вопрос, который любят задавать на собеседовании — «почему так, а не по одному?».

Что происходит и почему. vector в C++ — это обёртка над обычным массивом в куче (динамической памяти). У массива есть жёсткое ограничение: его размер нельзя изменить после выделения. Если вы попросите десятое место в массиве на пять ячеек, программа просто вылезет за границы выделенной памяти — это неопределённое поведение, один из самых опасных багов в C++.

Поэтому vector хранит не один размер, а два: size() — сколько элементов реально лежит внутри, и capacity() — сколько места выделено под них с запасом. Пока size() < capacity(), добавление элемента (push_back) — дешёвая операция: просто кладём значение в уже готовую ячейку и увеличиваем счётчик size. Но как только место заканчивается, происходит реаллокация: vector выделяет новый, больший блок памяти (обычно вдвое больше прежнего), копирует туда все старые элементы, удаляет старый блок и только потом добавляет новый элемент.

Как это работает под капотом. Реаллокация — это O(n): нужно скопировать все n элементов на новое место. Если бы vector увеличивал capacity на единицу при каждом push_back, копирование происходило бы на каждой вставке, и суммарная стоимость n вставок превратилась бы в O(n²) — квадратичную сложность вместо линейной. Удвоение решает эту проблему: реаллокации происходят всё реже (после 1, 2, 4, 8, 16 элементов...), и хотя каждая отдельная реаллокация становится дороже, в среднем на весь процесс вставки n элементов уходит O(n) операций. Это называется амортизированной сложностью — по одной вставке дорого предсказать, но в среднем на элемент выходит O(1).

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

Частые ошибки на собеседовании. Путают size() и capacity() — говорят, что вызов v.resize(10) и v.reserve(10) делают одно и то же. Не делают: resize реально создаёт 10 элементов (заполняя их значением по умолчанию), а reserve просто выделяет память под 10 элементов, не создавая их — size остаётся прежним. Ещё одна классическая ошибка — забыть, что после push_back в цикле старые итераторы «протухают», и попытаться использовать сохранённый ранее итератор — это undefined behavior. И третья: думать, что удвоение — это стандарт языка. На самом деле стандарт C++ не фиксирует коэффициент роста, просто требует амортизированную O(1) сложность push_back — конкретные реализации (libstdc++, MSVC) могут расти по-разному (например, в 1.5 раза), но идея та же.

Итоги-шпаргалка. vector — это динамический массив с запасом памяти (capacity ≥ size). Пока есть запас, push_back — O(1). Когда запас кончается — реаллокация: новый блок побольше, копирование всех элементов, O(n) разово, но амортизированно O(1) на вставку. reserve() резервирует память заранее и без лишних копирований, если вы знаете примерный размер данных. После реаллокации все старые указатели и итераторы недействительны.