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

std::vector хранит элементы в непрерывном блоке динамически выделенной памяти, что обеспечивает:

• Константное время доступа по индексу (operator[], .at()) за O(1), так как вычисляется смещение: адрес_начала + индекс * sizeof(Тип).
• Высокую производительность при итерации благодаря предсказуемости для кэша процессора (cache locality).

Механика изменения размера (reallocation): При добавлении элементов (например, push_back) и нехватке текущей емкости (capacity):

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

Критически важное следствие: Итераторы, указатели и ссылки на элементы вектора инвалидируются при реаллокации.

Пример:

std::vector<int> vec = {1, 2, 3}; // capacity может быть 3
int* old_data_ptr = vec.data();

vec.push_back(4); // Может вызвать reallocation, если capacity == size
// old_data_ptr теперь может указывать на освобожденную память (dangling pointer)