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.

Solution 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.

Solution 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;

Solution 3

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.

Solution 4

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

Solution 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.

View more solutions

Comments

[Tom Duckering]

Yeah, that's probably a better way. Wrap the access in a function and it's all quite nice.

[Paige Ruten]

See the question title, "... with size determined at run time". So he can't use the stack or a constant.

[Brian R. Bondy]

You can create size determined arrays on the stack in g++

[Drew Hall]

That's a C99 feature called Variable Length Arrays (VLAs)--it can probably be enabled in any modern compiler that supports C & C++.

[Kip]

i believe this is how multidimensional arrays are handled under the covers too

[Stefan Monov]

The performance characteristics are worth noting. Array resizing in one direction will be fast. But element access will be slow, due to bad cache locality (the vectors may end up in distant parts of memory). On the other hand, if you were to use contiguous storage like in most other answers, you'd have slightly slower vertical resizing, slightly faster horizontal resizing, and much better cache locality.

[Stefan Monov]

Two potential improvements. You can make it a template class. And you can replace getArrayValue and setArrayValue with operator()(int,int) returning a reference. Or ideally, an emulation of the [x][y] syntax via a proxy class - but it's difficult to ensure the proxy class is always optimized away, I think.