Freaky way of allocating two-dimensional array?

Question

The variable e is a pointer to an array of n + 1 elements of type double.

Using the dereference operator on e gives you the base-type of e which is " array of n + 1 elements of type double".

The malloc call simply takes the base-type of e (explained above) and gets its size, multiplies it by n + 1, and passing that size to the malloc function. Essentially allocating an array of n + 1 arrays of n + 1 elements of double.

This is the typical way you should allocate 2D arrays dynamically.

• e is an array pointer to an array of type double [n+1].
• sizeof(*e) therefore gives the type of the pointed-at type, which is the size of one double [n+1] array.
• You allocate room for n+1 such arrays.
• You set the array pointer e to point at the first array in this array of arrays.
• This allows you to use e as e[i][j] to access individual items in the 2D array.

Personally I think this style is much easier to read:

double (*e)[n+1] = malloc( sizeof(double[n+1][n+1]) );

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)¹. 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:

1. 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 );
     }
   }
   

2. All the rows of the allocated array are *contiguous*, which is not the case with the piecemeal allocation method above;
3. 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.}