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).

Answer 2

I would expect multidimensional arrays to offer operations such as "Give me the number of dimensions" or "Give me a certain column" or "Give me a certain sub-view". C arrays don't offer these operations.

Answer 3

From Wikipedia:

Multi-dimensional arrays

The number of indices needed to specify an element is called the dimension, dimensionality, or rank of the array type. (This nomenclature conflicts with the concept of dimension in linear algebra,[5] where it is the number of elements. Thus, an array of numbers with 5 rows and 4 columns, hence 20 elements, is said to have dimension 2 in computing contexts, but represents a matrix with dimension 4-by-5 or 20 in mathematics. Also, the computer science meaning of "rank" is similar to its meaning in tensor algebra but not to the linear algebra concept of rank of a matrix.)

Many languages support only one-dimensional arrays. In those languages, a multi-dimensional array is typically represented by an Iliffe vector, a one-dimensional array of references to arrays of one dimension less. A two-dimensional array, in particular, would be implemented as a vector of pointers to its rows. Thus an element in row i and column j of an array A would be accessed by double indexing (A[i][j] in typical notation). This way of emulating multi-dimensional arrays allows the creation of ragged or jagged arrays, where each row may have a different size — or, in general, where the valid range of each index depends on the values of all preceding indices.

This representation for multi-dimensional arrays is quite prevalent in C and C++ software. However, C and C++ will use a linear indexing formula for multi-dimensional arrays that are declared as such, e.g. by int A[10][20] or int A[m][n], instead of the traditional int **A.[6]:p.81

For an example of a language supporting multidimensional arrays, see here.

Answer 4

C does not have multidimensional arrays but C have arrays of arrays.

In the Standard, the wording multidimensional array is used but C multidimensional arrays are in reality arrays of arrays. From Kernighan & Ritchie:

"In C, a two-dimensional array is really a one-dimensional array, each of whose elements is an array."

Some languages support multidimensional arrays as first class types. The "Expert C Programming" book shows the example of Ada which supports both arrays of arrays and multidimensional arrays.

Answer 5

I get his point. He actually differ them from implementation point of view, but both are actually valid to be said multidimensional arrays.

The "array of array" kind uses linear indexing as it's actually implemented as one dimensional array, despite at language level it's referenced via multiple index. Ex, in C:

int a[5][5];

would actually have the same structure as:

int a[25];

The compiler would translate an access such as:

a[i][j]

to:

a[i * jDimensionWidth + j]

where jDimensionWidth = 5 in above example. And it's even possible to access it like:

int* b = (int*) a;
printf("%d\n",b[12] == a[2][2]); // should output 1

The "multidimensional array" kind is implemented through Iliffe vector as he said, where the indexing can't be linearized because the address is not linear as well since the vector is typically implemented as heap object. This kind of multidimensional array doesn't fit the equation (for 2-dimensional array):

addr(a[i + 1]) = addr(a[i]) + (a[i].width * sizeof(a[i][j].datatype))

which is fulfilled by the "array of array" kind.