Paul J. Lucas

Posted on

# Dynamically Allocating 2D Arrays in C++

## Introduction

Assuming you’ve read Dynamically Allocating 2D Arrays Efficiently (and Correctly!) in C, the last paragraph teased:

In C++, you can eliminate the row pointers and still use the [][] syntax by use of templates and overloading operator[](), but that’s a story for another time.

That time has come.

## A Small 2D Matrix Class

In C++, a small 2D matrix class can be written. A bare-bones implementation is:

template<typename T>
class matrix2d {
public:
typedef T value_type;
typedef value_type* pointer;
typedef value_type const* const_pointer;
typedef value_type& reference;
typedef value_type const& const_reference;

typedef std::size_t size_type;
typedef std::ptrdiff_t difference_type;

matrix2d( size_type idim, size_type jdim ) :
_dim{ idim, jdim },
_elem{ alloc( _dim ) }
{
}

~matrix2d() noexcept {
delete[] _elem;
}

pointer operator[]( size_type row ) noexcept {
return &_elem[ row * _dim.first ];
}

const_pointer operator[]( size_type row ) const noexcept {
return &_elem[ row * _dim.first ];
}

private:
std::pair<size_type,size_type> _dim;
pointer _elem;

static pointer alloc( std::pair<size_type,size_type> const &dim ) {
return new value_type[ dim.first * dim.second ];
}
};

The set of typedefs at the beginning are boiletplate to make the class play nicely with the STL.

Unlike the C implementation, the 2D matrix class remembers its row size — which means that an overloaded operator[]() can use it to calculate the offset for the ith row:

pointer operator[]( size_type row ) noexcept {
return &_elem[ row * _dim.first ];
}

Hence in code like:

matrix2d<int> m2d{ 3, 3 };
m2d[i][j] = 0;

the [i] calls the overloaded operator[]() that returns a pointer to the start of the ith row within the contiguous elements in row-major order that the non-overloaded [j] accesses the jth element (of the ith “sub-array” row). Unlike the C implementation, no additional row pointers are needed because they’re calculated at run-time.

## Element Access

The caveat is that each matrix element access via [i][j] now requires a multiplication that wasn’t required in the C implementation. Like many other things in computer science, it’s a trade-off. However, this can be mitigated in a couple of ways. Instead of writing:

for ( size_t i = 0; i < 3; ++i ) {
for ( size_t j = 0; j < 3; ++i ) {
// ... m2d[i][j] ...
}
}

this can be written:

for ( size_t i = 0; i < 3; ++i ) {
auto row = m2d[i];
for ( size_t j = 0; j < 3; ++i ) {
// ... row[j] ...
}
}

so that only one multiplication is done per row rather than per element.

Another way to mitigate this is by adding iterator boilerplate to the class:

class matrix2d {
public:
// ...
typedef pointer iterator;
typedef const_pointer const_iterator;
typedef std::reverse_iterator<iterator> reverse_iterator;
typedef std::reverse_iterator<const_iterator> reverse_const_iterator;
// ...

size_type size() const noexcept {
return _dim.first * _dim.second;
}

iterator begin() noexcept {
return _elem;
}

const_iterator cbegin() const noexcept {
return _elem;
}

const_iterator begin() const noexcept {
return cbegin();
}

reverse_iterator rbegin() noexcept {
return reverse_iterator{ end() };
}

const_reverse_iterator crbegin() const noexcept {
return const_reverse_iterator{ cend() };
}

const_reverse_iterator rbegin() const noexcept {
return crbegin();
}

iterator end() noexcept {
return _elem + size();
}

const_iterator cend() const noexcept {
return _elem + size();
}

const_iterator end() const noexcept {
return cend();
}

reverse_iterator rend() noexcept {
return reverse_iterator{ begin() };
}

const_reverse_iterator crend() const noexcept {
return const_reverse_iterator{ cbegin() };
}

const_reverse_iterator rend() const noexcept {
return crend();
}

// ...

Now you can do:

for ( auto elem : m2d ) {
// ... elem ...
}

to iterate over all the elements with no multiplications being done.

## Copy, Move, & Assignment

To make matrix2d correct, it requires the addition of a copy constructor:

matrix2d( matrix2d const &from ) :
_dim{ from._dim },
_elem{ alloc( _dim ) }
{
copy_elem( from );
}

// ...
private:
// ...

static pointer alloc( std::pair<size_type,size_type> const &dim ) {
return new value_type[ dim.first * dim.second ];
}

void copy_elem( matrix2d const &from ) noexcept {
for ( size_type i = 0; i < from.size(); ++i )
_elem[i] = from._elem[i];
}
};

A move constructor would improve move efficiency:

matrix2d( matrix2d &&from ) noexcept :
_dim{ from._dim },
_elem{ std::exchange( from._elem, nullptr ) }
{
}

Note that from._dim need not be zeroed.

And copy & move assignment:

matrix2d& operator=( matrix2d const &from ) {
if ( &from != this ) {
delete[] _elem;
_dim = from._dim;
alloc( _dim );
copy_elem( from );
}
return *this;
}

matrix2d& operator=( matrix2d &&from ) noexcept {
delete[] _elem;
_dim = from._dim;
_elem = std::exchange( from._elem, nullptr );
return *this;
}

## Finishing Touches

In addition to size() that returns the total number of elements, dim() might come in handy to get each dimension:

std::pair<size_type,size_type> dim() const noexcept {
return _dim;
}

And lastly, swap(), both as a member function:

void swap( matrix2d &other ) {
_dim = std::exchange( other._dim, _dim );
_elem = std::exchange( other._elem, _elem );
}

and a global function so std::swap() works:

namespace std {
template<typename T>
inline void swap( matrix2d<T> &a, matrix2d<T> &b ) {
a.swap( b );
}
}

## Conclusion

The power of classes in C++ enable a more memory efficient implementation of a dynamically allocated 2D matrix by eliminating the row pointers required in C — but with the caveat of requiring a multiplication for random element access.