Two- and one-dimensional arrays equivalence in C++

Question

It is known that two- and one-dimensional arrays can be used equivalently, by simple coordinate conversion. Is such equivalence guaranteed by the C++ standard, or maybe it's the most convenient way of organizing data, but doesn't have to be obeyed everywhere? For example, is the following code compiler-independent?

std::ofstream ofbStream;
ofbStream.open("File", std::ios::binary);
char Data[3][5];

for(int i=0; i<3; ++i)
for(int j=0; j<5; ++j)
{
    Data[i][j] = (char) 5*i+j;
}

ofbStream.write(&Data[0][0], 15);

ofbStream.close();

The program is expected to write the numbers: 0, 1, 2, ..., 14 to a file.

Answer 1

In practice, this is just fine. Any compiler that doesn't do that would have countless problems with existing code.

Very strictly speaking, though, the pointer arithmetic needed is Undefined Behavior.

char Data[3][5];
char* p = &Data[0][0];
p + 7; // UB!

5.7/5 (emphasis mine):

When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that that difference of the subscripts of the resulting and original array elements equals the integral expression. ... If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

The Standard does guarantee that all the array elements are adjacent in memory and are in a specific order, and that dereferencing a pointer with the correct address (no matter how you got it) refers to the object at that address, but it doesn't guarantee that p + 7 does anything predictable, since p and p + 7 don't point at elements of the same array or past-the-end. (Instead they point at elements of elements of the same array.)

Answer 2

In his book The C++ Programming Language, Bjarne Stroustrup mentions (C.7.2; p. 838 of the Special Edition, 2000):

... We can initialize ma like this:

void int_ma() {
    for(int i=0; i<3; i++)
        for(int j=0; j<5; j++) ma[i][j] = 10 * i + j; }

...

The array ma is simply 15 ints that we access as if it were 3 arrays of 5 ints. In particular, there is no single object in memory that is the matrix ma - only the elements are stored. The dimensions 3 and 5 exist in the compiler source only.

(emphasis mine).

In other words, the notation [][]...[] is a compiler construction; syntactical sugar if you will.

For entertainment purposes, I wrote the following code:

#include<cstdlib>
#include<iostream>
#include<iterator>
#include<algorithm>

int main() {
  double ma[5][3]; double *beg = &ma[0][0]; // case 1
  //double ma[3][5]; double *beg = &ma[0][0]; // case 2
  //double ma[15]; double *beg = &ma[0]; // case 3

  double *end = beg + 15;

  // fill array with random numbers
  std::generate(beg, end, std::rand);

  // display array contents
  std::copy(beg, end, std::ostream_iterator<double>(std::cout, " "));
  std::cout<<std::endl;  
  return 0;
}

And compared the assembly generated for the three cases using the compilation command (GCC 4.7.2):

g++ test.cpp -O3 -S -oc1.s 

The cases are called c1.s, c2.s, and c3.s. The output of the command shasum *.s is:

5360e2438aebea682d88277da69c88a3f4af10f3  c1.s
5360e2438aebea682d88277da69c88a3f4af10f3  c2.s
5360e2438aebea682d88277da69c88a3f4af10f3  c3.s

Now, I must mention that the most natural construction seems to be the one-dimensional declaration of ma, that is: double ma[N], because then the initial position is simply ma, and the final position is simply ma + N (this is as opposed to taking the address of the first element of the array).

I find that the algorithms provided by the <algorithm> C++ Standard Library header fit much more snuggly in this case.

Finally, I must encourage you to consider using std::array or std::vector if at all possible.

Cheers.

Answer 3

C++ stores multi-dimensional arrays in row major order as a one-dimensional array extending through memory.

Answer 4

As other commenters have indicated, the 2-dimensional array will be mapped to 1-dimensional memory. Is your assumption platform independent? I would expect so, but you should always test it to be sure.

#include <iostream>
#include <iterator>
#include <algorithm>

int main() {

   char Data[3][5];
   int count = 0;

   for (int i = 0; i < 3; ++i)
      for (int j = 0; j < 5; ++j)
         Data[i][j] = count++;

   std::copy(&Data[0][0], &Data[0][0] + 15, std::ostream_iterator<int>(std::cout,", "));
}

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,

http://www.fredosaurus.com/notes-cpp/arrayptr/23two-dim-array-memory-layout.html

How are multi-dimensional arrays formatted in memory?

Memory map for a 2D array in C

Answer 5

Quote

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.

C++ ISO standard