Tables

Summary

Much data forms not a row but a grid: the grades of a course by student and by test, a board, a matrix. This lesson presents the table, the two-dimensional structure, in its two C++ forms: the vector of vectors, whose size is decided at run time, and the array of arrays, whose size is known at compile time. Then come the traversals by rows and by columns; the transpose and the matrix product, of cubic cost; the neighbors of a cell, which force us to take care of the edges; and the table stored in a single vector with the index i * columns + j, which is how memory sees it.

Learning objectives

Represent a table as std::vector<std::vector<T>> or as an std::array of std::array, and choose between the two according to whether or not the size is known at compile time.
Traverse a table by rows and by columns, and compute the totals and the means of each row and of each column.
Implement table operations (the transpose, the matrix product, the count of the neighbors of a cell) making sure that no index goes beyond the edges.
Represent a table in a flat vector with the index i * columns + j, and explain with an example the correspondence between a cell and its position.

Rows and columns

A table of $m$ rows and $n$ columns is a collection of $m \cdot n$ data items of the same type, each designated by two indices: that of its row, $i$ , with $0 \leq i < m$ , and that of its column, $j$ , with $0 \leq j < n$ . Mathematics calls it a matrix and writes $a_{ij}$ ; the course Algebra and Geometry II studies matrices and their operations, and this lesson writes some of them as programs. The order of the indices admits no exceptions: first the row, then the column. Confusing them is the most frequent error with tables, and the compiler cannot warn about it, because both indices are of the same type.

The lesson Vectors presented the variable-size sequence. If this is so, a table is a sequence of rows, and each row is in turn a sequence: a vector whose elements are vectors, std::vector<std::vector<int>>.

C++ program

#include <print>#include <vector>int main(){    std::vector<std::vector<int>> table{{1, 2, 3}, {4, 5, 6}};    std::println("{}", table);    std::println("Rows {}, columns {}", table.size(), table[0].size());    std::println("Row 1: {}; row 1, column 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);}

Output

[[1, 2, 3], [4, 5, 6]]Rows 2, columns 3Row 1: [4, 5, 6]; row 1, column 2: 6   1  20   3   4   5   6[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

Line 6 writes the table as a list of rows, each between its braces, and range formatting prints it the same way, with square brackets. table.size() is the number of rows, and table[0].size(), the length of the first one, which in a well-formed table is the number of columns. table[1] is the whole of row 1, a std::vector<int>, and table[1][2], element 2 of that row: the double index is not a new operation but two successive accesses; the first chooses the row and the second, within it, the column. Lines 11 to 16 write the table as a grid with two nested range-based for loops; the row is taken by const reference so as not to copy it at each iteration. Line 17 creates a 3 by 4 table filled with zeros: with parentheses, as in the lesson Vectors, it asks for 3 copies of a row of four zeros.

ExampleTraversing by rows and by columns

A 3 by 4 table, traversed row by row (i in the outer loop) and then column by column (the loops swapped). Each cell shows the order in which it is visited.

Proof

The table, with the row indices on the left and the column indices on top.
By rows: with $i = 0$ , the inner loop traverses $j = 0, 1, 2, 3$ .
With $i = 1$ , the inner loop starts again at $j = 0$ .
With $i = 2$ : the table has been traversed the way a text is read, line after line.
By columns: with $j = 0$ , the inner loop traverses $i = 0, 1, 2$ .
With $j = 1$ , the second column.
With $j = 2$ .
With $j = 3$ . Each cell has once again been visited exactly once: swapping the loops does not change what is visited, but when.

Rows of different lengths

Nothing forces the rows of a vector of vectors to have the same length: each one is an independent vector. Sometimes that is what is wanted, as in Pascal’s triangle; but in a table, rectangular by definition, a shorter row is an error in the data, and the program that uses table[0].size() as the number of columns reads beyond it. A table that comes from outside must therefore be checked.

C++ program

#include <print>#include <vector>// Precondition: none.// Postcondition: returns true if table has at least one row and all its// rows have the length of the first one.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));}

Output

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

The function excludes the table without rows, in which table[0] does not exist. The functions of this lesson that read table[0].size() require a rectangular, non-empty table in their precondition, and isRectangular makes it possible to ensure it.

The array of arrays

When the dimensions are known at compile time (a chessboard, a magic square), the table can be an std::array of std::array: std::array<std::array<int, 3>, 3> is read from the inside out, “3 rows of 3 integers”. The magic square of order 3, whose rows, columns and diagonals add up to 15, serves as an example.

C++ program

#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("Center {}, {} bytes", magic[1][1], sizeof(magic));}

Output

[[2, 7, 6], [9, 5, 1], [4, 3, 8]]Center 5, 36 bytes

There are three braces at each end. std::array has a single member, a C array, so that the outer brace is that of std::array, the second that of this inner array, and only the third that of each row. With two braces, the first row is taken as the initializer of the inner array, and the second one no longer has anything to initialize.

C++ program

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

Compiler error messages

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: the list {4, 5, 6} is left over. The flat list, {1, 2, 3, 4, 5, 6}, also compiles and fills the rows in order, but it hides the shape of the table; the course writes the three braces.

The 36 bytes of the sizeof are those of nine 4-byte int values (the usual size, which the standard does not guarantee), with nothing else: the array of arrays stores the rows one after another in a single block. The vector of vectors, by contrast, requests one block per row, in addition to the one for the rows, and those blocks need not be contiguous. The choice therefore follows the rule of the lessons Arrays and Vectors.

If both dimensions are known at compile time, the array of arrays: a single block, the rectangular shape guaranteed by the type and the possibility of constexpr.
If either of them is known only at run time, the vector of vectors, with the obligation to check that the rows have the same length, or the flat vector of the last section.

Tables

Summary

Learning objectives

Tables

Rows and columns

Rows of different lengths

The array of arrays

Your question about this lesson

Questions about this lesson