Ways to visualize how multidimensional array is laid in memory?

Question

These are all part of the classwork I had to deal with, and it's all good when there's always a reliable compiler with me to take care of these complicated array & pointer arithmetic for me, but sadly it's not the case.

And personally, I wanna know how things are laid in the computer's memory for the sake of education!

Is there any beautiful visual model for the single & multi-dimensional which makes the following god-awful abomination of codes so self-explanatory?

I would really appreciate it if I could find any.

//Here's where the classwork starts

//Given this declaration: 
double points[3][4] = {};
//Surprisingly, these 6 lines of code contain same address!
points;        //= 0012F5A4   
&points;       //= 0012F5A4
points[0];     //= 0012F5A4   
&points[0];    //= 0012F5A4
*points;       //= 0012F5A4
&points[0][0]; //= 0012F5A4   

double *pd0 = points[0][1];
//-> error: incompatible type (cannot convert 'double' to 'double*' in initialization)

double *pd1 = &points[0][1];
//-> compatible type

double *pd2 = &points[5][2];
//-> compatible type (possible runtime error; points to the element out of bound)

double *pd3 = &**points;
//-> compatible type

double (*p4d0)[4] = points[0];
//-> error: incompatible type (cannot convert 'double*' to 'double (*)[4]' in initialization)

double (*p4d1)[4] = &points[0];
//-> compatible type

double (*p4d2)[4] = (double (*)[4])points[0];
//-> compatible type

double (*p4d2_1)[5] = (double (*)[5])points[0];
//-> compatible type (possible runtime error; out of bound)

double (*p4d3)[4] = (double (*)[4])&points[0][0];
//-> compatible type

double (*p4d4)[] = &points[0];
//-> error: incompatible type (cannot convert 'double (*)[4]' to 'double (*)[]' in initialization)

double (*p4d5)[3][4] = points;
//-> error: incompatible type (cannot convert 'double (*)[4]' to 'double (*)[3][4]' in initialization)

double (*p4d6)[3][4] = &points;
//-> compatible type

double (*p4d7)[][4] = &points;
//-> error: incompatible type (cannot convert 'double (*)[3][4]' to 'double (*)[][4]' in initialization)

double (*p4d8)[][] = &points;
//-> error: incompatible type (multidimensional array must have bounds for all dimensions except the first)
//End

How about something like [this old answer of mine](http://stackoverflow.com/questions/18440205/casting-void-to-2d-array-of-int-c/18440456#18440456)? It also shows how a pointer-to-pointer is "laid out". — Some programmer dude, Nov 18 '15 at 08:53
I think `double (*p4d4)[] = &points[0];` and `double (*p4d7)[][4] = &points;` should be compatible. Aren't they? — user1969104, Nov 18 '15 at 09:07
@user1969104 I get following 2 errors in g++ compiler with maximum warning turned on; "cannot convert 'double (*)[3][4]' to 'double (*)[][4]" "cannot convert 'double (*)[4]' to 'double (*)[]" — Yunhyeok Choi, Nov 18 '15 at 10:10
it seems the instructor has skipped some key details. all the 'same address' items are because the 'name' of an array degrades to the address of the first byte in the array. An array, such as you are describing, is simply a series of bytes in memory, where the layout is row by row, where each row contains column by column. The first dimension is the 'rows' the second dimension is the 'columns', How many bytes are in each column depends on the data type. in a 32bit architecture, where a 'int' is 4 bytes, and the data type is 'int', then each column of each row takes 4 bytes. — user3629249, Nov 19 '15 at 18:52
a `double` usually takes twice the number of bytes as a `int`, so the total memory (assuming a double takes 8 bytes) for this statement: `double points[3][4]` is 8*3*4 bytes (element size * number of rows * number of columns per row). the layout in memory would be: pointers{row0{ col0,col1,col2 }, row1{...} } etc. so pointers, &pointers[0], &pointers]0][0], etc are all the same address — user3629249, Nov 19 '15 at 19:00

score 1 · Accepted Answer · edited May 23 '17 at 12:03

Here's a way to think of your points[3][4] array. It is an array of 3 rows and 4 columns. The rows are numbered 0, 1, and 2, and the columns are numbered 0, 1, 2, and 3.

Let's populate the array with values, to help visualize it.

      0  1  2  3
  --            --
0 |  11 12 13 14  |
1 |  21 22 23 24  |
2 |  31 32 33 34  |
  --            --

The twelve values are arranged in memory in the following order. Each row is placed contiguously after the previous row:

11 12 13 14 21 22 23 24 31 32 33 34

Even though the variable is defined as a 2-dimensional array, it appears in memory as though it is a 1-dimensional array of 12 values.

A double occupies 8 contiguous bytes. Therefore, the address of each array element is 8 higher than the previous address. So if the array starts at address 0x0012F5A4, here are the addresses of all of the elements.

Address     Value
-------     -----
0012F5A4    11.0
0012F5AC    12.0
0012F5B4    13.0
0012F5BC    14.0
0012F5C4    21.0
0012F5CC    22.0
0012F5D4    23.0
0012F5DC    24.0
0012F5E4    31.0
0012F5EC    32.0
0012F5F4    33.0
0012F5FC    34.0

To emphasize that these are double values, I added the ".0" to each one in the above table, For the remainder of this post, I'll omit the ".0" when referring to the values.

Now let's take each case one by one. I'll explain only the first seven cases in your question.

Case 1

double *pd0 = points[0][1];
//-> error: incompatible type (cannot convert 'double' to 'double*' in initialization)

Here, pd0 is declared as a pointer to a double. Pointer variables contain the addresses of other variables.
On the right side of the assignment statement, points[0][1] contains the double value 12 in my example array. The error occurs because you are trying to assign a double value to a pointer variable.

Case 2

double *pd1 = &points[0][1];
//-> compatible type

This is fine because the & is the referencing operator. It provides the address of the variable it precedes. So &points[0][1] is the address of the double value stored at points[0][1]. In my example array, this address is 0x0012F5AC. The pointer pd1 is therefore being assigned the address 0x0012F5AC.

Case 3

double *pd2 = &points[5][2];
//-> compatible type (possible runtime error; points to the element out of bound)

If your compiler is smart enough to implement runtime array-bounds checking, then this might produce an exception when the statement executes since the array was not defined to have a row [5]. Pointer pd2 would be assigned the address of a hypothetical element well beyond the end of the 12-element array. Even if an exception doesn't occur, if the data at that address is used, it will most certainly not produce a predictable result, and might result in an eventual crash of the program.

Case 4

double *pd3 = &**points;
//-> compatible type

To understand this, let's add some parentheses to the right hand side, to emphasize the order in which the operators are applied.

double *pd3 = &(*(*points));

Now working from the inside out,

The term points identifies the entire 2-dimensional array.
The term (*points) identifies the address of the first row in the array.
The term (*(*points)) (or **points) identifies the value of the first element in the first row of the array.
The term &(*(*points)) (or &**points) identifies the address of that element.

So we are assigning the address of that single element to the pointer variable pd3.

Case 5

double (*p4d0)[4] = points[0];
//-> error: incompatible type (cannot convert 'double*' to 'double (*)[4]' in initialization)

For this case, I'll refer you to the answer given by John Bode in this post. Bode says,

When an array expression appears in most contexts, its type is implicitly converted from "N-element array of T" to "pointer to T", and its value is set to point to the first element in the array. The exceptions to this rule are when the array expression is an operand of either the sizeof or address-of (&) operators, or when the array is a string literal being used as an initializer in a declaration.

So points[0] is implicitly converted from "4-element array of double" to "pointer to double".
p4d1 is declared expressly as a pointer to an array of 4 doubles. The incompatibility arises because "pointer to double" is not the same type as "pointer to an array of 4 doubles".

Case 6

double (*p4d1)[4] = &points[0];
//-> compatible type

As in Case 5, p4d1 is a pointer to an array of 4 doubles.
&points[0] provides the address of the 0th row. Recall that in the excerpt from John Bode's post, he said that an exception to the rule converting an array expression to a pointer occurs when using the address-of (&) operator. So &points[0] is also a pointer to an array of 4 doubles. After executing the above statement, p4d1 contains that address.

Case 7

double (*p4d2)[4] = (double (*)[4])points[0];
//-> compatible type

This solves the problem of Case 5. It is casting points[0] to the same type as p4d2, effectively undoing the implicit conversion to "pointer to double".

I'll leave the remaining cases for you to sort out.

Thanks, for the thorough explanation! One thing in the case 6. Since the array expression is the operand of the & operator, which falls into to one of the exception, shouldn't it stay the way it is, instead of implicitly converted to a pointer? — Yunhyeok Choi, Nov 18 '15 at 16:55
It's a pointer either way. Without the & operator, it's reduced to a pointer to double; with the & operator the exception is invoked, making it a pointer to a 4-element array of double. — sifferman, Nov 18 '15 at 17:00

Paul Ogilvie · Answer 2 · 2015-11-18T15:29:45.303

The lay-out in memory: multi-dimensional arrays are laid-out in row-major order in memory.

That means that in the sequential computer memory, it is row after row after row... This is exactly as you would initialize a multi-dimensional array, e.g.:

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

As for:

points;        //= 0012F5A4   // means the address of the first element
&points;       //= 0012F5A4   // yields the address of the array
points[0];     //= 0012F5A4   // means: address of the first element of the first row of the array
&points[0];    //= 0012F5A4   // means: address of the first row of the array
*points;       //= 0012F5A4   // yields the first row, which is an address
&points[0][0]; //= 0012F5A4   // yields adress of first element of first row.

In the above, remember that a[2][2] means a+2*3+2 (a plus the sizee of 2 rows, plus 2 elements).

All other compiler errors speak for themselves.

Is the address of the array same as the location of where the memory specifically occupied for that array starts? — Yunhyeok Choi, Nov 18 '15 at 16:50
The "adderss of the array" is the same as the address of the first row, which is the same as the adress of the first element of the first row, so yes, the address of the array is the same as the start of the memory occupied by the array — Paul Ogilvie, Nov 18 '15 at 17:04

Ways to visualize how multidimensional array is laid in memory?

2 Answers2