std::vector

Размер std::array входит в его тип: std::array<int, 5> хранит ровно пять чисел. Но часто количество значений становится известно только во время работы программы. Например, программа, которая отбирает числа по условию, заранее не знает, сколько их наберётся.

Представьте лоток для яиц с ячейками в один ряд. Яйца кладут подряд, с первой ячейки, а последние ячейки могут пока пустовать. Когда свободных ячеек не осталось, берут лоток побольше и перекладывают в него все яйца. Так же устроен std::vector:

#include <iostream>
#include <vector>

int main() {
    std::vector<int> found;
    for (int i = 1; i <= 10; ++i) {
        if (i % 3 == 0) {
            found.push_back(i);
        }
    }
    std::cout << found.size() << '\n';  // 3
    for (int x : found) {
        std::cout << x << ' ';  // 3 6 9
    }
}

Контейнер — объект, который хранит набор элементов одного типа. std::vector<int> — контейнер чисел типа int: тип элементов пишут в угловых скобках. Новый вектор пуст. В примере работают две функции:

• push_back добавляет элемент в конец;
• size() возвращает число элементов.

Цикл по диапазону обходит элементы в порядке добавления.

Доступ по индексу

Вектор можно сразу заполнить значениями в фигурных скобках. Как и у массива, v[0] — первый элемент, а v[v.size() - 1] — последний. Если индекс выходит за пределы вектора, чтение или запись по нему дают неопределённое поведение.

std::vector<int> v{4, 8, 15};
for (std::size_t i = 0; i < v.size(); ++i) {
    v[i] = v[i] * 2;
}
std::cout << v[0] << ' ' << v[2] << '\n';  // 8 30

Ещё несколько функций вектора:

• size() возвращает std::size_t, как и у строки, поэтому счётчик для индексов объявляют того же типа;
• v.empty() возвращает true, если в векторе нет элементов;
• v.back() возвращает последний элемент, а v.pop_back() удаляет его;
• элементом вектора может быть и другой вектор: std::vector<std::vector<int>> t{{1, 2}, {3, 4}}; хранит таблицу по строкам, t[1] — вторая строка, а t[1][0] — число 3.

Размер и ёмкость

Элементы вектора лежат в памяти подряд, одним блоком, как яйца в лотке. В блоке может остаться свободное место. Сколько его, стандарт не задаёт: у вектора v{1, 2, 3} его может не быть совсем.

Ёмкость — это сколько элементов поместится в блок, то есть число ячеек лотка. Её возвращает capacity(), а size() считает только занятые ячейки. Пока size() меньше capacity(), push_back кладёт элемент в свободное место.

Когда места нет, push_back выделяет блок побольше, переносит в него элементы и освобождает старый. Это перевыделение памяти. Насколько вырастет ёмкость, решает стандартная библиотека: libc++, с которой курс собирает программы, удваивает её, а другие библиотеки могут растить иначе. Поэтому не пишите код, который рассчитывает на конкретное значение.

Добавляйте элементы кнопкой и следите, когда вектор переезжает в новый блок: номер и адрес блока меняются, а старый блок освобождается.

Здесь лоток перестаёт быть точной картинкой. Старый лоток остаётся на столе, а старый блок вектора освобождается, и всё, что указывало на его элементы, указывает уже в пустоту.

reserve и resize

Если число элементов известно заранее, место можно выделить сразу. После reserve(n) ёмкость не меньше n, но элементов не прибавляется: size() остаётся прежним. Если n не больше текущей ёмкости, вызов ничего не делает.

resize(n) меняет сам размер: недостающие элементы получают значение 0, как int x{}, а лишние удаляются.

std::vector<int> a;
a.reserve(100);
std::cout << a.size() << ' ' << (a.capacity() >= 100) << '\n';  // 0 1
std::vector<int> b{7};
b.resize(3);
std::cout << b.size() << ' ' << b[0] << ' ' << b[2] << '\n';  // 3 7 0

Частая ошибка

После reserve элементы записывают по индексу:

std::vector<int> v;
v.reserve(3);
v[0] = 7;  // ✗

Вызов reserve выделил память, но элементов не создал: v.size() по-прежнему равен 0, и v[0] обращается за пределы вектора. Это неопределённое поведение, хотя программа компилируется без предупреждений. Добавляйте элементы через push_back или задайте размер через resize(3).

Главное

• std::vector хранит элементы подряд, а их число может меняться во время работы программы.
• size() — сколько элементов в векторе, capacity() — сколько поместится в блок без перевыделения памяти.
• Когда блок полон, push_back переносит элементы в новый, больший блок.
• reserve выделяет место без элементов, а resize создаёт или удаляет элементы.