Векторы

Последовательность, которая растёт

Создание и заполнение вектора

Урок Массивы представил индексированную последовательность: элементы одного типа, один за другим, пронумерованные с нуля. Её современная форма фиксированного размера, std::array<int, 7>, несёт размер в типе, и компилятор должен его знать. Однако тот, кто пишет программу, вычисляющую средний балл группы, не знает, сколько в ней будет студентов. Отсюда следует потребность в последовательности, размер которой есть ещё одно данное, меняющееся во время выполнения: это вектор, std::vector<T>, из заголовочного файла <vector>, где T есть тип элементов.

#include <print>#include <vector>​int main(){    std::vector<int> squares{};    std::println("В начале: размер {}, пуст: {}", squares.size(), squares.empty());    for (int k{1}; k <= 5; ++k) {        squares.push_back(k * k);    }    std::println("{}", squares);    std::println("Размер {}, первый {}, последний {}", squares.size(), squares[0], squares.back());    squares[1] = 0;    squares.pop_back();    std::println("{}", squares);}

В начале: размер 0, пуст: true[1, 4, 9, 16, 25]Размер 5, первый 1, последний 25[1, 0, 9, 16]

Строка 6 создаёт пустой вектор целых чисел: в отличие от массива, не нужно объявлять, сколько в нём будет элементов. size() возвращает, сколько их есть, а empty() сообщает, нет ли ни одного. Цикл в строках с 8 по 10 добавляет пять квадратов с помощью push_back, которая помещает свой аргумент в конец и увеличивает размер на единицу. Строка 11 выводит весь вектор в формате диапазонов, который предыдущий урок использовал с массивами. Доступ по индексу прежний, а squares.back() сокращает squares[squares.size() - 1]. Строка 13 присваивает значение существующему элементу, а строка 14 удаляет последний с помощью pop_back. Операции этого урока, вкратце, таковы.

• v.push_back(x) добавляет x в конец; v.pop_back() удаляет последний (для пустого вектора это неопределённое поведение).
• v.size() есть размер, типа std::size_t, беззнакового целого для размеров, который представил урок Массивы; v.empty() равносильно v.size() == 0.
• v[i] и v.at(i) дают элемент с индексом i, который должен удовлетворять i < v.size(); v.front() и v.back() дают первый и последний и требуют, чтобы вектор не был пуст.
• v.resize(n) оставляет в векторе n элементов: удаляет лишние в конце или добавляет в конец элементы, инициализированные как пустыми фигурными скобками (нулями, для чисел).

Как и у массивов, v[i] не гарантирует никакого контроля, а v.at(i) гарантирует: при индексе 7 и пяти элементах он останавливает программу с сообщением vector::_M_range_check: __n (which is 7) >= this->size() (which is 5), где названы индекс и размер. Механизм, вызывающий эту остановку, исключение, изучается в курсе «Программирование на C++ II».

Фигурные и круглые скобки

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

#include <print>#include <vector>​int main(){    const std::vector<int> a{5};    const std::vector<int> b(5);    const std::vector<int> c{3, 7};    const std::vector<int> d(3, 7);    std::println("{} {} {} {}", a, b, c, d);}

[5] [0, 0, 0, 0, 0] [3, 7] [7, 7, 7]

a содержит один элемент, 5; b, пять нулей; c, 3 и 7; d, три семёрки. Список в фигурных скобках говорит, таким образом, «вот элементы», а круглые скобки оставлены для того, чтобы запросить n копий одного значения, как вектор счётчиков, равных нулю.

Последний элемент пустого вектора

Пустой вектор есть законный случай (вход без данных, фильтр, который никто не проходит), и каждую формулу с его размером нужно пересматривать для этого случая; самая коварная из них v.size() - 1. Поскольку v.size() есть беззнаковое целое, вычитание 1, когда оно равно 0, даёт не $-1$, а «заворачивается», как было показано в уроке Целые числа и их представление, до наибольшего значения std::size_t.

#include <cstddef>#include <print>#include <vector>​int main(){    const std::vector<int> values{};    std::println("values.size() - 1 = {}", values.size() - 1);    // Ошибочная граница: для пустого вектора условие истинно.    for (std::size_t i{0}; i <= values.size() - 1; ++i) {        std::println("{}", values[i]);    }}

values.size() - 1 = 18446744073709551615/usr/include/c++/15/bits/stl_vector.h:1282: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::const_reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) const [with _Tp = int; _Alloc = std::allocator<int>; const_reference = const int&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.

Первая строка вывода есть $18\,446\,744\,073\,709\,551\,615$, то есть $2^{64} - 1$, наибольшее значение std::size_t на этой платформе. Отсюда следует, что условие цикла, 0 <= 18446744073709551615, истинно и что первая итерация читает values[0] у вектора, в котором нет элемента 0: неопределённое поведение. То, что наблюдается, зависит от опций, как и у массивов: при компиляции без оптимизации библиотека GCC 15 контролирует индекс в operator[] и останавливает программу утверждением, которое гласит __n < this->size(); с оптимизацией этот контроль исчезает, и цикл, который не останавливается вовремя, пытается читать там, где нет ни одного элемента (подтверждено в Linux с -O2: поскольку у пустого вектора нет блока памяти, программа завершается ошибкой сегментации, без сообщения, объясняющего причину). Исправление состоит в том, чтобы записать границу без вычитания, i < values.size(), что для пустого вектора ложно с самого начала; а там, где вычитание кажется необходимым, сначала спросить values.empty().