C++ Module 5 – Arrays, vectors and aggregate types

2D grids in C++: flat storage and std::mdspan

Store a grid as a vector of vectors or as one flat vector, index it with C++23 std::mdspan and m[r, c], and see why row-by-row loops ran over ten times faster.

Intermediate
25 minutes
Examples run with Clang 21.0.0, GCC 16.2.0 and Python 3.14.8
By MySmartCoPilot

What you will learn

Store a grid in a vector of vectors and in flat storage
Use std::mdspan to index flat storage as a 2D grid
Traverse grids in a cache-friendly order

Before you start

std::vector: the container to reach for first

What you’ll learn · Before you start

What you will learn

Store a grid in a vector of vectors and in flat storage
Use std::mdspan to index flat storage as a 2D grid
Traverse grids in a cache-friendly order

Before you start

std::vector: the container to reach for first

On this page

C++ has no built-in grid type, so a 2D grid, a game board, an image or a matrix, is stored in one of three ways. A vector of vectors, std::vector<std::vector<int>>, is the easiest to write: g[r][c] reads row r, column c. But every row is a separate allocation somewhere on the heap. Flat storage, one std::vector<int> of rows * cols elements with row r starting at index r * cols, keeps the whole grid in one contiguous block, which is the layout C arrays, image formats and maths libraries use. And std::mdspan (C++23) is a view over flat storage that does the index arithmetic for you, so you write m[r, c] and still get one block of memory.

For anything large or speed-sensitive, use flat storage with an mdspan, and visit it row by row: in this lesson’s measurements on an Apple M5 Pro, going down the columns of a large grid instead was more than ten times slower with both compilers, Apple clang and GCC 16. The lesson also covers the comma trap of C++23 subscripts and how to check neighbours without reading outside the grid.

Three ways to store the same grid

The same grid as a vector of vectors and as flat storage

Text description of the diagram

The diagram shows the lesson's 3 x 4 grid, in which the value 10 × row + column is stored at row r, column c.

As a std::vector<std::vector<int>>, the grid takes 4 allocations: the outer vector holds 3 row objects, and each row object points to its own buffer of 4 ints (0 1 2 3, then 10 11 12 13, then 20 21 22 23). The three buffers can be anywhere on the heap.
As one flat std::vector<int>, the grid takes 1 allocation of 12 ints. Row 0 fills indexes 0 to 3, row 1 indexes 4 to 7 and row 2 indexes 8 to 11, so the element at row r, column c is at index r × 4 + c: row 1, column 2 is index 6, which holds 12.

Reading a row means reading neighbouring memory in both layouts. Going down a column means jumping 4 ints ahead in the flat vector, and to a different buffer in the vector of vectors.

three_ways.cpp C++ · three_ways.cpp

// The same 3 x 4 grid stored three ways.
#include <cstddef>
#include <mdspan>
#include <print>
#include <vector>

int main() {
    const std::size_t rows = 3, cols = 4;

    // 1. A vector of vectors: one allocation for the outer vector and one more for each row.
    std::vector<std::vector<int>> nested(rows, std::vector<int>(cols));
    // 2. One flat vector: the element in row r, column c is at index r * cols + c.
    std::vector<int> flat(rows * cols);
    // 3. A std::mdspan (C++23) over the flat vector's elements: it does the index arithmetic.
    std::mdspan grid(flat.data(), rows, cols);

    for (std::size_t r = 0; r < rows; ++r)
        for (std::size_t c = 0; c < cols; ++c) {
            int value = static_cast<int>(10 * r + c);   // 10 * row + column, so 21 is row 2, column 1
            nested[r][c] = value;
            flat[r * cols + c] = value;
        }

    std::println("nested: {}", nested);
    std::println("flat:   {}", flat);
    std::print("grid:   ");
    for (std::size_t r = 0; r < grid.extent(0); ++r) {
        std::print("{}[", r ? " " : "");
        for (std::size_t c = 0; c < grid.extent(1); ++c) std::print("{}{}", c ? ", " : "", grid[r, c]);
        std::print("]");
    }
    std::println("");

    grid[1, 2] = 99;                                  // writes through the view, into flat
    std::println("after grid[1, 2] = 99: flat[{}] = {}, nested[1][2] = {}", 1 * cols + 2, flat[1 * cols + 2], nested[1][2]);
    std::println("grid: {} rows, {} columns, {} elements", grid.extent(0), grid.extent(1), grid.size());
}

One grid, three ways, two compilers Python · three_ways_session.py

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra three_ways.cpp -o three_ways
./three_ways
g++-16 -std=c++23 -Wall -Wextra three_ways.cpp -o three_ways-gcc
./three_ways-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra three_ways.cpp -o three_ways
$ ./three_ways
nested: [[0, 1, 2, 3], [10, 11, 12, 13], [20, 21, 22, 23]]
flat:   [0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23]
grid:   [0, 1, 2, 3] [10, 11, 12, 13] [20, 21, 22, 23]
after grid[1, 2] = 99: flat[6] = 99, nested[1][2] = 12
grid: 3 rows, 4 columns, 12 elements
$ g++-16 -std=c++23 -Wall -Wextra three_ways.cpp -o three_ways-gcc
$ ./three_ways-gcc
nested: [[0, 1, 2, 3], [10, 11, 12, 13], [20, 21, 22, 23]]
flat:   [0, 1, 2, 3, 10, 11, 12, 13, 20, 21, 22, 23]
grid:   [0, 1, 2, 3] [10, 11, 12, 13] [20, 21, 22, 23]
after grid[1, 2] = 99: flat[6] = 99, nested[1][2] = 12
grid: 3 rows, 4 columns, 12 elements

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 three_ways_session.py

The vector of vectors prints as rows inside rows. nested(rows, std::vector<int>(cols)) copies the row vector three times, which makes 4 allocations: the outer vector and one per row. Rows may even differ in length, which is the one thing this layout does that the others cannot.
The flat vector prints as one list in which the rows simply follow each other. The element at row r, column c is flat[r * cols + c]: row 1, column 2 is index 6.
The mdspan grid copies nothing. std::mdspan grid(flat.data(), rows, cols) remembers a pointer to the first element and the two extents, the sizes of its dimensions, and turns grid[r, c] into flat[r * cols + c]. Writing grid[1, 2] = 99 changed flat[6], while the separate nested copy kept 12.

std::mdspan: a 2D view of flat memory

std::mdspan comes from the header <mdspan>, and both compilers used here ship it. It is a view, like std::span in one dimension: it does not own the elements, so it must not outlive the vector it looks into, and it dangles just like a pointer if that vector reallocates. Writing m[r, c] with two indexes inside one pair of brackets is new in C++23 too: a class may now declare operator[] with several parameters.

An mdspan’s type says how much it knows while compiling, and how the indexes map to memory:

layouts.cpp C++ · layouts.cpp

// One buffer of 6 ints, three mdspan views: sizes fixed at compile time, row-major and column-major.
#include <cstddef>
#include <mdspan>
#include <print>

int main() {
    int buffer[6]{1, 2, 3, 4, 5, 6};

    // Both sizes known while compiling: 2 rows, 3 columns. Row-major (layout_right) is the default.
    std::mdspan<int, std::extents<std::size_t, 2, 3>> by_rows(buffer);
    // The same 6 ints read column after column (layout_left), the order Fortran and MATLAB use.
    std::mdspan<int, std::extents<std::size_t, 2, 3>, std::layout_left> by_columns(buffer);

    for (std::size_t r = 0; r < 2; ++r) {
        std::println("row {}: by_rows {} {} {}   by_columns {} {} {}", r, by_rows[r, 0], by_rows[r, 1], by_rows[r, 2],
                     by_columns[r, 0], by_columns[r, 1], by_columns[r, 2]);
    }
    std::println("by_rows[1, 0] is buffer[{}]; by_columns[1, 0] is buffer[{}]", by_rows.mapping()(1, 0), by_columns.mapping()(1, 0));
    std::println("static extents cost no memory: sizeof(by_rows) = {}", sizeof by_rows);

    std::mdspan<int, std::dextents<std::size_t, 2>> sized_at_run_time(buffer, 3, 2);   // 3 x 2 this time
    std::println("3 x 2 view: [2, 1] = {}, sizeof = {}", sized_at_run_time[2, 1], sizeof sized_at_run_time);
}

Fixed and run-time extents, row-major and column-major Python · layouts_session.py

from session import run

run("""
clang++ -std=c++23 -Wall -Wextra layouts.cpp -o layouts
./layouts
g++-16 -std=c++23 -Wall -Wextra layouts.cpp -o layouts-gcc
./layouts-gcc
""")

Output

$ clang++ -std=c++23 -Wall -Wextra layouts.cpp -o layouts
$ ./layouts
row 0: by_rows 1 2 3   by_columns 1 3 5
row 1: by_rows 4 5 6   by_columns 2 4 6
by_rows[1, 0] is buffer[3]; by_columns[1, 0] is buffer[1]
static extents cost no memory: sizeof(by_rows) = 8
3 x 2 view: [2, 1] = 6, sizeof = 24
$ g++-16 -std=c++23 -Wall -Wextra layouts.cpp -o layouts-gcc
$ ./layouts-gcc
row 0: by_rows 1 2 3   by_columns 1 3 5
row 1: by_rows 4 5 6   by_columns 2 4 6
by_rows[1, 0] is buffer[3]; by_columns[1, 0] is buffer[1]
static extents cost no memory: sizeof(by_rows) = 8
3 x 2 view: [2, 1] = 6, sizeof = 24

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 layouts_session.py

std::extents<std::size_t, 2, 3> fixes both sizes while compiling. Such an mdspan is just a pointer, 8 bytes. std::dextents<std::size_t, 2> keeps two sizes chosen while the program runs, and takes 24 bytes.
The default layout, std::layout_right, is row-major: the last index changes fastest, as in a C array of arrays. std::layout_left is column-major, the order of Fortran and MATLAB, so the same six ints read 1 3 5 along row 0 instead of 1 2 3.
mapping()(r, c) shows where an element lives: by_rows[1, 0] is buffer[3], by_columns[1, 0] is buffer[1]. That is how you pass data between C++ and a column-major library without copying it.
extent(0), extent(1) and size() give the number of rows, columns and elements. m[r, c] does not check its indexes, any more than v[i] does.

The comma trap: grid[1, 2] on a vector of vectors

The multidimensional subscript changed the meaning of a comma between brackets. Before C++20, a[1, 2] used the comma operator, which throws away its left side, so it meant a[2]; C++20 deprecated that. In C++23 it is a call of operator[] with two arguments, which std::vector does not have:

comma_subscript.cpp C++ · comma_subscript.cpp

// grid[1, 2] on a vector of vectors: meant as "row 1, column 2".
#include <print>
#include <vector>

int main() {
    std::vector<std::vector<int>> grid{{1, 2, 3}, {4, 5, 6}};
    std::println("{}", grid[1, 2]);
}

Clang refuses it; GCC warns and reads grid[2] Python · comma_session.py

from session import run

# C++23 reads grid[1, 2] as a call of operator[] with two arguments, which std::vector does not have.
run("""
clang++ -std=c++23 comma_subscript.cpp -o comma_subscript
g++-16 -std=c++23 comma_subscript.cpp -o comma_subscript-gcc
./comma_subscript-gcc
""", max_lines=6)

Output

$ clang++ -std=c++23 comma_subscript.cpp -o comma_subscript
comma_subscript.cpp:7:28: error: no viable overloaded operator[] for type 'std::vector<std::vector<int>>'
    7 |     std::println("{}", grid[1, 2]);
      |                        ~~~~^~~~~
/Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/c++/v1/__vector/vector.h:413:83: note: candidate function not viable: requires single argument '__n', but 2 arguments were provided
  413 |   [[__nodiscard__]] _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference operator[](size_type __n) _NOEXCEPT {
      |                                                                                   ^          ~~~~~~~~~~~~~
[4 more lines]
[exit status 1]
$ g++-16 -std=c++23 comma_subscript.cpp -o comma_subscript-gcc
comma_subscript.cpp: In function 'int main()':
comma_subscript.cpp:7:28: warning: top-level comma expression in array subscript changed meaning in C++23 [-Wcomma-subscript]
    7 |     std::println("{}", grid[1, 2]);
      |                            ^
$ ./comma_subscript-gcc
/opt/homebrew/Cellar/gcc/16.2.0/include/c++/16/bits/stl_vector.h:1253: constexpr std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::reference std::vector< <template-parameter-1-1>, <template-parameter-1-2> >::operator[](size_type) [with _Tp = std::vector<int>; _Alloc = std::allocator<std::vector<int> >; reference = std::vector<int>&; size_type = long unsigned int]: Assertion '__n < this->size()' failed.
[stopped by SIGABRT: a shell reports exit status 134]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 comma_session.py

Clang rejects the line. GCC 16 warns that the meaning changed and, as its manual says it does when no two-argument operator[] exists, falls back to the old comma operator: it read grid[2], a row that does not exist, and libstdc++’s debug assertion stopped the program. For a vector of vectors write grid[1][2]; grid[1, 2] is only for types such as std::mdspan that define it.

Visit the grid row by row

Row-major storage means that the elements of one row sit next to each other, and the next row follows. A loop with the column in the inner loop reads memory in order; a loop with the row in the inner loop jumps a whole row ahead on every step. This program measures both, for a grid that fits in the processor’s caches and one that does not:

traverse.cpp C++ · traverse.cpp

// Times four ways to add up every int of an n x n grid, for a small and a large grid, and prints the fastest of
// 5 runs of each. Timings differ from run to run and from computer to computer; the ratios are what matter.
#include <algorithm>
#include <chrono>
#include <cstddef>
#include <cstdint>
#include <mdspan>
#include <print>
#include <vector>

using Clock = std::chrono::steady_clock;
volatile std::int64_t sink = 0;   // each sum is stored here, so the compiler cannot skip computing it

[[gnu::noinline]] std::int64_t flat_rows(const std::vector<int>& g, std::size_t n) {
    std::int64_t sum = 0;
    for (std::size_t r = 0; r < n; ++r)
        for (std::size_t c = 0; c < n; ++c) sum += g[r * n + c];   // the next int in memory every time
    return sum;
}

[[gnu::noinline]] std::int64_t flat_columns(const std::vector<int>& g, std::size_t n) {
    std::int64_t sum = 0;
    for (std::size_t c = 0; c < n; ++c)
        for (std::size_t r = 0; r < n; ++r) sum += g[r * n + c];   // jumps n ints ahead every time
    return sum;
}

[[gnu::noinline]] std::int64_t mdspan_rows(std::mdspan<const int, std::dextents<std::size_t, 2>> m) {
    std::int64_t sum = 0;
    for (std::size_t r = 0; r < m.extent(0); ++r)
        for (std::size_t c = 0; c < m.extent(1); ++c) sum += m[r, c];
    return sum;
}

[[gnu::noinline]] std::int64_t nested_rows(const std::vector<std::vector<int>>& g) {
    std::int64_t sum = 0;
    for (const auto& row : g)
        for (int x : row) sum += x;
    return sum;
}

template <class F>
double fastest_ms(F f) {
    double best = 1e300;
    for (int run = 0; run < 5; ++run) {
        auto start = Clock::now();
        sink = f();
        std::chrono::duration<double, std::milli> took = Clock::now() - start;
        best = std::min(best, took.count());
    }
    return best;
}

int main() {
    for (std::size_t n : {512, 4096}) {
        std::vector<int> flat(n * n);
        for (std::size_t i = 0; i < flat.size(); ++i) flat[i] = static_cast<int>(i % 10);
        std::vector<std::vector<int>> nested(n, std::vector<int>(n));
        for (std::size_t r = 0; r < n; ++r)
            for (std::size_t c = 0; c < n; ++c) nested[r][c] = flat[r * n + c];
        std::mdspan<const int, std::dextents<std::size_t, 2>> view(flat.data(), n, n);

        double rows = fastest_ms([&] { return flat_rows(flat, n); });
        double columns = fastest_ms([&] { return flat_columns(flat, n); });
        double md = fastest_ms([&] { return mdspan_rows(view); });
        double nest = fastest_ms([&] { return nested_rows(nested); });
        std::println("{} x {} ints, {} KiB:", n, n, flat.size() * sizeof(int) / 1024);
        std::println("  flat, row by row        {:8.3f} ms", rows);
        std::println("  flat, column by column  {:8.3f} ms  ({:.0f} times slower)", columns, columns / rows);
        std::println("  mdspan, row by row      {:8.3f} ms", md);
        std::println("  vector of vectors, rows {:8.3f} ms", nest);
    }
}

Four ways to add up a grid, timed Python · traverse_session.py

from session import run

# The cache line and the level-2 cache of this Mac's performance cores (Apple M5 Pro), in bytes, then both compilers
# with -O2. The milliseconds change from run to run; the ratios are what matter.
run("""
/usr/sbin/sysctl -n hw.cachelinesize hw.perflevel0.l2cachesize
clang++ -std=c++23 -O2 -Wall -Wextra traverse.cpp -o traverse
./traverse
g++-16 -std=c++23 -O2 -Wall -Wextra traverse.cpp -o traverse-gcc
./traverse-gcc
""")

Output

$ /usr/sbin/sysctl -n hw.cachelinesize hw.perflevel0.l2cachesize
128
16777216
$ clang++ -std=c++23 -O2 -Wall -Wextra traverse.cpp -o traverse
$ ./traverse
512 x 512 ints, 1024 KiB:
  flat, row by row           0.022 ms
  flat, column by column     0.623 ms  (28 times slower)
  mdspan, row by row         0.023 ms
  vector of vectors, rows    0.022 ms
4096 x 4096 ints, 65536 KiB:
  flat, row by row           1.277 ms
  flat, column by column    97.001 ms  (76 times slower)
  mdspan, row by row         1.194 ms
  vector of vectors, rows    1.293 ms
$ g++-16 -std=c++23 -O2 -Wall -Wextra traverse.cpp -o traverse-gcc
$ ./traverse-gcc
512 x 512 ints, 1024 KiB:
  flat, row by row           0.115 ms
  flat, column by column     0.337 ms  (3 times slower)
  mdspan, row by row         0.110 ms
  vector of vectors, rows    0.113 ms
4096 x 4096 ints, 65536 KiB:
  flat, row by row           6.978 ms
  flat, column by column    86.412 ms  (12 times slower)
  mdspan, row by row         6.990 ms
  vector of vectors, rows    7.051 ms

This output changes from run to run: the times depend on the computer and on what else it is doing

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 traverse_session.py

The first two lines are the processor’s cache line, 128 bytes, and the level-2 cache of its performance cores, 16 MiB. Memory reaches the processor in whole cache lines:

Row by row, all 32 ints of every 128-byte line get used, and the hardware sees the pattern and fetches the next lines early.
Column by column, every step jumps a whole row ahead, 16 KiB in the large grid, so each read lands in a different cache line, uses 4 of its 128 bytes and has to wait for a slower level of the memory system. In the recorded run, the 64 MiB grid took more than 50 times longer this way with Clang and more than 10 times longer with GCC, and even the 1 MiB grid, which fits in the level-2 cache, was several times slower.
The two compilers differ because Clang turned the row loop into vector instructions that add 16 ints per step, while GCC’s -O2 build added them one at a time. Both compilers were equally slow down the columns: there, memory is the limit.
mdspan costs nothing: its row loop ran as fast as the hand-written r * n + c. The vector of vectors was just as fast here too, because each row is contiguous. Its costs show elsewhere: one allocation per row, 24 bytes of bookkeeping per row, and rows scattered over the heap, so stepping between rows, as a column loop or a neighbour check does, jumps to unrelated memory.

Vector of vectors, flat vector or mdspan?
Criterion	Nested vectors	Flat vector	mdspan view
Allocations	Rows + 1	1	1 (the vector's)
Element	g[r][c]	g[r * cols + c]	m[r, c]
Ragged rows	Yes	No	No
Row by row	As fast	Fastest	As fast
Pass it as	A reference	Vector and width	One small value
When to choose	Small or ragged grids	C libraries	C++23 grids

Neighbours: check every bound before you read

Grid searches, flood fills and game boards all look at the cells around a cell, and the cells on the edge have fewer neighbours. Check each bound before the read:

neighbours.cpp C++ · neighbours.cpp

// For every cell of a small map, counts how many of its four neighbours (up, down, left, right) are land, '#'.
#include <mdspan>
#include <print>
#include <string_view>
#include <vector>

using Map = std::mdspan<const char, std::dextents<int, 2>>;   // int coordinates: one step up from row 0 is -1

bool in_bounds(Map m, int r, int c) {
    return r >= 0 && r < m.extent(0) && c >= 0 && c < m.extent(1);
}

int land_around(Map m, int r, int c) {
    const int dr[]{-1, 1, 0, 0};
    const int dc[]{0, 0, -1, 1};
    int land = 0;
    for (int k = 0; k < 4; ++k) {
        int nr = r + dr[k], nc = c + dc[k];
        if (in_bounds(m, nr, nc) && m[nr, nc] == '#') ++land;   // check first, then read
    }
    return land;
}

int land_around_unchecked(Map m, int r, int c) {   // the same without in_bounds: the bug
    const int dr[]{-1, 1, 0, 0};
    const int dc[]{0, 0, -1, 1};
    int land = 0;
    for (int k = 0; k < 4; ++k)
        if (m[r + dr[k], c + dc[k]] == '#') ++land;
    return land;
}

int main() {
    const std::string_view lines[]{".#..", "##.#", "..##"};
    const int rows = 3, cols = 4;
    std::vector<char> cells;
    for (std::string_view line : lines) cells.insert(cells.end(), line.begin(), line.end());
    Map map(cells.data(), rows, cols);

    for (int r = 0; r < rows; ++r) {
        std::print("{}   ", lines[r]);
        for (int c = 0; c < cols; ++c) std::print("{}", land_around(map, r, c));
        std::println("");
    }
    std::println("corner (0, 0) without the check: {}", land_around_unchecked(map, 0, 0));
}

Checked counts, then the unchecked function under AddressSanitizer Python · neighbours_session.py

from session import run

# The checked counts, then the unchecked function under AddressSanitizer (key lines, addresses hidden).
run("""
clang++ -std=c++23 -Wall -Wextra neighbours.cpp -o neighbours
./neighbours
clang++ -std=c++23 -g -fsanitize=address neighbours.cpp -o neighbours-asan
ASAN_OPTIONS=symbolize=0 ./neighbours-asan 2>&1 | grep -E "ERROR|of size|located" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
""")

Output

$ clang++ -std=c++23 -Wall -Wextra neighbours.cpp -o neighbours
$ ./neighbours
.#..   2111
##.#   1231
..##   1212
corner (0, 0) without the check: 2
$ clang++ -std=c++23 -g -fsanitize=address neighbours.cpp -o neighbours-asan
$ ASAN_OPTIONS=symbolize=0 ./neighbours-asan 2>&1 | grep -E "ERROR|of size|located" | sed -E 's/==[0-9]+==//; s/0x[0-9a-f]+/0x…/g'
ERROR: AddressSanitizer: heap-buffer-overflow on address 0x… at pc 0x… bp 0x… sp 0x…
READ of size 1 at 0x… thread T0
0x… is located 4 bytes before 16-byte region [0x…,0x…)
allocated by thread T0 here:

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 neighbours_session.py

The counts are right, and so, by luck, is the unchecked corner: it read two bytes outside the map and neither happened to be '#'. AddressSanitizer shows what really happened: the step up from row 0 read 4 bytes before the map’s buffer, row -1 of a 4-column map. Two rules prevent this:

Test all four bounds, r >= 0, r < rows, c >= 0 and c < cols, before every read. Checking only that the flat index lies inside the vector is not enough: one step right from the last column lands, inside the vector, on the first cell of the next row.
Use signed coordinates for neighbour arithmetic, as std::dextents<int, 2> does here. With std::size_t, row 0 minus 1 wraps around to 18,446,744,073,709,551,615, so a forgotten r >= 0 test fails in a different way.

Your turn: a Matrix with m[r, c]

Write the multidimensional operator[] of a small Matrix type over flat storage, then use it for a transpose and a product. The struct and its constructor are written for you; only the parts marked “your code here” are yours:

matrix_exercise.cpp C++ · matrix_exercise.cpp

// Exercise: a matrix in flat storage. Write the bodies marked "your code here", then build and run this file:
//   clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined matrix_exercise.cpp -o matrix_exercise
//   ./matrix_exercise
// Every check must say "ok".
#include <cstddef>
#include <print>
#include <vector>

struct Matrix {
    std::size_t rows;
    std::size_t cols;
    std::vector<int> data;   // rows * cols values, row after row

    Matrix(std::size_t r, std::size_t c) : rows(r), cols(c), data(r * c) {}

    // Element (r, c), to read or change: m[r, c] = 5;
    int& operator[](std::size_t r, std::size_t c) {
        return data[0];   // your code here
    }
    // The same for a const Matrix, which may only be read.
    const int& operator[](std::size_t r, std::size_t c) const {
        return data[0];   // your code here
    }
};

// The transpose: element (r, c) of the result is element (c, r) of m.
Matrix transpose(const Matrix& m) {
    Matrix t(m.cols, m.rows);
    // your code here
    return t;
}

// The product a × b. a.cols equals b.rows; the result has a.rows rows and b.cols columns.
Matrix multiply(const Matrix& a, const Matrix& b) {
    Matrix p(a.rows, b.cols);
    // your code here
    return p;
}

int failures = 0;

void check(bool passed, const char* what) {
    std::println("{}  {}", passed ? "ok    " : "FAILED", what);
    if (!passed) ++failures;
}

Matrix from_rows(std::size_t rows, std::size_t cols, const std::vector<int>& values) {
    Matrix m(rows, cols);
    m.data = values;
    return m;
}

int main() {
    Matrix m(2, 3);
    m[0, 2] = 7;
    m[1, 0] = 4;
    check(m[0, 2] == 7 && m[1, 0] == 4 && m[1, 1] == 0, "m[r, c] reads back what was written");
    check(m.data == std::vector<int>{0, 0, 7, 4, 0, 0}, "elements are stored row after row");

    const Matrix a = from_rows(2, 3, {1, 2, 3, 4, 5, 6});
    check(a[1, 2] == 6, "a const Matrix can be read");

    Matrix t = transpose(a);
    check(t.rows == 3 && t.cols == 2 && t.data == std::vector<int>{1, 4, 2, 5, 3, 6}, "the transpose of a 2 x 3 matrix is 3 x 2");

    Matrix p = multiply(a, t);   // (2 x 3) times (3 x 2) gives 2 x 2
    check(p.rows == 2 && p.cols == 2 && p.data == std::vector<int>{14, 32, 32, 77}, "a times its transpose");

    Matrix row = from_rows(1, 3, {1, 2, 3});
    Matrix column = from_rows(3, 1, {4, 5, 6});
    check(multiply(row, column).data == std::vector<int>{32}, "(1 x 3) times (3 x 1) is the single number 32");
    check(multiply(column, row).data == std::vector<int>{4, 8, 12, 5, 10, 15, 6, 12, 18}, "(3 x 1) times (1 x 3) is 3 x 3");

    Matrix ones(100, 100), twos(100, 100);
    for (int& x : ones.data) x = 1;
    for (int& x : twos.data) x = 2;
    Matrix big = multiply(ones, twos);
    check(big[0, 0] == 200 && big[99, 99] == 200 && big[42, 7] == 200, "100 x 100: every element is 200");

    std::println("{} of 8 checks failed", failures);
    return failures == 0 ? 0 : 1;
}

As it starts, every check fails:

The starting point Python · exercise_session.py

from session import run

# The exercise as it starts: every function body still has to be written, so every check fails.
run("""
clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined matrix_exercise.cpp -o matrix_exercise
./matrix_exercise
""")

Output

$ clang++ -std=c++23 -Wall -Wextra -fsanitize=address,undefined matrix_exercise.cpp -o matrix_exercise
matrix_exercise.cpp:17:33: warning: unused parameter 'r' [-Wunused-parameter]
   17 |     int& operator[](std::size_t r, std::size_t c) {
      |                                 ^
matrix_exercise.cpp:17:48: warning: unused parameter 'c' [-Wunused-parameter]
   17 |     int& operator[](std::size_t r, std::size_t c) {
      |                                                ^
matrix_exercise.cpp:21:39: warning: unused parameter 'r' [-Wunused-parameter]
   21 |     const int& operator[](std::size_t r, std::size_t c) const {
      |                                       ^
matrix_exercise.cpp:21:54: warning: unused parameter 'c' [-Wunused-parameter]
   21 |     const int& operator[](std::size_t r, std::size_t c) const {
      |                                                      ^
4 warnings generated.
$ ./matrix_exercise
FAILED  m[r, c] reads back what was written
FAILED  elements are stored row after row
FAILED  a const Matrix can be read
FAILED  the transpose of a 2 x 3 matrix is 3 x 2
FAILED  a times its transpose
FAILED  (1 x 3) times (3 x 1) is the single number 32
FAILED  (3 x 1) times (1 x 3) is 3 x 3
FAILED  100 x 100: every element is 200
8 of 8 checks failed
[exit status 1]

Recorded with Python 3.14.8 on macOS 26 arm64. To run it yourself: mise exec python@3.14.8 -- python3 exercise_session.py

You are done when it prints 0 of 8 checks failed with no sanitizer report. Hints: both versions of operator[] return data[r * cols + c]; the transpose copies m[r, c] into t[c, r]; and element (i, j) of a product is the sum of a[i, k] * b[k, j] for k from 0 to a.cols - 1. Keep k in the innermost loop, or try moving it outwards and time the 100 × 100 product both ways: the loop order matters for the same reason as above.

Matrix Calculator Multiply or transpose a small matrix by hand-free and compare the result with your program's output.

Interview questions

Fresher · Why is a flat vector indexed with r * cols + c often better than a vector of vectors for a grid?

A flat vector keeps the whole grid in one block of memory: one allocation, no per-row bookkeeping, and every row directly after the one before it. A vector of vectors makes one allocation per row and scatters the rows over the heap. Creating it is slower, it uses more memory (24 bytes of row object per row on a 64-bit computer, plus each allocation’s overhead), and any access that moves between rows jumps to unrelated memory. Reading row by row is fast in both, because each row is contiguous, but column order and neighbour lookups suffer. A flat vector also hands the whole grid to C libraries and to std::mdspan as one pointer. A vector of vectors is still the right choice when rows have different lengths.

Key takeaways

A vector of vectors allocates every row separately; a flat vector keeps the grid in one block, with row r, column c at index r * cols + c.
std::mdspan (C++23) is a view over flat storage: m[r, c] does the arithmetic, it copies and owns nothing, and its row loop ran exactly as fast as hand-written indexing.
layout_right is row-major, the default; layout_left is column-major, for data from Fortran or MATLAB.
In C++23 grid[1, 2] is a two-argument operator[]: an error for a vector of vectors in Clang, and a warning plus a read of grid[2] in GCC 16.
Visit row-major grids row by row: on a 64 MiB grid, column order was more than 50 times slower with Clang and more than 10 times with GCC.
Before reading a neighbour, test all four bounds; use signed coordinates for the arithmetic.

References

Working Draft, Programming Languages: C++ (N4950): multidimensional access (mdspan) and arrays (ISO/IEC JTC1/SC22/WG21)
P0009R18: MDSPAN (ISO/IEC JTC1/SC22/WG21)
P2128R6: Multidimensional subscript operator (ISO/IEC JTC1/SC22/WG21)
Using the GNU Compiler Collection: Options Controlling C++ Dialect (-Wcomma-subscript) (GNU Project)
AddressSanitizer (Clang documentation) (LLVM Project)

Report a problem with this lesson

In this module: Arrays, vectors and aggregate types

std::vector: the container to reach for first Free: 22 minutes
std::array, C arrays and array decay Free: 18 minutes
C-style strings and why std::string replaced them Free: 22 minutes
2D grids in C++: flat storage and std::mdspan Free: 25 minutes
C++ structs, aggregates and designated initialisers Free: 22 minutes
std::pair, std::tuple and structured bindings Free: 20 minutes
std::optional, std::variant and std::any Free: 25 minutes

Your country

2D grids in C++: flat storage and std::mdspan

What you will learn

Before you start

What you will learn

Before you start

Three ways to store the same grid

std::mdspan: a 2D view of flat memory

The comma trap: grid[1, 2] on a vector of vectors

Visit the grid row by row

Neighbours: check every bound before you read

Your turn: a Matrix with m[r, c]

Check yourself

Interview questions

Key takeaways

References

Related tools