Multidimensional Arrays

Part I · Module 6 · Chapter 6.5 · Multidimensional Arrays

1. The Problem With One Dimension

A sensor has three gain settings and four channels, and each combination has a calibration value — twelve numbers that belong in a table.

A one-dimensional array can hold twelve numbers:

    int calibration[12];

and then every access has to do arithmetic you performed in your head:

    calibration[gain * 4 + channel]

That works, and it is where the bugs come from. The 4 is the channel count, written by hand at every access; swap gain and channel and it still compiles; change the number of channels and every access is wrong. The structure of the data — two independent coordinates — is nowhere in the code.

2. There Is No Two-Dimensional Array

    int table[3][4];

The temptation is to read that as a grid, three by four. Here is the accurate reading, and the whole chapter follows from it:

table is an array of 3 elements. Each of those elements is an array of 4 int.

C has no two-dimensional array type. It has arrays, and an array's elements can be arrays. Everything else is a consequence.

table[1] is therefore not a number — it is one of the three elements, which is an array of 4 int. Applying a second subscript to that array gives an int:

table        an array of 3 arrays of 4 int
table[1]     an array of 4 int
table[1][2]  an int

table[1][2] is two ordinary indexing operations, not one special two-dimensional one.

3. The Sizes Say the Same Thing

#include <stdio.h>

int main(void)
{
    int table[3][4] = {
        { 10, 11, 12, 13 },
        { 20, 21, 22, 23 },
        { 30, 31, 32, 33 },
    };

    printf("sizeof table          %2zu bytes\n", sizeof table);
    printf("sizeof table[0]       %2zu bytes\n", sizeof table[0]);
    printf("sizeof table[0][0]    %2zu bytes\n", sizeof table[0][0]);
    printf("rows                  %2zu\n", sizeof table / sizeof table[0]);
    printf("columns               %2zu\n", sizeof table[0] / sizeof table[0][0]);
    printf("table[1][2]           %2d\n", table[1][2]);

    return 0;
}

Output:

sizeof table          48 bytes
sizeof table[0]       16 bytes
sizeof table[0][0]     4 bytes
rows                   3
columns                4
table[1][2]           22

Read those three sizes as a sentence. One element of one row is 4 bytes — an int. One row is 16 bytes — four of them. The whole table is 48 bytes — exactly three rows.

The Chapter 6.1 idiom still works, at each level. sizeof table / sizeof table[0] divides the whole thing by one row and gives the row count. sizeof table[0] / sizeof table[0][0] divides one row by one element and gives the column count. Neither needs a literal repeated from the declaration.

4. Row-Major, Derived

Where are those 48 bytes? The answer follows from Chapter 6.1 and needs nothing new.

Chapter 6.1 established that an array's elements are contiguous, with no gaps, proven by sizeof being exactly the count times the element size. Apply that twice:

Each row is contiguous, because table[0] is an array of 4 int occupying exactly 16 bytes.

The rows are contiguous, because table is an array of 3 elements occupying exactly 48 bytes — three 16-byte rows with nothing left over.

Three contiguous 16-byte runs packed into one contiguous 48-byte run can only be arranged one way: row 0, then row 1, then row 2.

This is called row-major order: the whole of one row, then the whole of the next. In table[r][c], moving c by one moves one element; moving r by one moves one whole row.

Knowing the order matters for two reasons. It tells you what table[1][2] means without guessing — row 1, column 2, counting both from zero. And it is the reason a traversal that runs along each row in turn walks straight through memory, while one that runs down each column in turn jumps a row's width every step. On the machines you are likely to use, the first is faster; that is a property of the hardware rather than of C, so measure before treating it as a rule, but the ordering itself is a C guarantee you can rely on.

5. Traversing a Table

One loop per dimension, each of them Chapter 6.3's shape:

#include <stdio.h>

int main(void)
{
    int table[3][4] = {
        { 10, 11, 12, 13 },
        { 20, 21, 22, 23 },
        { 30, 31, 32, 33 },
    };

    size_t rows = sizeof table / sizeof table[0];
    size_t cols = sizeof table[0] / sizeof table[0][0];

    for (size_t r = 0; r < rows; r++) {
        for (size_t c = 0; c < cols; c++) {
            printf("%3d", table[r][c]);
        }
        printf("\n");
    }

    return 0;
}

Output:

 10 11 12 13
 20 21 22 23
 30 31 32 33

Nothing here is new. The outer loop is a traversal of a 3-element array; the inner loop is a traversal of a 4-element array. Both bounds come from sizeof rather than from literals, so both follow the declaration.

The printf("\n") sits in the outer loop, after the inner one finishes — that is what makes the output a table rather than one long line, and it is the one place a nested traversal's structure is visible in the output.

6. The Subscripts Are Not Interchangeable

#include <stdio.h>

int main(void)
{
    int grid[3][4] = {{10,11,12,13},{20,21,22,23},{30,31,32,33}};

    printf("grid[1][2] = %d   (row 1, column 2)\n", grid[1][2]);
    printf("grid[2][1] = %d   (row 2, column 1)\n", grid[2][1]);

    return 0;
}

Output:

grid[1][2] = 22   (row 1, column 2)
grid[2][1] = 31   (row 2, column 1)

7. Initializing a Table

All four forms are useful, and all four follow from §2's array-of-arrays model.

    int nested[2][3]  = { {1, 2, 3}, {4, 5, 6} };
    int flat[2][3]    = { 1, 2, 3, 4, 5, 6 };
    int partial[2][3] = { {1}, {4, 5} };
    int deduced[][3]  = { {1,2,3}, {4,5,6}, {7,8,9} };

Contents, printed row by row:

123456  flat
123456  nested
100450  partial
deduced rows: 3

Nested braces are the form to write. Each inner brace initialises one row, which matches what the declaration means, and it makes the shape visible in the source.

Flat supplies the twelve values in row-major order and relies on the layout to distribute them. It gives the same contents, and the compiler points out that you are leaning on something:

warning: suggest braces around initialization of subobject [-Wmissing-braces]

The warning is good advice. Flat initialisation is correct but silent about structure, so a missing value shifts everything after it into the wrong row with nothing to signal it.

Partial is where the array-of-arrays model pays off. { {1}, {4, 5} } gives 1 0 0 and 4 5 0 — Chapter 6.2's zero rule applied per row, because each inner brace initialises a separate array and leaves the rest of that array zero. If you thought of this as a flat grid, the result would be hard to predict; with the right model it is exactly what you would expect.

Deduced omits the first dimension. int deduced[][3] means as many rows as the initializer supplies, each of 3 — the row count is counted for you, three here. Only the first dimension may be omitted, and the reason is in §2: the compiler must know what one element is — an array of 3 int, 12 bytes — before it can lay out an array of them. It can count how many there are; it cannot infer how big each one is.

8. More Than Two Dimensions

The rule is the same applied again:

#include <stdio.h>

int main(void)
{
    int cube[2][3][4] = {0};

    cube[1][2][3] = 7;

    printf("sizeof cube        %zu\n", sizeof cube);
    printf("sizeof cube[0]     %zu\n", sizeof cube[0]);
    printf("sizeof cube[0][0]  %zu\n", sizeof cube[0][0]);
    printf("cube[1][2][3]      %d\n", cube[1][2][3]);

    return 0;
}

Output:

sizeof cube        96
sizeof cube[0]     48
sizeof cube[0][0]  16
cube[1][2][3]      7

cube is an array of 2 elements; each is an array of 3 elements; each of those is an array of 4 int. Peeling one subscript at a time gives 96, then 48, then 16, then 4 — each level dividing by that dimension.

= {0} zeroes all twenty-four elements, exactly as in Chapter 6.2, because the zero rule applies to every element the initializer does not reach, at every level.

Three dimensions are occasionally the right model — a stack of grids, a set of measurements per channel per gain. Beyond that, the declarations become hard to read and the index order hard to keep straight, and the usual answer is a better-named structure rather than a fourth subscript. Module 10 provides the tool for that.

9. The Table From §1, Properly

#include <stdio.h>

int main(void)
{
    int calibration[3][4] = {
        { 100, 102,  99, 101 },
        { 200, 205, 198, 203 },
        { 400, 408, 396, 405 },
    };

    size_t gain_count    = sizeof calibration / sizeof calibration[0];
    size_t channel_count = sizeof calibration[0] / sizeof calibration[0][0];

    size_t gain = 1;
    size_t channel = 2;

    printf("gain %zu, channel %zu: %d\n", gain, channel, calibration[gain][channel]);

    for (size_t g = 0; g < gain_count; g++) {
        int row_total = 0;
        for (size_t c = 0; c < channel_count; c++) {
            row_total = row_total + calibration[g][c];
        }
        printf("gain %zu total %d\n", g, row_total);
    }

    return 0;
}

Output:

gain 1, channel 2: 198
gain 0 total 402
gain 1 total 806
gain 2 total 1609

Compare the access with §1's. calibration[gain][channel] states what it means; calibration[gain * 4 + channel] states how it is computed and hides what it means. The 4 has disappeared from the code and lives only in the declaration, where it belongs — and channel_count comes from sizeof, so changing the table to five channels requires editing exactly one line.

The accumulator is declared inside the outer loop, so it is a fresh object per row — Chapter 5.6's block scope doing useful work. Declaring it outside and forgetting to reset it is the classic bug in this shape.

10. What You Should Be Able to Say Now

1. C has no two-dimensional array type. int table[3][4] is an array of 3 arrays of 4 int.
2. table[1] is an array, not a number; table[1][2] is two ordinary subscripts.
3. sizeof table[0] is one whole row; sizeof table is exactly the row count times that.
4. The sizeof idiom gives the row count and the column count at their own levels.
5. Rows are stored one after another — row-major order — which follows from Chapter 6.1's contiguity applied twice.
6. Advancing the column index moves one element; advancing the row index moves one whole row.
7. Traversal is Chapter 6.3's loop, nested, with both bounds from sizeof.
8. The subscripts are not interchangeable — harmless-looking on a square table, out of bounds on a non-square one.
9. Nested braces are the initializer form to write; partial initialisation zeroes the rest per row.
10. Only the first dimension may be omitted, because the compiler must know how big one element is.

11. Exercises

Exercise 1 — give every size. For double m[4][5] with double at 8 bytes, give sizeof m, sizeof m[0], sizeof m[0][0], and both counts from the idiom.

Exercise 2 — name the type. For int t[2][6], say what each of these is — an int, an array of int, or an array of arrays — and how many bytes it occupies.

t        t[0]        t[1][5]        t[1]

Exercise 3 — predict the output. Do not compile yet.

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

Exercise 4 — predict the contents. Give every element of each, in row order.

int a[2][3] = { {1, 2}, {3} };
int b[2][3] = { 1, 2, 3, 4 };
int c[3][2] = { {1,1}, {2,2}, {3,3} };
int d[][2]  = { {9,8}, {7,6} };

Exercise 5 — explain the asymmetry. Say why int x[][3] is allowed and int y[3][] is not, in terms of §2's model. Then say what sizeof x[0] would be for int x[][3].

Exercise 6 — find the transposition. This is meant to print each row's total. Say what it actually computes, which index goes out of range and on which pass, and whether the compiler would warn.

int grid[3][4] = { /* ... */ };
for (size_t r = 0; r < 4u; r++) {
    int total = 0;
    for (size_t c = 0; c < 3u; c++) {
        total = total + grid[r][c];
    }
    printf("%d\n", total);
}

Exercise 7 — repair the accumulator. This reports the wrong totals for every row after the first. Say what the numbers will be for the table in §9, name the rule that explains it, and give the one-line repair.

int row_total = 0;
for (size_t g = 0; g < gain_count; g++) {
    for (size_t c = 0; c < channel_count; c++) {
        row_total = row_total + calibration[g][c];
    }
    printf("gain %zu total %d\n", g, row_total);
}

Exercise 8 — design the table. A device has 2 banks, 8 registers per bank, and records 4 samples per register. Declare the array, give its total size in bytes with int at 4 bytes, write the three sizeof expressions that recover each dimension, and write the nested traversal that sums every sample. Say which subscript order you chose and why.

12. Summary

• There is no two-dimensional array in C — only an array whose elements are arrays.
• table[1] is a row, table[1][2] is an element, and both subscripts are ordinary indexing.
• sizeof at each level gives the row size, the element size, and both counts.
• Row-major order follows from Chapter 6.1's contiguity applied twice: each row is contiguous, and the rows are contiguous.
• Moving the column index steps one element; moving the row index steps a whole row.
• Traversal is Chapter 6.3's loop, nested, with bounds from sizeof and variables named for their dimension.
• Swapping the subscripts is nearly invisible on a square table and out of bounds on a non-square one.
• Nested braces are the initializer to write; partial initialisation zeroes per row; only the first dimension may be omitted.

Module 6 is complete. An array is a fixed run of same-typed objects with no stored length, indexed by distance from the start, traversed by a loop whose bounds come from the declaration, and arranged — even in several dimensions — as one contiguous run you can reason about byte by byte. One thing has been conspicuously missing throughout, and Chapter 6.1 said why: not one of these arrays has been passed to a function. The next module builds the idea that makes that possible, and the first thing it does with it is explain the rule that has been deferred since Chapter 5.3 — what an array argument actually becomes, and why the length does not travel with it.