Multi-Dimensional Arrays in Memory

Question

I am wondering if the C++ standard guarantees that multidimensional arrays (not dynamically allocated) are flattened into a 1D array of exactly the same space. For example, if I have

char x[100];
char y[10][10];

Would these both be equivalent? I'm aware that most compilers would flatten y, but is this actually guaranteed to happen? Reading section 11.3.4 Arrays of the C++ Standard, I cannot actually find anywhere that guarantees this.

The C++ standard guarantees that y[i] follows immediately after y[i-1]. Since y[i-1] is 10 characters long, then, logically speaking, y[i] should take place 10 characters later in memory; however, could a compiler pad y[i-1] with extra characters to keep y[i] aligned?

Answer 1

What you are looking for is found in [dcl.array]/6

An object of type “array of N U” contains a contiguously allocated non-empty set of N subobjects of type U, known as the elements of the array, and numbered 0 to N-1.

What this states is that if you have an array like int arr[10] then to have 10 int's that are contiguous in memory. This definition works recursively though so if you have

int arr[5][10]

then what you have is an array of 5 int[10] arrays. If we apply the definition from above then we know that the 5 int[10] arrays are contiguous and then int[10]'s themselves are contiguous so all 50 int's are contiguous. So yes, a 2d array look just like a 1d array in memory since really that is what they are.

This does not mean you can get a pointer to arr[0][0] and iterate to arr[4][9] with it. Per [expr.add]/4

When an expression J that has integral type is added to or subtracted from an expression P of pointer type, the result has the type of P.

• If P evaluates to a null pointer value and J evaluates to 0, the result is a null pointer value.

• Otherwise, if P points to an array element i of an array object x with n elements ([dcl.array]), the expressions P + J and J + P (where J has the value j) point to the (possibly-hypothetical) array element i+j of x if 0≤i+j≤n and the expression P - J points to the (possibly-hypothetical) array element i−j of x if 0≤i−j≤n.

• Otherwise, the behavior is undefined.

What this states is that if you have a pointer to an array, then the valid indices you can add to it are [0, array_size]. So if you did

int * it = &arr[0][0]

then what it points to is the first element of the first array which means you can legally only increment it to it + 10 since that is the past then end element of the first array. Going into the second array is UB even though they are contiguous.