How an n-dimensional (n>=2) array is represented in memory?

Question

Can anyone provide me with a formula so that I can understand the memory representation of an n-dimensional(n>=2) array like this "How_are_two-dimensional_arrays_represented_in_memory"?

This calculation is applicable for 2D-arrays only.

How to calculate, suppose, a 5D array?

Ok....

I think I found the answer: Array_data_structure#Two-dimensional_arrays

Answer 1

A 2-dimensional array in C is nothing more or less than an array of arrays. A 3-dimensional array is an array of arrays of arrays. And so on.

The relevant section from the C99 standard is 6.5.2.1, "Array subscripting":

Successive subscript operators designate an element of a multidimensional array object. If E is an n-dimensional array (n ≥ 2) with dimensions i × j × . . . × k, then E (used as other than an lvalue) is converted to a pointer to an (n − 1)-dimensional array with dimensions j × . . . × k. If the unary * operator is applied to this pointer explicitly, or implicitly as a result of subscripting, the result is the pointed-to (n − 1)-dimensional array, which itself is converted into a pointer if used as other than an lvalue. It follows from this that arrays are stored in row-major order (last subscript varies fastest).

Some confusion is caused by the fact that the indexing operator is defined in terms of pointer arithmetic. This does not imply that arrays are "really pointers" -- and in fact they very definitely are not. Declaring an array object does not create any pointer objects at all (unless of course it's an array of pointers). But an expression that refers to the array usually (but not always) "decays" to a pointer to the array's first element (that's a pointer value, not a pointer object).

Now simple array objects, of however many dimensions, are quite inflexible. Prior to C99, all array objects had to be of a fixed size determined at compile time. C99 introduced variable-length arrays (VLAs), but even so a VLA's size is fixed when it's declared (and not all compilers support VLAs, even 12 years after the C99 standard was issued).

If you need something more flexible, a common approach is to declare a pointer to the element type, and then allocate an array using malloc() and have the pointer point to the array's first element:

int *ptr = malloc(N * sizeof *ptr);
if (ptr == NULL) /* handle allocation failure */

This lets you refer to elements of the heap-allocated array using the same syntax you'd use for a declared fixed-size array object, but in arr[i] the expression arr decays to a pointer, whereas in ptr[i] `ptr is already a pointer.

The same thing can be extended to higher dimensions. You can allocate an array of pointers, and then initialize each pointer to point to the beginning of an allocated array of whatever.

This gives you something that acts very much like a 2-dimensional (or more) array, but you have to manage the memory yourself; that's the price of the greater flexibility.

Strictly speaking, this is not a 2-dimensional array. A 2-dimensional array, as I said above, is only an array of arrays. It's probably not entirely unreasonable to think of it as a 2-D array, but that conflicts with the usage in the C Standard; it's similar to referring to a linked list as a 1-D array.

The comp.lang.c FAQ is a good resource; section 6, which covers arrays and pointers, is particularly excellent.

Answer 2

How arrays are stored in memory for C is not, as I recall, standardized. But for some information about arrays, and how they might be stored in memory, see the following two links:

http://webster.cs.ucr.edu/AoA/Windows/HTML/Arraysa2.html

http://publications.gbdirect.co.uk/c_book/chapter5/arrays.html

The first link is more general, and discusses different ways of storing arrays, while the second discusses the most likely way a C array may be layout in memory.

Answer 3

A 2 dimensional array is really an array of pointers to arrays. A 2-dimensional array of integers a[i][j] will take up i*sizeof(int*) for the array of pointers, and i*j*sizeof(int) for the final array.

A 3-D array a[i1][i2][i3] is an array of pointers to arrays of pointers to arrays. The first level of arrays contains i1 pointers, the second level contains i1*i2 pointers, the third level contains i1*i2*i3 integers.

In general, an N-dimensional array with sizes i1..iN will have N-1 levels of arrays of pointers and 1 level of arrays of ints. The arrays in level N have length iN and there are product of i1..iN-1 arrays in that level.

So, a 5-D array:

1 array, length i1, of pointers
i1 arrays, length i2, of pointers
i1*i2 arrays, length i3, of pointers
i1*i2*i3 arrays, length i4, of pointers
i1*i2*i3*i4 arrays, length i5, of ints

Hope that helps (and I hope I got the indices right).

That wikipedia link you posted refers to a /different kind of multidimensional array/. By default, C multidimensional arrays are the way I just described. You can also abstract them as a single dimensional array. This saves memory and makes the entire array contiguous, but it makes accessing elements somewhat more complex. For the 5-D example:

// WARNING I AM CHANGING NOTATION. N1..N5 are the lengths in each direction.
// i1..i5 are the indicies.
int* bigarray = malloc(sizeof(int)*N1*N2*N3*N4*N5);
// now instead of bigarray[i1][i2][i3][i4][i5], write this:
*(bigarray + i1*N2*N3*N4*N5 + i2*N3*N4*N5 + i3*N4*N5 + i4*N5 + i5);

each term there is an offset times the number of elements we need to offset. For example, to increment by one first-dimension level we need to traverse the the four remaining dimensions once to 'wrap around', if you will.