What is the difference between a 2D array and an array of arrays?
I have read comments that seem to differentiate between the two:
int** arr = ...; cout << arr[i][j];This breaks if he's using 2d arrays, or pointer-to-array types, rather than an array of arrays. – @Dave
See also: How do I use arrays in C++?
There are four different concepts here.
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.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);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). 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.
malloc()), or statically (defined with the static keyword or outside any function). I think what you mean is that the size is fixed at compile time -- though with C99 variable-length arrays, that's not entirely true either.arr[x][y] syntax to access individual elements. The difference is in whether the prefix of each [] operator is a pointer expression or an array expression that decays to a pointer. There are 4 combinations. (For 3-d array-like structures, there are 8 combinations; for N dimensions, there are 2**N.)
malloc()? You need a pointer-to array for that.int (*p)[10][10] = malloc(sizeof *p);. Or, perhaps more legibly: typedef int matrix[10][10]; matrix *p = malloc(sizeof *p);.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;
int (*x)[10];, which is a good trick to turn a flat array into a 2D array that can be indexed with [x][y] instead of [x * width + y].2D array != array of arrays. (Not just Dave.) Originally, only the first line in this answer was present; the other stuff was later edited on.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!
The 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:
For 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.
int arr_[width * height]; int (*arr)[width] = (void *)arr_; arr[x][y] = 0;
x[7*3] is same as index of x[3*7] so you are storing just half of the possible data and will loose the other half or overwriting the first half. So consider using it like so x[7*widthIndexlength+3].