How do I declare a 2d array in C++ using new?

Question

How do i declare a 2d array using new?

Like, for a "normal" array I would:

int* ary = new int[Size]

but

int** ary = new int[sizeY][sizeX]

a) doesn't work/compile and b) doesn't accomplish what:

int ary[sizeY][sizeX] 

does.

Answer 1

Here, I have two options. The first one shows the concept of an array of arrays or pointer of pointers. I prefer the second one because the addresses are contiguous, as you can see in the image.

#include <iostream>

using namespace std;


int main(){

    int **arr_01,**arr_02,i,j,rows=4,cols=5;

    //Implementation 1
    arr_01=new int*[rows];

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

    for(i=0;i<rows;i++){
        for(j=0;j<cols;j++)
            cout << arr_01[i]+j << " " ;
        cout << endl;
    }


    for(int i=0;i<rows;i++)
        delete[] arr_01[i];
    delete[] arr_01;


    cout << endl;
    //Implementation 2
    arr_02=new int*[rows];
    arr_02[0]=new int[rows*cols];
    for(int i=1;i<rows;i++)
        arr_02[i]=arr_02[0]+cols*i;

    for(int i=0;i<rows;i++){
        for(int j=0;j<cols;j++)
            cout << arr_02[i]+j << " " ;
        cout << endl;
    }

    delete[] arr_02[0];
    delete[] arr_02;


    return 0;
}

Answer 2

typedef is your friend

After going back and looking at many of the other answers I found that a deeper explanation is in order, as many of the other answers either suffer from performance problems or force you to use unusual or burdensome syntax to declare the array, or access the array elements ( or all the above ).

First off, this answer assumes you know the dimensions of the array at compile time. If you do, then this is the best solution as it will both give the best performance and allows you to use standard array syntax to access the array elements.

The reason this gives the best performance is because it allocates all of the arrays as a contiguous block of memory meaning that you are likely to have less page misses and better spacial locality. Allocating in a loop may cause the individual arrays to end up scattered on multiple non-contiguous pages through the virtual memory space as the allocation loop could be interrupted ( possibly multiple times ) by other threads or processes, or simply due to the discretion of the allocator filling in small, empty memory blocks it happens to have available.

The other benefits are a simple declaration syntax and standard array access syntax.

In C++ using new:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {

typedef double (array5k_t)[5000];

array5k_t *array5k = new array5k_t[5000];

array5k[4999][4999] = 10;
printf("array5k[4999][4999] == %f\n", array5k[4999][4999]);

return 0;
}

Or C style using calloc:

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {

typedef double (*array5k_t)[5000];

array5k_t array5k = calloc(5000, sizeof(double)*5000);

array5k[4999][4999] = 10;
printf("array5k[4999][4999] == %f\n", array5k[4999][4999]);

return 0;
}

Answer 3

Although this popular answer will give you your desired indexing syntax, it is doubly inefficient: big and slow both in space and time. There's a better way.

Why That Answer is Big and Slow

The proposed solution is to create a dynamic array of pointers, then initializing each pointer to its own, independent dynamic array. The advantage of this approach is that it gives you the indexing syntax you're used to, so if you want to find the value of the matrix at position x,y, you say:

int val = matrix[ x ][ y ];

This works because matrix[x] returns a pointer to an array, which is then indexed with [y]. Breaking it down:

int* row = matrix[ x ];
int  val = row[ y ];

Convenient, yes? We like our [ x ][ y ] syntax.

But the solution has a big disadvantage, which is that it is both fat and slow.

Why?

The reason that it's both fat and slow is actually the same. Each "row" in the matrix is a separately allocated dynamic array. Making a heap allocation is expensive both in time and space. The allocator takes time to make the allocation, sometimes running O(n) algorithms to do it. And the allocator "pads" each of your row arrays with extra bytes for bookkeeping and alignment. That extra space costs...well...extra space. The deallocator will also take extra time when you go to deallocate the matrix, painstakingly free-ing up each individual row allocation. Gets me in a sweat just thinking about it.

There's another reason it's slow. These separate allocations tend to live in discontinuous parts of memory. One row may be at address 1,000, another at address 100,000—you get the idea. This means that when you're traversing the matrix, you're leaping through memory like a wild person. This tends to result in cache misses that vastly slow down your processing time.

So, if you absolute must have your cute [x][y] indexing syntax, use that solution. If you want quickness and smallness (and if you don't care about those, why are you working in C++?), you need a different solution.

A Different Solution

The better solution is to allocate your whole matrix as a single dynamic array, then use (slightly) clever indexing math of your own to access cells. The indexing math is only very slightly clever; nah, it's not clever at all: it's obvious.

class Matrix
{
    ...
    size_t index( int x, int y ) const { return x + m_width * y; }
};

Given this index() function (which I'm imagining is a member of a class because it needs to know the m_width of your matrix), you can access cells within your matrix array. The matrix array is allocated like this:

array = new int[ width * height ];

So the equivalent of this in the slow, fat solution:

array[ x ][ y ]

...is this in the quick, small solution:

array[ index( x, y )]

Sad, I know. But you'll get used to it. And your CPU will thank you.