Multidimensional arrays

Why this matters

Lots of data is naturally a grid: a spreadsheet, a chess board, the pixels of an image, a distance table between cities, a matrix in a physics simulation. C lets you declare arrays with two (or more) indexes. Underneath, they are still one flat block of memory, and knowing how the grid is laid out in that block tells you how to pass grids to functions, why one loop order is faster than the other, and how images and matrices are stored in files.

Declaring and using a 2D array

#include <stdio.h>

int main(void)
{
    int grid[3][4] = {
        {1, 2, 3, 4},
        {5, 6, 7, 8},
        {9, 10, 11, 12},
    };

    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 4; c++) {
            printf("%3d", grid[r][c]);
        }
        printf("\n");
    }
    printf("grid[1][2] = %d\n", grid[1][2]);
    printf("sizeof grid = %zu, sizeof grid[0] = %zu, sizeof grid[0][0] = %zu\n",
           sizeof grid, sizeof grid[0], sizeof grid[0][0]);
    return 0;
}

  1  2  3  4
  5  6  7  8
  9 10 11 12
grid[1][2] = 7
sizeof grid = 48, sizeof grid[0] = 16, sizeof grid[0][0] = 4

int grid[3][4] is read as "grid is an array of 3 elements, each of which is an array of 4 ints". By convention the first index is the row and the second the column, so grid[1][2] is row 1, column 2 (both counting from 0): the value 7.

The initializer uses one inner brace list per row. The same rules as 1D arrays apply: missing elements become 0, so int grid[3][4] = {0}; zeroes everything.

The sizeof line shows the nesting: the whole grid is 48 bytes; grid[0], one row, is an array of 4 ints (16 bytes); grid[0][0] is one int.

Row-major layout

Memory is one-dimensional. C lays a 2D array out row by row (called row-major order): first all of row 0, then all of row 1, and so on.

  the grid as you picture it:          as it really sits in memory:

        col 0  col 1  col 2  col 3
  row 0 [  1  |  2  |  3  |  4  ]      +---+---+---+---+---+---+---+---+---+----+----+----+
  row 1 [  5  |  6  |  7  |  8  ]      | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
  row 2 [  9  | 10  | 11  | 12  ]      +---+---+---+---+---+---+---+---+---+----+----+----+
                                       |<--- row 0 --->|<--- row 1 --->|<----- row 2 ---->|

So the address of grid[r][c] is

  start of grid + (r * 4 + c) * sizeof(int)
                    ^
                    number of columns

grid[1][2] is element 1 * 4 + 2 = 6 of the flat block, the seventh int, which holds 7. The compiler must know the number of columns to compute this; the number of rows never appears in the formula. Keep that in mind for the next section.

Loop order matters

Visiting grid[r][c] with r in the outer loop walks memory straight through, one int after another. Swapping the loops (columns outer) jumps 16 bytes on every step. For small arrays you will not notice, but for a 4000x4000 image the row-by-row loop can be several times faster, because the CPU loads memory into its caches in chunks of 64 bytes, and walking sequentially uses every byte of each chunk. Prefer row-major traversal unless the algorithm needs otherwise.

Passing 2D arrays to functions

As with 1D arrays, a 2D array argument decays to the address of its first element. Its first element is a whole row (an array of COLS ints), so the function must know the row length. You may leave the first dimension empty, but not the second:

#include <stdio.h>

#define COLS 4

void print_grid(const int g[][COLS], int rows)
{
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < COLS; c++) {
            printf("%3d", g[r][c]);
        }
        printf("\n");
    }
}

void transpose(const int in[3][COLS], int out[COLS][3])
{
    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < COLS; c++) {
            out[c][r] = in[r][c];
        }
    }
}

int main(void)
{
    int a[3][COLS] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}};
    int t[COLS][3];

    transpose(a, t);
    for (int r = 0; r < COLS; r++) {
        for (int c = 0; c < 3; c++) {
            printf("%3d", t[r][c]);
        }
        printf("\n");
    }
    printf("--\n");
    print_grid(a, 2);
    return 0;
}

  1  5  9
  2  6 10
  3  7 11
  4  8 12
--
  1  2  3  4
  5  6  7  8

#define COLS 4 makes a named constant (the preprocessor replaces every COLS with 4), so the column count is written in one place. The transpose function writes into out, which belongs to main, exactly like the 1D fill_squares pattern from the previous lesson.

Leaving out the column count is an error:

main.c:1:12: error: array type has incomplete element type 'int[]'
note: declaration of 'g' as multidimensional array must have bounds for all dimensions except the first

Characters in a grid

2D arrays of char are handy for boards and maps:

#include <stdio.h>

int main(void)
{
    char board[3][3] = {
        {'X', 'O', 'X'},
        {' ', 'X', 'O'},
        {'O', ' ', 'X'},
    };

    for (int r = 0; r < 3; r++) {
        printf(" %c | %c | %c\n", board[r][0], board[r][1], board[r][2]);
        if (r < 2) printf("---+---+---\n");
    }

    char d = board[0][0];
    if (d != ' ' && board[1][1] == d && board[2][2] == d) {
        printf("%c wins on the diagonal\n", d);
    }
    return 0;
}

 X | O | X
---+---+---
   | X | O
---+---+---
 O |   | X
X wins on the diagonal

Neighbors and edges

Grid algorithms often look at the cells around [r][c]: in a game, an image filter, a minesweeper count. The neat way to visit the 8 neighbors is a pair of offset loops, from -1 to 1 in each direction, skipping the (0, 0) offset. At the edges some neighbors fall outside the grid, and since C does not check bounds, g[-1][c] silently reads whatever is before the array. Always test 0 <= nr && nr < ROWS && 0 <= nc && nc < COLS before indexing. The last exercise of this lesson is exactly this problem.

More dimensions

The pattern extends: double cube[10][20][30] is 10 arrays of 20 arrays of 30 doubles, laid out with the last index changing fastest. Functions taking it must state every dimension but the first: void f(double c[][20][30], int n). Beyond three dimensions, programs usually switch to a flat 1D array and compute indexes by hand, which is also how dynamically sized grids are done once you have malloc.

Common mistakes

• Swapping row and column: grid[c][r] where you meant grid[r][c]. With non-square grids this reads out of bounds. Name loop variables r and c, not i and j.
• grid[r, c]: in C the comma here is the comma operator, so this means grid[c], a whole row. gcc warns left-hand operand of comma expression has no effect and then reports a type error.
• Omitting the column count in a parameter: see the error above.
• Edge checks after indexing: if (g[nr][nc] && nr >= 0) reads first and checks second. Check bounds first; && stops at the first false operand.

Recap

• T a[R][C] is R rows, each an array of C elements; index as a[r][c].
• Storage is row-major: element [r][c] is at flat position r * C + c.
• Traverse with the row index in the outer loop for sequential memory access.
• Function parameters must give every dimension except the first: int g[][C].
• Check bounds before reading neighbors at the edges.

Going further: write a function that prints a 5x6 Life grid with # for alive and . for dead, then use live_neighbors from the exercise to compute and print the next generation (a live cell survives with 2 or 3 live neighbors; a dead cell becomes alive with exactly 3). Try it on the "blinker" from the starter.