Ответ
std::vector хранит элементы в непрерывном блоке динамически выделенной памяти, что обеспечивает:
- Константное время доступа по индексу (
operator[],.at()) за O(1), так как вычисляется смещение:адрес_начала + индекс * sizeof(Тип). - Высокую производительность при итерации благодаря предсказуемости для кэша процессора (cache locality).
Механика изменения размера (reallocation):
При добавлении элементов (например, push_back) и нехватке текущей емкости (capacity):
- Выделяется новый, больший блок памяти (обычно в 1.5 или 2 раза больше).
- Существующие элементы копируются или перемещаются (если
noexceptперемещающий конструктор) в новый блок. - Старый блок памяти освобождается.
Критически важное следствие: Итераторы, указатели и ссылки на элементы вектора инвалидируются при реаллокации.
Пример:
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)Ответ 18+ 🔞
А, ну ты глянь-ка, какой вопрос подкинули! Про std::vector, да? Ну это ж классика, ёпта, основа основ, как хлеб с маслом. Сейчас разжуём, что к чему.
Представь себе, что std::vector — это такой дисциплинированный грузовичок. Он не разбрасывает свои коробки с данными где попало по всему складу памяти. Нет, он их аккуратно, в одну линию, в непрерывный блок памяти укладывает. Динамически выделенной, само собой. И из-за этой его педантичности вытекают две офигенные штуки.
Первое: доступ по индексу — это просто праздник какой-то, O(1). Почему? Да потому что адрес любого элемента считается за одну арифметическую операцию: взял адрес начала, прибавил индекс * размер_одного_элемента и — оп! — ты уже там. Никаких поисков, прыжков по ссылкам. Прямо как в массиве, только размер меняется. operator[] или .at() — разница лишь в том, что второй ещё и по голове настучит, если индекс кривой.
Второе: итерация по нему — просто песня для процессора. Потому что данные лежат плотно, друг за дружкой. Кэш процессора это обожает, предсказывает заранее, что грузить, и всё летает. Cache locality, мать его. Производительность — огонь.
А теперь про самое интересное — про то, как он растёт. Механика, блядь, изменения размера, она же реаллокация.
Вот смотри. У тебя есть вектор. У него есть size() — сколько элементов реально внутри, и capacity() — сколько он может вместить, не переезжая. Пока size < capacity, push_back просто кладёт элемент в конец на свободное место. Всё спокойно.
Но! Как только ты пытаешься запихнуть элемент, а свободного места нет (size == capacity), начинается ёперный театр:
- Вектор идёт в операционную систему и выпрашивает новый, больший кусок памяти. Обычно в 1.5 или 2 раза больше старого. Жадничает, сука.
- Потом он начинает перетаскивать все свои старые элементы из старого дома в новый. Если у типа есть
noexceptперемещающий конструктор, он их аккуратно перемещает (быстро). Если нет — копирует (медленнее). - И, наконец, старый блок памяти он без сожаления освобождает. Сносит, блядь, старую хату.
И вот тут — внимание, самый важный момент, который все хуярят! — наступает инвалидация. После реаллокации всё, что было связано со старым адресом памяти, превращается в тыкву.
Итераторы, указатели и ссылки на элементы вектора — все они накрываются медным тазом. Они начинают указывать в освобождённую память, в никуда. Использовать их — это прямой билет в undefined behavior, в мир, где демоны вылезают из носа.
Пример, чтобы вообще всё стало ясно:
std::vector<int> vec = {1, 2, 3}; // Допустим, capacity == 3. Всё тесно.
int* old_data_ptr = vec.data(); // Ловим указатель на старый массив данных.
vec.push_back(4); // А тут бац! Места нет. Вызывается reallocation.
// Вуаля! old_data_ptr теперь — висячий указатель (dangling pointer).
// Он указывает на память, которую уже отжали обратно у программы.
// Трогать его — всё равно что совать палец в розетку.