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.