How are multi-dimensional arrays formatted in memory?

In answer to your also: Both, though the compiler is doing most of the heavy lifting.

In the case of statically allocated arrays, "The System" will be the compiler. It will reserve the memory like it would for any stack variable.

In the case of the malloc'd array, "The System" will be the implementer of malloc (the kernel usually). All the compiler will allocate is the base pointer.

The compiler is always going to handle the type as what they are declared to be except in the example Carl gave where it can figure out interchangeable usage. This is why if you pass in a [][] to a function it must assume that it is a statically allocated flat, where ** is assumed to be pointer to pointer.

The answer is based on the idea that C doesn't really have 2D arrays - it has arrays-of-arrays. When you declare this:

int someNumbers[4][2];

You are asking for someNumbers to be an array of 4 elements, where each element of that array is of type int [2] (which is itself an array of 2 ints).

The other part of the puzzle is that arrays are always laid out contiguously in memory. If you ask for:

sometype_t array[4];

then that will always look like this:

| sometype_t | sometype_t | sometype_t | sometype_t |

(4 sometype_t objects laid out next to each other, with no spaces in between). So in your someNumbers array-of-arrays, it'll look like this:

| int [2]    | int [2]    | int [2]    | int [2]    |

And each int [2] element is itself an array, that looks like this:

| int        | int        |

So overall, you get this:

| int | int  | int | int  | int | int  | int | int  |

unsigned char MultiArray[5][2]={{0,1},{2,3},{4,5},{6,7},{8,9}};

in memory is equal to:

unsigned char SingleArray[10]={0,1,2,3,4,5,6,7,8,9};

A static two-dimensional array looks like an array of arrays - it's just laid out contiguously in memory. Arrays are not the same thing as pointers, but because you can often use them pretty much interchangeably it can get confusing sometimes. The compiler keeps track properly, though, which makes everything line up nicely. You do have to be careful with static 2D arrays like you mention, since if you try to pass one to a function taking an int ** parameter, bad things are going to happen. Here's a quick example:

int array1[3][2] = {{0, 1}, {2, 3}, {4, 5}};

In memory looks like this:

0 1 2 3 4 5

exactly the same as:

int array2[6] = { 0, 1, 2, 3, 4, 5 };

But if you try to pass array1 to this function:

void function1(int **a);

you'll get a warning (and the app will fail to access the array correctly):

warning: passing argument 1 of ‘function1’ from incompatible pointer type

Because a 2D array is not the same as int **. The automatic decaying of an array into a pointer only goes "one level deep" so to speak. You need to declare the function as:

void function2(int a[][2]);

or

void function2(int a[3][2]);

To make everything happy.

This same concept extends to n-dimensional arrays. Taking advantage of this kind of funny business in your application generally only makes it harder to understand, though. So be careful out there.