3

Possible Duplicate:
How do I use arrays in C++?

To put it simply, is a multidimensional array in C++ an array of arrays or is it simply a single array which behaves like it's multidimensional?

A friend of mine explained that arrays in C++ are simply constant pointers, and that multidimensional arrays are also constant pointers whose elements are addressed by more than one index (i.e. they are pointers pointing to one big array, and the offset of the elements are calculated using multiple indices).

I believe that multidimensional arrays are single dimensional arrays of pointers which point to other arrays because when passing multidimensional arrays as function arguments I often use the syntax:

void copy_matrix(int ** matrix);

If not, is it possible to create an array of arrays in C++ and assign the value of each sub-array at compile time - equivalent to the semantics of the following statements:

int line[2][2];

line[0] = {100, 100};
line[1] = {200, 200};

The above statements generate a compile time error. A quick (untested) hack I came up with was:

int line[2][2];

void assign(int index, int * point, int length) {
    for (int i = 0; i < length; i++) {
        line[index][i] = point[i];
    }
}

assign(0, {100, 100}, 2);
assign(1, {200, 200}, 2);

However, I believe that there must be a more elegant way to achieve the same result. I hope to clearly understand these concepts, and any input is appreciated.

Community
  • 1
  • 1
Aadit M Shah
  • 72,912
  • 30
  • 168
  • 299
  • http://stackoverflow.com/questions/4810664/how-do-i-use-arrays-in-c should be a good read. – Alok Save Sep 17 '11 at 14:44
  • 1
    Your `void copy_matrix(int ** matrix);` will also generate a compiler error if `matrix` is declared as `int matrix[2][2]`. g++ for example complains `cannot convert 'int (*)[2]' to 'int**' for argument '1' to 'void copy_matrix(int**)'`. – David Hammen Sep 17 '11 at 17:16
  • C++0x seems to support the simpler initialization syntax that you wanted. – Brent Bradburn Sep 17 '11 at 19:39

4 Answers4

4

The brace-list initializer only works during initialization, and it cannot be used for assignment, as you seem to attempt.

Instead, just initialize the multi-dimensional array all at once:

int line[2][2] = { {100, 100}, {200, 200} };

In response to your first sentence: Arrays are arrays and pointers are pointers, and they're not the same thing. An array does however decay to a pointer to the first element with ease, and x[n] is equivalent to *(x + n). This applies recursively to multi-dimensional arrays as well.

Arrays T[N] are contiguous in memory for T and sizeof(T[N]) == N * sizeof(T); therefore, arrays of arrays T[N][M] are contiguous both for T[N] and for T.

Kerrek SB
  • 464,522
  • 92
  • 875
  • 1,084
  • Except there is no such thing as `T[i]` anywhere in memory of `T` is a multidimensional array. `T[i]` is a figment of C (and C++) imagination. How C and C++ treat (or rather, mistreat) arrays and multidimensional arrays is one of the things that drive scientific programmers absolutely insane. – David Hammen Sep 17 '11 at 16:46
  • @David: That's right, as far as the language is concerned, you are not allowed to exploit the contiguity of memory of a multidimensional array. However, at the same time you *are* guaranteed that the memory is in fact contiguous. This is still a useful guarantee if you want to take memory locality into account, though. – Kerrek SB Sep 17 '11 at 20:19
1

Multi-dimensional arrays in C and C++ are arrays of arrays. But since an array simply lays out its objects in memory one after the other, an array of arrays just lays out the arrays one after the other. So you can treat it like a single array if you decay it into a pointer.

You initialize an array by putting its values between curly braces, delimited by commas. You initialize an array of arrays the same way - by putting its values (themselves arrays) in braces.

So:

 int line[2][2]={
                  { 100, 100 }, // line[0]
                  { 200, 200 }  // line[1]
                };

There are no shortcuts for assignment though. You have to do it member-by-member (or use some function like memcpy).

David Schwartz
  • 179,497
  • 17
  • 214
  • 278
  • 2
    There is a huge difference between an array of arrays (e.g., `int**`) and a multidimensional array (e.g. `int[4][2]`) in C and C++. That they are indexed the same way in the C/C++ code is syntactic sugar. For a ragged array such as `int ** ragged`, accessing an element of the array requires going through two pointers. For a multidimensional array, you only go through one pointer. – David Hammen Sep 17 '11 at 15:47
  • 1
    `int **` is a pointer to a pointer, not an array of arrays. `int (foo[4])[4];` is an array of arrays and is the same as `int foo[4][4];`. Multi-dimensional arrays are arrays of arrays -- and would have the exact semantics they had even if the standard didn't mention them specifically. – David Schwartz Sep 17 '11 at 16:00
  • While `a[x][y]` is the same as `*(*(a+x)+y)` because the standard says so, no sane compiler would compute `a[x][y]` that way, even at optimization level 0. Because the standard also says that an array must occupy a contiguous chunk of memory, `a[x][y]` can be found by two multiplies and an addition: `element_size*((column_dimension*x+y)`. In fact, there is nothing in memory that contains `a[x]`. It instead has to be computed. – David Hammen Sep 17 '11 at 16:39
  • I'm not sure why you say no sane compiler would compute `a[x][y]` that way, it's precisely the same operation, in each case two multiplies and an addition (a + s1*x + s2*y). And of course there's a chunk of memory that contains `a[x]`, you can get its address with `&a[x]` (since `a` is an array of arrays of integers, each of its elements such as `a[x]` is an array of integers). Somehow we must be talking past each other. – David Schwartz Sep 17 '11 at 16:45
  • Yeah, I suspect we are talking past one another. What I meant by "*In fact, there is nothing in memory that contains `a[x]`*": `a[x]` is an address. In a ragged array, there is a specific chunk of memory that contains `a[x]`: It is `a[x]`. In a multidimensional array, there is no chunk of memory that contains this address. `a[x]` must instead be computed. – David Hammen Sep 17 '11 at 17:12
  • @D.Hammen: I think that you and D.Schwartz *are* talking past one another because he is (correctly) treating `a[x]` as a reference to the 1D sub-array whereas your comments are treating `a[x]` as a *pointer to* a 1D sub-array (as if this were a "ragged array"). So you are correct that no such pointer actually exists, but I don't think that D.Schwartz means to imply that it does exist. A key thing to understand is that (in this context) `&a[x]` returns a pointer to the sub-array -- it does not return a pointer to a pointer to the sub-array. – Brent Bradburn Sep 17 '11 at 20:23
  • @D.Hammen: On another note, your first comment is correct, but I don't understand how it relates to the answer given. Is it because you can't pass a multidimensional array to `int copy_matrix(int ** matrix);`? I don't think this answer was addressing that part of the question. I don't see any problems with the answer given by D.Schwartz other than the fact that it doesn't address every aspect of the OP's question. – Brent Bradburn Sep 17 '11 at 20:25
  • 1
    @D.Hammen: Oh, I get it. You are saying that "ragged arrays" are "arrays of arrays" where D.Schwartz is saying that multidimensional arrays are "arrays of arrays". I agree with D.Schwartz on this (or perhaps both could be considered correct), but maybe this issue isn't worth arguing about -- is there a definitive source for this? – Brent Bradburn Sep 17 '11 at 21:03
0

It's been a while since I last coded something on C++ (more of a Java person now) but if I remember correctly multidimensional arrays are indeed arrays of arrays.

And you can initialize array this way: int line[2][2] = {{100, 100}, {200, 200}};

P.S.: square brakes are just simplification: a[x] is the same as *(a+x) and a[x][y] is the same as *(*(a+x)+y)

P.P.S.: slightly corrected initialization

Andrei LED
  • 2,560
  • 17
  • 21
  • 1
    Multidimensional arrays in C and in C++ are not arrays of arrays. Ragged arrays are arrays of arrays. Big difference. – David Hammen Sep 17 '11 at 15:49
  • Ragged arrays are not C/C++ arrays. A C/C++ array must be a vector of variables of the same type. Ragged arrays contain elements that differ in type. Multidimensional arrays are in fact arrays of arrays. They would work precisely the same even if the standard never mentioned them, because an array can be an array of any type, including one that is itself an array, simply because nothing prohibits this. – David Schwartz Sep 17 '11 at 16:48
  • @David Schwartz: Look at the original question. The OP asked about the validity of `void copy_matrix(int ** matrix)` which certainly will not work if `matrix` is declared as `int[2][2] matrix`. – David Hammen Sep 17 '11 at 17:08
  • @David Schwartz: *Ragged arrays contain elements that differ in type.* Google the term "ragged array". `double** foo` is a ragged array. These can come in handy for representing upper triangular matrices, for example. – David Hammen Sep 17 '11 at 17:21
  • 1
    A multidimensional array *is* an array of arrays. A ragged array is an array of *pointers* to arrays. In both cases, the elements are of only one type. – Brent Bradburn Sep 17 '11 at 19:26
  • No, `double** foo` is not an array at all. It is a pointer to a vector of pointers. And in such a ragged array, each pointer can point to any number of `double`s, and hence they differ in memory layout (one can hold a vector of 12 doubles, one can hold a vector of 8 doubles). That's what makes them ragged. Ragged arrays are *not* C/C++ arrays, are not arrays of arrays, and they are not relevant to this question and only obfuscate. – David Schwartz Sep 18 '11 at 01:08
0

To put it simply, is a multidimensional array in C++ an array of arrays or is it simply a single array which behaves like it's multidimensional?

It is the latter. There is a huge difference in both the memory representation and in how indices are interpreted between multidimensional and ragged arrays.

A multidimensional array such as int array[L][M][N] occupies a contiguous chunk of memory. Accessing an individual element array[i][j][k] is equivalent to *(&array[0][0][0]+(i*M+j)*N+k). The lookup involves but one pointer dereference.

A ragged array such as int *** ragged is a one dimensional array of int** pointers. Each of those int** pointers is a one dimensional array of int* pointers, and each of those is a one dimensional array of ints. Here array[i][j][k] is equivalent to *(*(*(array+i)+j)+k). The lookup involves three pointer dereferences.

David Hammen
  • 32,454
  • 9
  • 60
  • 108
  • You are confusing an array of arrays with an array of pointers. If an array of int's occupies a contiguous chunk of memory, so would an array of arrays. I'm not sure why you bring up ragged arrays, they have nothing to do with the question. – David Schwartz Sep 17 '11 at 16:49
  • 1
    I am not confusing an array of arrays with an array of pointers. This is just quibbling over what the term "array of arrays" means. To me, and to most scientific programmers, an array of arrays is `Type **`, while `Type foo[Size1][Size2]` is anything but an array of arrays. It is a `Size`×`Size2` matrix: A single entity. An inertia tensor or a stress–energy tensor is not an array of arrays, for example. – David Hammen Sep 17 '11 at 17:02
  • `Type **` is a pointer to a pointer. In C or C++, arrays contain their objects laid out in memory one after the other. `Type foo[Size1][Size2]` is an array of arrays. It is precisely the same as `(Type foo[Size1])[size2]` which is *clearly* an array of arrays. – David Schwartz Sep 18 '11 at 01:05