views:

1591

answers:

7

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.

+3  A: 

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.

Bernard
+4  A: 

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;
yjerem
Yeah, that's probably a better way. Wrap the access in a function and it's all quite nice.
Bernard
i believe this is how multidimensional arrays are handled under the covers too
Kip
+11  A: 

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.

Brian R. Bondy
See the question title, "... with size determined at run time". So he can't use the stack or a constant.
yjerem
... but your answer shouldn't be downvoted. (Wasn't me :P)
yjerem
You can create size determined arrays on the stack in g++
Brian R. Bondy
Drew Hall
Thanks, I mentioned that in my description
Brian R. Bondy
+2  A: 

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.
paxdiablo
+2  A: 

boost::multi_array

doing it by hand will be a mess.

Dustin Getz
Not really, it's pretty much a 20-line class - see paxdiablo's answer :) multi_array is as complex as it is because it implements n-dimensional arrays.
Stefan Monov
+3  A: 

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

Iulian Şerbănoiu
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
I totally agree with your argument
Iulian Şerbănoiu
+1  A: 

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. ;)

John at CashCommons
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.
Stefan Monov