2D Matrix allocation on heap in c++

I am looking for a way to allocate a 2D (m x n) matrix on the heap where the elements are consecutive in memory. Currently I know of two ways to accomplish that:

First approach

int* M = new int[m * n];

• Pro: The size of M can by dynamically determined.
• Con: Indexing of M is a bit of a pain. (M[i * m + j])

Second approach

typedef 开发者_如何学Goint dim[2];
dim* M = new dim[n];

• Pro: Indexing of M is just how I want it to be.
• Con: The size of the first dimension (m) cannot be set dynamically.

Question

Is there a way to allocate a 2D matrix dynamically on the heap where I can index the elements with [i][j] and the memory allocation is consecutive?

I know it would make a lot of sense to use a class for that, but I am specifically looking for a way as described above.

You can try this

int** M = new int*[m];
int *M_data = new int[m*n];

for(int i=0; i< m; ++i) 
{
    M[i] = M_data + i * n;
}

Here is a minimal version of the IntArray2D class I mentioned in my comment:

class IntArray2D
{
    std::vector<int> data_;
    int height_;
    int width_;

public:

    IntArray2D(int height, int width)
    : data_(height * width), height_(height), width_(width) 
    {
    }

    int* operator[](int index)
    {
        return &data_[index * width_];
    }

    const int* operator[](int index) const
    {
        return &data_[index * width_];
    }
};

Example usage:

IntArray2D test(100, 10);
test[99][9] = 42;
int i = test[0][0];

You may want to add bounds checking, and to do that in both dimensions, you need to return an appropriate proxy object instead of a pointer. Exercise left to the reader ;-)

NOTE: see the edit below for ways to do it. I will keep the original post as is.

Original post

To make both sizes dynamic AND the elements consecutive, you have no other way than your first method. (note: see the edit, there are ways to do it, but with g++)

Think of it this way: When you tell the compiler to compute array[i][j], it would automatically translate it to either:

*(array+i*m+j)

if the array is static and m (the number of columns) is known. Or if the array is 2D (of type type **):

*(*(array+i)+j)

The second case is how you would do it normally with 2D arrays, but the data are NOT consecutive. That leaves you with the first option. Now in the first option, at compile time, the compiler has to know m. If you want m to be set at runtime, the compiler just can't compute i*m+j.

Now there are ways to work around this. One is the use of classes as you mentioned, which wraps around the array = new type[n*m]; and overloads the [] operator properly. Another way to do it, which would require more memory (and thus I personally don't recommend) is to take a second array of type type ** and instead of setting each element to a new type[m], you set it to the beginning of rows in your one dimensional array.

Nonetheless, bottom line is, somewhere you have to have new type[n*m]

Edit: methods to do it, using g++

This emerged from the comments below:

type *array_helper = new type[n*m];
type (*array)[m] = (type (*)[m])array_helper;

Then you can use array and the elements are consecutive.

I also tried this, and it worked

type array[n][m];

and I printed the addresses, specifically checked array[i][m-1] and array[i+1][0] and the addresses are consecutive.

You want a pointer-to-(int-array):

 cin >> w >> h;
 int (*data)[w] = (int (*)[w])new int[w*h];
 for(int y=0;y<h;y++)
 for(int x=0;x<w;x++)
     data[y][x] = (w*y)+x;

Building off crazyjul's answer you can do it with just one memory allocation.

int **arr = new int*[col*(row+1)];
for(int a=0; c<col; ++a){
    arr[a] = (int*)&arr[(a+1)*row];
}

C-like pseudocode:

int** M = new int*[m];
for(int i in 0..m-1) {
    M[i] = new int[n];
}

Use boost array, matrix or STL vector?

One more thing for your matrix: Why shouldn't my Matrix class's interface look like an array-of-array?