Arrakis Arrakis - 1 month ago 25
C Question

C / C++ MultiDimensional Array Internals

I have a question about how C / C++ internally stores multidimensional arrays declared using the notation

foo[m][n]
. I am not questioning pure pointers to pointers etc... I am asking because of speed reasons...

Correct me if I am wrong, but syntactically
foo
is an array of pointers, which themselves point to an array

int foo[5][4]
*(foo + i) // returns a memory address
*( *(foo + i) + j) // returns an int


I have heard from many places that the C/C++ compiler converts
foo[m][n]
to a one dimensional array behind the scenes (calculating the required one dimension index with
i * width + j
). However if this was true then the following would hold

*(foo + 1) // should return element foo[0][1]


Thus my question:
Is it true that
foo[m][n]
is (always?) stored in memory as a flat one dimensional array?? If so, why does the above code work as shown.

Answer

Yes, C/C++ stores a multi-dimensional (rectangular) array as a contiguous memory area. But, your syntax is incorrect. To modify element foo[0][1], the following code will work:

*((int *)foo+1)=5;

The explicit cast is necessary, because foo+1, is the same as &foo[1] which is not at all the same thing as foo[0][1]. *(foo+1) is a pointer to the fifth element in the flat memory area. In other words, *(foo+1) is basically foo[1] and **(foo+1) is foo[1][0]. Here is how the memory is laid out for some of your two dimensional array:

enter image description here

Comments