c - What's the difference between arrays of arrays and multidimensional arrays?

Question

I had a language-agnostic discussion with someone in the C++ chat and he said that arrays of arrays and multidimensional arrays are two things.

But from what I learned, a multidimensional array is nothing more than an array of other arrays that all have the same size. In particular he is saying

Well, they kind of are in C, where you simulate multiple dimensions with nested arrays but that’s only because C doesn’t actually support multiple dimension arrays

Can someone please explain what the canonical computer-science definition of "multiple dimension arrays" is and why C (or the abstract definition "array of arrays") does not fit that definition?

Answer 1

Take .NET arrays which illustrate this nicely:

C# has a distinction between jagged arrays which are defined in a nested fashion:

int[][] jagged = new int[3][];

Each nested array can have a different length:

jagged[0] = new int[3];
jagged[1] = new int[4];

(And note that one of the nested arrays isn’t initialised at all, i.e. null.)

By contrast, a multidimensional array is defined as follows:

int[,] multidim = new int[3, 4];

Here, it doesn’t make sense to talk of nested arrays, and indeed trying to access multidim[0] would be a compile-time error –?you need to access it providing all dimensions, i.e. multidim[0, 1].

Their types are different too, as the declarations above reveal.

Furthermore, their handling is totally different. For instance, you can iterate over the above jagged array with an object of type int[]:

foreach (int[] x in jagged) …

but iterating over a multidimensional array is done with items of type int:

foreach (int x in multidim) …

Conceptually, a jagged array is an array of arrays (…?of arrays of arrays … ad infinitum) of T while a multidimensional array is an array of T with a set access pattern (i.e. the index is a tuple).