How are 3D arrays stored in C?

Question

I understand that arrays in C are allocated in row-major order. Therefore, for a 2 x 3 array:

0  1
2  3
4  5

Is stored in memory as

0 1 2 3 4 5

However, what if I have a 2 x 3 x 2 array:

0  1
2  3
4  5

and

6  7
8  9
10 11

How are these stored in memory? Is just consecutive like:

0 1 2 3 4 5 6 7 8 9 10 11

Or is it some other way? Or does it depend on something?

Answer 1

I think you have answered your own question. Multi-dimensional arrays are stored in row-major order.

See ANSI C specification section 3.3.2.1 (there is also a specific example):

Successive subscript operators designate a member of a multi-dimensional array object. If E is an n -dimensional array ( n =2) with dimensions i x j "x ... x" k , then E (used as other than an lvalue) is converted to a pointer to an ( n -1)-dimensional array with dimensions j "x ... x" 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).

For your example, you can just try it out and see - http://codepad.org/10ylsgPj

Answer 2

3d array is an extended 2d array.

For example we have an array - int arr(3)(5)(6);

This is an array which consists of two 2d arrays where array would have a 2d array having 4 rows and 3 columns.

Answer 3

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]

Answer 4

To answer OP's comment to the main question (it will be somewhat long, so I decided to go with an answer, not a comment):

Should arrays in C be declared as array[ny][nx] where ny and nx are the number of elements in the y and x direction. Furthermore, does that mean that my 3D array should be declared as array[nz][ny][nx]?

In math, a MxN matrix has M rows and N columns. A usual notation for a matrix element is a(i,j), 1<=i<=M, 1<=j<=N. So the first matrix in your question is a 3x2 matrix.

Indeed it is different from the notation typically used for e.g. GUI elements. A 800x600 bitmap has 800 pixels horizontally (along X axis) and 600 pixels vertically (along Y axis). If some would want to describe it as a matrix, in math notation it would be a 600x800 matrix (600 rows, 800 columns).

Now, multidimensional arrays in C are stored in memory in such a way that a[i][j+1] is next to a[i][j] while a[i+1][j] is N elements away. It is usually said that "the last subscript varies fastest", or often as "stored by rows": a row (i.e. elements with same first index) in a 2-dimensional matrix has placed contiguously in memory while a column (same second index) consist of elements lying far away from each other. It is important to know for performance considerations: access to neighbor elements is usually much faster (due to HW caches etc.), so for example nested loops should be organized such that the innermost one iterates over the last index.

Back to the question: if your mental picture (abstraction) of a 2D array is that of a lattice in Carthesian coordinates, then yes, you may think of it as array[NY][NX] in C. However if you need to describe real 2D or 3D data as an array, the choice of indexes probably depends on other things: data formats, convenient notation, performance, etc. For example, if the in-memory representation for a bitmap is array[NX][NY] in a format you need to work with, you will declare it that way, and maybe you don't even need to know that the bitmap becomes sort of "transposed" :)

Answer 5

Yep, you're right - they are stored consecutively. Consider this example:

#include <stdio.h>

int array3d[2][3][2] = {
  {{0, 1}, {2, 3}, {3, 4}},
  {{5, 6}, {7, 8}, {9, 10}}
};

int main()
{
  int i;
  for(i = 0; i < 12; i++) {
    printf("%d ", *((int*)array3d + i));
  }
  printf("\n");
  return 0;
}

Output:

0 1 2 3 3 4 5 6 7 8 9 10

Answer 6

All "dimensions" are stored consecutively in memory.

Consider

    int arr[4][100][20];

you can say that arr[1] and arr[2] (of type int[100][20]) are contiguous
or that arr[1][42] and arr[1][43] (of type int[20]) are contiguous
or that arr[1][42][7] and arr[1][42][8] (of type int) are contiguous