How is a 2 dimensional array implemented in C++

Question

Possible Duplicate:
2D-array as argument to function

How are 2D arrays implemented in C++? Is it contiguous in memory?

i.e If a is an array first address contains element a(0,0) then next address a(0,1) then a(1,0), a(1,1) and so on...?

Answer 1

Yes it is contiguous in row major order. Suppose you have a 2d array named a[3][3]. Then in memory elements will be in this order: a[0][0], a[0][1], a[0][2], a[1][0], a[1][1], a[1][2], a[2][0], a[2][1], a[2][2].

Here is more details with an example

Answer 2

Given a declaration T D[C], where T is a type name, D an identifier and C an integral constant expression, the Standard says (highlighting mine):

(§8.3.4/1) [...] then the type of the identifier [...] is an array type. [...] The constant expression specifies the bound of (number of elements in) the array. If the value of the constant expression is N, the array has N elements numbered 0 to N-1, and the type of the identifier of D is “derived-declarator-type-list array of N T”. An object of array type contains a contiguously allocated non-empty set of N subobjects of type T. [...]

And:

(§8.3.4/3) When several “array of” specifications are adjacent, a multidimensional array is created; [...]

As well as:

(§8.3.4/9) [ Note: It follows from all this that arrays in C++ are stored row-wise (last subscript varies fastest) and that the first subscript in the declaration helps determine the amount of storage consumed by an array but plays no other part in subscript calculations. — end note ]

Conclusion
All this makes it clear that T a[N][M] is a contiguously stored list of N objects, each of which is a contigously stored list of M objects of type T. So yes, the whole two-dimensional array is one contiguously stored object.

Does that mean you can use one combined index to access the elements directly? So, given an array int a[10][5], can you use a[0][23] instead of a[2][3]? Stricly speaking, no, because that is a violation of the first rule above, whereby only indexes 0..4 are valid for the second index. However, as far as that particular expression is concerned, if you were to consider a[0] as a pointer p to the first element of the first row of the array, and a[0][23] as *(p+23), you could be sure to access the correct element. More on this question in this existing question.