C, Multidimensional arrays: array whose elements are one-dimensional arrays?

Question

Does this statement make sense, from the book C Programming: A Modern Approach, 2nd Edition on page 269

Just as the name of a one-dimensional array can be used as a pointer, so can the name of any array, regardless of how many dimensions it has. Some care is required, though. Consider the following array:

int a[NUM_ROWS][NUM_COLS];

a is not a pointer to a[0][0]; instead, it's a pointer to a[0]. This makes more sense if we look at it from the standpoint of C, which regards a not as a two-dimensional array but as a one-dimensional array whose elements are one-dimensional arrays. When used as a pointer, a has type int (*) [NUM_COLS] (pointer to an integer array of length NUM_COLS).

I'm confused because when I think "array whose elements are one-dimensional arrays" I think a jagged-array, but that's not what's going on here.. This is more like a macro with pointer arithmetic?

Is this in reference to the type system and how it treats multidimensional arrays? Could any one explain this?

Answer 1

Yes, it makes sense, and no, it's not even talking about "ragged" or "jagged" arrays. It's simply that when we say

int a[NUM_ROWS][NUM_COLS];

what we're creating is an array a, and what it's an array of is... other arrays. You could think of it like this:

        +---------------------------------------+
        | +--------+--------+--------+--------+ |
a: [0]: | |        |        |        |        | |
        | +--------+--------+--------+--------+ |
        +                                       +
        | +--------+--------+--------+--------+ |
   [1]: | |        |        |        |        | |
        | +--------+--------+--------+--------+ |
        +                                       +
        | +--------+--------+--------+--------+ |
   [2]: | |        |        |        |        | |
        | +--------+--------+--------+--------+ |
        +---------------------------------------+

(Here NUM_COLS is evidently 4, and NUM_ROWS is 3.)

A two- (or more) dimensional array is 100% analogous to a simple, single-dimensional array -- you just have to be careful thinking about the analogies. If a is an array, then any mention of a in an expression where its value is needed results in a pointer to the array's first element, &a[0]. So given the two-dimensional array a we're talking about, a's value is &a[0] and is a pointer to an array of NUM_COLS integers.

It has to work this way, if multidimensional array subscripts are to work correctly. If we write a[i][j], that's interpreted as (a[i])[j]. a turns into a pointer to the array's first element, as usual, but a[i] is equivalent to *(a + i), where the pointer arithmetic ends up being scaled by the size of the pointed-to element -- that is, under the hood, it's more like *(a+ i * sizeof(*a)). So sizeof(*a) has to be sizeof(int [NUM_COLS]), or NUM_COLS * sizeof(int). That way a[i] gets you the i'th subarray, and then j can select one of the cells -- the int-sized cells -- of the subarray.

One final note: I've talked colloquially about "multi-dimensional arrays", but strictly speaking, and as many of the regulars here are fond of pointing out, C has no multidimensional arrays; it has only single-dimensional arrays, and what we think of as a two-dimensional array is actually, as we've seen here, a single-dimensional array whose elements happen to be other single-dimensional arrays. (If C had true multi-dimensional arrays, the subscripts would probably look like a[i,j] instead of a[i][j].)

---

Addendum: Despite your mention of pointer arithmetic, and my mention of pointer arithmetic, it's important to realize that there are no pointers involved in a's definition. Pointers arise only when we try to "take the value of" a, or explain how a[i] is equivalent to *(a + i).

For a data structure that does involve pointers, we could contrast the situation described by the code

int *a2[NUM_ROWS];
for(i = 0; i < NUM_ROWS; i++)
    a2[i] = malloc(NUM_COLS * sizeof(int));

This gives us a very different memory layout:

    +-----+
a2: |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+
    |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+
    |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+

And this is what's usually called a "ragged" or "jagged" array, since it's obviously not necessary that all the rows in this case be the same length. Nevertheless, almost magically, the cells in the "ragged" array can also be accessed using the a2[i][j] notation. And for full dynamism, we could use

int **a3 = malloc(NUM_ROWS * sizeof(int *));
for(i = 0; i < NUM_ROWS; i++)
    a3[i] = malloc(NUM_COLS * sizeof(int));

resulting in this memory layout:

    +-----+
a3: |     |
    |  *  |
    |  |  |
    +--|--+
       |
       |
       V
    +-----+
    |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+
    |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+
    |     |     +--------+--------+--------+--------+
    |  *------->|        |        |        |        |
    |     |     +--------+--------+--------+--------+
    +-----+

And a3[i][j] works here, too.

(Of course, in real code constructing "dynamic arrays" like a2 and a3, we'd have to check to make sure that malloc didn't return NULL.)

Answer 2

Another way to look at it...

For any type T, we create an array as

T arr[N];

where T can be int, char, double, struct foo, whatever, and reads as “N-element array of T”. It can also be another array type. So, instead of just int, suppose T is an M-element array of int, which we’d write as

int arr[N][M];

This reads as “arr is an N-element array of M-element arrays of int”. This isn’t a jagged array - all the “rows” are the same size. But it’s not exactly a 2-dimensional array, either - it is an array of arrays. The expression arr[i] has an array type (int [M]).

This view helps us figure out pointer to array types as well. Except when it is the operand of the sizeof or unary & operator, or is a string literal used to initialize a character array in a declaration, an expression of type “N-element array of T” (T [N]) will be converted (“decay”) to an expression of type “pointer to T” (T *). Again, if you replace T with an array type int [M], then you have an expression of type “N-element array of M-element arrays of int” (int [N][M]), which “decays” to type “pointer to M-element array of int” (int (*)[M]).