Dynamic 2D Array

[Vijay0753]

Can someone explain how this works? I'm a little confused with the pointer to a pointer idea

    int **memo = new int*[rows];
    for (int i =0; i<rows; i++) 
        memo[i] = new int[cols];
   

[TheToaster]

The first line declares a pointer to a pointer called memo. What this means is that you have a pointer (*), where the element that it points to is of type int*.

When you get to the second line, you are dynamically allocating an array of int*'s, of size rows. In memory, this looks like this (assuming rows is 3):

//memo
//[int**] --------->[int*][int*][int*] 

Notice that memo is pointing to the first element of the array, or the first int* in the array of 3 int*'s. A pointer to an array will always work like this. It always points to the first element. You can get the other elements by using the bracket notation and moving the pointer.

Thus, a for loop is used to move through each element of the array (remember, each element is an int*) and allocate a new array of 3 ints for each pointer. Each int* after this operation will point to the first element of another array. after the for loop, it looks sort of like this.

//                      [int] [int] [int]
//                      [int] [int] [int]
//                      [int] [int] [int]
//                        ^      ^     ^
// memo                   |      |     |
//[int**] -------------->[int*][int*][int*] 

Thus, you are left with a 3x3 array. When you access it, you must first choose which int* in the first array you want (the columns), then you choose which int of the array that int* points to you want (row).

[Vijay0753]

Do i not choose the row first and then the column?

[Handy Andy]

Hello Vijay0753,

Yes. Whether it is a regular or dynamic array I have alway seen it referred to as row then column.

Maybe this might help:

[int*][int*][int*][int*][int*][int*][int*][int*][int*][int*][int*][int*]
row-0 col-0 col-1 col-2 row-1 col-0 col-1 col-2 row-2 col-0 col-1 col-2

And you might understand it better looking at it this way:

[row*][col*][col*][col*]
[row*][col*][col*][col*]
[row*][col*][col*][col*]

Andy

[dutch]

Don't allocate the row data one row at a time.
Instead, allocate it all at once.

#include <iostream>
#include <iomanip>
using namespace std;

int main() {

    int rows = 0, cols = 0;
    cout << "Enter rows and cols: ";
    cin >> rows >> cols;

    // allocate
    int **a = new int*[rows];      // allocate row pointers
    a[0] = new int[rows * cols];   // allocate data
    for (int r = 1; r < rows; ++r) // set row pointers
        a[r] = a[r - 1] + cols;

    // fill
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            a[r][c] = (r+1) * (c+1);

    // print
    for (int r = 0; r < rows; ++r) {
        for (int c = 0; c < cols; ++c) 
            cout << setw(3) << a[r][c] << ' ';
        cout << '\n';
    }

    // delete
    delete[] a[0]; // delete data
    delete[] a;    // delete row pointers
}

[jonnin]

^^^ I can't stress this enough. It is much more efficient in a dozen or more ways, and if the dimensions are large, the savings can be substantial.

[Vijay0753]

 int **a = new int*[rows];      // allocate row pointers
    a[0] = new int[rows * cols];   // allocate data
    for (int r = 1; r < rows; ++r) // set row pointers
        a[r] = a[r - 1] + cols;

    // fill
    for (int r = 0; r < rows; ++r)
        for (int c = 0; c < cols; ++c)
            a[r][c] = (r+1) * (c+1);

" a[0] = new int[rows * cols];"
Here, we're creating a row with the capacity of rows * cols. How does that help?

" a[r] = a[r - 1] + cols;"
Why are we adding the number of cols to an element in the array a[r]?

Sorry if I sound dumb, I'm new to this

[jonnin]

How does that help?
it puts all your data in one solid block. that means you can choose to iterate it directly, with a 1-d for loop, instead of a 2-d for loop, which depending on what you are doing is often useful. Its a triple whammy to do it the other way: you pay for nested loops (2 conditional checks, 2 variable increments, etc), you pay for page faults (data isnt a solid block), and you pay for indexing (its more internal math to index 2-d than 1-d). You won't notice the speed on today's bajillion ops per second, until you need something in a hurry or have something huge.

It also lets you reshape the data, eg at 100 item can be 1x100, 2x50, 10x10, etc. You can't do that with non solid blocks. It lets you memcpy, or .write(), etc without any issues, and more efficiently. And these are just a few examples. Most of what you can do better with 1 block you can do with 2, its just faster. In a few places, though, you can't do it at all without a data copy that was not necessary or jumping thru hoops. The read/write ability alone is pure gold as file read/write are often bottlenecks.

that addition is not data, its pointers. reread that line of code until you understand that this is pointer math, not data!! What ie is doing is giving you a big block of values...
0,1,2,3,4,5,6,7,8,9,...
lets say you want to break that into a 2x5...
your first row pointer is a 0, your second is at 5. cols is 5. so the pointer+0 and the pointer+5 give you the row pointers that break it into 2-d. You are just taking addresses in the right spots to make it look like 2-d, and can be indexed etc 2-d, but its still one nice 1-d block when you need that capability.

You are not dumb, pointers take a bit to fully understand. We all went thru it.