Best way to represent a 2-D array in C++ with size determined at run time

Question

In C++ I'd like to do something like:

int n = get_int_from_user();

char* matrix = new char[n][n];

matrix[0][0] = 'c';
//...
matrix[n][n] = 'a';

delete [][] matrix;

but of course this doesn't work. What is the best way to do something similar? I've seen some solutions to this but they seem pretty messy.

Answer 1

The manual dynamic way:

Let's say you want an array of width*height, the most efficient way is to just use a single dimensional array:

char *matrix = new char[width*height];

To delete it:

delete[] matrix;

To access it:

char getArrayValue(char *matrix, int row, int col)
{
  return matrix[row + col*width];
}

To modify it:

void setArrayValue(char *matrix, int row, int col, char val)
{
  matrix[row + col*width] = val;
}

---

Boost Matrix:

Consider using boost::matrix if you can have the dependency.

You could then tie into the boost linear algebra libraries.

Here is some sample code of boost::matrix:

#include <boost/numeric/ublas/matrix.hpp>
using namespace boost::numeric::ublas;
matrix<char> m (3, 3);
for (unsigned i = 0; i < m.size1 (); ++ i)
    for (unsigned j = 0; j < m.size2 (); ++ j)
        m (i, j) = 3 * i + j;

---

On the stack for some compilers:

Some compilers actually allow you to create arrays on the stack with runtime determined sizes. g++ is an example of such a compiler. You cannot do this by default VC++ though.

So in g++ this is valid code:

int width = 10;
int height = 10; 
int matrix[width][height];

Drew Hall mentioned that this C99 feature is called Variable Length Arrays (VLAs) and it can probably be turned on in any modern compiler.

Answer 2

I usually do something like this:

char *matrix = new char [width * height];

matrix[i + j * width] = 'c'; // same as matrix[i][j] = 'c';

delete [] matrix;

Answer 3

What about std::vector< std::vector<int> > array2d; ?

Answer 4

You seem to be missing the whole point of C++ (C with classes) :-). This is the sort of use that's crying out for a class to implement it.

You could just use STL or other 3rd party class library which I'm sure would have the data structure you're looking for but, if you need to roll your own, just create a class with the following properties.

• constructor which, given n, will just create a new n*n array of char (e.g., charray)..
• member functions which get and set values based on x.y which simply refer to charray[x*n+y];
• destructor which delete[]'s the array.

Answer 5

For a true two dimensional array:

int n = get_int_from_user();

char** matrix = new char*[n];
for (int i = 0; i < n; i++) {
    matrix[i] = new char[n];
}

// Operations on matrix.

for (int i = 0; i < n; i++) {
    delete [] matrix[i];
}
delete matrix;

Just off the top of my head. Mistakes, no doubt. However, other people have posted a more elegant approach, I think.

Answer 6

boost::multi_array

doing it by hand will be a mess.

Answer 7

I like the 1-d array approach (the selected answer by Brian R. Bondy) with the extension that you wrap the data members into a class so that you don't need to keep track of the width separately:

class Matrix
{
    int width;
    int height;
    char* data;
public:
    Matrix();
    Matrix(int width, int height);
    ~Matrix();

    char getArrayValue(int row, int col);
    void setArrayValue(int row, int col, char val);
}

The implementation is an exercise for the reader. ;)

Answer 8

I think this would be a good one.

int n = get_int_from_user();

char **matrix=new (char*)[n];

for(int i=0;i<n;i++)
    matrix[i]=new char[n];

matrix[0][0] = 'c';
//...
matrix[n][n] = 'a';

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

Answer 9

std::vector<int> m;

Then call m.resize() at runtime.

int* matrix = new int[w*h];

if you want to do something like Gaussian elimination your matrix should be

int** matrix = new int*[h];
for(size_t i(0); i < h; ++i)
    matrix[i] = new int[w];

(in Gaussian elimination we usually need to exchange one row with another so it's better to swap pointers to rows in constant time rather than swapping by copying in linear time).