Why does int*[] decay into int** but not int[][]?

Question

I'm trying to understand the nature of type-decay. For example, we all know arrays decay into pointers in a certain context. My attempt is to understand how int[] equates to int* but how two-dimensional arrays don't correspond to the expected pointer type. Here is a test case:

std::is_same<int*, std::decay<int[]>::type>::value; // true 

This returns true as expected, but this doesn't:

std::is_same<int**, std::decay<int[][1]>::type>::value; // false 

Why is this not true? I finally found a way to make it return true, and that was by making the first dimension a pointer:

std::is_same<int**, std::decay<int*[]>::type>::value; // true 

And the assertion holds true for any type with pointers but with the last being the array. For example (int***[] == int****; // true).

Can I have an explanation as to why this is happening? Why doesn't the array types correspond to the pointer types as would be expected?

Answer 1

Why does int*[] decay into int** but not int[][]?

Because it would be impossible to do pointer arithmetic with it.

For example, int p[5][4] means an array of (length-4 array of int). There are no pointers involved, it's simply a contiguous block of memory of size 5*4*sizeof(int). When you ask for a particular element, e.g. int a = p[i][j], the compiler is really doing this:

char *tmp = (char *)p           // Work in units of bytes (char)           + i * sizeof(int[4])  // Offset for outer dimension (int[4] is a type)           + j * sizeof(int);    // Offset for inner dimension int a = *(int *)tmp;            // Back to the contained type, and dereference 

Obviously, it can only do this because it knows the size of the "inner" dimension(s). Casting to an int (*)[4] retains this information; it's a pointer to (length-4 array of int). However, an int ** doesn't; it's merely a pointer to (pointer to int).

For another take on this, see the following sections of the C FAQ:

• 6.18: My compiler complained when I passed a two-dimensional array to a function expecting a pointer to a pointer.
• 6.19: How do I write functions which accept two-dimensional arrays when the width is not known at compile time?
• 6.20: How can I use statically- and dynamically-allocated multidimensional arrays interchangeably when passing them to functions?

(This is all for C, but this behaviour is essentially unchanged in C++.)