C / C++ MultiDimensional Array Internals

Question

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 1

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: