1D array decays to pointer, but 2D array doesn't do so, why? [duplicate]

Question

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.

Answer 1

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]

Answer 2

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

Answer 3

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.

Answer 4

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.