1

As part of a hobby project, I needed a rectangular Matrix object to maintain state of a grid. At first, the implementation seemed trivial and unworthy of further discussion: (I haven't included all the code, only the relevant code)

template<typename T>
class Matrix {
    uint64_t rows, columns;
    std::vector<T> _data;

    uint64_t get_flat_index(uint64_t row, uint64_t column) const {
        return row * columns + column;
    }

public:
    Matrix(uint64_t rows, uint64_t columns) :
    rows(rows), columns(columns), _data(rows * columns, {}) {}

    //Auto-generated by compiler
    //Matrix(Matrix const&) = default;
    //Matrix(Matrix &&) = default;
    //Matrix & operator=(Matrix const&) = default;
    //Matrix & operator=(Matrix &&) = default;
    //~Matrix() = default;

    T & operator()(uint64_t row, uint64_t column) {
        return _data[get_flat_index(row, column)];
    }

    T const& operator()(uint64_t row, uint64_t column) const {
        return _data[get_flat_index(row, column)];
    }

    bool is_valid(uint64_t row, uint64_t column) const {
        return row < rows && column < columns;
    }

    T & at(uint64_t row, uint64_t column) {
        if(!is_valid(row, column)) throw std::runtime_error("row/column out of bounds!");
        return operator()(row, column);
    }

    T const& at(uint64_t row, uint64_t column) const {
        if(!is_valid(row, column)) throw std::runtime_error("row/column out of bounds!");
        return operator()(row, column);
    }

    uint64_t get_rows() const {return rows;}
    uint64_t get_columns() const {return columns;}

    void resize(uint64_t new_rows, uint64_t new_columns) {
        if (new_rows == rows && new_columns == columns) return;

        if (new_columns == columns) {
            _data.resize(new_rows * new_columns, {});
        }
        else {
            std::vector<T> new_data(new_rows * new_columns, {});
            for (uint64_t row = 0; row < std::min(rows, new_rows); row++) {
                auto beginning_of_row = _data.begin() + (row * columns);
                auto ending_of_row = beginning_of_row + std::min(columns, new_columns);
                auto beginning_of_new_row = new_data.begin() + (row * new_columns);
                std::copy(beginning_of_row, ending_of_row, beginning_of_new_row);
            }
            _data = std::move(new_data);
        }

        columns = new_columns;
        rows = new_rows;
    }

    //Other code, not related to this post
};

So it all seems pretty great right? I can write stuff like Matrix<int> m(50,50);, m(5, 10) = 17;, try {m.at(52, 47) = 99;} catch (std::runtime_error const& e) {std::cerr << "Whoops!" << std::endl;}, and it all just works, right?

Well, it turns out there's at least one situation where the code misbehaves in a major way:

Matrix<bool> is_tested(60, 60); 
is_tested(30, 40) = true; //Does not compile! Whoops.

Yeah. Turns out that because std::vector<bool> has been specialized, it messes with the integrity of my code.

My initial solution was to write a specialization for Matrix<bool>.

template<>
class Matrix<bool> {
    uint64_t rows, columns;
    std::unique_ptr<bool[]> _data;

    //Duplicated: 
    uint64_t get_flat_index(uint64_t rows, uint64_t columns) {/*...*/}
public:
    Matrix(uint64_t rows, uint64_t columns) :
    rows(rows), columns(columns), _data(std::make_unique<bool[]>(rows * columns)) {}

    //I don't get this for free anymore!
    Matrix(Matrix const& m) : Matrix(m.rows, m.columns) {
        std::copy(m._data.get(), m._data.get() + rows * columns, _data.get());
    }

    //I have to include this manually now.
    Matrix(Matrix &&) = default;

    //More duplicated code...
    bool & operator()(uint64_t row, uint64_t column) {/*...*/}
    bool const& operator()(uint64_t row, uint64_t column) const {/*...*/}
    bool is_valid(uint64_t row, uint64_t column) const {/*...*/}
    bool & at(uint64_t row, uint64_t column) {/*...*/}
    bool const& at(uint64_t row, uint64_t column) const {/*...*/}
    uint64_t get_rows() const {/*...*/}
    uint64_t get_columns() const {/*...*/}

    void resize(uint64_t new_rows, uint64_t new_columns) {
        if (new_rows == rows && new_columns == columns) return;

        std::unique_ptr<bool[]> new_data{ std::make_unique<bool[]>(new_rows * new_columns) };

        if (new_columns == columns) {
            std::copy(
                begin(),
                begin() + ((new_rows < rows) ? new_rows * new_columns : rows * new_columns),
                new_data.get()
            );
        }
        else {
            for (uint64_t row = 0; row < std::min(rows, new_rows); row++) {
                auto beginning_of_row = _data.get() + (row * columns);
                auto ending_of_row = beginning_of_row + std::min(columns, new_columns);
                auto beginning_of_new_row = new_data.get() + (row * new_columns);
                std::copy(beginning_of_row, ending_of_row, beginning_of_new_row);
            }
        }

        _data = std::move(new_data);
        columns = new_columns;
        rows = new_rows;
    }

    //All the other code needs to be duplicated as well!
};

This is, of course, frustrating, not least of which since every time I spot a mistake in one version of the code, I have to fix it in the other, and same goes if I redesign something.

So my next thought was to ditch std::vector<T> entirely, and just specialize around std::unique_ptr<T[]>. This solves the code duplication problem, but it means I can't take advantage of any optimization potential that std::vector<T> offers over std::unique_ptr<T[]>, like smart use of allocators and other benefits, all to ensure that Matrix<bool> works correctly. I tried a version that partitions out the divergent code into a superclass called _matrix_impl<T> that specializes around bool itself, leaving Matrix<T> to not have to specialize anything itself, but there was still a significant amount of code duplication on things like the variable declarations and the get_flat_index code (not to mention a lot of the code not listed here being duplicated) and it created its own nightmare for code maintainability, vis-a-vis inheritance of template superclasses.

So ultimately, my question is: what is the best solution for this situation? Since my code doesn't have things like insert, emplace, or other similar constructs, does it make sense to just use std::unique_ptr<T[]> for everything, since many of the benefits I'd otherwise have access to are moot anyways? If I use std::vector<T>instead, is there a way to gracefully handle Matrix<bool> without dealing with the headache that is std::vector<bool>? Is there a superior third/fourth option I haven't even considered?

3

Since my code doesn't have things like insert, emplace, or other similar constructs, does it make sense to just use std::unique_ptr<T[]> for everything, since many of the benefits I'd otherwise have access to are moot anyways?

It's not a bad idea from a performance standpoint; given that you matrix is fixed-size, you can get away with just one pointer instead of three, so your matrix objects are going to be slightly lighter weight than when using std::vector as a data backend; also, given that that pointer has now way to be modified outside the constructor, the compiler may be able to be extra smart and avoid re-reading it from your object when performing manipulations intermixed with extern function calls (it's a common cause of slight slowdown with std::vector).

OTOH, you are not getting the copy/assignment stuff for free, if this is important it's for you to judge.

If I use std::vector<T> instead, is there a way to gracefully handle Matrix<bool> without dealing with the headache that is std::vector<bool>?

A possibility that I actually used is to use the std::vector<T>::reference typedefs for your accessors, thus forwarding whatever proxy object std::vector<bool> likes to use straight to your user. So, something like:

typedef std::vector<T>::reference reference;
typedef std::vector<T>::const_reference const_reference;

reference operator()(uint64_t row, uint64_t column) {
    return _data[get_flat_index(row, column)];
}

const_reference operator()(uint64_t row, uint64_t column) const {
    return _data[get_flat_index(row, column)];
}

// ... same with at & co. ...

Incidentally, if you are to implement your Matrix class using std::vector as a backend, you can avoid storing the number of rows - the std::vector already stores the full size, so the height is just one division away (but as usual, check if the size reduction of the Matrix object is worth the extra cost of the division by profiling the code against common scenarios).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.