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.


 

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>