Freaky way of allocating two-dimensional array?

In a project, somebody pushed this line:

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

Which supposedly creates a two-dimensional array of (n+1)*(n+1) doubles.

Supposedly, I say, because so far, nobody I asked could tell me what this does, exactly, nor where it originated from or why it should work (which allegedly, it does, but I'm not yet buying it).

Perhaps I'm missing something obvious, but I'd appreciate it if somebody could explain above line to me. Because personally, I'd feel much better if we'd use something we actually understand.

回答1:

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.

回答2:

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]) );

回答3:

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:

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.}