Pointer-to-pointer dynamic two-dimensional array

Question

First timer on this website, so here goes..

I'm a newbie to C++ and I'm currently working through the book "Data structures using C++ 2nd ed, of D.S. Malik".

In the book Malik offers two ways of creating a dynamic two-dimensional array. In the first method, you declare a variable to be an array of pointers, where each pointer is of type integer. ex.

int *board[4];

..and then use a for-loop to create the 'columns' while using the array of pointers as 'rows'.

The second method, you use a pointer to a pointer.

int **board;
board = new int* [10]; 

etc.

My question is this: which is the better method? The ** method is easier for me to visualize, but the first method can be used in much the same way. Both ways can be used to make dynamic 2-d arrays.

Edit: Wasn't clear enough with the above post. Here's some code I tried:

int row, col;

cout << "Enter row size:";
cin >> row;
cout << "\ncol:";
cin >> col;

int *p_board[row];
for (int i=0; i < row; i++)
    p_board[i] = new int[col];

for (int i=0; i < row; i++)
{
    for (int j=0; j < col; j++)
    {
        p_board[i][j] = j;
        cout << p_board[i][j] << " ";
    }
    cout << endl;
}
cout << endl << endl;

int **p_p_board;
p_p_board = new int* [row];
for (int i=0; i < row; i++)
    p_p_board[i] = new int[col];

for (int i=0; i < row; i++)
{
    for (int j=0; j < col; j++)
    {
        p_p_board[i][j] = j;
        cout << p_p_board[i][j] << " ";
    }
    cout << endl;
}

Solution 1

The first method cannot be used to create dynamic 2D arrays because by doing:

int *board[4];

you essentially allocated an array of 4 pointers to int on stack. Therefore, if you now populate each of these 4 pointers with a dynamic array:

for (int i = 0; i < 4; ++i) {
  board[i] = new int[10];
}

what you end-up with is a 2D array with static number of rows (in this case 4) and dynamic number of columns (in this case 10). So it is not fully dynamic because when you allocate an array on stack you should specify a constant size, i.e. known at compile-time. Dynamic array is called dynamic because its size is not necessary to be known at compile-time, but can rather be determined by some variable in runtime.

Once again, when you do:

int *board[4];

or:

const int x = 4; // <--- `const` qualifier is absolutely needed in this case!
int *board[x];

you supply a constant known at compile-time (in this case 4 or x) so that compiler can now pre-allocate this memory for your array, and when your program is loaded into the memory it would already have this amount of memory for the board array, that's why it is called static, i.e. because the size is hard-coded and cannot be changed dynamically (in runtime).

On the other hand, when you do:

int **board;
board = new int*[10];

or:

int x = 10; // <--- Notice that it does not have to be `const` anymore!
int **board;
board = new int*[x];

the compiler does not know how much memory board array will require, and therefore it does not pre-allocate anything. But when you start your program, the size of array would be determined by the value of x variable (in runtime) and the corresponding space for board array would be allocated on so-called heap - the area of memory where all programs running on your computer can allocate unknown beforehand (at compile-time) amounts memory for personal usage.

As a result, to truly create dynamic 2D array you have to go with the second method:

int **board;
board = new int*[10]; // dynamic array (size 10) of pointers to int

for (int i = 0; i < 10; ++i) {
  board[i] = new int[10];
  // each i-th pointer is now pointing to dynamic array (size 10) of actual int values
}

We've just created an square 2D array with 10 by 10 dimensions. To traverse it and populate it with actual values, for example 1, we could use nested loops:

for (int i = 0; i < 10; ++i) {   // for each row
  for (int j = 0; j < 10; ++j) { // for each column
    board[i][j] = 1;
  }
}

Solution 2

What you describe for the second method only gives you a 1D array:

int *board = new int[10];

This just allocates an array with 10 elements. Perhaps you meant something like this:

int **board = new int*[4];
for (int i = 0; i < 4; i++) {
  board[i] = new int[10];
}

In this case, we allocate 4 int*s and then make each of those point to a dynamically allocated array of 10 ints.

So now we're comparing that with int* board[4];. The major difference is that when you use an array like this, the number of "rows" must be known at compile-time. That's because arrays must have compile-time fixed sizes. You may also have a problem if you want to perhaps return this array of int*s, as the array will be destroyed at the end of its scope.

The method where both the rows and columns are dynamically allocated does require more complicated measures to avoid memory leaks. You must deallocate the memory like so:

for (int i = 0; i < 4; i++) {
  delete[] board[i];
}
delete[] board;

I must recommend using a standard container instead. You might like to use a std::array<int, std::array<int, 10> 4> or perhaps a std::vector<std::vector<int>> which you initialise to the appropriate size.

Solution 3

In both cases your inner dimension may be dynamically specified (i.e. taken from a variable), but the difference is in the outer dimension.

This question is basically equivalent to the following:

Is int* x = new int[4]; "better" than int x[4]?

The answer is: "no, unless you need to choose that array dimension dynamically."

Comments

[user2280041]

I already know most of that. I just want to know if there's any real difference in the two methods used. I posted some code in my edit to help you understand better.

[user2280041]

The first method wont work even if you use a variable to determine the array size? //int *board[x]; With a variable used you would no longer have a static number of rows, and then end up with a dynamic 2D array, right? Sorry if this seems stupid, but I'm trying to understand what you're telling me.

[Alexander Shukaev]

This is what I was suspecting. You're doing on of the most popular mistakes among C++ newcomers by assuming that. I did it myself when I was novice too, so it's fine. You cannot do int *board[x]; if x is not const, i.e. again known at compile-time. Try yourself, and you'll get compile error. In addition, I've expanded my answer, please read it, and try to understand again. If you have troubles, ask again.

[Lightness Races in Orbit]

@user2280041: Why didn't you read sftrabbit's lovingly-produced answer? It took him some time to do. I quote: The major difference is that when you use an array like this, the number of "rows" must be known at compile-time. He went on to examine other differences, which you might find interesting.

[Lightness Races in Orbit]

Actually, no, you most likely will not get a compile error. Some toolchains support non-standard extensions to make that valid. (That doesn't make it a good idea, though.)

[user2280041]

@Lightness Races in Orbit - Yeah, this is why I was so confused over this. I'm using codeblocks with GCC, which supports it through some kind of extension. The standard doesn't allow it, so I'll stick to the pointer to pointer road.

[Andrew]

NOTE: this does not discuss deleting the arrays, and therefore doesn't discuss how to clean up the memory pointed to by the pointers. Other answers address this already.

[vincent thorpe]

@Alexander Shukaev but if we need to have two dimensional array pointer-to-pointer of a list of objects from a class that does require constructor? how could be done this ? the object must be like this: TEdit bucket3 = new TEdit(this); but how we can get a **arrray with this kind of object? bucket3 = new TEdit[5](this); bucket3 = new TEdit(this)[5]; // both statements gives error Russian are the best with Cpp delphi.