17

What is the difference between a 2D array and an array of arrays?

I have read comments, such as @Dave's, that seem to differentiate between the two.

This breaks if he's using 2d arrays, or pointer-to-array types, rather than an array of arrays. – Dave

I always thought that both referred to:

int arr_arr[][];

EDIT: @FutureReader, you may wish to see How do I use arrays in C++?

Community
  • 1
  • 1
Mateen Ulhaq
  • 24,552
  • 19
  • 101
  • 135

5 Answers5

30

There are four different concepts here.

  • The two-dimensional array: int arr[][]. It cannot be resized in any direction, and is contiguous. Indexing it is the same as ((int*)arr)[y*w + x]. Must be allocated statically.
  • The pointer-to array: int (*arr)[]. It can be resized only to add more rows, and is contiguous. Indexing it is the same as ((int*)arr)[y*w + x]. Must be allocated dynamically, but can be freed free(x);
  • The pointer-to-pointer: int **arr. It can be resized in any direction, and isn't necessarily square. Usually allocated dynamically, not necessarily contiguous, and freeing is dependent on its construction. Indexing is the same as *(*(arr+y)+x).
  • The array-of-pointers: int *arr[]. It can be resized only to add more columns, and isn't necessarily square. Resizing and freeing also depends on construction. Indexing is the same as *(*(arr+y)+x).

Every one of these can be used arr[y][x], leading to the confusion.

Dave
  • 10,964
  • 3
  • 32
  • 54
  • A two-dimensional array can be allocated like an object of any other type, either automatically ("on the stack", i.e., declared as a local object), or dynamically (via `malloc()`), or statically (defined with the `static` keyword or outside any function). I think what you mean is that the size is fixed at compile time -- though with C99 variable-length arrays, that's not entirely true either. – Keith Thompson Oct 31 '11 at 04:20
  • 2
    Strictly speaking, only the first of these is two-dimensional array; the others are data structures that can *emulate* 2-d arrays. But for all four forms, once everything has been allocated (which can be tricky), you can use the same `arr[x][y]` syntax to access individual elements. The difference is in whether the prefix of each `[]` operator is a pointer expression or an array expression that *decays* to a pointer. There are 4 combinations. (For 3-d array-like structures, there are 8 combinations; for N dimensions, there are 2**N.) – Keith Thompson Oct 31 '11 at 04:23
  • How would you allocate a 2-dimensional array with `malloc()`? You need a pointer-to array for that. – Dave Oct 31 '11 at 05:07
  • Yes, you'd need a pointer to array. `int (*p)[10][10] = malloc(sizeof *p);`. Or, perhaps more legibly: `typedef int matrix[10][10]; matrix *p = malloc(sizeof *p);`. – Keith Thompson Oct 31 '11 at 05:12
12

A 2 dimensional array is by definition an array of arrays.

What Dave was saying is that in that context, there are different semantics between the definition of a 2D array like this:

int x[][];

this:

int *x[];

or this:

int **x;
Jacob Relkin
  • 161,348
  • 33
  • 346
  • 320
  • But then why do people imply the two are heterogeneous? – Mateen Ulhaq Oct 31 '11 at 03:01
  • 5
    Sometimes you might see a 2D array defined as `int (*x)[10];`, which is a good trick to turn a flat array into a 2D array that can be indexed with `[x][y]` instead of `[x * width + y]`. – Chris Lutz Oct 31 '11 at 03:08
  • @muntoo: What do you mean by "heterogeneous"? Do you mean "synonymous"? – Keith Thompson Oct 31 '11 at 04:16
  • 1
    @KeithThompson No, I meant that some people on SO imply that `2D array != array of arrays`. (Not just Dave.) Originally, only the first line in this answer was present; the other stuff was later edited on. – Mateen Ulhaq Oct 31 '11 at 07:45
  • 2
    @muntoo: Ok. I think "different" would have expressed that more clearly. – Keith Thompson Oct 31 '11 at 07:51
10

The answer here is a little more subtle.

An array of arrays is defined as such:

int array2[][];

The pointer-to-array types are defined as:

int (*array2)[];

The array-of-pointer types are defined as:

int* array2[];

The compiler treats both of these a little differently, and indeed there is one more option:

int** array2;

A lot of people are taught that these three are identical, but if you know more about compilers you will surely know that difference is small, but it is there. A lot of programs will run if you substitute one for another, but at the compiler and ASM level things are NOT the same. A textbook on C compilers should provide a much more in depth answer.

Also, if one is interested in the implementation of a 2D array there are multiple methods that vary in efficiency, depending on the situation. You can map a 2D array to a 1D array, which ensures spacial locality when dealing with linearized data. You can use the array of arrays if you want the ease of programming, and if you need to manipulate the rows/columns separately. There are certain blocked types and other fancy designs that are cache-smart, but rarely do you need to know the implementation if you the user.

Hope I helped!

foslock
  • 3,639
  • 2
  • 22
  • 26
  • 1
    No, that's an array of pointers. int (*array)[n] is an pointer to an array. – Dave Oct 31 '11 at 03:22
  • 3
    The difference is not "very small". It's the difference between arrays and pointers, which is a very important distinction (and one that too many C programmers miss). – Keith Thompson Oct 31 '11 at 04:14
  • @KeithThompson: How important of a distinction can it be if so many C programmers can use the language effectively while missing it? – Nicol Bolas Nov 01 '11 at 02:38
  • 1
    @NicolBolas: I'm not convinced that they do use it effectively. Not understanding the distinction makes certain kinds of errors very easy. – Keith Thompson Nov 01 '11 at 02:48
  • Thanks for the comments, I edited the answer to provide more depth and fixed the pointer-to-array typo. – foslock Nov 02 '11 at 18:30
1

The following is a 2D array that can be called an array of arrays:

int AoA[10][10];

The following is a pointer to a pointer that has been set up to function as a 2D array:

int **P2P = malloc(10 * sizeof *P2P);
if(!P2P) exit(1);
for(size_t i = 0; i < 10; i++)
  {
    P2P[i] = malloc(10 * sizeof **P2P);
    if(!P2P[i])
      {
        for(; i > 0; i--)
            free(P2P[i - 1]);
        free(P2P); 
      }
  }

Both can be accessed via AoA[x][y] or P2P[x][y], but the two are incompatible. In particular, P2P = AoA is something that newbies sometimes expect to work, but will not - P2P expects to point to pointers, but when AoA decays into a pointer, it is a pointer to an array, specifically int (*)[10], which is not the int ** that P2P is supposed to be.

Chris Lutz
  • 73,191
  • 16
  • 130
  • 183
0

2d array can include this:

int x[width * height]; // access: x[x + y * width];

From Wikipedia:

For a two-dimensional array, the element with indices i,j would have address B + c · i + d · j, where the coefficients c and d are the row and column address increments, respectively.

Pubby
  • 51,882
  • 13
  • 139
  • 180
  • 3
    Or if you want to show off, `int arr_[width * height]; int (*arr)[width] = (void *)arr_; arr[x][y] = 0;` – Chris Lutz Oct 31 '11 at 03:10
  • 1
    That's not really a 2-dimensional array; it's a 1-d array (that can be used to emulate a 2-d array). – Keith Thompson Oct 31 '11 at 04:15
  • @KeithThompson Actually it's the other way around. This is the truest form of 2d array, with array-of-arrays being a representation. http://en.wikipedia.org/wiki/Array_data_structure – Pubby Oct 31 '11 at 12:52
  • @Pubby8: You're mistaken. The Wikipedia article you cite doesn't actually support your claim. And section 6.5.2.1 of the [C standard](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) refers to arrays of arrays as multidimensional arrays. – Keith Thompson Oct 31 '11 at 18:26
  • index of `x[7*3]` is same as index of `x[3*7]` so you are storing just half of the possible data and will loose the other half or overwriting the first half. So consider using it like so `x[7*widthIndexlength+3]`. – Ol Sen May 13 '17 at 21:43
  • usually x is width, so it should be `variable_name[x + y * width]` – JHBonarius Oct 11 '18 at 09:13