4

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.

Adayah
  • 140
  • 2
  • 5
  • 1
    Multidimensional arrays are just arrays of arrays. Arrays are always stored contiguously. I'm not sure how it would work in terms of pointer arithmetic, though, as I believe something like `&Data[0][0] + 10` is undefined, despite being within the overall range. – chris May 24 '13 at 16:31
  • 3
    arrays are in memory and memory is 1D. – andre May 24 '13 at 16:36
  • 1
    It is guaranteed by the standard, by the definition given in the standard of how the subscript operator works on multidimensional arrays. – Matteo Italia May 24 '13 at 16:49
  • 1
    very related: http://stackoverflow.com/questions/7269099/may-i-treat-a-2d-array-as-a-contiguous-1d-array – Nate Kohl May 24 '13 at 16:55
  • @andre: C++ does not require memory to be 1D in general. Within an array, sure. – aschepler May 24 '13 at 17:14

5 Answers5

4

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.

Escualo
  • 40,844
  • 23
  • 87
  • 135
4

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.)

aschepler
  • 70,891
  • 9
  • 107
  • 161
  • I'm not sure that it's UB, since that pointer arithmetic is how the subscript operator for multidimensional arrays is defined to behave, so it should be well-defined. See C++11, §8.3.4, ¶7-9. – Matteo Italia May 25 '13 at 18:08
  • Those paragraphs in 8.3.4 are non-normative and don't say anything about pointer arithmetic outside an array of scalars. – aschepler May 25 '13 at 19:01
  • 1
    This has been debated before, see the comments to http://stackoverflow.com/a/7164753/214671 – Matteo Italia May 26 '13 at 01:02
1

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

kgraney
  • 1,975
  • 16
  • 20
0

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

Community
  • 1
  • 1
Steven Maitlall
  • 777
  • 3
  • 5
0

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

Xale
  • 359
  • 1
  • 5