Voozh

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.

URL: https://dev.to/pauljlucas/dynamically-allocating-2d-arrays-in-c-36c5

⇱ Dynamically Allocating 2D Arrays in C++ - DEV Community