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?
