How does (*prt)[N][N] work when dealing with heap allocation memory?

Question

Today a colleague at work showed me a way of declaring a 2D array in such a way that I can allocate it linearly but still use 2D square bracket ([][]) notation to access elements.

For example:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 2

int main () {
  int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE);

  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      (*a)[i][j] = 0;
    }
  }

  (*a)[0][1] = 100;

  /* should yield:
   *   0
   *   100
   *   0
   *   0
   */
  for (int i = 0; i < SIZE; i++) {
    for (int j = 0; j < SIZE; j++) {
      printf ("%d\n", (*a)[i][j]);
    }
  }

  free (a);

  return EXIT_SUCCESS;
}

This is in contrast to computing the index and then perform pointer arthimetic (e.g. *(a + (x * SIZE + y)) or more tersly a[x * SIZE + y]) to access an element.

The critical part is the shape declaration of the pointer x (e.g. (*x)[][]), which seems to encode this information as a type for the value that x points to.

Beyond this though I do not understand how this works. What does this notation exactly doing? Is it syntactic sugar? It looks symilar to dynamic stack allocation for arrays (see Array size at run time without dynamic allocation is allowed? as one example of this), but clearly this allocation is happening on the heap.

I've looked for more information about this notation/declaration of the pointer but can't find much other than the term element type coming up - but I'm not certain that this is related.

EDIT #1:

I should have mentioned this question is in the context of using the heap, and not the stack. I'm aware of stack based dynamic allocation of arrays, but the work I'm doing specifically looks at dynamic memory allocations.

Answer 1

It is not wrong but not the more usual (and idiomatic way). To declare a dynamic array of size N, you use: int *arr = malloc(N * sizeof(int));. In fact this declares arr as a pointer to the first element of an array of N int. A 2D array is an array of arrays so to declare an 2D array N*N, the more common way is :

int (*arr)[N] = malloc(N * N * sizeof(int));

This actually declares arr as a pointer to the first element of N arrays of N int. You can then normally use arr[i][j].

So what is that amazing int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE);?

You declare arr as a pointer to the first (and single) element of an array of 2D arrays NxN of integers. The good news is that the declaration is explicit for the size of all dimensions, but the downside is that you must consistently dereference it: (*arr)[i][j] which is not different per definition of the [] operator in C from arr[0][i][j].

It is nothing more than my own opinion, but I strongly urge you to stick to the first method. That first and single element trick is likely to disturb any future reader or maintainer of your code because it is not idiomatic.

Answer 2

int (*a)[SIZE][SIZE]

declares a as a pointer to a SIZE by SIZE array of int - assuming SIZE == 3, you get something like this:

   +---+          +---+---+---+
a: |   | -------> |   |   |   |
   +---+          +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+

(actually, layout would be strictly linear, but we'll go with this representation for now).

To access any element of the pointed-to array, we'd write (*a)[i][j] - we have to dereference a explicitly, since we don't want to index into a, we want to index into what a points to.

Remember that a[i] is defined as *(a + i) - given an address a, offset i elements (not bytes!) from that address and deference the result. Thus, (*a)[i][j] is equivalent to a[0][i][j].

Now, if a points to a 3x3 array of int, then a + 1 points to the next 3x3 array of int:

   +---+          +---+---+---+
a: |   | -------> |   |   |   |
   +---+          +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+
a + 1: ---------> |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+
                  |   |   |   |
                  +---+---+---+

which we would access as (*(a + 1))[i][j], or simply a[1][i][j].

Now, why use a pointer to an array in the first place? In this case we're dynamically allocating the array, which we would do if a) we didn't know how many SIZExSIZE arrays we'd need until runtime, or b) if the resulting array would be too large to allocate as an auto variable, or c) if we want to extend or shrink the number of SIZExSIZE arrays as necessary.

How does this method of allocating a multidimensional array work? Let's start by allocating an N-element array of T:

T *arr = malloc( sizeof *arr * N );

sizeof *arr is equivalent to sizeof (T), so we're setting aside space for N objects of type T.

Now let's replace T with an array type, R [M]:

R (*arr)[M] = malloc( sizeof *arr * N );

sizeof *arr is equivalent to sizeof (R [M]), so we're setting aside space for N objects of type R [M] - IOW, N M-element arrays of R. We've dynamically created the equivalent of R a[M][N].

We could also have written this as

R (*arr)[M] = malloc( sizeof (R) * M * N );

although I prefer using sizeof *arr; you'll see why in a second.

Now, we can replace R with yet another array type, S [L]:

S (*arr)[L][M] = malloc( sizeof *arr * N );

sizeof *arr is equivalent to sizeof (S [L][M]), so we're allocating enough space for N objects of type S [L][M], or N L by M arrays of S. We've dynamically created the equivalent of S arr[L][M][N].

The semantics for dynamically allocating 1D, 2D, and 3D arrays are exactly the same - all that's changed is the type. By using sizeof *arr each time, I only need to track how many elements I need of that type.

Answer 3

What int (*a)[SIZE][SIZE] = malloc (sizeof (int) * SIZE * SIZE); does is declaring a pointer to a two-dimensional array of integers. This would only be useful when you purposely want to allocate the space in the heap instead of in the stack (for example, if the dimensions of the array are unknown at compile time) You would then dereference the pointer and access it as you would with a normal two-dimensional array.

You could skip the dereferencing step by declaring your variable as an array of pointers, each one of them pointing to a standard array of integers int *a[SIZE], or even as int **a. In both cases you could access any value using bracket notation a[x][y] without needing to dereference a before.

If you know the dimensions of the array prior at compilation time, and don't need to allocate it in the heap, you can just declare the array like this:

int a[SIZE][SIZE];

which is both shorter and more efficient as it allocates the space in the stack.

You can always access an array using [][]. You have to keep in mind that everything in C works with memory address offsets. When you have an integer array declared as int a[4] and you access it with square brackets like this a[3] you're telling the processor to take the memory address of a and apply an offset of 3 * sizeof(int). You could access the same element by using *(&a + 3), or even with 3[a], as taking the address and adding the offset is the same as taking the offset and adding the address.

So when you use a[2][3], the compiler is doing exactly the same as above, only with more dimensions. So you don't need to do a[x * SIZE + y] because that's exactly what the compiler is doing for you when you do a[x][y].

EDIT: as some pointed out in the comments, actually pointers don't necessarily store a memory reference, altough that's definitely the most common implementation.

I hope my explanation was clear.

Answer 4

int (*a)[SIZE][SIZE] is an array pointer to an array of type int[SIZE][SIZE]. This is a special kind of pointer that is used to point at whole arrays, but otherwise works like any other pointer. So when you write (*a)[i][j] you say "give me the contents of the pointer (the 2D array), then in those contents give me item number [i][j]".

But since array pointers behave like other pointers, you can use it point to the first element instead of the whole 2D array. (Just like you can use int* to point at the first item of an int[n] array.) This is done using the trick of omitting the left-most dimension: int (*a)[SIZE] = .... This now points to the first 1D array in the array of arrays. And now you can use it as a[i][j] instead, which is far more readable and convenient.

Array pointers, the above trick, and how to use them to dynamically allocate 2D arrays as one single chunk of memory is all addressed in my answer to Correctly allocating multi-dimensional arrays.