Таблицы

Таблицы

Строки и столбцы

Таблица из $m$ строк и $n$ столбцов является коллекцией из $m \cdot n$ данных одного типа, каждое из которых обозначается двумя индексами: индексом своей строки, $i$, где $0 \leq i < m$, и индексом своего столбца, $j$, где $0 \leq j < n$. Математика называет её матрицей и пишет $a_{ij}$; курс «Алгебра и геометрия II» изучает матрицы и действия над ними, а этот урок записывает некоторые из них в виде программ. Порядок индексов не допускает исключений: сначала строка, затем столбец. Путаница между ними является самой частой ошибкой при работе с таблицами, и компилятор не может о ней предупредить, потому что оба индекса имеют один и тот же тип.

Урок Векторы ввёл последовательность переменного размера. Если это так, таблица есть последовательность строк, и каждая строка в свою очередь является последовательностью: вектор, элементы которого являются векторами, std::vector<std::vector<int>>.

#include <print>#include <vector>​int main(){    std::vector<std::vector<int>> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);    std::println("Строк: {}, столбцов: {}", table.size(), table[0].size());    std::println("Строка 1: {}; строка 1, столбец 2: {}", table[1], table[1][2]);    table[0][1] = 20;    for (const std::vector<int>& row : table) {        for (const int value : row) {            std::print("{:>4}", value);        }        std::println("");    }    const std::vector<std::vector<int>> zeros(3, std::vector<int>(4));    std::println("{}", zeros);}

[[1, 2, 3], [4, 5, 6]]Строк: 2, столбцов: 3Строка 1: [4, 5, 6]; строка 1, столбец 2: 6   1  20   3   4   5   6[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Строка 6 программы записывает таблицу как список её строк, каждую в своих фигурных скобках, и форматирование диапазонов выводит её так же, но с квадратными скобками. table.size() есть число строк, а table[0].size() есть длина первой из них, которая в правильно построенной таблице равна числу столбцов. table[1] есть вся строка 1, значение типа std::vector<int>, а table[1][2] есть элемент 2 этой строки: двойной индекс не является новой операцией, он означает два последовательных обращения, первое из которых выбирает строку, а второе, внутри неё, столбец. Строки программы с 11 по 16 выводят таблицу в виде прямоугольной схемы двумя вложенными циклами for по диапазону; строка таблицы берётся по константной ссылке, чтобы не копировать её на каждой итерации. Строка 17 создаёт таблицу 3 на 4, заполненную нулями: круглые скобки, как в уроке Векторы, запрашивают 3 копии строки из четырёх нулей.

Строки разной длины

Ничто не обязывает строки вектора векторов иметь одинаковую длину: каждая из них является независимым вектором. Иногда именно это и нужно, как в треугольнике Паскаля; но в таблице, прямоугольной по определению, более короткая строка есть ошибка в данных, и программа, которая использует table[0].size() как число столбцов, читает за её пределами. Поэтому, получив таблицу извне, нужно удостовериться в её форме.

#include <print>#include <vector>​// Предусловие: нет.// Постусловие: возвращает true, если в table есть хотя бы одна строка и все её// строки имеют длину первой.bool isRectangular(const std::vector<std::vector<int>>& table){    if (table.empty()) {        return false;    }    for (const std::vector<int>& row : table) {        if (row.size() != table[0].size()) {            return false;        }    }    return true;}​int main(){    const std::vector<std::vector<int>> pascal{{1}, {1, 1}, {1, 2, 1}, {1, 3, 3, 1}};    const std::vector<std::vector<int>> grid{{1, 2, 3}, {4, 5, 6}};    std::println("{} {}", pascal, isRectangular(pascal));    std::println("{} {}", grid, isRectangular(grid));}

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]] false[[1, 2, 3], [4, 5, 6]] true

Функция исключает таблицу без строк, в которой table[0] не существует. Функции этого урока, которые читают table[0].size(), требуют в своём предусловии прямоугольную и непустую таблицу, а isRectangular позволяет это обеспечить.

Массив массивов

Когда размеры известны при компиляции (шахматная доска, магический квадрат), таблица может быть массивом std::array из std::array: std::array<std::array<int, 3>, 3> читается изнутри наружу, «3 строки по 3 целых числа». Примером служит магический квадрат порядка 3, все строки, столбцы и диагонали которого дают в сумме 15.

#include <array>#include <print>​int main(){    constexpr std::array<std::array<int, 3>, 3> magic{{        {2, 7, 6},        {9, 5, 1},        {4, 3, 8},    }};    std::println("{}", magic);    std::println("Центр {}, {} байт", magic[1][1], sizeof(magic));}

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]Центр 5, 36 байт

Фигурных скобок по три с каждой стороны. У std::array только один член, массив в стиле C, так что внешняя скобка принадлежит std::array, вторая этому внутреннему массиву, и только третья каждой строке. С двумя скобками первая строка берётся как инициализатор внутреннего массива, и второй строке уже нечего инициализировать.

#include <array>#include <print>​int main(){    const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);}

main.cpp: In function ‘int main()’:main.cpp:6:71: error: too many initializers for ‘const std::array<std::array<int, 3>, 2>’    6 |     const std::array<std::array<int, 3>, 2> table{{1, 2, 3}, {4, 5, 6}};      |                                                                       ^

Too many initializers: лишним оказывается список {4, 5, 6}. Плоский список, {1, 2, 3, 4, 5, 6}, тоже компилируется и заполняет строки по порядку, но скрывает форму таблицы; курс пишет три скобки.

36 байт из sizeof принадлежат девяти значениям int по 4 байта (обычный размер, который стандарт не гарантирует), и ничего больше: массив массивов хранит строки одну за другой в едином блоке. Вектор векторов, напротив, запрашивает по блоку на каждую строку, помимо блока для самих строк, и эти блоки вовсе не обязаны быть смежными. Поэтому выбор следует правилу уроков Массивы и Векторы.

• Если оба размера известны при компиляции, массив массивов: один блок, прямоугольная форма, гарантированная типом, и возможность constexpr.
• Если какой-либо из них известен только при выполнении, вектор векторов, с обязанностью убедиться, что строки имеют одинаковую длину, или плоский вектор из последней части урока.