Can someone explain to me why technically a 2D array does not actually decay to int** whereas when you have a single dimensional array, you do get pointer decay to int* (if you had array of int).
I understand what pointer decay is, but I don't get why the 2D array doesn't exhibit this decay?
It's a common confusion with people new to C or C++, but I find myself tripping over it often too.
They have different memory layouts. A 2D array is one contiguous piece of memory while int** is an array of pointers. With a 2D array, the offset into a location is computed as rownum * collength + colnum (or vice versa depending on how you label rows/columns). That would not work with int**, which actually produces two memory reads; the first to get the column pointer, then the read of the data at an offset from that memory.
This different layout is, incidentally, why you must declare the array dimensions (all but the left-most) in functions that accept 2D arrays; otherwise it would not be possible for the compiler to generate the code to compute the offsets.
The following is an attempt at a picture of the memory layout of int**. The left column is a contiguous array of pointers where each contains the address of a contiguous piece of memory with the data. Note that the data in each column does not have to be the same length (although that might not necessarily be a good thing for code readability):
int **array;
int i, j;
int cntr = 1;
array = malloc( 3 * sizeof( int* ));
for ( i = 0; i < 3; i++ ) {
array[i] = malloc( 4 * sizeof( int ));
for ( j = 0; j < 4; j++ )
array[i][j] = cntr++;
}
Gives something like this:
array ==> |addr1| ==> [1,2,3,4]
|addr2| ==> [5,6,7,8]
|addr3| ==> [9,10,11,12]
In contrast, This is what the layout might look like for int[3][4]. The brackets just show the logical break of each column of data. The integer values are contiguous in memory:
int array[3][4];
int i, j;
int cntr = 1;
for ( i = 0; i < 3; i++ )
for ( j = 0; j < 4; j++ )
array[i][j] = cntr++;
Gives something like this:
array ==> [1,2,3,4][5,6,7,8][9,10,11,12]
The pattern is that an expression of type "N-element array of T" will be converted to an expression of type "pointer to T". If T is an array type, then you wind up with a pointer to an array. Given a declaration like
T arr[M][N];
the expression arr has type "M-element array of N-element arrays of T". Except when it is the operand of the sizeof, _Alignof, or unary & operators, it will be converted to an expression of type "pointer to N-element array of T", or T (*)[N].
When in doubt, write out the type in English, such as "four-element array of five-element arrays of six-element arrays of int", then replace the first "n-element array of" with "pointer to", giving "pointer to 5-element arrays of 6-element arrays of int":
Declaration Expression Type Decays to
----------- ---------- ---- ---------
int arr[4][5][6]; arr int [4][5][6] int (*)[5][6]
arr[i] int [5][6] int (*)[6]
arr[i][j] int [6] int *
&arr int (*)[4][5][6] n/a
The result of converting a two-dimensional array to a pointer to its first element is a pointer, not an array. Since it is not an array, it is not converted further.
It does decay. An expression whose type is "array of T" decays into a pointer to its first element. For a 2-dimensional array of T, the first element has type array of T. So:
int arr[5];
In most contexts, arr has type "pointer to int". Now apply the same rule to a 2-dimensional array:
int arr2[5][5];
Here, arr2 has type "pointer to array of 5 int". Note that the type of this object is not "array of T", so it does not decay further.
It is common mistake that one might think that if int* i == int i[5] than int** i == int i[5][5] but it is not like that that for two reasons. First an int** is a pointer to a pointer and has nothing to do with the ways arrays are laid out and secondly a 2D array is actually 1D array internally and what it does is lay the second arrays side by side.
That means that in an array of [2][2] internally is creating an array of [4] and when you try and access [0][0] than that gets translated to [0], [0][1] will get translated to [1], [1][0] will get translated to [2] and [1][1] will get translated to [3]
Example:
#include <iostream>
void Print(int* i, int element)
{
std::cout << i[element] << std::endl;
}
int main()
{
int i[5][5];
i[2][2] = 125;
Print((i[0]), 12);
}
This will print 125 because I set [2][2] as 125 and that will be consider as equal to 12 because the first [0] will occupy from 0 - 4, [1] will occupy from 5-10 and so on and so forth.
A two-dimensional array is an array of arrays.
An "array of T" is - in most contexts - converted to a "pointer to T, so an "array of T[N]" is converted to a "pointer to T[N]".
Since the memory representation of an
int arr[M][N];
is completely different from
int **dptr = malloc(M*sizeof *dptr);
for(int i = 0; i < M; ++i) {
dptr[i] = malloc(N*sizeof *dptr[i]);
an int[M][N] cannot even be converted to an int**.
A 2D array is a contiguous block of memory. When accessing it as a 2D array you need row length to jump from column to column. A pointer to a pointer is exactly that. It can simulate a 2D array if the first pointer is an array of pointers to a second dimension of arrays but it is a very different beast to the contiguous block of memory that a 2D array is.
