Dynamically Allocating 2D Arrays in C++
Tags: cpp
Published: 2023-07-20 14:49:06

---
title: Dynamically Allocating 2D Arrays in C++
published: true
description: A small 2D matrix class.
tags: #cpp
# cover_image: https://direct_url_to_image.jpg
# Use a ratio of 100:42 for best results.
# published_at: 2023-07-20 12:48 +0000
---

## Introduction

Assuming you’ve read [Dynamically Allocating 2D Arrays Efficiently (and Correctly!) in C](https://dev.to/pauljlucas/dynamically-allocating-2d-arrays-efficiently-and-correctly-in-c-23d0), 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:

```cpp
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 `typedef`s at the beginning are [boiletplate](https://en.wikipedia.org/wiki/Boilerplate_code) to make the class play nicely with the [STL](https://en.wikipedia.org/wiki/Standard_Template_Library).

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:

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

Hence in code like:

```cpp
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](https://en.wikipedia.org/wiki/Row-_and_column-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:

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

this can be written:

```cpp
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:

```cpp
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:

```cpp
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:

```cpp
    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:

```cpp
    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:

```cpp
    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:

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

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

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

and a global function so [`std::swap()`](https://en.cppreference.com/w/cpp/algorithm/swap) works:

```cpp
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.