C / ARRAYS
Multidimensional arrays and row-major order
Lay out, index and traverse C multidimensional arrays knowing exactly where each element sits in memory and why the column count is part of the type.
What you will learn
- Read int a[3][4] as three arrays of four ints, not a grid of pointers.
- Compute any element's flat offset as row * columns + column.
- Nest loops with the last subscript innermost so reads move forward in memory.
- Recognise that a decays to int (*)[4], so the column count is part of the type.
Understanding Multidimensional arrays and row-major order
There is no two-dimensional type in C. int grid[2][3] declares an array of two elements whose element type is int[3], so grid[0] and grid[1] are each complete three-int arrays and grid[1][2] subscripts inside the second one. That is why sizeof grid[0] is the size of a row rather than the size of an int, and why nothing in the program holds a table of row addresses.
Because the elements of any array occupy consecutive storage, and that rule applies to the rows as much as to the ints inside them, the whole object is one unbroken run of six ints: row 0 first, then row 1 with no gap. Row-major order is exactly this arrangement, and it fixes the address arithmetic, since &grid[i][j] is the base address plus (i * 3 + j) * sizeof(int). The 3 in that formula is the column count, which is why the columns must be part of the type while the row count may be omitted: the compiler needs the row width to know how far to jump, not how many rows exist.
Two consequences follow. Traversing with the last subscript in the inner loop walks addresses upward one int at a time, while making the first subscript innermost strides a whole row per step, and on a large array that second pattern touches many more cache lines for the same work. Also, when grid is used in an expression it becomes int (*)[3], a pointer to a three-int row, and never int **; a pointer-to-pointer layout would need a separate array of addresses, which a [2][3] array simply does not contain.
<stdio.h>
int main(void)
{
int grid[2][3] = { {10, 20, 30}, {40, 50, 60} };
int *flat = &grid[0][0];
for (int r = 0; r < 2; r++) {
for (int c = 0; c < 3; c++) {
printf("grid[%d][%d] = %d at offset %ld\n",
r, c, grid[r][c], (long)(&grid[r][c] - flat));
}
}
printf("read linearly:");
for (int i = 0; i < 6; i++)
printf(" %d", flat[i]);
printf("\n");
printf("sizeof grid %zu, row %zu, element %zu\n",
sizeof grid, sizeof grid[0], sizeof grid[0][0]);
return 0;
}
A C multidimensional array is one contiguous block written out a full row at a time, so a[i][j] is nothing more than the element at linear offset i * columns + j.
Worked examples
Stepping a pointer one whole row at a time
Shows that a 2D array converts to a pointer to its first row, so incrementing it moves a full row forward.
<stdio.h>
int main(void)
{
int m[3][2] = { {1, 2}, {3, 4}, {5, 6} };
int (*row)[2] = m;
printf("one step is %zu bytes\n", sizeof *row);
for (int i = 0; i < 3; i++, row++)
printf("row %d starts with %d, ends with %d\n", i, (*row)[0], (*row)[1]);
printf("m[2][1] the long way: %d\n", *(&m[0][0] + 2 * 2 + 1));
return 0;
}
Example explained
Line 1int (*row)[2] = m; works because m converts to a pointer to its first element, and that element is a whole int[2].
Line 2sizeof *row is 8, so row++ advances eight bytes and lands exactly on the start of the next row.
Line 3(*row)[1] dereferences to the row and then subscripts inside it; *row[1] would instead mean *(row[1]), the second row dereferenced.
Line 4*(&m[0][0] + 2 * 2 + 1) applies r * cols + c by hand and reaches the same int the compiler would compute for m[2][1].
The same bytes, walked in column order
Compares a 2D array against a flat array built with the r * COLS + c formula, then reads the 2D array down its columns.
<stdio.h>
ROWS
COLS
int main(void)
{
int a[ROWS][COLS] = { {1, 2, 3, 4}, {5, 6, 7, 8} };
int flat[ROWS * COLS] = {1, 2, 3, 4, 5, 6, 7, 8};
int same = 1;
for (int r = 0; r < ROWS; r++)
for (int c = 0; c < COLS; c++)
if (a[r][c] != flat[r * COLS + c])
same = 0;
printf("layouts identical: %s\n", same ? "yes" : "no");
printf("column order:");
for (int c = 0; c < COLS; c++)
for (int r = 0; r < ROWS; r++)
printf(" %d", a[r][c]);
printf("\n");
return 0;
}
Example explained
Line 1flat[r * COLS + c] reproduces the index computation the compiler performs for a[r][c], so every pair matches and same stays 1.
Line 2Putting c in the outer loop prints 1 5 2 6 3 7 4 8, which is the array read down its columns rather than along its rows.
Line 3Each step of that inner loop moves COLS * sizeof(int), sixteen bytes here, so on a wide array consecutive reads fall in different cache lines.
Line 4The array itself never changes; only the order in which the loops visit the fixed row-major layout changes.
Important notes
C guarantees the rows sit end to end with no padding between them, which is what makes the flat view work, but the standard is fussy about running a plain int * off the end of one row into the next; memcpy or memset across the whole array is unambiguously fine.
Row-major is C's convention, not a universal one. Fortran, MATLAB and several BLAS bindings store columns first, so an array handed across that boundary needs a transpose or an explicit layout flag.
Common mistakes
Treating a 2D array as int **: a converts to int (*)[4], so the assignment is rejected, and forcing it with a cast makes the first ints be interpreted as addresses and the program crashes on the first dereference.
Writing a[1, 2]: the comma operator discards the 1 and leaves a[2], a whole row, so printf("%d", a[1, 2]) prints a truncated address instead of an element.
Hard-coding the wrong width in a flat index, such as p[r * 4 + c] for an int a[2][5]: it compiles and runs silently but reads elements from the middle of the wrong row.
Try it yourself
Change, predict, then run
Declare int t[3][4], fill it with t[r][c] = r * 4 + c using nested loops, then print all twelve values by advancing a single int * from &t[0][0] and check that they come out as 0 through 11 in order.
Open the C workspaceCheck your understanding
For int a[4][6];, what is the relationship in memory between a[1][5] and a[2][0]?
- They are adjacent: a[2][0] is the very next int after a[1][5]
- They are six ints apart, because each row begins a fresh block of six
- Their addresses are unrelated, because each row can be stored separately
- a[2][0] comes first, because the last subscript varies most slowly
Show answer
Rows are stored one after another with no gap, so the last element of row 1 is immediately followed by the first element of row 2. The six-int answer confuses the row stride, which is the distance from a[1][0] to a[2][0], with the distance from the end of one row to the start of the next, which is zero.