контейнеры и память — устройство и практикаcontainers and memory — internals and practice
Три указателя (begin, end, end_of_storage) — это весь std::vector. Всё остальное — геометрический рост capacity, амортизированная сложность push_back и то, почему процессор обожает непрерывную память — следствия этой простой структуры.Three pointers (begin, end, end_of_storage) — that's the entirety of std::vector. Everything else — geometric capacity growth, push_back's amortized complexity, and why the CPU loves contiguous memory — follows from this simple structure.
Типичная реализация std::vector<T> — три указателя: начало данных, конец используемых данных (size), конец выделенной памяти (capacity). Сам объект vector занимает 24 байта на 64-битной системе (3×8), независимо от количества хранимых элементов — сами элементы всегда живут в отдельном блоке кучи.A typical std::vector<T> implementation is three pointers: start of data, end of used data (size), end of allocated memory (capacity). The vector object itself occupies 24 bytes on a 64-bit system (3×8), regardless of how many elements it holds — the elements themselves always live in a separate heap block.
// упрощённо то, чем является std::vector внутри// simplified — what std::vector is internally
template<typename T>
class SimpleVector {
T* data_ = nullptr; // begin// begin
std::size_t size_ = 0; // сколько элементов сконструировано// how many elements are constructed
std::size_t capacity_ = 0; // сколько памяти реально выделено// how much memory is actually allocated
};
static_assert(sizeof(SimpleVector<int>) == 3 * sizeof(void*));size() — количество реально сконструированных объектов; capacity() — сколько влезет без новой аллокации. size() <= capacity() — инвариант, который держится всегда. Разница capacity() - size() — это память, уже выделенная, но пока не занятая — цена, которую платят за амортизированный O(1) push_back.size() is how many objects are actually constructed; capacity() is how many fit without a new allocation. size() <= capacity() is an invariant that always holds. The difference capacity() - size() is memory already allocated but not yet occupied — the price paid for amortized O(1) push_back.
Когда push_back вызывается при size() == capacity(): выделяется новый блок побольше (обычно ×1.5 или ×2 от текущей capacity — конкретный множитель не специфицирован стандартом и различается между libstdc++ (×2) и libc++ (×1.5)), каждый существующий элемент перемещается (move-конструктором, если он `noexcept`, иначе копируется) в новый блок, старые объекты разрушаются, старая память освобождается.When push_back is called at size() == capacity(): a bigger new block is allocated (typically ×1.5 or ×2 the current capacity — the exact factor isn't specified by the standard and differs between libstdc++ (×2) and libc++ (×1.5)), every existing element is moved (via the move constructor, if it's `noexcept`, otherwise copied) into the new block, the old objects are destroyed, and the old memory is freed.
Реаллокация — это O(n) операция (перемещение всех элементов), но происходит она всё реже по мере роста, поэтому суммарная стоимость n вставок остаётся O(n), а амортизированная стоимость одной вставки — O(1).Reallocation is an O(n) operation (moving every element), but it happens increasingly rarely as the vector grows, so the total cost of n insertions stays O(n) and the amortized cost per insertion is O(1).
Геометрический (а не линейный, +1 или +constant) рост — ключевое решение: при линейном росте каждая вставка вызывала бы реаллокацию, давая O(n) на вставку и O(n²) суммарно на n вставок. Множитель роста — компромисс между тратой памяти впустую (больший множитель) и частотой реаллокаций (меньший множитель).Geometric (not linear, +1 or +constant) growth is the key decision: with linear growth, every insertion would trigger a reallocation, giving O(n) per insertion and O(n²) total for n insertions. The growth factor is a trade-off between wasted memory (larger factor) and reallocation frequency (smaller factor).
Элементы vector лежат в памяти подряд, без единого байта отступа между ними (кроме выравнивания типа). Когда процессор читает v[0], кэш-линия (обычно 64 байта) подтягивает с ним и несколько следующих элементов — последующие обращения к v[1], v[2]... часто оказываются кэш-хитом без обращения к основной памяти.A vector's elements sit in memory back-to-back, with no padding between them beyond the type's own alignment. When the CPU reads v[0], the cache line (typically 64 bytes) pulls in several following elements along with it — subsequent accesses to v[1], v[2]... often turn out to be cache hits with no trip to main memory.
std::list с тем же количеством элементов раскидывает узлы по куче в порядке аллокации, а не логическом порядке — обход списка почти гарантированно даёт кэш-промах на каждом узле. На практике линейный поиск по vector<int> часто быстрее, чем по list<int>, даже там, где асимптотика формально одинакова (оба O(n)) — разница в константе, продиктованной кэшем, может быть 10-кратной и больше.A std::list with the same element count scatters its nodes across the heap in allocation order, not logical order — traversing the list almost guarantees a cache miss on every node. In practice, a linear search over vector<int> is often faster than over list<int>, even where the asymptotics are formally identical (both O(n)) — the cache-driven constant factor can be 10x or more.
Это же свойство объясняет правило "используй vector по умолчанию" — даже операции, где list формально выигрывает по Big-O (вставка в середину — O(1) против O(n) у vector), на практике часто проигрывают на реалистичных размерах, потому что стоимость промахов кэша при последующих обходах перевешивает выигрыш от отсутствия сдвига элементов.This same property explains the "use vector by default" rule of thumb — even operations where list formally wins on Big-O (middle insertion is O(1) vs. vector's O(n)) often lose in practice at realistic sizes, because the cost of cache misses during subsequent traversal outweighs the gain from not shifting elements.
reserve(n) меняет только capacity, не создавая элементов — size() не меняется, v[i] для новых индексов — UB. resize(n) реально конструирует (или уничтожает) элементы, меняя size(). Частая ошибка — вызвать reserve и затем писать в v[i] вместо push_back.reserve(n) only changes capacity without constructing elements — size() doesn't change, and v[i] for new indices is UB. resize(n) actually constructs (or destroys) elements, changing size(). A common mistake is calling reserve and then writing to v[i] instead of push_back.
После множества pop_back capacity не уменьшается автоматически — vector не отдаёт память назад сам. shrink_to_fit() — non-binding запрос к реализации, который может (и часто действительно) уменьшить capacity до size, но стандарт не обязывает это делать.After many pop_back calls, capacity doesn't shrink automatically — a vector never gives memory back on its own. shrink_to_fit() is a non-binding request to the implementation, which may (and often does) reduce capacity to size, but the standard doesn't require it to.
emplace_back конструирует объект прямо в памяти вектора (in-place), избегая временного объекта — но если push_back вызывает реаллокацию, ВСЕ существующие элементы всё равно перемещаются, независимо от того, был ли новый элемент сконструирован in-place или скопирован. Выигрыш emplace_back — только в самом новом элементе, не в остальных.emplace_back constructs the object directly in the vector's memory (in-place), avoiding a temporary — but if the push triggers a reallocation, ALL existing elements are still moved regardless of whether the new element was constructed in-place or copied. emplace_back's win applies only to the new element itself, not the rest.