What is difference between types int** and int[][]?

Question

If the following assignment is valid:

int a[2] = {1,2};
int* b = a;

then what is wrong with this:

int a[2][2]={1,2,3,4};
int** b = a;

C++ gives an error that it can't convert int[][] to int**. What is difference between the two types if int[] is the same as int*?

Answer 1

Take it easy. It is only a compiler error. Arrays are pretty tricky. Here is the rule:

The value of a variable of type array decays to the address of element zero of this array

Your first snippet looks like:

int a[2] = {1,2};

So according to the rule if a is in the right hand side of a assignment then it decays to address of the element zero and that is why it has type int *. This brings you to

int *b = a;

In the second snippet what you really have is an array of arrays. (By the way, to make it explicit I've changed your code a bit.)

int a[2][2]={{1,2},{3,4}};

This time a will decay to the pointer to an array of two integers! So if you would want to assign a to something, you would need this something to have the same type.

int (*b)[2] = a; //Huh!

(This syntax maybe a bit stunning to you, but just think for a moment that we have written int *b[2]; Got the point? b would be an array of pointers to integers! Not really what we wanted...)

You could stop reading here, but you could also move on, because I have not told you all the truth. The rule I mentioned has three exceptions...

The value of the array will not decay to the address of the element zero if

1. array is operand of sizeof
2. array is operand of &
3. array is a literal string initializer for a character array

Let's explain these exceptions in more detail and with examples:

int a[2];

int *pi = a ; /* the same as pi = &a[0]; */

printf("%d\n", sizeof(a)); /* size of the array, not of a pointer is printed! */

int (*pi2)[2] = &a; /* address of the array itself is taken (not the address of a pointer) */

And finally

char a[] = "Hello world ";

Here not a pointer to "Hello world" is copied, but the whole string is copied and a points to this copy.

There is really a lot of information and it is really difficult to understand everything at once, so take your time. I recommend you to read K&R on this topic and afterwards this excellent book.

Answer 2

This is something that comes up a lot, so I will attempt to explain it as clearly as I can.

When you make an array, it stores the elements contiguously in memory, so:

int arr[2] = { 1, 2 };

Translates to:

arr:
+---+---+
| 1 | 2 |
+---+---+

A pointer points to an object in memory, and when dereferenced, via unary * or via [], it accesses that contiguous memory. So after

int *ptr = arr;

ptr (or &ptr[0] if you like) points to the box 1 is in, and ptr + 1 (or &ptr[1]) points to the box 2 is in. This makes sense.

But if arrays are contiguous in memory, arrays of arrays are contiguous in memory. So:

int arr[2][2] = {{ 1, 2 }, { 3, 4 }};

Looks in memory like this:

arr:
+---+---+---+---+
| 1 | 2 | 3 | 4 |
+---+---+---+---+

Which looks a lot like our flat array.

Now, let's consider how a pointer to a pointer to an int would be laid out in memory:

ptr:
+-------+-------+
| &sub1 | &sub2 |
+-------+-------+

sub1:
+---+---+
| 1 | 2 |
+---+---+

sub2:
+---+---+
| 3 | 4 |
+---+---+

ptr (or &ptr[0]) points to sub1, and ptr + 1 (or &ptr[1]) points to sub2. sub1 and sub2 have no actual relation to each other, and can be anywhere in memory, but because it's a pointer to a pointer, the double-dereference of a 2D array is preserved, even though the memory structure is not compatible.

Arrays of type T decay to pointers to type T, but arrays of arrays of type T do not decay to pointers to pointers to type T, they decay to pointers to arrays of type T. So when our 2D arr decays to a pointer, it is not a pointer to a pointer to an int, but a pointer to an int [2]. The full name of this type is int (*)[2], and to make your line of code work you'd want to use

int (*ptr)[2] = arr;

Which is the correct type. ptr expects to point to a contiguous array of memory, like arr does - ptr (or &ptr[0]) points to arr and ptr + 1 (or &ptr[1]) points to &arr[1]. ptr[0] points to the box that holds 1, and ptr[1] points to the box that holds 3, so ptr[0][0] yields 1, ptr[0][1] yields 2, and so on.

Why do you need to know this? 2D pointers seem more complicated than they're worth - if you were using malloc you'd have to call malloc repeatedly in a loop, and do the same for free. OR, you could use some evil* trickery to make a flat, 1-dimensional allocation of memory act like a 2D array:

// x and y are the first and second dimensions of your array
// so it would be declared T arr[x][y] if x and y were static

int (*arr)[y] = malloc(x * y * sizeof(arr[0][0]));
if(!arr) /* error */;

Now arr points to a contiguous block of arrays of size y of int objects. Since the object it points to is an array, we don't need the double-pointer-indirection of int ** objects, and when you're done, you can free it with one call:

free(arr);

Compare this to a version using int **:

int **arr = malloc(x * sizeof(*arr));
if(!arr) /* error */;
for(size_t ii = 0; ii < x; ii++)
  {
    arr[ii] = malloc(y * sizeof(**arr));
    if(!arr[ii])
      {
        free(arr[ii]);
        free(arr);
      }
  }
// do work
for(size_t ii = 0; ii < x; ii++)
    free(arr[ii]);
free(arr);

The above code has a memory leak. See if you can find it. (Or just use the version with those seemingly tricky pointers-to-arrays.)

Answer 3

The famous decay convention: an array is treated as a pointer that points to the first element of the array.

int a[2] = {1,2};
int* b = a; //decay

But the decay convention shouldn't be applied more than once to the same object.

int a[2][2]={1,2,3,4};
int** b = a; //decay more than once