Why is dimension range of higher dimensions in multi-dimensional array required?

Question

As per the post,

Passing a 2D array to a C++ function

int array[10][10];
void passFunc(int a[][10]) //  <---Notice 10 here
{
    // ...
}
passFunc(array);

Why is this higher dimension required from compilers internal point of view.

Answer 1

An alternative explanation (to array-to-pointer decay):

Let's say we have a one-dimensional array, and we use it like this:

int array[10];
int i = array[3];

The compiler has to know where to find array[3]. It knows it needs to skip 3 ints before it can get to the one in array[3]. So it works.

But if we have a two-dimensional array,

int array[2][5];
int i = array[1][1];

To get i here, how many ints does the compiler need to skip? It needs to skip an entire row, plus one. To skip one is easy, since we know the size of one int. But we also need to know the size of the row in the array—and the size of the row is determined by the size of the type * number of columns per row. This is one way of looking at it, which explains why you need the latter dimension.

Let's make this a small brain teaser by taking it one dimension further, to

int array[2][2][2];
int i = array[1][1][1];

and let's call the dimensions X, Y, Z.

Here, we can say we have a finite 3D space of ints. The unit is of course the size of one int. The number of rows is defined by Y, the number of planes is defined by Z. That leaves X as the basic unit, which is the size of one int, as we said. The combination of the three yields a "point."

To be able to get to any point in that 3D space, we need to know where each dimension "stops" and the next one begins. So we need:

1. The size of the unit (int), to traverse the X dimension
2. The size of each plane (Y), to traverse the Y dimension
3. The number of planes, to traverse the Z dimension

So again, X is already given to us, because we're using int. But we don't know the size of each plane, nor do we know how many planes there are. So we need to specify all but the first dimension. And that's the general rule.

This also explains why this issue invites a bit more elaborate explanation than mere pointer decay, because once you get to more than 2 dimensions, you still need to know how this works. In other words, you need the overall size (product of dimensions) to not overflow, and you need the dimension of each size to be able to use successive [] indices.

Answer 2

Arrays in C/C++ are a type, but not a first-class object and they "decay" into a pointer to the first element when passed to functions.

An int[10][10] is an array of 10 int[10] arrays... the function declarations:

void foo(int x[][10]);

typedef int IntArray10[10];
void bar(IntArray10 *x);

are for the compiler identical.

When passing a 2d array to a function therefore you're passing a pointer to the first element (and the first dimension is ignored) but the element itself is an array and the compiler needs to know its size.

Answer 3

Contrary to what you might think from the "[]" in the parameter int a[][10], the function doesn't take a two-dimensional array but a pointer to a one-dimensional array - its prototype is equivalent to

void passFunc(int (*a)[10])

array can decay into a pointer to its first element, like all arrays.
That pointer is, as usual, &array[0], and in this case it is a pointer to an array with ten ints - an int (*)[10].

So it's not that you need to specify the "higher dimension", it's that the parameter is a pointer to an array of ten elements and not a two-dimensional array at all.

(You can't have a be a pointer to an array of unspecified size because the compiler needs to know where a[1] is located in relation to a[0], i.e. it needs to know sizeof(*a).)

Answer 4

It is required because in C doesn't exist the concept of multidimensional array.
We can define an array of anything, even another array. The last could be seen as a multidimensional array.
Now consider a bidimensional array as:

int arrray[5][4];

This is to be interpreted as an array of 5 elements, each one being an array of 4 int.
In memory the layout is sequential: first the 4 elements of the first array, then the second and so on up to the 5th array of 4 elements.
To access the 2nd element of 3rd array array[2][1] the compiler have to skip the first 2 arrays, but to do so needs to know how many elements to skip.
I.e. mathematically the address of the 2nd element of the 3rd array is:

//pElement2Array3  points the 2nd element of the 3rd array.
//Note that 4 is the number of elements of the base dimension
int *pElement2Array3 = &array[0] + (2 * 4) + 1;

(Note: the term (2 * 4) + 1 is not multiplied by the sizeof(int) because this is done automatically by pointer arithmetic.)
The math above is automatically performed by the compiler when using the addressing array[2][1], but to execute it the compiler have to know how many elements are in the base array (that could be ana array of array of array...).

Answer 5

Simply put, because multi-dimensional arrays "grow" from right to left. Think of it like this:

int arr [a]; is an array of a integers.

int arr [b][a] is an array of b arrays of a integers.

And so on.

As for why you can omit the left-most dimension when passing an array to a function, it is because of "array decay". 6.7.6.3/7 says:

A declaration of a parameter as ‘‘array of type’’ shall be adjusted to ‘‘qualified pointer to type’’

That is, if you declare a function parameter as int param[10] or int param[], it gets silently/invisibly replaced by the compiler with a pointer to int: int* param, which points at the first element of the array. The array itself remains allocated by the caller.

It works like this to prevent arrays from getting passed to functions by value, which would be very ineffective and in most cases doesn't make any sense.

Now for the case of multi-dimensional arrays, the same rule above applies. So if you have int param[10][10] it decays into a pointer to the first element. The first element is an array of 10 integers, so you get an array pointer to an array of 10 integers: int (*param)[10].

The very same would happen if you have int param[][10], you would still get a int (*param)[10]. So the left-most dimension could be anything - it doesn't matter since it is ignored anyhow.

But the other dimensions following the left-most are required, or otherwise the compiler wouldn't know which pointer type that the array would decay into. Outside the special case of function declarations, there is no such thing as int(*param)[] which would mean "an array pointer to an array of unknown size".

Answer 6

As a function parameter int a[][10] is equivalent to int (*a)[10], means : a is a pointer to an array of 10 int. It doesn't represent a 2D array in this case.

If the higher dimension left blank then it is not possible for the compiler to know the length of array the pointer a is pointing to and pointer arithmetic can't be performed.