How do you dynamically allocate a matrix?

Question

How do you dynamically allocate a 2D matrix in C++? I have tried based on what I already know:

#include <iostream>

int main(){
    int rows;
    int cols;
    int * arr;
    arr = new int[rows][cols];
 }

It works for one parameter, but now for two. What should I do?

Solution 1

A matrix is actually can be represented as an array of arrays.

int rows = ..., cols = ...;
int** matrix = new int*[rows];
for (int i = 0; i < rows; ++i)
    matrix[i] = new int[cols];

Of course, to delete the matrix, you should do the following:

for (int i = 0; i < rows; ++i)
    delete [] matrix[i];
delete [] matrix;

---

I have just figured out another possibility:

int rows = ..., cols = ...;
int** matrix = new int*[rows];
if (rows)
{
    matrix[0] = new int[rows * cols];
    for (int i = 1; i < rows; ++i)
        matrix[i] = matrix[0] + i * cols;
}

Freeing this array is easier:

if (rows) delete [] matrix[0];
delete [] matrix;

This solution has the advantage of allocating a single big block of memory for all the elements, instead of several little chunks. The first solution I posted is a better example of the arrays of arrays concept, though.

Solution 2

You can also use std::vectors for achieving this:

using: 'std::vector< std::vector >'

Example:

#include <vector>
std::vector< std::vector<int> > a;
  
  //m * n is the size of the matrix

    int m = 2, n = 4;
    //Grow rows by m
    a.resize(m);
    for(int i = 0 ; i < m ; ++i)
    {
        //Grow Columns by n
        a[i].resize(n);
    }
    //Now you have matrix m*n with default values

    //you can use the Matrix, now
    a[1][0]=1;
    a[1][1]=2;
    a[1][2]=3;
    a[1][3]=4;

//OR
for(i = 0 ; i < m ; ++i)
{
    for(int j = 0 ; j < n ; ++j)
    {      //modify matrix
        int x = a[i][j];
    }

}

Solution 3

Try boost::multi_array

#include <boost/multi_array.hpp>

int main(){
    int rows;
    int cols;
    boost::multi_array<int, 2> arr(boost::extents[rows][cols] ;
}

Solution 4

arr = new int[cols*rows];

If you either don't mind syntax

arr[row * cols + col] = Aij;

or use operator[] overaloading somewhere. This may be more cache-friendly than array of arrays, or may be not, more probably you shouldn't care about it. I just want to point out that a) array of arrays is not only solution, b) some operations are more easier to implement if matrix located in one block of memory. E.g.

for(int i=0;i < rows*cols;++i)
   matrix[i]=someOtherMatrix[i];

one line shorter than

for(int r=0;i < rows;++r)
  for(int c=0;i < cols;++s)
     matrix[r][c]=someOtherMatrix[r][c];

though adding rows to such matrix is more painful

Solution 5

const int nRows = 20;
const int nCols = 10;
int (*name)[nCols] = new int[nRows][nCols];
std::memset(name, 0, sizeof(int) * nRows * nCols); //row major contiguous memory
name[0][0] = 1; //first element
name[nRows-1][nCols-1] = 1; //last element
delete[] name;

View more solutions

Comments

[dmckee --- ex-moderator kitten]

Been done over and over again: stackoverflow.com/questions/365782/… stackoverflow.com/questions/527887/… and others

[pyon]

In retrospect, some of the other answers are simply much better than mine. (I still don't know C++, but at least now I'm aware that I don't know C++.) Would it be possible to accept one of them now?

[pyon]

+1 for using std::vector. I don't use the STL too much myself, but that's because I'm a masochist when it comes to memory management. Using the STL is way less error prone.

[visual_learner]

Why would you try to hack up a two-dimensional array when it's perfectly easy to make a real two-dimensional array?

[pyon]

+1 for using Boost, but using such a library depends on how good the compiler you use is at optimizing your code.

[Asongfac Roland]

because you can access the two-dimensional way in a cache friendly manner when performance is really key

[pyon]

Even better: allocate a 1D array of elements and another 1D array of pointers to the first element of every row.

[dmckee --- ex-moderator kitten]

While this works, it has a repeated manual overhead. You a prepared class (there are many) or wrap up c-style n-dimensional arrays in a class of your own devising.

[greyfade]

That's not a bad idea. It has the obvious advantage of maintaining cache locality while still keeping the multidimensional array syntax. I like it.

[Rini Ann]

Instead of resizing just construct it with the correct size. int m = 10, n = 4; std::vector< std::vector<int> > a(m, std::vector<int>(n,0));

[Patrizio Bertoni]

I'd prefer the first, for the sake of clarity.

[pyon]

@PatrizioBertoni: I prefer the second, obviously. There's a cute trick for storing an arbitrary n-dimensional matrix M as two 1-dimensional arrays, c (coefficients) and x (actual elements). Then, given a vector of indices i, the i-th element of M is just the c*i-th element of x, where * means dot product. I'm fond of this trick because (0) it works for arbitrary n, (1) it illustrates the importance of 0-based indexing, (2) for those of us who care about linear algebra, it demystifies tensor products... :-p

[Andreas]

Some explanation would be just perfect! ;)

[CutePoison]

Why do we need to deallocate each row first? Why cant we just delete [] matrix?

[pyon]

In the first possibility, each row has been allocated as a separate memory block.

[rcgldr]

@Andreas - name is a pointer to an array of size nCols, in this case, a pointer to the first row of a matrix. name+i would be a pointer to row[i] of the matrix.

[Andreas]

@rcgldr Thank you but I perfectly understand the code. If someone adds an additional answer many years later when there are already lots of answers, even an accepted one, then it would be of great value if the answer gives a quick explanation about how it is different to the existing ones.

[rcgldr]

@Andreas - I lost an edit to my last comment. This method only works if the number columns is fixed. Otherwise an array of pointers seems like the best way to go. Doing a single allocation for the entire matrix, and a single allocation for the array of pointers only requires two allocations. If there is a maximum for the number of rows, then the array of pointers can be a fixed size array within a matrix class, only needing a single allocation for the data.

[rcgldr]

@Andreas - I wrote a matrix class that allows embedded matrices. The embedded matrix constructor has an additional parameter, a pointer to some row within another matrix, which it uses to initialize an array of pointers for the embedded matrix.

[LCsa]

Why is the if (rows) necessary before allocation/deletion?

[LCsa]

@pyon Could you elaborate on the (2) tensor product part in your zero-indexed list? :D

[pyon]

@LCsa: Let $A$ be a commutative ring, let $M, N$ be $A$-modules, and let $S \subset M$ and $T \subset N$ be generating sets for them. Then $U = \{ m \otimes n : m \in M, n \in N \}$ is a generating set for the tensor product $M \otimes N$. Moreover, if $M, N$ are free $A$-modules and $S, T$ are $A$-bases of $M, N$, respectively, then $M \otimes N$ is also a free $A$-module and $U$ is a basis. Explicitly representing facts like this in a computer (whenever it is possible) makes it easier for me to get an intuitive feel for why they are true.