2D array vs array of arrays

The answer here is a little more subtle.

An array of arrays is defined as such:

int array2[][];

The pointer-to-array types are defined as:

int (*array2)[];

The array-of-pointer types are defined as:

int* array2[];

The compiler treats both of these a little differently, and indeed there is one more option:

int** array2;

A lot of people are taught that these three are identical, but if you know more about compilers you will surely know that difference is small, but it is there. A lot of programs will run if you substitute one for another, but at the compiler and ASM level things are NOT the same. A textbook on C compilers should provide a much more in depth answer.

Also, if one is interested in the implementation of a 2D array there are multiple methods that vary in efficiency, depending on the situation. You can map a 2D array to a 1D array, which ensures spacial locality when dealing with linearized data. You can use the array of arrays if you want the ease of programming, and if you need to manipulate the rows/columns separately. There are certain blocked types and other fancy designs that are cache-smart, but rarely do you need to know the implementation if you the user.

Hope I helped!

A 2 dimensional array is by definition an array of arrays.

What Dave was saying is that in that context, there are different semantics between the definition of a 2D array like this:

int x[][];

this:

int *x[];

or this:

int **x;

There are four different concepts here.

• The two-dimensional array: int arr[][]. It cannot be resized in any direction, and is contiguous. Indexing it is the same as ((int*)arr)[y*w + x]. Must be allocated statically.
• The pointer-to array: int (*arr)[]. It can be resized only to add more rows, and is contiguous. Indexing it is the same as ((int*)arr)[y*w + x]. Must be allocated dynamically, but can be freed free(x);
• The pointer-to-pointer: int **arr. It can be resized in any direction, and isn't necessarily square. Usually allocated dynamically, not necessarily contiguous, and freeing is dependent on its construction. Indexing is the same as *(*(arr+y)+x).
• The array-of-pointers: int *arr[]. It can be resized only to add more columns, and isn't necessarily square. Resizing and freeing also depends on construction. Indexing is the same as *(*(arr+y)+x).

Every one of these can be used arr[y][x], leading to the confusion.