Doesn't a 2D array decay to pointer to pointer

Question

Up till now I was pretty much sure that

int arr[4][5];

Then arr will decay to pointer to pointer.

But this link proves me wrong.

I am not sure how did I get about arr being pointer to pointer but it seemed pretty obvious to me. Because arr[i] would be a pointer, and hence arr should be a pointer to pointer.

Am I missing out on something.

Answer 1

A simple rule is:

A reference to an object of type array-of-T which appears in an expression decays (with three exceptions) into a pointer to its first element; the type of the resultant pointer is pointer-to-T.

When you deal with 1D array, array name converts to pointer to first element when passed to a function.
A 2D array can be think as of an array of arrays. In this case int arr[4][5];, you can think arr[] as an array name and when passed to a function then converts to a pointer to the first element of array arr. Since first element of arr is an array, arr[i] is a pointer to ith row of the array and is of type pointer to array of 5 ints.

Answer 2

Yep you are missing out on a lot :)

To avoid another wall of text I'll link to an answer I wrote earlier today explaining multi-dimensional arrays.

With that in mind, arr is a 1-D array with 4 elements, each of which is an array of 5 ints. When used in an expression other than &arr or sizeof arr, this decays to &arr[0]. But what is &arr[0]? It is a pointer, and importantly, an rvalue.

Since &arr[0] is a pointer, it can't decay further. (Arrays decay, pointers don't). Furthermore, it's an rvalue. Even if it could decay into a pointer, where would that pointer point? You can't point at an rvalue. (What is &(x+y) ? )

Another way of looking at it is to remember that int arr[4][5]; is a contiguous bloc of 20 ints, grouped into 4 lots of 5 within the compiler's mind, but with no special marking in memory at runtime.

If there were "double decay" then what would the int ** point to? It must point to an int * by definition. But where in memory is that int * ? There are certainly not a bunch of pointers hanging around in memory just in case this situation occurs.

Answer 3

In general, a 2-dim array is implemented as an array of pointers (which, in a sense, is a pointer to a pointer... a pointer to the first element (i.e., pointer) in the array) When you specify the first index (i.e., arr[x]), it indexes into the array of pointers and gives the pointer to the x-th row. The the second index (i.e., arr[x][y]) gives the y-th int in that row.

In the case of a static declared array (as in your example), the actual storage is allocated as a single block ... in your example, as a single contiguous block of 20 integers (80 bytes, on most platforms). In this case, there IS no array of pointers, the compiler just does the appropriate arithmetic to address the correct element of the array. Specifically, arr[x][y] is equivalent to *(arr + x * 5 + y). This automatically-adjusted-arithmetic only happens in the original scope of the array... if you pass the array to a function, the dimension information is lost (just as the dimension is lost for a 1-dim array), and you have to do the array-indexing calculations explicitly.

To avoid this, do NOT declare the array as static, but as an array of pointers, with each pointer pointed to a 1-dim array, such as in this example:

int arr0[5];
int arr1[5];
int arr2[5];
int arr3[5];
int* arr[4] = { arr0, arr1, arr2, arr3 };

Then, when you pass arr to a function, you can address it as a 2-dim array within the function as well.