How are 3D arrays stored in C?

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?

---

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]

---

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

---

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

---

Yes, they're are just stored in consecutive order. You can test that like this:

#include <stdio.h>

int main (int argc, char const *argv[])
{
  int numbers [2][3][4] = {{{1,2,3,4},{5,6,7,8},{9,10,11,12}}
                          ,{{13,14,15,16},{17,18,19,20},{21,22,23,24}}};

  int i,j,k;

  printf("3D:\n");
  for(i=0;i<2;++i)
    for(j=0;j<3;++j)
      for(k=0;k<4;++k)
        printf("%i ", numbers[i][j][k]);

  printf("\n\n1D:\n");
  for(i=0;i<24;++i)
    printf("%i ", *((int*)numbers+i));

  printf("\n");

  return 0;
}

That means that accesses to a multiindexed array with dimensions (N,M,L) are transformed to onedimensional accesses like this:

array[i][j][k] = array[M*L*i + L*j + k]

---

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

---

Let's say you have an array char arr[3][4][5]. It is an array of 3 arrays of 4 arrays of 5 chars.

For simplicity, let's say that the value in arr[x][y][z] is xyz and in arr[1][2][3] we store 123.

So the layout in memory is:

  |  00  01  02  03  04  05  06  07  08  09  10  11  12  13  14  15  16  17  18  19
--+--------------------------------------------------------------------------------   
00| 000 001 002 003 004 010 011 012 013 014 020 021 022 023 024 030 031 032 033 034 
20| 100 101 102 103 104 110 111 112 113 114 120 121 122 123 124 130 131 132 133 134 
40| 200 201 202 203 204 210 211 212 213 214 220 221 222 223 224 230 231 232 233 234

arr[0], arr[1] and arr[2] are coming one after another, but each element in the is of type char[4][5] (those are the three rows in the table).

arr[x][0] - arr[x][3] are also coming one after another, and each element in them is of type char[5] (those are the four parts of each line in the table, 000 - 004 is one element of arr[0][0] )

arr[x][y][0] - arr[x][y][4] are 5 bytes that are coming one after another.

---

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" :)

---

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.