Newbie question: Right way of creating a matrix using the new operator?

Hi,

I'm trying to dynamically create a matrix, let's call it M, which can be accesed using the usual M[i][j] notation. That's it, it should behave as if I had declared it as a double M[5][5], except the size should be a variable rather than 5.

This is the simplest example:

Code:

---

#include <iostream.h>

void createMatrix(int size) {

        double *M = new double[size*size]; // doesn't work :(

        /*
        // This does work, but is really awful... there's got to be a better way!

        double **M = new double*[size];

        for (int k = 0; k < size; k++)
                M[k] = new double[size];

        */

        // this MUST work:

        for(int i = 0; i < size; i++)
                for(int j = 0; j < size; j++)
                        M[i][j] = 3.141592;        // whatever

        delete[] M;
}

int main() {
        int n;

        cout << "Size of the matrix? ";
        cin >> n;

        createMatrix(n);

        return 0;

}

---

Please, tell me there's a better solution that the horrible hack I did!!

:)

The double pointer method is the only way I know that you can dynamically create a 2*2 array besides using a container. Oh and it is <iostream> and not <iostream.h> and put it in the std namespace.

Code:

---

void createMatrix(int size)
{
        double **M =  new double*[size];
        for(int i=0; i < size; i++)
                M[i] = new double[size];

        // Do something with it here

        for(int i=0; i < size; i++)
                delete[] M[i];
        delete[] M;
}

---

Another why using vectors:

Code:

---

void createMatrix(int size)
{
        vector< vector<double> > M;
        M.resize(size);
        for(int i=0; i < size; i++)
                M[i].resize(size);
}

---

Thanks for the reply... does anybody else know if the right way of dynamically creating a n*n array is:

Code:

---

        double **M = new double*[size];

        for (int k = 0; k < size; k++)
                M[k] = new double[size];

---

Because this is really ugly syntax, and, if I understand memory allocation correctly, awfully inefficient because not only we have significant overhead allocating memory in a loop but we'll also, with all probability, end with a fragmented matrix, as there's no reason to expect those allocations will put our new arrays contiguously in memory.

This program is supposed to use a very large matrix.

Quote:

---

Originally Posted by Thantos

Code:

---

void createMatrix(int size)
{
        double **M =  new double*[size];
        for(int i=0; i < size; i++)
                M[i] = new double[size];

        // Do something with it here

        for(int i=0; i < size; i++)
                delete[] M[i];
        delete[] M;
}

---

---

Thanks for the correction... one memory leak less :)

[QUOTE]
Another why using vectors:

Code:

---

void createMatrix(int size)
{
        vector< vector<double> > M;
        M.resize(size);
        for(int i=0; i < size; i++)
                M[i].resize(size);
}

---

This is much better... but, can I access individual members of M with the M[i][j] notation if I use this? Also, is this what you guys mean when you said "using a container"?

Quote:

---

but, can I access individual members of M with the M[i][j] notation if I use this?

---

...and how many seconds would that take to test? :confused:

Quote:

---

Also, is this what you guys mean when you said "using a container"?

---

Yes.

Quote:

---

Originally Posted by 7stud

...and how many seconds would that take to test? :confused:

---

Ok, I tested it... seems to work great :D

But what about efficiency? It seems to me this is the same thing I was doing initially but with a better syntax, which probably means the overhead and fragmentation problems I wrote about are still there...

And there's no need to deallocate memory while using containers... right?

Ya all of the deallocation is taken for you with the containers within the destructor of the container you are using. I am not sure what you mean about fragmentation when using dynamic memory but I don't think so.

Because calls of new and delete are generally slow, thers is one way I like:

Code:

---

        //Allocate the actual data

        int* rawData = new int[rows*cols];
 
        //Allocate pointers to the data
        int** data = new int*[rows];
 
        //Point the pointers into the data
        for (int i=0; i < rows; ++i)
            data[i] = &rawData[cols*i];

---

I hope this code will not confuse you.

- Micko

Quote:

---

But what about efficiency? It seems to me this is the same thing I was doing initially but with a better syntax, which probably means the overhead and fragmentation problems I wrote about are still there...

---

That's what I was wondering about, too.

Quote:

---

And there's no need to deallocate memory while using containers... right?

---

The class takes care of all that: you can expand or contract the vector at will as well using insert(), pushback(), and erase().

Quote:

---

I am not sure what you mean about fragmentation when using dynamic memory but I don't think so.

---

I think he suspects that since the allocations take place at different times, e.g. one allocation per loop iteration, that the allocated memory will not necessarily be contiguous. My first question is: since dynamically allocated memory is allocated on the heap, is there a way for any other processes to allocate memory on the heap in between a for-loops allocations? My second question is: does it even matter whether the memory is contiguous or not. The look up is done with a pointer, so is it even relevant where the actual arrays are located?

Arrays are always contiguous in memory. And yes, it does matter for arrays. When you code something like a[5], that tells the computer to go start at *a, or a[0], and go over five. Therefore, those array indices must be contiguous in memory.

Container classes are another story, however. You could implement a container to act like an array that's really a linked list or hash under the hood.

A multi dimensional array allocated like this probably won't be contigious. But thats ok as each dimension will be contigious onto itself. It only becomes a problem when you try to treat a multi dimensional array as a single dimensional array.

Quote:

---

Container classes are another story, however. You could implement a container to act like an array that's really a linked list or hash under the hood.

---

Except vectors require that &v[1] == (&v[0] + 1)

Quote:

---

Originally Posted by Thantos

Except vectors require that &v[1] == (&v[0] + 1)

---

I wasn't talking about the vector class. I know that the STL containers have restrictions on speed and space and such. That doesn't stop someone from creating a class with the much of the interface of a vector with another underlying container -- even if that does mean differing performance.

I was just trying to point out that when using a class, one shouldn't overly concern oneself with the underlying structure.

>>double *M = new double[size*size]; // doesn't work :(

This does work if you index it properly. instead of indexing M[x][y], you use M[ x*size + y ].

Quote:

---

Arrays are always contiguous in memory.

---

Yes, that is why pointer arithmetic works. However, when you have an array of 10 pointers that each point to an array, the question seems to have been whether all ten arrays are contiguous in memory, which presumably is what the poster was referring to when he asked about "fragmented memory", and secondly whether that even matters?

It depends 7stud.

double M[5][10] is contigious in memory So I could go:

double* ptr = M[0];
ptr[25] = 10;

And it would be "okay".

There are ways of having a two dimensional (or really any multi dimensional) array reference a single contigious block of memory. They just aren't really worth it most of the time.

Just a bit of review. The question is about dynamically allocating a two dimensional array--not statically declaring a two dimension array like this:

double nums[3][4];

Here is the code:

Code:

---

double **M = new double*[size];

for (int k = 0; k < size; k++)
        M[k] = new double[size];

---

Is there any reason to believe each allocation of memory on the heap by each iteration of the for loop is contiguous in memory? Does that matter, i.e does it somehow "fragment the memory"? I'm inclined to think it doesn't matter.

>>Is there any reason to believe each allocation of memory on the heap by each iteration of the for loop is contiguous in memory?

I dont think you can assume each allocation will be contiguous.

These are some seriously great replies! This board rocks! Here are a few additional comments:

Micko:

Your code is somewhat confusing but I like your method a lot... just one allocation and we end with a matrix of contiguous data. This is just what I was looking for. The fact we have to pull this kind of tricks for allocating a matrix really shows that C++ was never designed with numerical computation in mind :D Fortran kicks some serious C++ butt in this area.

Perspective:

Great tip, I'll keep it in mind for future use.

7stud and Thantos:

Why it matters that it is contiguous in memory?

Because the algorithms that I'll apply to this matrix won't iterate trough it from left to right and top to bottom but will need to move both vertically and across diagonals. Existing code assumes the data is contiguous in memory.

Besides, if the memory is not contiguous there will be lots of things going on under the surface each time we move from one place to other and this could easily double or triple (or worse) the number of instructions required. This is a computationally intensive algorithm that uses both large datasets and iterative methods so it must be as efficient as possible. Running 2-3 times slower isn't acceptable.

I may be wrong, but I think even doing something as simple as M[i][j+1] = M[i+1][j-1] will have significant overhead if the memory isn't contiguous.

I don't think there is any reason to believe consecutive allocations of memory must result in a contiguous block of memory and therefore having such an outcome is an unlikely result.

At least, that's what the way I understand it.

Quote:

---

I may be wrong, but I think even doing something as simple as M[i][j+1] = M[i+1][j-1] will have significant overhead if the memory isn't contiguous.

---

I'm just speculating, but I don't see why accessing an element of an array like that would be any different for contiguous or non contiguous memory. It seems to me, in both cases you would be looking up a row at an address stored in a pointer and then moving to a specific offset in that row. It's not as if you were doing something like M+10, or M + 30 to get to the element, which would fail if the memory wasn't contiguous.

Quote:

---

Micko:

Your code is somewhat confusing but I like your method a lot..

---

If I understand it correctly, it does this:

Quote:

---

data:

1,1,1
2,2,2

---

Quote:

---

1)
creates an array:

1 <-------rawData
1
1
2
2
2

---

Quote:

---

2)
creates an array of pointers whose size matches the number of rows in the original data:

int* <-------data
int*

---

Quote:

---

3)
takes each pointer in the pointer array and points it at the data:
1 <-----int*
1
1
2 <-----int*
2
2

---

Quote:

---

4)
which leaves you with this:
1 <-----int*<-------------data
1
1
2 <-----int*
2
2

Note the pointer rawData is irrelevant and it's not used anymore.

---

I don't undertand what Perspective was talking about here:

Quote:

---

Originally Posted by Perspective

>>double *M = new double[size*size]; // doesn't work :(

This does work if you index it properly. instead of indexing M[x][y], you use M[ x*size + y ].

---

Perspective seems to be saying you can't access the elements using the 2d array notation M[row][col], but instead you have to use 1 dimensional array notation M[n]. However, the 2d array notation works in this example:

Code:

---

#include <iostream>
using namespace std;

int main()
{

        int rows = 2;
        int cols = 3;
       
        //Allocate the actual data
        int* rawData = new int[rows*cols];
 
        //Allocate pointers to the data
        int** data = new int*[rows];
 
        //Point the pointers into the data
        for (int i=0; i < rows; ++i)
            data[i] = &rawData[cols*i];

        //Fill the array using single array notation:
        for(i=0; i < rows*cols; i++)
        {
                rawData[i] = (i+1)*10; //10, 20, 30, 40, 50, 60
        }

        //display array using single dimension notation:
        for(int j=0; j < rows*cols; j++)
        {
                cout<<rawData[j]<<endl;
        }

        //display an element of the array using 2d array notation:
        cout<<data[1][2]<<endl;  //last element in the array

        return 0;
}

---

Quote:

---

Originally Posted by Thantos

Another why using vectors:

Code:

---

void createMatrix(int size)
{
  vector< vector<double> > M;
  M.resize(size);
  for(int i=0; i < size; i++)
        M[i].resize(size);
}

---

---

Even better, vectors have constructors:

Code:

---

vector<vector<double> > M(size, vector<double>(size));

---

Done!
________________________

There are two issues here - do you want to use regular C style arrays or vectors? and Do you want to use a single dimension of contiguous memory disguised as a 2-D array? These issues are separate.

The best high-level way would be to use two dimensional vectors as in the code above. It will be fast, clear and easy to use. The performance loss from using vector is generally minimal and if used correctly often non-existant. Test it to find out if you are really worried about it.

If you find that your application is not fast enough, or if you don't care about learning good C++ coding techniques as much as making this particular program as fast and efficient as possible, you can try to use a one-dimensional C-style array like Micko showed.