What is the difference between arrays of arrays and multidimensional arrays?

Question

I had a language conversation with someone in a 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, all of which are the same size. In particular, he says

Well, they seem to be in C, where you are modeling multiple dimensions with nested arrays but this is only because C does not actually support arrays with multiple dimensions

Can someone explain what the definition of canonical computer science is for “arrays with many dimensions” and why C (or the abstract definition of “arrays of arrays”) does not fit this definition?

Answer 1

Take .NET arrays that illustrate this well:

C # has a distinction between gear arrays that are defined in a nested manner:

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 is not initialized at all, i.e. null .)

In contrast, a multidimensional array is defined as follows:

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

There is no point in talking about nested arrays, and indeed, an attempt to access multidim[0] will be a compile-time error - you need to access it by providing all sizes, i.e. multidim[0, 1] .

Their types are also different, as the above ads show.

In addition, their processing is completely different. For example, you can iterate over the above array with binding to an object of type int[] :

 foreach (int[] x in jagged) … 

but iterating over a multidimensional array is performed with elements of type int :

 foreach (int x in multidim) … 

Conceptually , an array with teeth is an array of arrays (... arrays of arrays ... ad infinitum) T , and a multidimensional array is an array T with a set of access patterns (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 specific column" or "Give me a specific subview." C do not offer these operations.

Answer 3

From Wikipedia:

Multidimensional Arrays

The number of indices needed to indicate an element is called the dimension, dimension, or rank of the array type. (This nomenclature contradicts the concept of dimension in linear algebra, [5], where is the number of elements. Thus, an array of numbers with 5 rows and 4 columns, and hence 20 elements, has dimension 2 in computational contexts, but is a matrix with dimension 4 by 5 or 20. In mathematics, the meaning of “rank” informatics is similar to that in tensor algebra, but not to the concept of linear matrix rank algebra.)

Many languages ​​support only one-dimensional arrays. In these languages, a multidimensional array is usually represented by the Iliffe vector, a one-dimensional array of references to arrays of one dimension smaller. A two-dimensional array, in particular, will be implemented as a vector of pointers to its rows. Thus, the element in row i and column j of array A will be accessible by double indexing (A [i] [j] in a typical record). This method of emulating multidimensional arrays allows you to create torn or jagged arrays, where each row can have a different size - or, in general, where the permissible range of each index depends on the values ​​of all previous indices.

This representation for multidimensional arrays is fairly common in C and C ++ software. However, C and C ++ will use a linear indexing formula for multidimensional arrays that are declared as such, for example. 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 that supports multidimensional arrays, see here .

Answer 4

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

The standard uses a multi-dimensional array of formulations, but multi-dimensional arrays of C are actually arrays of arrays. From Kernigan and Richie:

"In C, a two-dimensional array is indeed a one-dimensional array, each of which is an array."

Some languages ​​support multidimensional arrays as first class types. The Expert C Programming book shows an Ada example that supports both array arrays and multidimensional arrays.

Answer 5

I understand. It actually distinguishes them from the implementation point of view, but both are actually valid for multidimensional arrays.

The array array array uses linear indexing, since it is actually implemented as a single dimensional array, despite the level of the language to which it refers through several indices. Ex, in C:

 int a[5][5]; 

will have the same structure as:

 int a[25]; 

The compiler will translate access, for example:

 a[i][j] 

in

 a[i * jDimensionWidth + j] 

where jDimensionWidth = 5 in the above example. And you can even access it, for example:

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

The type "multidimensional array" is implemented through the Iliffe vector, as he said, where indexing cannot be linearized, because the address is not linear, since the vector is usually implemented as a heap object. This type of multidimensional array does not correspond to the equation (for a two-dimensional array):

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

which is executed as an "array array".