What is the difference between a 2D array and an array of arrays?
I have read comments, such as @Dave's, that seem to differentiate between the two.
This breaks if he's using 2d arrays, or pointer-to-array types, rather than an array of arrays. – Dave
I always thought that both referred to:
int arr_arr[][];EDIT: @FutureReader, you may wish to see How do I use arrays in C++?
25 Answers
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 freedfree(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.
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;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!
5The following is a 2D array that can be called an array of arrays:
int AoA[10][10];The following is a pointer to a pointer that has been set up to function as a 2D array:
int **P2P = malloc(10 * sizeof *P2P);
if(!P2P) exit(1);
for(size_t i = 0; i < 10; i++) { P2P[i] = malloc(10 * sizeof **P2P); if(!P2P[i]) { for(; i > 0; i--) free(P2P[i - 1]); free(P2P); } }Both can be accessed via AoA[x][y] or P2P[x][y], but the two are incompatible. In particular, P2P = AoA is something that newbies sometimes expect to work, but will not - P2P expects to point to pointers, but when AoA decays into a pointer, it is a pointer to an array, specifically int (*)[10], which is not the int ** that P2P is supposed to be.
2d array can include this:
int x[width * height]; // access: x[x + y * width];From Wikipedia:
6For a two-dimensional array, the element with indices i,j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.
