CODEWITHSUNDEEP
c++arraysmultidimensional-arraymatrix
Grzenio
Grzenio

Reputation: 36639

Two (or more) dimensional dynamically created arrays in C++

I am implementing a dynamic programming algorithm that needs to create some two dimensional memory before it starts (the size of the memory depends on the parameters, also there are no clear upper bounds for these). I tried to use a normal 2-dim C++ array, but obviously I don't know the second dimension up front, so it didn't work. What is the most reasonable way to achieve it? Are there any classes from the standard library or boost that would make it as easy as it should be?

The functionality I need is rather basic: create MxN, get or set matrix[i][j]

Upvotes: 1

Views: 489

Answers (4)

6502
6502

Reputation: 114461

A very simple 2d array requires just a few lines of code

template<typename T>
struct Matrix2d
{
    int rows, cols;
    std::vector<T> data;
    Matrix2d(int rows, int cols) : rows(rows), cols(cols), data(rows*cols)
    { }

    T operator()(int i, int j) const { return data[i*cols+j]; }
    T& operator()(int i, int j) { return data[i*cols+j]; }
};

Element access is done using mat(i, j) for reading and mat(i, j) = v for writing.

As James Kanze suggested for the special case of a 2d array it's also easy to get the C++ standard array syntax mat[i][j] and mat[i][j] = v for element access using operator[] instead of operator():

    T* operator[](int i) { return &data[i*cols]; }
    const T* operator[](int i) const { return &data[i*cols]; }

With this solution however it gets harder to extend to an higher number of dimensions (a trivial problem with mat(i, j, k) notation).

Upvotes: 1

Nathan Monteleone
Nathan Monteleone

Reputation: 5470

The most basic way you could go is just use an array of std::vectors. You can then resize the vectors any time you like.

Also, if you can just defer creation of the array until you know both dimensions, you could use boost.MultiArray. I think that might be more what you're looking for.

Upvotes: 1

T.E.D.
T.E.D.

Reputation: 44804

The only thing that strikes me off the top of my head would be the ugly way: Implement it as a single-dimensioned array, and perform the double indexing manually with something like:

value = arr[i*num_i + j];

You could always write a class to hide the uglyness...

Upvotes: 3

obmarg
obmarg

Reputation: 9559

Seems like a using a vector would be a good idea here, assuming you either don't plan on copying it around much, or don't mind the overhead of the copy. This code is untested, might not be 100% right)

typedef std::vector< std::vector< int > > 2dVector;

2dVector vec( 2 );
vec[ 0 ].resize( someSize );
vec[ 1 ].resize( someSize );

vec[ 0 ][ 0 ] = 100;
//Keep on doing stuff here.

Alternatively, you could use something like a boost::shared_array (or the tr1/c++11 equivalets) to dynamically allocate your array (this code is also untested, might not be right):

typedef boost::shared_array< boost::shared_array< int > > 2dArray;

2dArray arr( new boost::shared_array< int >( firstDimensionSize ) );
BOOST_FOREACH( boost::shared_array< int >& inner, arr )
{
   inner = new int[ secondDimensionSize ];
}

arr[ 0 ][ 1 ] = 100;

EDIT: A quick google also reveals the boost multidimensional array library. I've not used it, or read the description much, but perhaps it is worth looking into

Upvotes: 0

Related Questions