Paul J. LucasIntroduction
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 overloadingoperator[](), 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._dimneed 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.
