std::vector в C++: как устроен и как использовать эффективно

Почему vector — контейнер по умолчанию

В C++ действует простое правило: если не знаете, какой контейнер взять — берите std::vector. Это динамический массив с последовательным хранением элементов в памяти. Последовательное расположение даёт дружелюбность к кэшу процессора — обход vector почти всегда быстрее обхода списка или дерева, даже когда теоретическая сложность одинакова.

#include <vector>
#include <iostream>

int main() {
    std::vector<int> v = {10, 20, 30};
    v.push_back(40);
    for (int x : v) std::cout << x << ' ';  // 10 20 30 40
}

size, capacity и рост

У вектора две характеристики размера. size() — сколько элементов лежит сейчас. capacity() — сколько поместится без перевыделения памяти. Когда push_back упирается в capacity, вектор выделяет новый буфер большего размера (обычно в 1.5–2 раза), копирует или перемещает туда все элементы и освобождает старый.

std::vector<int> v;
std::cout << v.size() << ' ' << v.capacity() << "\n";  // 0 0
v.push_back(1);
std::cout << v.size() << ' ' << v.capacity() << "\n";  // 1 1
for (int i = 0; i < 100; ++i) v.push_back(i);          // capacity прыгает

Перевыделение — дорогая операция, особенно для тяжёлых объектов. Если итоговый размер хотя бы примерно известен, всегда делайте reserve:

std::vector<std::string> lines;
lines.reserve(10000);  // одна аллокация вместо ~14 перевыделений

При этом reserve не меняет size — вектор по-прежнему «пустой» для обхода, просто память зарезервирована. А resize меняет именно размер: добавленные элементы инициализируются значением по умолчанию.

v.reserve(100);  // size=0, capacity≥100 — для будущих push_back
v.resize(100);   // size=100 — элементы уже существуют, v[0..99] валидны

push_back против emplace_back

push_back принимает готовый объект и копирует/перемещает его внутрь. emplace_back конструирует объект прямо в памяти вектора — без промежуточного экземпляра:

struct Point { int x, y; Point(int x, int y) : x(x), y(y) {} };

std::vector<Point> points;
points.push_back(Point(1, 2));  // создали временный, переместили
points.emplace_back(3, 4);      // сконструировали на месте — быстрее и короче

Для простых типов (int, double) разницы нет, для объектов с конструкторами — emplace_back предпочтительнее.

Инвалидация итераторов — главная ловушка

Когда вектор перевыделяет память, все указатели, итераторы и ссылки на его элементы становятся висячими. Это источник самых коварных багов:

std::vector<int> v = {1, 2, 3};
int& ref = v[0];
auto it = v.begin();

v.push_back(4);   // возможно перевыделение!
// ref и it теперь могут указывать на освобождённую память
// std::cout << ref;  // UB — неопределённое поведение

Правила простые:

• push_back/emplace_back без свободной capacity — инвалидирует всё.
• Любая вставка/удаление в середину — инвалидирует итераторы после точки вставки.
• reserve, resize, clear — тоже могут инвалидировать.

Если нужно держать ссылку на элемент через модификации — храните индекс, а не ссылку.

Удаление: erase-remove идиома и её наследники

Удаление из середины вектора стоит O(n) — хвост сдвигается. Классический способ удалить все значения:

// C++03..17
v.erase(std::remove(v.begin(), v.end(), 42), v.end());

// C++20 — короче
std::erase(v, 42);
std::erase_if(v, [](int x) { return x < 0; });

Если порядок элементов не важен, удаление за O(1) делается через swap с последним:

std::swap(v[i], v.back());
v.pop_back();

Доступ к элементам: [] против at()

v[i] — без проверки границ, максимально быстро, выход за пределы — UB. v.at(i) — кидает std::out_of_range. В горячих циклах используют [], при работе с пользовательскими индексами — at(). Для обхода лучше всего range-for или итераторы.

Сортировка и поиск

std::sort(v.begin(), v.end());                    // по возрастанию
std::sort(v.begin(), v.end(), std::greater<>());  // по убыванию

// бинарный поиск — только в отсортированном!
bool found = std::binary_search(v.begin(), v.end(), key);

auto it = std::find(v.begin(), v.end(), 7);        // линейный поиск
auto mn  = std::min_element(v.begin(), v.end());   // итератор на минимум

Полезные мелочи

• v.front(), v.back() — первый/последний элемент (пустой вектор — UB).
• v.empty() вместо v.size() == 0 — читаемее.
• v.data() — сырой указатель, нужен для C-API.
• v.shrink_to_fit() — неблокирующая просьба ужать capacity до size.
• std::vector<bool> — специализация-ловушка: это битовый массив, v[i] возвращает прокси, а не bool&. В реальном коде лучше std::vector<char> или std::deque<bool>.

Итог

std::vector решает 90 % задач хранения коллекций. Держите в голове три вещи: reserve перед массовыми вставками, инвалидация итераторов при росте, emplace_back для объектов. С этим вектор будет работать предсказуемо и быстро.

vector и память: что внутри

Вектор — это три указателя: начало буфера, конец использованных данных, конец выделенной памяти. sizeof(vector<T>) — 24 байта на 64-битной системе независимо от содержимого: вся тяжесть в куче. Поэтому передача вектора по значению — это копия всей кучи, а по const& — бесплатно:

void process(const std::vector<int>& v);   // чтение без копии
void consume(std::vector<int> v);          // забираем владение — вызывающий решит, копия или move

2D-данные: почему vector<vector> — плохо

vector<vector<int>> — массив массивов с разрозненными аллокациями: каждый ряд в своей куче, плохая локальность кэша. Для матриц берите плоский вектор с доступом data[y * width + x]:

struct Matrix {
    int w, h;
    std::vector<double> d;
    double& at(int x, int y) { return d[y * w + x]; }
};

Один буфер, одна аллокация, кэш-дружественный обход.

Мини-проект: кольцевой буфер

Полезное упражнение — ring buffer на векторе фиксированной ёмкости: push перезаписывает самый старый элемент, индексы через % capacity. Такой буфер — основа логирования и потоковой обработки в embedded, где нельзя бесконечно растить контейнер.

Шпаргалка сложности операций

• v[i], v.front(), v.back() — O(1).
• push_back, pop_back — O(1) амортизированно.
• insert/erase в середине — O(n): хвост сдвигается.
• find, count — O(n); binary_search после sort — O(log n).
• reserve, resize — O(n) при перевыделении.

Чего НЕ делать с vector

• Не используйте vector<bool> для серьёзной работы — это битовый массив с прокси вместо ссылок.
• Не держите ссылки/указатели на элементы через push_back без reserve.
• Не используйте v.erase(it) в цикле — инвалидация; идиома erase-remove или erase_if.
• Не рассчитывайте, что clear() освободит память — capacity остаётся; для освобождения v.shrink_to_fit() или swap с пустым.