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

This is a discussion on Newbie question: Right way of creating a matrix using the new operator? within the C++ Programming forums, part of the General Programming Boards category; Arrays are always contiguous in memory. Yes, that is why pointer arithmetic works. However, when you have an array of ...

  1. #16
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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?
    Last edited by 7stud; 04-25-2005 at 10:06 AM.

  2. #17
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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.

  3. #18
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    Last edited by 7stud; 04-25-2005 at 10:17 AM.

  4. #19
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    >>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.

  5. #20
    Registered User
    Join Date
    Apr 2005
    Posts
    5
    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 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.

  6. #21
    Registered User
    Join Date
    Apr 2003
    Posts
    2,662
    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.
    Micko:

    Your code is somewhat confusing but I like your method a lot..
    If I understand it correctly, it does this:
    data:

    1,1,1
    2,2,2
    1)
    creates an array:

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

    int* <-------data
    int*
    3)
    takes each pointer in the pointer array and points it at the data:
    1 <-----int*
    1
    1
    2 <-----int*
    2
    2
    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;
    }
    Last edited by 7stud; 04-25-2005 at 08:18 PM.

  7. #22
    Registered User
    Join Date
    Jan 2005
    Posts
    7,344
    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.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Weird errors.
    By Desolation in forum C++ Programming
    Replies: 20
    Last Post: 05-09-2007, 02:10 PM
  2. Replies: 6
    Last Post: 11-08-2005, 03:05 PM
  3. Replies: 3
    Last Post: 04-29-2005, 03:03 AM
  4. & operator question
    By VanJay011379 in forum C++ Programming
    Replies: 5
    Last Post: 07-10-2002, 07:13 PM
  5. Help on scrolling matrix for a newbie
    By Saturn V in forum C++ Programming
    Replies: 1
    Last Post: 06-04-2002, 10:12 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21