How does a pointer to a pointer correspond to a 2D array?

Question

I know this question was probably asked before, but I don't understand it in this context:

Here's the code I'm trying to examine, I'll comment it. Please let me know where I'm wrong

int **A;                    // declaring a pointer to a pointer

A = new int*[n];            // assigning that pointer to a newly-allocated 
                            // space (on the heap) for an array
                            // of [size n] of pointers to integers

for (i = 0; i < n; ++i)     // looping from 0 to n-1
    A[i] = new int[n];      // assigning each slot's pointer to a 
                            // new array of size n?

for (i = 0; i < n; ++i)     // loop through all the rows
    for (j = 0; j < n; ++j) // loop through each column for the current row
        A[i][j] = 0;        // assign the value to 0

Please let me know where I'm wrong. I don't understand anything from A = new int*[n]; I'm just trying to figure it out using common sense but I'm having troubles.

Thank you!

Answer 1

Your code and comments are correct. To clear up the confusion about pointers:

• A 2D array is simply an array of arrays.
• In order to allow the arrays to have a dynamic size (i.e. size n not known at compile time), an array of pointers is created. Each pointer in the array itself points to an array of ints.
• The resulting structure is very similar to an array of arrays - it's an array of pointers to arrays. The pointers are there simply because you cannot have e.g. int a[n][n]; at compile time because the size is not known.

Here's a diagram of this:

> [       ]      //">" is a pointer, pointing at an array ([ ])


    [ ]  [ ]  [ ]
> [  ^    ^    ^ ]  // The array is an array of pointers "^", each of which points to an array

Answer 2

What's an "array"? It's a block of memory, represented by its address.

If you want a 2-dimensional array, then you need lots of those blocks -- and you need to know where each of them is located. That means you need an array of addresses, or in other words, an array of int* -- which gives you an int**.

What new int*[n] does is that it allocates memory for an array of addresses, and inside each of them, you go and put the address of an array of ints, allocated via new int[n].