Understanding declaration of semi-dynamic array in C

Question

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?

You should remember that a pointer can point not only to an individual object, but to an element in an array of objects. This is so pervasive in C that an individual object is often viewed as a one-element array. So your picture could be extended with more `int` cells in the heap adjacent to existing cells without changing anything else. — n. m. could be an AI, Jun 26 '23 at 07:52
I see, so if I understood you right, my diagram is correct but because it is semi-dynamic 2D-array then instead of pointing to an individual `int`, the user can decide to allocate more then one `int` (meaning, array of ints) but the pointer points to the first element, so their diagram takes into account that the user allocated more than one `int`. Right? — CStudent, Jun 26 '23 at 07:57
If these are only dynamically allocated 2D arrays in your class documentation, it is missing the *actual* dynamic 2D array. Please see: [Correctly allocating multi-dimensional arrays](https://stackoverflow.com/q/42094465/694733). — user694733, Jun 26 '23 at 08:05
You can have a dynamic true 2D array with a help of a pointer to an array: `int (*arr)[2] = calloc(2, sizeof *arr);`. It shares the same layout as `int arr[2][2]` but it is dynamically allocated. — tstanisl, Jun 26 '23 at 08:40

score 3 · Answer 1 · answered Jun 26 '23 at 10:01

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 Correctly allocating multi-dimensional arrays for details.

Since C23 the `int (*arr[2])[2];` could be rewritten as `typeof(int[2]) * arr[2];` which is arguably easier to read. — tstanisl, Jun 26 '23 at 10:19

score 2 · Accepted Answer · answered Jun 26 '23 at 07:59

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.

Thanks for the explanation! The thing that is not quite clear to me yet is why in the semi-dynamic array I get in the heap what seems like to be an array of ints instead of only one int? — CStudent, Jun 26 '23 at 08:07
@CStudent That's a good question, I posted an additional answer regarding that. — Lundin, Jun 26 '23 at 10:01
The example in class show 3 different ways to allocate a 2x2 `int` array. More genrally. for an indirect 2D array of `rows` rows and `cols` columns, you would allocate `rows` pointers to `int`, and an array of `cols` ints for each pointer. — chqrlie, Jun 26 '23 at 10:04

score 1 · Answer 3 · answered Jun 27 '23 at 15:16

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.

That is a very clear explanation, Thanks! – CStudent Jun 27 '23 at 18:18 — CStudent, Jun 27 '23 at 18:18

Understanding declaration of semi-dynamic array in C

3 Answers3