Pointers and Multidimensional Arrays in C language

In the previous lesson we saw that an array in C language is stored in memory as a block of contiguous cells. We also saw that the name of an array is actually a pointer to the first element of the array. Therefore there exists a close relationship between arrays and pointers.

In this lesson we will go further and see how to use pointers to process the elements of a multidimensional array in C language.

Processing the elements of a multidimensional array

We saw in the lesson on multidimensional arrays that C language stores multidimensional arrays in memory as a one-dimensional array. In particular, they are stored by rows.

This means that the elements of row 0 are stored in sequence, followed by the elements of row 1, and so on.

Let's take, for example, a two-dimensional array of m rows and n columns. From a logical point of view the array has the following shape:

However, in memory the array is stored as a one-dimensional array of m * n elements. In particular, the array is stored by rows, that is the elements of row 0 are stored in sequence, followed by the elements of row 1, and so on. The corresponding one-dimensional array has the following shape:

In other words, a multidimensional array is flattened into a one-dimensional array.

When we work with pointers to multidimensional arrays we can take advantage of this behavior.

In fact, if we take a pointer that points to the element in row 0 and column 0, that is the first element of the array, we can increment the pointer to access all subsequent elements.

To clarify how to do this, let's take an example. We have defined a two-dimensional array in this way:

int a[NUMBER_ROWS][NUMBER_COLUMNS];

We want to initialize all the elements of the array to 0. The first most obvious technique we can use is to employ two nested for loops, like this:

/* Initialization of a Two-dimensional Array */
int row, column;

for (row = 0; row < NUMBER_ROWS; row++)
    for (column = 0; column < NUMBER_COLUMNS; column++)
        a[row][column] = 0;

However, we can obtain the same result using only one for loop and a pointer.

We can, in fact, rewrite everything like this:

int *p;

for (p = &a[0][0]; p <= &a[NUMBER_ROWS - 1][NUMBER_COLUMNS - 1]; p++)
    *p = 0;

The loop starts by assigning to p the address of the first element of the array, that is &a[0][0].

The subsequent increments of the pointer p move the address contained in it first to the element a[0][1], that is the second element of the first row, then to the element a[0][2], then to the element a[0][3], and so on.

When p reaches the element a[0][NUMBER_COLUMNS - 1], that is the last element of the first row, the loop increments p and moves it to the element a[1][0], that is the first element of the second row. This happens precisely because the array is flattened in memory.

The loop continues to increment p until it reaches the last element of the array, that is a[NUMBER_ROWS - 1][NUMBER_COLUMNS - 1]. The flattening in memory makes the last element of the array actually the last element of the flattened one-dimensional array.

This example leads us to an important consequence:

type array[m][n];
type *p = array;

int k = i * n + j;
p[k];

Furthermore, we also have a second important consequence:

type array[m][n];
type *p = array;

/* ERROR */
p[i][j];

Knowing the fact that a multidimensional array is stored in memory as a one-dimensional array is an important concept for working with pointers to multidimensional arrays. Furthermore, in some cases it can be useful to optimize the code.

Processing the rows of a multidimensional array

We have seen that a multidimensional array is flattened in memory, therefore, from the point of view of memory and processor, it is effectively a one-dimensional array.

But how can we process a single row of a multidimensional array? We can do it using a pointer.

In particular, suppose we have a two-dimensional array a of dimensions m rows and n columns:

int a[m][n];

We can create a pointer p that points to row i of array a like this:

int *p = a[i];

Or, equivalently:

int *p = &a[i][0];

The first expression works because essentially a[i] is a pointer to row i of array a. In fact, a[i] is equivalent to &a[i][0].

Furthermore, each row of the array is in turn an array, so a[i] is an array and can be treated as a pointer to the first element.

To convince ourselves that the two expressions above work, we just need to remember the relationship that links array indexing to pointer arithmetic. In fact it holds that:

a[i] == *(a + i)

That is, a[i] is equivalent to *(a + i), which is a pointer to row i of array a.

Once we have obtained the pointer p to row i of array a, we can process the elements of row i using a for loop that scrolls through all the elements of the row.

For example, suppose we want to zero all the elements of row i of array a. We can do it like this:

int *p = a[i];

for (int j = 0; j < n; j++)
    p[j] = 0;

Where n is the number of columns of array a.

The advantage of this approach is that we can treat the rows of a multidimensional array as one-dimensional arrays, and therefore we can eventually pass them to functions that expect a one-dimensional array.

For example, suppose we have a function find_maximum that finds the maximum of a one-dimensional array:

int find_maximum(int *array, int n) {
    int maximum = array[0];

    for (int i = 1; i < n; i++)
        if (array[i] > maximum)
            maximum = array[i];

    return maximum;
}

We can use this function to find the maximum of each row of a two-dimensional array a like this:

int maximums[m];

for (int i = 0; i < m; i++)
    maximums[i] = find_maximum(a[i], n);

Where m is the number of rows of array a.

Then, we can even find the maximum of all the row maximums by passing the array maximums to the function find_maximum:

int global_maximum = find_maximum(maximums, m);

type a[m][n];

type *p = a[i];

Processing the columns of a multidimensional array

Unlike rows, directly processing the columns of a multidimensional array is not as simple.

The reason lies precisely in the flattening in memory of multidimensional arrays. The flattening simplifies the processing of rows, but makes the processing of columns more complex.

There exists, however, a little trick that allows us to process the columns of a multidimensional array. But the syntax becomes more complicated. Let's see how to do it.

Suppose we have a two-dimensional array a of dimensions m rows and n columns:

int a[NUMBER_ROWS][NUMBER_COLUMNS];

We want to write a loop that, given the column index j as input, zeros all the elements of column j of array a.

The first method consists of using the scheme seen above. Knowing that the element in position i and j of array a is accessible through the index k = i * n + j, we can write a for loop like this:

/* j is the index of the column to zero */
int j;
int *p = a;

for (int i = 0; i < NUMBER_ROWS; i++)
    p[i * NUMBER_COLUMNS + j] = 0;

In this way, the loop scrolls through all the rows of array a and zeros the element in position i and j of the array.

The second way consists of using the following syntax:

/* j is the index of the column to zero */
int j;

int (*p)[NUMBER_COLUMNS] = a;

for (p = &a[0]; p < &a[NUMBER_ROWS]; p++)
    (*p)[j] = 0;

In this case, p is a pointer to an array of NUMBER_COLUMNS elements. Therefore, when we increment p, we increment the pointer by NUMBER_COLUMNS elements, that is by one row.

In this way, the loop scrolls through all the rows of array a and zeros the element in position i and j of the array.

The disadvantage of this approach is that the syntax is more complex compared to the first method and, furthermore, one must know in advance the number of columns of the array.

Pointers to Variable Length Multidimensional Arrays in C99

Starting from the C99 standard, it is possible to define variable length multidimensional arrays, that is arrays whose dimensions are calculated from an expression at runtime.

We can use pointers to point to these arrays but we must pay some attention.

In fact, when a variable length array has more than one dimension, the type of the pointer depends on the length of each dimension except the first.

Let's take the example of a two-dimensional array:

void function(int m, int n) {
    int a[m][n];
    int (*p)[n];

    p = a;

    /* ... */
}

In this case, p is a pointer to an array of n elements, that is a pointer to a single row of the array.

This code works because the variable n is used both to define the array a and to define the type of pointer p.

There is a detail, however, that is not immediately evident. The type of pointer p is int (*)[n], that is a pointer to an array of n elements. But this type is not fixed and depends, rather, on n. In this case we speak of variably modified type.

A variably modified type is a type whose meaning depends on a variable. In this case, the type int (*)[n] is a variably modified type because the number of columns n is a variable.

Although the C99 standard allows these types, compilers are not always able to verify the correctness of an assignment.

For example, the following code is compiled correctly but works only if m and n are equal:

int a[m][n];
int (*p)[m];

/* WORKS ONLY IF m == n */
p = a;

Otherwise, if m and n are different, the compiler does not signal any error but the program could behave unpredictably.

For this reason, variably modified types are allowed only in certain circumstances:

• They can be used only in the body of a function;
• Or, they can be used in the prototype of a function.

In other words, variables of this type can only be local variables.

As for the rest, pointers to variable length multidimensional arrays behave like pointers to static multidimensional arrays. Therefore, we can use pointer arithmetic in the exact same way.

For example, we can write a loop that scrolls through all the elements of a variable length multidimensional array and sets them to zero like this:

int m = 5;
int n = 3;
int a[m][n];

int *p = a;

/* Sets all elements of the array to 0 */
for (int i = 0; i < m * n; i++)
    p[i] = 0;

In Summary

In this article we have seen how to process the elements of a multidimensional array using pointers.

We have seen that a multidimensional array is stored in memory as a one-dimensional array. This characteristic is called flattening.

Through flattening, we can process the elements of a multidimensional array using only one for loop and a pointer.

Furthermore, we have seen how to process the rows of a multidimensional array using a pointer. We have seen that we can treat the rows of a multidimensional array as one-dimensional arrays.

This, however, is not possible for columns. However, we have seen a little trick that allows us to process the columns of a multidimensional array.