Multidimensional Array Pointer

[rynone]

I need to create a dynamic array. I have read many forums and the best solution is to create a single dimensional array with pointers. However, the simplified code below provides and exception at the line as shown. I seem to misunderstand how the memory allocation works.

  class Matrix
{
public:
   int rows, cols;
   void create(int i, int j);
   double *ipp;
};

void Matrix::create(int i, int j) {
   rows = i;
   cols = j;
   iip = new double[rows*cols];  //  << Problem Here
	for (int r = 1; r <= rows; r++) {
		for (int k = 1; k <= cols; k++) {
			ipp[(r - 1)*cols + k] = 0;
		}
	}
}


//MAIN PROGRAM

int main() {
   ...
   //msize determined by user input
   
   Matrix matr;
   
   matr.create(msize, msize);
   
   ...
}

[tpb]

I don't see anything wrong with the "problem" line. But the next two lines (for loops) are running their indices from 1 up to and including rows (or cols). Idiomatically we would start them at 0 and go up to (but not including) rows or cols. Although you are subtracting 1 from r when you use it to calculate the 1D index, you aren't doing the same for k. It's best just to start them both at 0.

Here's another way of implementing a 2D matrix.

#include <iostream>
#include <iomanip>
#include <algorithm>

template <typename T>
class Matrix {

    class Row {
        T *m_p;
    public:
        Row() : m_p(nullptr) {}
        void alloc(size_t cols) {
            m_p = new T[cols];
            std::fill(&m_p[0], &m_p[cols], T());
        }
        ~Row() { delete [] m_p; }

        T& operator[](size_t i) { return m_p[i]; }
        const T& operator[](size_t i) const { return m_p[i]; }
    };

    Row *m_p;
    size_t m_rows, m_cols;

public:
    Matrix(int r, int c);
    ~Matrix() { delete [] m_p; }

    Row& operator[](size_t i) { return m_p[i]; }
    const Row& operator[](size_t i) const { return m_p[i]; }

    size_t rows() const { return m_rows; }
    size_t cols() const { return m_cols; }
};

template <typename T>
Matrix<T>::Matrix(int r, int c)
    : m_p(new Row[r]), m_rows(r), m_cols(c) {
    for (size_t i = 0; i < m_rows; i++)
        m_p[i].alloc(m_cols);
}

int main() {
    size_t rowsize = 7, colsize = 12;
    Matrix<double> m(rowsize, colsize);

    for (size_t r = 0; r < m.rows(); r++)
        for (size_t c = 0; c < m.cols(); c++)
            m[r][c] = (r+1) * (c+1);

    std::cout << std::fixed << std::setprecision(1);
    for (size_t r = 0; r < m.rows(); r++) {
        for (size_t c = 0; c < m.cols(); c++)
            std::cout << std::setw(5) << m[r][c] << ' ';
        std::cout << '\n';
    }
}

[jonnin]

memory in C is called row-major. regardless, its stored like this
for a '2 d' non pointer array like int matrix[3][3] (r-ows and c-olumns)
matrix[r][c] then looks like this in memory:
r0c0r0c1r0c2r1c0r1c2r1c3r2c0r2c1r2c2

and matrix (the name of the array) is like a pointer that points to r0c0

note that the same thing is NOT assured for double pointers.
for a double pointer, we have

ro-> c1c2c3
other data between possibly
r1 -> c1c2c3
again other data in memory, r2 could even come before r0!
r2-> c1c2c3

this is one of the problems, fragmented memory is less efficient due to page faults.

if you allocated a single pointer and manually indexed, its one solid block and you can read/write it in a single operation for files, iterate it in a 1-d loop, and dozens of other things that you just cannot do with double *. Double matrix can be collapsed to 1-d by exploiting how it exists in memory, but you can't put a very large matrix on the stack, it won't fit.

[tpb]

jonnin wrote:

this is one of the problems, fragmented memory is less efficient due to page faults

You are absolutely right. I should have mentioned that. Here's a non-fragmented version I came up with.

#include <iostream>
#include <iomanip>
#include <algorithm>

template <typename T>
class Matrix {

    class Row {
        T* m_row;
    public:
        Row(T* row) : m_row(row) {}
        T& operator[](size_t col) { return m_row[col]; }
        const T& operator[](size_t col) const { return m_row[col]; }
    };

    T *m_p;
    size_t m_rows, m_cols;

public:
    Matrix(int r, int c);
    ~Matrix() { delete [] m_p; }

    Row operator[](size_t row) { return Row(&m_p[row * m_cols]); }
    const Row operator[](size_t row) const { return Row(&m_p[row * m_cols]); }

    size_t rows() const { return m_rows; }
    size_t cols() const { return m_cols; }
};

template <typename T>
Matrix<T>::Matrix(int r, int c)
    : m_p(new T[r*c]), m_rows(r), m_cols(c) {
    std::fill(&m_p[0], &m_p[m_rows * m_cols], T());
}

int main() {
    size_t rowsize = 7, colsize = 12;
    Matrix<double> m(rowsize, colsize);

    for (size_t r = 0; r < m.rows(); r++)
        for (size_t c = 0; c < m.cols(); c++)
            m[r][c] = (r+1) * (c+1);

    std::cout << std::fixed << std::setprecision(1);
    for (size_t r = 0; r < m.rows(); r++) {
        for (size_t c = 0; c < m.cols(); c++)
            std::cout << std::setw(5) << m[r][c] << ' ';
        std::cout << '\n';
    }
}

[rynone]

Thanks for the many good answers!

I found jonnin's answer quite insightful because I have massive matrices (in excess of 20 000 x 20 000). I thought that it could be too big to fit in the memory therefore breaking it up would be better. I tried using excel but the double precision is also not enough when one has to invert the matrix, therefore I went for something stronger such as C++.

I've changed my code to follow tpb's example above and it gives me the same error , this time at line 32 (as per tpb's code above), just after I register a small matrix (24 x 24).

Line 32: ": m_p(new T[r*c]), m_rows(r), m_cols(c) {"

The error is "Unhandled exeption at 0x776D6517 (ntdll.dll) in MyApplication.exe: 0xC00000005: Access violation writing location 0x0073507C." This is a similar error which I had with my original code. It seems that the program does not want me to allocate a block of memory using a class definition. I can post my full code (or email) but it seems a bit over the top.

[Thomas1965]

Consider using a vector instead of pointers. In this way you don't need to bother about the copy and move semantics.
The CPP Core Guidelines recommend the use of STL containers over dynamic memory management.

class Matrix
{
public:
  Matrix(size_t rows, size_t cols): mRows(rows), mCols(cols)
  {
    data.resize(rows * cols, 0);
  }
  size_t mRows, mCols;
 private:
  vector<double> data;
};

I have massive matrices (in excess of 20 000 x 20 000)

This size will work only on a 64bit machine

[jonnin]

I have massive matrices (in excess of 20 000 x 20 000)

This size will work only on a 64bit machine
^^^^ More precisely, it will only fit on a 64 bit machine that has its memory mostly empty or defragmented. That bad boy takes up 3.2 * 10 to the NINTH bytes of memory. To allocate it, you need that much free memory in one solid block. The nature of matrices is that you probably need at least 2 or 3 of those in hand at once, maybe 2 sources and a result for addition or something. I think these are around 3GB each if I did that right. But you said double isn't big enough. If you go to a 10 byte, or 12 or whatever is available on your machine for extended double formats, it will need even more space!

if these are 'sparse' you can save a lot of space by using some scheme to store them in less space.

if they are not sparse, and you lack the ram, you will have to do them in chunks and swap to disk. If they will fit, carry on, but be aware that creating a dozen temporary matrices for a big equation may be out of the picture.

it should work on 24x24 though. There is a bug... you just have to find it. You can check that new actually allocated memory, as it can fail if you don't have the memory available. If that isn't it, you have something else... out of bounds bug or whatever. There are of course already done matrix libraries. Rolling your own is not recommended unless learning (use smaller matrices for this) or doing something highly specialized.

[lastchance]

rynone wrote:

I have massive matrices (in excess of 20 000 x 20 000)

rynone wrote:

one has to invert the matrix

Getting it into memory is the least of your problems.

What is your application, @rynone? Is your matrix sparse (i.e. is it mainly zeroes)? Does it have a special form (e.g. tridiagonal)? In short, where does it come from?


I take it the confusion between variables ipp and iip in your original code is just a typo/cut-and-paste error?

Can you show a little more of your latest code, please - accurately copied.

[tpb]

I've changed my code to follow tpb's example above and it gives me the same error , this time at line 32 (as per tpb's code above),

I stupidly used int instead of size_t for r and c.