This idiom falls naturally out of 1D array allocation. Let's start with allocating a 1D array of some arbitrary type T:
T *p = malloc( sizeof *p * N );
Simple, right? The expression *p has type T, so sizeof *p gives the same result as sizeof (T), so we're allocating enough space for an N-element array of T. This is true for any type T.
Now, let's substitute T with an array type like R [10]. Then our allocation becomes
R (*p)[10] = malloc( sizeof *p * N);
The semantics here are exactly the same as the 1D allocation method; all that's changed is the type of p. Instead of T *, it's now R (*)[10]. The expression *p has type T which is type R [10], so sizeof *p is equivalent to sizeof (T) which is equivalent to sizeof (R [10]). So we're allocating enough space for an N by 10 element array of R.
We can take this even further if we want; suppose R is itself an array type int [5]. Substitute that for R and we get
int (*p)[10][5] = malloc( sizeof *p * N);
Same deal - sizeof *p is the same as sizeof (int [10][5]), and we wind up allocating a contiguous chunk of memory large enough to hold a N by 10 by 5 array of int.
So that's the allocation side; what about the access side?
Remember that the [] subscript operation is defined in terms of pointer arithmetic: a[i] is defined as *(a + i)1. Thus, the subscript operator [] implicitly dereferences a pointer. If p is a pointer to T, you can access the pointed-to value either by explicitly dereferencing with the unary * operator:
T x = *p;
or by using the [] subscript operator:
T x = p[0]; // identical to *p
Thus, if p points to the first element of an array, you can access any element of that array by using a subscript on the pointer p:
T arr[N];
T *p = arr; // expression arr "decays" from type T [N] to T *
...
T x = p[i]; // access the i'th element of arr through pointer p
Now, let's do our substitution operation again and replace T with the array type R [10]:
R arr[N][10];
R (*p)[10] = arr; // expression arr "decays" from type R [N][10] to R (*)[10]
...
R x = (*p)[i];
One immediately apparent difference; we're explicitly dereferencing p before applying the subscript operator. We don't want to subscript into p, we want to subscript into what p points to (in this case, the array arr[0]). Since unary * has lower precedence than the subscript [] operator, we have to use parentheses to explicitly group p with *. But remember from above that *p is the same as p[0], so we can substitute that with
R x = (p[0])[i];
or just
R x = p[0][i];
Thus, if p points to a 2D array, we can index into that array through p like so:
R x = p[i][j]; // access the i'th element of arr through pointer p;
// each arr[i] is a 10-element array of R
Taking this to the same conclusion as above and substituting R with int [5]:
int arr[N][10][5];
int (*p)[10][5]; // expression arr "decays" from type int [N][5][10] to int (*)[10][5]
...
int x = p[i][j][k];
This works just the same if p points to a regular array, or if it points to memory allocated through malloc.
This idiom has the following benefits:
- It's simple - just one line of code, as opposed to the piecemeal allocation method
T **arr = malloc( sizeof *arr * N );
if ( arr )
{
for ( size_t i = 0; i < N; i++ )
{
arr[i] = malloc( sizeof *arr[i] * M );
}
}
- All the rows of the allocated array are *contiguous*, which is not the case with the piecemeal allocation method above;
- Deallocating the array is just as easy with a single call to
free. Again, not true with the piecemeal allocation method, where you have to deallocate each arr[i] before you can deallocate arr.
Sometimes the piecemeal allocation method is preferable, such as when your heap is badly fragmented and you can't allocate your memory as a contiguous chunk, or you want to allocate a "jagged" array where each row can have a different length. But in general, this is the better way to go.
1. Remember that arrays are not pointers - instead, array expressions are converted to pointer expressions as necessary.
