C++ and more!

Giovanni Dicanio's corner on the Internet.

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.

 

Attachment: Matrix2D.zip
Posted: Dec 28 2010, 05:00 AM by Gdicanio | with no comments
Filed under: