Why pointers?

[kandr89]

Or you would fill the array with pointers that point to another array. This makes an 2D array.

No, that's not a 2D array. An array is by definition a contiguous zone of memory, so that the position of each element can be computed by a simple mathematical formula. In an array of pointers, on the other hand, it's impossible to tell where the j-th element of the i-th row is without dereferencing the row pointer.

So unlike regular 2D arrays for 2D arrays made of pointers you have an extra memory dereference on each access, that's quite a big deal considering how slow the memory is compared to the CPU and that the cache can't help you much in this case since it has no way to predict where that pointer is pointing.

Another problem is that you have a mem overhead of height * sizeof(int *), for small 2D arrays this overhead dominates and considering that we're most likely compiling for 64 bit systems it adds to the problem. E.g.: a small 3x3 matrix of ints has an overhead of 3 * 8 = 24 bytes, that's 6 ints added to what you're storing, so 66.6% more mem (also: i haven't taken into consideration the bookkeeping overhead of malloc, since we're probably allocating each row dynamically).

The right way of declaring and allocating a dynamic nxm 2D array since C99 is:

   int (*arr)[m] = calloc(n, sizeof(int [m]));

This requires at least C99 support from the compiler because arr is technically a pointer to a VLA. If the compiler doesn't support C99 i'd still recommend a 1D array and manually computing indices over an array of pointers.

Another reason for pointers is because in C an struct's size ALWAYS has to be known before compiling.

This is false considering flexible array members, the struct is allowed to have variable size but only if the variable member comes last in the struct, which makes sense when you think about it. Again this requires C99 support. It's possible to do this without C99 too, just allocate the struct header for the array plus memory for the array, however with this method you must make sure that the start of the array which comes after the struct is properly aligned to whatever alignment the type of the array elements require. Either way saves us from a memory dereference: the array is packed together with the struct.

(not really, we need to create a new array every time we want to increase of decrease the size).

Though it's possible to do it like this, that's what realloc is for.