Friday, 15 February 2013

Multi-dimensional array in C/C++

At a low level, there is no such thing as a multi-dimensional array. There is just a flat block of memory, large enough to hold a given number of elements. In C, a multi-dimensional array is conceptually an array whose elements are also arrays. So if you do:
int array[2][3];
Conceptually you end up with:
array[0] => [0, 1, 2]
array
[1] => [0, 1, 2]
This results in the elements being arranged contiguously in memory, because array[0] and array[1] are not actually holding any data, they are just references to the two inner arrays. Note that this means that only the [0, 1, 2] entries actually occupy space in memory. If you extend this pattern out to the next dimension, you can see that:
int array[2][3][2];
...will give you a structure like:
array[0] => [0] => [0, 1]
            [1] => [0, 1]
            [2] => [0, 1]
array[1] => [0] => [0, 1]
            [1] => [0, 1]
            [2] => [0, 1]
Which continues arranging the elements consecutively in memory (as above, only the [0, 1] entries actually occupy space in memory, everything else is just part of a reference to one of these entries). As you can see, this pattern will continue no matter how many dimensions you have.

And just for fun:
int array[2][3][2][5];
Gives you:
array[0] => [0] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [1] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [2] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
array[1] => [0] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [1] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
            [2] => [0] => [0, 1, 2, 3, 4]
                   [1] => [0, 1, 2, 3, 4]
What is the meaning of int (*p)[5], char *x[3][4], int *(*a[10])() and int (*t[])() ?
Ans :
int (*p)[5] : A pointer to an array of 5 integers.char *x[3][4] : x is an composed of "3 arrays of 4 pointers to character".int *(*a[10])() : An array of 10 pointers to functions returning an integer pointer.int (*t[])() : An array of pointers to function returning an integer pointer.