Multidimensional C-style arrays

Consider a game like Connect Four. The standard board for this game is a 6×7 grid, with players taking turns dropping colored discs. The first to get four discs in a row wins.

While you could store the board data as 42 individual variables, we know that when you have multiple instances of an element, it's better to use an array:

int board[42]; // a C-style array of ints (value 0 = empty, 1 = player 1, 2 = player 2)

This defines a C-style array with 42 elements arranged sequentially in memory. We can imagine these elements laid out as a single row of values, like this:

// board[0] board[1] board[2] board[3] ... board[40] board[41]

The dimension of an array is the number of indices needed to select an element. An array containing only a single dimension is called a single-dimensional array or a one-dimensional array (sometimes abbreviated as a 1d array). board above is an example of a one-dimensional array, as elements can be selected with a single index (e.g. board[15]).

But note that our one-dimensional array doesn't look much like our Connect Four board, which exists in two dimensions. We can do better.

Two-dimensional arrays

In previous lessons, we noted that the elements of an array can be of any object type. This means the element type of an array can be another array! Defining such an array is simple:

int grid[4][6]; // a 4-element array of 6-element arrays of int

An array of arrays is called a two-dimensional array (sometimes abbreviated as a 2d array) because it has two subscripts.

With a two-dimensional array, it is convenient to think of the first (left) subscript as selecting the row, and the second (right) subscript as selecting the column. Conceptually, we can imagine this two-dimensional array laid out as follows:

// col 0    col 1    col 2    col 3    col 4    col 5
// [0][0]   [0][1]   [0][2]   [0][3]   [0][4]   [0][5]   row 0
// [1][0]   [1][1]   [1][2]   [1][3]   [1][4]   [1][5]   row 1
// [2][0]   [2][1]   [2][2]   [2][3]   [2][4]   [2][5]   row 2
// [3][0]   [3][1]   [3][2]   [3][3]   [3][4]   [3][5]   row 3

To access the elements of a two-dimensional array, we simply use two subscripts:

grid[1][4] = 9; // grid[row][col], where row = 1 and col = 4

Thus, for a Connect Four board, we can define a 2d array like this:

int board[6][7];

And now we have a 6×7 grid of elements that we can easily manipulate using row and column indices!

Multidimensional arrays

Arrays with more than one dimension are called multidimensional arrays.

C++ even supports multidimensional arrays with more than 2 dimensions:

int space[8][8][8]; // an 8x8x8 array (an array of 8 arrays of 8 arrays of 8 ints)

For example, a 3D voxel-based world (like in Minecraft) might store terrain data in a 3-dimensional array.

Arrays with dimensions higher than 3 are supported, but rare.

How 2d arrays are laid out in memory

Memory is linear (1-dimensional), so multidimensional arrays are actually stored as a sequential list of elements.

There are two possible ways for the following array to be stored in memory:

// col 0   col 1   col 2   col 3
// [0][0]  [0][1]  [0][2]  [0][3]  row 0
// [1][0]  [1][1]  [1][2]  [1][3]  row 1
// [2][0]  [2][1]  [2][2]  [2][3]  row 2

C++ uses row-major order, where elements are sequentially placed in memory row-by-row, ordered from left to right, top to bottom:

[0][0] [0][1] [0][2] [0][3] [1][0] [1][1] [1][2] [1][3] [2][0] [2][1] [2][2] [2][3]

Some other languages (like Fortran) use column-major order, where elements are sequentially placed in memory column-by-column, from top to bottom, left to right:

[0][0] [1][0] [2][0] [0][1] [1][1] [2][1] [0][2] [1][2] [2][2] [0][3] [1][3] [2][3]

In C++, when initializing an array, elements are initialized in row-major order. And when traversing an array, it is most efficient to access elements in the order they are laid out in memory.

Initializing two-dimensional arrays

To initialize a two-dimensional array, it is easiest to use nested braces, with each set of numbers representing a row:

int grid[3][4]
{
  { 10, 20, 30, 40 },     // row 0
  { 50, 60, 70, 80 },     // row 1
  { 90, 100, 110, 120 }   // row 2
};

Although some compilers will let you omit the inner braces, we highly recommend you include them anyway for readability purposes.

When using inner braces, missing initializers will be value-initialized:

int grid[3][4]
{
  { 10, 20 },        // row 0 = 10, 20, 0, 0
  { 50, 60, 70 },    // row 1 = 50, 60, 70, 0
  { 90, 100, 110 }   // row 2 = 90, 100, 110, 0
};

An initialized multidimensional array can omit (only) the leftmost length specification:

int grid[][4]
{
  { 10, 20, 30, 40 },
  { 50, 60, 70, 80 },
  { 90, 100, 110, 120 }
};

In such cases, the compiler can do the math to figure out what the leftmost length is from the number of initializers.

Omitting non-leftmost dimensions is not allowed:

int grid[][]
{
  { 10, 20, 30 },
  { 40, 50, 60 }
};

Just like normal arrays, multidimensional arrays can still be initialized to 0 as follows:

int grid[3][4] {};

Two-dimensional arrays and loops

With a one-dimensional array, we can use a single loop to iterate through all of the elements in the array:

#include <iostream>
#include <iterator>

int main()
{
    int values[] { 10, 20, 30, 40, 50 };

    // for-loop with index
    for (std::size_t index{0}; index < std::size(values); ++index)
        std::cout << values[index] << ' ';

    std::cout << '\n';

    // range-based for-loop
    for (auto element: values)
        std::cout << element << ' ';

    std::cout << '\n';

    return 0;
}

With a two-dimensional array, we need two loops: one to select the row, and another to select the column.

And with two loops, we also need to determine which loop will be the outer loop, and which will be the inner loop. It is most efficient to access elements in the order they are laid out in memory. Since C++ uses row-major order, the row selector should be the outer loop, and the column selector should be the inner loop.

#include <iostream>
#include <iterator>

int main()
{
    int grid[3][5] {
        { 10, 20, 30, 40, 50 },
        { 60, 70, 80, 90, 100 },
        { 110, 120, 130, 140, 150 }};

    // double for-loop with indices
    for (std::size_t row{0}; row < std::size(grid); ++row) // std::size(grid) returns the number of rows
    {
        for (std::size_t col{0}; col < std::size(grid[0]); ++col) // std::size(grid[0]) returns the number of columns
            std::cout << grid[row][col] << ' ';

        std::cout << '\n';
    }

    // double range-based for-loop
    for (const auto& rowArray: grid)   // get each array row
    {
        for (const auto& element: rowArray) // get each element of the row
            std::cout << element << ' ';

        std::cout << '\n';
    }

    return 0;
}

A two-dimensional array example

Let's take a look at a practical example of a two-dimensional array:

#include <iostream>
#include <iterator>

int main()
{
    constexpr int rows{ 12 };
    constexpr int cols{ 12 };

    // Declare a 12x12 array
    int table[rows][cols]{};

    // Calculate a multiplication table
    // We don't need to calc row and col 0 since mult by 0 always is 0
    for (std::size_t row{ 1 }; row < rows; ++row)
    {
        for (std::size_t col{ 1 }; col < cols; ++col)
        {
            table[row][col] = static_cast<int>(row * col);
        }
     }

    for (std::size_t row{ 1 }; row < rows; ++row)
    {
        for (std::size_t col{ 1 }; col < cols; ++col)
        {
            std::cout << table[row][col] << '\t';
        }

        std::cout << '\n';
     }

    return 0;
}

This program calculates and prints a multiplication table for all values between 1 and 11 (inclusive). Note that when printing the table, the for loops start from 1 instead of 0. This is to omit printing the 0 column and 0 row, which would just be a bunch of 0s! Here is the output:

1    2    3    4    5    6    7    8    9    10   11
2    4    6    8    10   12   14   16   18   20   22
3    6    9    12   15   18   21   24   27   30   33
4    8    12   16   20   24   28   32   36   40   44
5    10   15   20   25   30   35   40   45   50   55
6    12   18   24   30   36   42   48   54   60   66
7    14   21   28   35   42   49   56   63   70   77
8    16   24   32   40   48   56   64   72   80   88
9    18   27   36   45   54   63   72   81   90   99
10   20   30   40   50   60   70   80   90   100  110
11   22   33   44   55   66   77   88   99   110  121

Cartesian coordinates vs Array indices

In geometry, the Cartesian coordinate system is often used to describe the position of objects. In two dimensions, we have two coordinate axes, conventionally named "x" and "y". "x" is the horizontal axis, and "y" is the vertical axis.

In two dimensions, the Cartesian position of an object can be described as an { x, y } pair, where x-coordinate and y-coordinate are values indicating how far to the right of the x-axis and how far above the y-axis an object is positioned. Sometimes the y-axis is flipped (so that the y-coordinate describes how far below the y-axis something is).

Now let's take a look at our 2d array layout in C++:

// col 0   col 1   col 2   col 3
// [0][0]  [0][1]  [0][2]  [0][3]  row 0
// [1][0]  [1][1]  [1][2]  [1][3]  row 1
// [2][0]  [2][1]  [2][2]  [2][3]  row 2

This is also a two-dimensional coordinate system, where the position of an element can be described as [row][col] (where the col-axis is flipped).

While each of these coordinate systems is fairly easy to understand independently, converting from Cartesian { x, y } to Array indices [row][col] is a bit counter-intuitive.

The key insight is that the x-coordinate in a Cartesian system describes which column is being selected in the array indexing system. Conversely, the y-coordinate describes which row is being selected. Therefore, an { x, y } Cartesian coordinate translates to an [y][x] array coordinate, which is backwards from what we might expect!

This leads to 2d loops that look like this:

    for (std::size_t y{0}; y < std::size(grid); ++y) // outer loop is rows / y
    {
        for (std::size_t x{0}; x < std::size(grid[0]); ++x) // inner loop is columns / x
            std::cout << grid[y][x] << ' '; // index with y (row) first, then x (col)

Note that in this case, we index the array as grid[y][x], which is probably backwards from the alphabetic ordering you were expecting.

Summary

Array dimension: The number of indices needed to select an element. Arrays requiring one index are one-dimensional (1d), arrays requiring two indices are two-dimensional (2d), and so on.

Two-dimensional arrays: Arrays where each element is itself an array, declared as int grid[rows][columns]. By convention, the first subscript selects the row and the second selects the column.

Multidimensional arrays: Arrays with more than one dimension. C++ supports arrays of any dimensionality, though arrays beyond 3 dimensions are rare.

Row-major order: The memory layout C++ uses for multidimensional arrays, where elements are stored row-by-row. The rightmost index changes fastest, so [0][0], [0][1], [0][2] come before [1][0].

Initializing multidimensional arrays: Use nested braces for clarity, with each inner brace representing a row. Missing initializers are value-initialized to zero. The leftmost dimension can be omitted if the array is initialized (the compiler calculates it from the number of rows provided).

Iterating multidimensional arrays: Requires nested loops. For efficiency, the outer loop should iterate rows and the inner loop should iterate columns (matching row-major order). Both index-based loops and range-based for loops work with multidimensional arrays.

Cartesian coordinates vs array indices: When converting from Cartesian coordinates {x, y} to array indices, remember that x corresponds to the column and y corresponds to the row, giving array[y][x] (not array[x][y]).

Multidimensional arrays provide an intuitive way to represent grid-like data such as game boards, images, or mathematical matrices. Understanding row-major order and proper indexing conventions ensures efficient memory access patterns.