How C arrays are structured

Question

I have a question about how C arrays are stored in memory. But I'm having trouble formulating the question, so here's my best try to put it into words. I have trouble with English. Let's say we have a three dimensional array:

int foo[2][3][4];

Elements can be accessed using either array or pointer notation:

foo[i][j][k]    
*(*(*(foo + i) + j) + k)

We could think of the array as a pointer to a pointer to a pointer to an int, or, for example, a pointer to a 2 dimensional array like (*a)[2][3].

The problem in my thinking is this: I would have thought that in order to 'extract' values in the array, we'd only have to dereference the top level of the array (i.e. [i]) once, the second level (i.e. [j]) twice, and the third level (i.e. [k]) three times. But actually we always have to dereference three times to get to any value. Why is this? Or is this really the case?

I try to imagine the array structure in memory.

Apologies for my poor way to express this.

"*We could think of the array as a pointer to a pointer to a pointer to an int*" no. "*a pointer to a 2 dimensional array like (*a)[2][3].*" sometimes. Conclusion: The former and the latter aren't the same. — alk, Sep 23 '18 at 14:39
In C an N-dimensional array is a 1-dimensional array of (N-1)-dimensional array elements is an .... — alk, Sep 23 '18 at 14:41

Some programmer dude · Accepted Answer · 2018-09-23T14:46:11.900

Your array of arrays of arrays foo is arranged like this in memory:

+--------------+--------------+--------------+--------------+--------------+--------------+--------------+--------------+----------+
| foo[0][0][0] | foo[0][0][1] | foo[0][0][2] | foo[0][0][3] | foo[0][1][0] | foo[0][1][1] | foo[0][1][2] | foo[0][1][3] | ... etc. |
+--------------+--------------+--------------+--------------+--------------+--------------+--------------+--------------+----------+

foo[0][0][0] will be at the lowest memory location, foo[1][2][3] will be at the highest.

And an important note: An array is not a pointer. It can decay to a pointer to its first element, but please don't "think of" an array as a pointer.

Another important note: The pointers &foo, &foo[0], &foo[0][0] and &foo[0][0][0] are all pointing to the same location, but they are all different types which makes them semantically different:

&foo is of the type int (*)[2][3][4]
&foo[0] is of the type int (*)[3][4]
&foo[0][0] is of the type int (*)[4]
And &foo[0][0][0] is of the type int *

Lastly a note about the array-to-pointer decay, it only happens in one step. That means foo decays to &foo[0], foo[0] decays to &foo[0][0], and foo[0][0] decays to &foo[0][0][0].

... and the array indexing operator is defined *only on values of pointer type, not arrays* - it works on arrays only because they decay to pointer to the first element, hence there is no "array or pointer" notation — Antti Haapala -- Слава Україні, Sep 23 '18 at 15:53
@Some programmer dude Thank you greatly, yes I wondered why &foo, foo, *foo **foo, all are the same address. There are many guides and books. Can you suggest just one, if there is just one? — sid, Sep 23 '18 at 19:08
@Some programmer dude Also, can you answer this: My problem is how to specifically relate *(*(foo + i) + j) + k form to the three pointers? The pointer to size 3 x 4 array of int, the pointer to size 4 array of int, and the pointer to int. — sid, Sep 23 '18 at 22:32

score 1 · Answer 2 · answered Sep 23 '18 at 14:42

An array is not as plain as a storage location (memory address), but an object with a type and layout.

So in your example, foo is an array of 3 arrays of 4 arrays of int, whose length is 2. *f is an array of 4 arrays of int, and **f is an array of int.

Even though each level of dereferencing gives the same memory address, they're different because they have different types, and thus the data at the same location should be interpreted differently.

How C arrays are structured

2 Answers2