Multi-dimensional array in C++ , a mystery to me :(

Question

I am having lots of problem understanding multidimensional arrays. Let an array be

x[2]; // now x is constant pointer to first element i.e x's name is address of x[0]

Now two dimensional array:

x[2][5]; // here x is address of x[0] which contains the address of first element of array x[][0];

Now the pointer

int(*y)[5]; 

is a pointer to array 5 of integers. How is it possible to write y = x?

Now I was doing some practical to understand this in VS, which is here, and my main question is in the image:

http://img184.imagevenue.com/img.php?image=96382_first_122_1120lo.jpg

Please answer the question conceptually; how C++ stores multi-dimensional array, etc.

I'll appreciate any help a lot :)

Answer 1

As others have pointed out, a multidimensional array is an array of arrays, not an array of pointers.

I think the main cause for misunderstanding is the concept of any array being actually a pointer. But it's not strictly true. An array is a variable that holds a fixed size contiguous collection of elements of the same type. So when you declare an array like int x[2] you are declaring a variable that holds two integers. Note that it doesn't hold any pointer.

Now the root of this common misunderstanding is that in C/C++ an array name evaluates to the address of its first element and therefore can be used as a pointer. In other words, when you write x, you implicitly mean &x or &x[0]. This was probably done to make expressions more readable.

A multi-dimensional array is simply an array of arrays. In other words, the same logic applies to them, there is nothing special. You read C/C++ declaration starting from the name and going outside, applying modifiers as you encounter them, first [] and (), then *, then type, so you interpret a multi-dimensional array like this (order of reading specified explicitly):

int              x      [                2]         [           5];
6. "of type int" 1. "x" 2. "is an array" 3. "of 2". 4. "arrays" 5. "of 5 elements"

So there is no such thing as multi-dimensional arrays in C/C++, but there is such thing as one-dimensional array of one-dimensional arrays. As per the rules for one-dimensional arrays, x, &x and &x[0] all evaluate to the address of the first element. But since the first element is an array, x[0] evaluates to the address of that array, that is, the address of its first element which is an int. The same goes for &x[0] and &x[0][0]. That's why the value of x[0] is the same of its address - because x[0] is an array.

Note that while these things evaluate to the same address, they have different types. x is a pointer to an array of 5 ints, as well as &x[0], as both of them evaluate to the address of the first element of x. x[0] evaluates to the address of the first element of x[0], so it's a pointer to int, the same goes for &x[0][0]. This example compiles fine and prints the same address for all 4 pointers:

  int x[2][5];
  int (*y1)[5] = x;
  int *y2 = x[0];
  int (*y3)[5] = &x[0];
  int *y4 = &x[0][0];
  printf("%p %p %p %p\n", y1, y2, y3, y4);

Now, there are different memory layouts for arrays used in different languages. For example, for a two-dimensional array you can group elements by rows or by columns. In C/C++, since there are no "true" multi-dimensional arrays, the memory layout is defined implicitly by the rules above. Since int x[2][5], which can be thought of as a two-dimensional array having 2 rows and 5 columns, actually is an array of 2 arrays, each of which represents a row, you get the "group by rows" layout, which is presented in shybovycha's answer.

Note that it is also possible to create an array of pointers and use it as a multi-dimensional array. The differences to "usual" multi-dimensional arrays are:

1. An array of pointers actually holds pointers inside. That is, addresses of the first elements of sub-arrays.
2. Memory layout isn't contiguous. Each sub-array can be allocated anywhere, for example using malloc() or new[].
3. Sub-arrays can be of different size.

The advantage of this approach is that you can use this array as a pointer to pointer (for example, int **y), which makes all multi-dimensional arrays of this kind compatible between each other, even if they have different sizes. But the sizes have to be stored separately in this case.

Answer 2

Look: any multi-dimensional array is the array of arrays. E.g. x[2][5] will be equal to this table:

x[0][0] x[0][1] x[0][2] x[0][3] x[0][4]

x[1][0] x[1][1] x[1][2] x[1][3] x[1][4]

Pointer assignment would be exactly the same: x[0] is the first row in your 2x5 table, so int *y = x[0] or int *y = x[1] will copy the address of first row to y.

But if you do int (*y) = x then it stores address of x[0][0] into y variable (int y creates an int instance while int (*y) gives you address of this instance).

UPD: Let us have int **x variable. It does not matter which size it has. Just take this as a truth that x, x[0] and x[0][0] would provide you with the same address. This could be explained like Pointer name means its address. Multi-dimensional array is a pointer to pointer. Its name means address of pointer it's pointing on which means address of the last pointer' first element. (sorry for complicity).