Вектор

vector — массив переменной длины, лежащий в памяти одним куском. Из этого следует почти всё остальное: обращение по индексу за константу, дружба с кешем и дороговизна вставки в середину.

Почему push_back дешёвый

Когда место кончается, вектор выделяет вдвое больше памяти и переносит туда всё содержимое. Одна такая операция стоит $O(n)$ — казалось бы, дорого.

Но происходит это редко. На $n$ добавлений приходится $n/2 + n/4 + \ldots < n$ перенесённых элементов, то есть в среднем на одно добавление — константа. Это называется амортизированной стоимостью, и её не надо путать со «средним случаем»: здесь нет никаких предположений о данных, оценка выполняется всегда.

Если размер известен заранее, переносов можно избежать вовсе:

vector<int> a;
a.reserve(n);      // выделить память под n элементов, размер пока 0
for (int i = 0; i < n; i++) a.push_back(i);

resize, assign, clear

Три метода, которые путают.

vector<int> a = {1, 2, 3};
a.resize(5, 2);    // {1, 2, 3, 2, 2} — старое сохранилось, новое заполнено двойками
a.assign(5, 2);    // {2, 2, 2, 2, 2} — старое выброшено целиком

resize меняет длину: обрезает лишнее или дописывает недостающее указанным значением. Старые элементы не трогает. assign заменяет содержимое целиком.

Отсюда правило: resize — когда надо изменить длину и сохранить данные, assign — когда надо заново заполнить одинаковыми значениями.

clear() удаляет все элементы, размер становится нулём.

Память при этом не возвращается

Ни clear, ни resize вниз не уменьшают capacity — объём выделенной памяти. Вектор из миллиона элементов после clear() продолжает держать место под миллион.

Обычно это не важно и даже полезно: следующий рост обойдётся без выделения. Но если векторов много и они большие, память кончится там, где казалось, что она освобождена.

Освободить по-настоящему можно так:

a.clear();
a.shrink_to_fit();          // просьба, а не приказ, но обычно работает
vector<int>().swap(a);      // надёжнее: подменяем пустым вектором

front и back

a.front()    // то же, что a[0]
a.back()     // то же, что a[a.size() - 1]
a.pop_back() // удалить последний

Пишется короче и читается лучше, особенно a.back() вместо a[a.size() - 1]. Обе функции на пустом векторе — неопределённое поведение, а не исключение.

Передача в функцию

Самая частая ошибка новичка в C++:

void solve(vector<int> a) { sort(a.begin(), a.end()); }   // копия!
void solve(vector<int>& a) { sort(a.begin(), a.end()); }  // так

В первом варианте функция получает копию: сортирует её и выбрасывает, а вызывающий код не видит изменений. Плюс копирование стоит $O(n)$ на каждый вызов, что в рекурсии превращается в катастрофу.

Если менять не нужно — const vector<int>& a: тоже без копии, но с гарантией, что функция ничего не испортит.

Двумерный вектор

vector<vector<int>> g(n, vector<int>(m, 0));   // n строк по m нулей

Строки лежат в памяти не подряд — это $n$ отдельных кусков. Для больших таблиц это заметно медленнее одномерного массива с ручным индексом i * m + j, потому что кеш работает хуже. На таблицах вроде $5000 \times 5000$ разница бывает кратной.