A simple 2D matrix class
There is a recurring question on some C++ forums about nesting std::vector’s to build a 2D matrix, i.e.:
std::vector< std::vector<double> > someMatrix;
This is not very efficient, both memory-wise and speed-wise.
In fact, each vector has an overhead due to the fact that it typically stores three pointers. So, e.g. in case of a 20 rows by 30 columns matrix, assuming that inner vectors represent matrix rows, the overhead is 20 rows x 3 pointers/row = 60 pointers, i.e. 60 pointers x 4 bytes/pointer = 240 bytes.
But there is also a speed penalty. In fact, dynamic memory allocated by each vector is in general scattered on the heap; instead, it would be better for locality to have contiguous memory allocated for the whole matrix.
So, a better technique consists in using just one instance of std::vector, storing all matrix elements in this very instance, using a proper ordering for elements, e.g. storing matrix elements row-wise.
The total size of the vector is rows * columns, and given a 2D index (row, column) it can be “linearized” to point to proper vector element using the following formula:
<vector index> = <column index> + <row index> * <matrix columns>
These concepts are developed in a simple reusable C++ template class attached to this blog post. This is a simple class for simple needs (i.e. just storing 2D matrix elements in an efficient way and accessing them conveniently). For more advanced matrix classes, with template meta-programming optimizations, Blitz++ library can be considered.