Understanding declaration of semi-dynamic array in C

We studied 2D arrays and right-left rule to understand complex declaration.

I have this declaration of semi-dynamic array:

int * array[2];

With the right-left rule I understand it as: array is an array of 2 pointers to int. And therefore when I draw a diagram I get this:

But in class they showed us the following diagram:

Where I'm wrong? How can I not be mistaken again when it comes to declaration of 2D arrays?

In addition to @chqrlie's answer, please note that the second picture of "semi-dynamic" is rather confusing and your picture at the top is arguably more correct (and in any case not wrong) - just note that you'd have to do array[n] to access the pointer but *(array[n]) to first get the correct pointer, then de-reference the pointer and access the actual item. *(array[n]) being equivalent to array[n][0].

int* array[2] is an array of 2 pointers. This array is allocated on the stack. Each of the pointers may be assigned to point at a single int item. This int may be allocated on the heap if you like. It could be a single item or it could be the first int in an array of int, in which case you would need to keep track of those array sizes somehow.

So in case of int* array[2] then array[0][1] may very well be an out-of-bounds access. Or at least it is not any more or less correct to access that item than say array[0][42] - it depends on context.

The picture of "semi dynamic" more correctly illustrates some strange abomination type such as

int (*arr[2])[2]; - "An array of pointers to arrays of int with size 2". Not a very helpful type for most purposes and kind of ridiculously hard to read.

In general we should always strive to use true 2D arrays whenever possible, even on the heap. The only time you would use an array of pointers or a pointer to an array of pointers, is when you have a specialized container which isn't really a multi-dimensional array, but something with individual dimension sizes (sometimes called "jagged array"). One example is an array of strings allocated on the heap - it makes perfect sense to use char** and malloc for implementing that.

The drawback of arrays of pointers/pointer look-up tables etc is that we get segmented allocation, which is much slower to access and allocate than real multi-dimensional arrays. And also needlessly complex in certain situations. Check out https://stackoverflow.com/questions/42094465/correctly-allocating-multi-dimensional-arrays for details.

Your understanding is correct, and does correspond to an array of pointers to int defined with automatic storage (on the stack), described in the class diagram as a semi-dynamic array.

The diagram shown in class describes 2 other types of arrays with different layouts:

• a true 2D array, ie: an array of 2 arrays of 2 int. No further allocation is needed for this one and both dimensions are fixed at compile time.
• a fully dynamic array, where you define array as a pointer to pointers to ints, int **array;. To use this type of storage, you need to allocate the array of pointers and the arrays each pointer points to. Both dimensions can be determined at runtime, but access is somewhat more expensive as 2 indirections are required to access the int values. Depending on the actual impementations, the compilers may be able to optimize several consecutive accesses, factoring out some redundant code.

Note that the above objects have a different layout and while you can access the elements using the same syntax array[row][col] for both reading and writing, you cannot pass these arrays as arguments to the same functions.

You're being led astray by some unconventional terminology. A 2D array is always declared as

T arr[M][N];  // for some arbitrary type T and size expressions
              // M and N

and the declaration can be read as "arr is an M-element array of N-element arrays of T".

Your "semi-dynamic" array is a 1D array of pointers:

int *arr[M];

each element may point to the first element of another array (whether dynamically allocated or not)

for ( size_t i = 0; i < M; i++ )
  arr[i] = malloc( sizeof *arr[i] * N ); // allocates space for N ints

And your "fully dynamic" array

int **arr;

isn't an array at all. It's just a pointer. It may point to the first element of an array of pointers (dynamically allocated or not), each element of which may point to the first element of an array (dynamically allocated or not):

arr = malloc( sizeof *arr * M ); // Allocates space for M pointers to int
for ( size_t i = 0; i < M; i++ )
  arr[i] = malloc( sizeof *arr[i] * N );  // Allocates space for N ints.  

Assuming M and N are 2, your 2D array will be laid out as

     +---+
arr: |   | arr[0][0]
     +---+
     |   | arr[0][1]
     +---+
     |   | arr[1][0]
     +---+
     |   | arr[1][1]
     +---+

whereas your 1D array of pointers will be laid out as

     +---+                                +---+
arr: |   | arr[0] ----------------------> |   | arr[0][0]
     +---+                                +---+
     |   | arr[1] -----------+            |   | arr[0][1]
     +---+                   |            +---+
                             |  
                             |            +---+
                             +----------> |   | arr[1][0]
                                          +---+
                                          |   | arr[1][1]
                                          +---+

and your pointer-to-pointer version will look like

     +---+     +---+                       +---+
arr: |   | --> |   | arr[0] -------------> |   | arr[0][0]
     +---+     +---+                       +---+
               |   | arr[1] -------+       |   | arr[0][1]
               +---+               |       +---+
                                   |
                                   |       +---+
                                   +-----> |   | arr[1][0]
                                           +---+
                                           |   | arr[1][1]
                                           +---+

Again, there's no rule that your pointers have to point to dynamically-allocated memory. The following is also valid (although I don't have a good use case for it at the moment):

int x[2];
int y[4];

int *arr[2] = {x, y};

which gives us

     +---+                           +---+ 
arr: |   | arr[0] --------------> x: |   | x[0] (arr[0][0])
     +---+                           +---+
     |   | arr[1] -------+           |   | x[1] (arr[0][1])
     +---+               |           +---+
                         |
                         |           +---+
                         +------> y: |   | y[0] (arr[1][0])
                                     +---+
                                     |   | y[1] (arr[1][1])
                                     +---+
                                     |   | y[2] (arr[1][2])
                                     +---+
                                     |   | y[3] (arr[1][3])
                                     +---+

x and y are not dynamically allocated; they're the same storage class as arr.