How is a multi-dimensional array defined in terms of a pointer?

Answer 1

Yes. More specifically, they can be used to represent a dynamic multi-dimensional array.

As most people know, for a one-dimensional dynamic array, you simply need a pointer to the first element in the array, where each element contains an object of the same type as the pointer. The pointer can be passed around functions just as if it were a static array, the only difference being the requirement to pass the upper bound of the array as well as the array itself.

For a two-dimensional array, you need a pointer-to-pointer which points to the first element of a one-dimensional pointer array, where each pointer in that array points to a one-dimensional array of objects. The pointer-to-pointer must be the same type as the pointers and the objects.

For a three-dimensional array you need a pointer-to-pointer-to-pointer. And so on. Each additional dimension simply adds a new level of indirection, and a new level of one-dimensional pointer arrays.

Of course multi-dimensional arrays are only useful if every dimension is fully utilised and doesn't require too much in the way of resizing. If that is not the case, then you may get more efficient memory consumption from a vector of vectors (of vectors), which allows dynamic resizing at every level without having to copy existing elements. The downside is you lose the random access provided by the array.

Answer 2

Suppose we want a 3x4x5 array of integers. First we allocate three arrays, one for each dimension:

int* p = malloc (3*4*5*sizeof(int));

int** pp = malloc (3*4*sizeof(int*));

int*** ppp = malloc (3*sizeof(int**));

Note that each array has an extra level of indirection. This is important!

The array pointed to by p is the actual array containing all the data, however it is one-dimensional. It has a length of 3x4x5=60 integers. The second array is also one dimensional and it will be used to hold 3x4=12 pointers. Each of these pointers will hold the start address of a group of 5 integers from the first array. The final array is also one dimensional and it will be used to hold 3 pointers. Each of those pointers will hold the start address of a group of 4 elements from the second array.

Before we can access the data array multi-dimensionally, we need to initialise the pointer arrays:

for (int index=0; index<3; ++index) {

ppp[index]=&pp[index*4];

}

for (int index=0; index<12; ++index) {

pp[index]=&p[index*5];

}

Now we can use the data array. Let's initialise the elements with the values 1 through 60:

int val=1;

for (int x=0; x<3; ++x) {

for (int y=0; y<4; ++y) {

for (int z=0; z<5; ++z) {

ppp[x][y][z] = val++;

}

}

}

Note that we access the array through ppp. We can also access the array through pp and p, however ppp is the only one that allows us to access the array using three-dimensional suffix notation.

Now let's print the elements. The simplest way to visualise a three-dimensional array is to imagine that it's really a one-dimensional array containing independent two-dimensional arrays. We can then print each of those two-dimensional arrays as a separate table:

for (int x=0; x<3; ++x) {

printf ("Table: %d\n", x);

for (int y=0; y<4; ++y) {

for (int z=0; z<5; ++z) {

printf ("%d\t", ppp[x][y][z]);

}

printf ("\n");

}

printf ("\n");

}

When we're finished with our arrays, we must clean up. It's always best to release resources in the reverse order they were allocated:

free (ppp);

free (pp);

free (p);