How do i allocate memory for a 2d array?

Question

How do i declare a 2d array using the 'new' operator? My book says this:

int (*p)[4];
p=new[3][4];

but it doesn't make sense to me. p is a pointer to an array of 4 ints, so how can it be made to point to a 2d array?

Answer 1

It seems you need pointer to pointer. EDIT: Well, to be more exact, the following example creates an array of pointers to arrays.

First do:

int **p = new int*[NUM];

Here you've created array of pointers. Now you need to create another array for every of them. That you can do this way:

for(int i = 0; i < NUM; i++)
{
    p[i] = new int[ANOTHER_NUM];
}

For deallocation you do similar, but in reverse way:

for(int i = 0; i < NUM; i++)
{
    delete[] p[i];
}

And finally:

delete[] p;

Now you can work with it. This way you can create N-dimensional array, just add more '*'. If you have any other particular question, ask in the comments, please.

But, generally, for further info I recommend you to try Google first with questions like "2D array in C++" or "dynamic allocation of 2D array C++", i. e. this query.

Answer 2

Other answers cover having a pointer array for your rows, with a pointer to an int array per row. Another option is to simply allocate a 1-D array big enough to hold all the 2-D array's elements:

int* p = new int [3 * 4];

Then instead of using the p[r][c] syntax, you use p[r * kNumCols + c]. In this example, kNumCols = 4. This is generally what's done in LAPACK-style number crunching, since it keeps things contiguous in memory and you don't need to allocate so many memory blocks.

Note: This generally is not slower than the alternative in practice, because the row offset calculation is moved out of the loop by the common subexpression optimization. Also, many optimizers know to look for this pattern. Further, by keeping your data co-located in a single block of memory, the data is more likely to stay in cache.

In C++, you could implement the p[][] notation with a helper template class:

template<class T>
class Array2DPtrRow
{public:
    Row(T* row_): row(row_) {}
    operator T*() { return row; }
    T& operator [](size_t c) { return row[c]; }
private:
    T* row;
};

template<class T, size_t NC>
class Array2DPtr
{public:
    Array2DPtr(T* buf_): buf(buf_) {}
    operator T*() { return buf; }
    Array2DPtrRow<T> operator [](size_t r)
        { return Array2DPtrRow<T>(buf + NC * r); }
private:
    T* buf;
};

This optimizes down to the same code as above, but allows you to use [][] notation and requires you to know your array dimensions at compile time. Usage example:

Array2DPtr<int, 4> p(new int[3 * 4]);
p[1][2];

This could be converted to make NC into a class member instead of a template parameter, but then the final object isn't just a pointer any more:

template<class T>
class Array2DPtr
{public:
    Array2DPtr(T* buf_, size_t nc_): buf(buf_), nc(nc_) {}
    operator T*() { return buf; }
    Array2DPtrRow<T> operator [](size_t r)
        { return Array2DPtrRow<T>(buf + nc * r); }
private:
    T* buf;
    size_t nc;
};

Array2DPtr<int> p(new int[3 * 4], 4);
p[1][2];

Note that none of these classes need copy constructors, assignment operators, or destructors because they don't take ownership of the pointed-to memory any more than a regular pointer does. So to release the memory, you still need to do:

delete[] p;

Or if your compiler can't figure it out:

delete[] (int*)p;