Question about multidimensional arrays

Question

I was wondering something about the multidimensional arrays and then I got a doubt about a concept, specifically about their representation on memory.

For example, an array can be defined as follows.

int a[3];

And this is represented as this.

Where each element is an int and all of them are in a continuous memory space.

Then a multidimensional array can be define as this.

int a[2][4];

Which is typically represented as.

But a more realistic representation of this array in memory wouldn't be something like this? (by analogy with the first image).

Because I was thinking that if, for example, int a[5]; defines 5 integers in a space of continuous memory, then int a[5][10]; defines 10 arrays of ints in a space of continuous memory, where each array define 5 integers, then any N-dimensional static array in C should be represented only as a strip of memory.

Answer 1

You're nearly right, yes. In fact,

int a[5][10];

declares 5 arrays each of which contain 10 integers, rater than the other way round. Other than that you're completely right.

See http://en.m.wikipedia.org/wiki/Row-major_order for a more detailed description and an explanation of why the order is important.

Answer 2

In addition to Jules' answer, I would like to add a bit of historical perspective.

The counter-intuitiveness of this in C is due to the simple fact:

• In general, int a[] (length unspecified) is some sort of syntactic sugar in place of int* a
• Likewise, int a[][] (again, lengths unspecified) is some sort of syntactic sugar in place of int** a.

Because the two-level pointer must be dereferenced in that order, it determines how a int a[M][N] would have to be laid out in memory.

Answer 3

Here's some code that clearly shows memory layout for arrays. Using a union, for which memory is overlaid for each union member, we can see that values are stored in row-major order.

#include <stdio.h>

#define N       4*4*4
#define N_2D    8
#define N_3D    4

union multi_d_arrays {
    int one_d[N];
    int two_d[N_2D][N_2D];
    int three_d[N_3D][N_3D][N_3D];
};

int main()
{
    int i, j, k;
    union multi_d_arrays m;

    /* initialise via one_d with sequential ints */
    for (i=0; i<N; i++)
        m.one_d[i] = i+1;

    /* in all cases the output should be sequential */
    printf("------------------------\n");
    for (i=0; i<N; i++)
        printf("m.one_d[%d] = %d\n", i, m.one_d[i]);

    printf("\n------------------------\n");
    for (i=0; i<N_2D; i++)
        for (j=0; j<N_2D; j++)
            printf("m.two_d[%d][%d] = %d\n", i, j, m.two_d[i][j]);

    printf("\n------------------------\n");
    for (i=0; i<N_3D; i++)
        for (j=0; j<N_3D; j++)
            for (k=0; k<N_3D; k++)
                printf("m.three_d[%d][%d][%d] = %d\n", i, j, k, m.three_d[i][j][k]);

    return 0;
}