Implementing a Dynamically Sized Matrix

Problem

You need to store and represent Matricies of numbers where the dimensions (number of rows and columns) are not known at compile time.

Solution

Example 11-28 provides a general purpose and efficient implementation of a dynamically sized matrix class using the stride iterator from Recipe 11.12 and a valarray.

Example 11-28. matrix.hpp

#ifndef MATRIX_HPP
#define MATRIX_HPP

#include "stride_iter.hpp" // see Recipe 11.12

#include <valarray>
#include <numeric>
#include <algorithm>

template<class Value_T>
class matrix
{
public:
  // public typedefs
  typedef Value_T value_type;
  typedef matrix self;
  typedef value_type* iterator;
  typedef const value_type* const_iterator;
  typedef Value_T* row_type;
  typedef stride_iter<value_type*> col_type;
  typedef const value_type* const_row_type;
  typedef stride_iter<const value_type*> const_col_type;

  // constructors
  matrix( ) : nrows(0), ncols(0), m( ) { }
  matrix(int r, int c) : nrows(r), ncols(c), m(r * c) { }
  matrix(const self& x) : m(x.m), nrows(x.nrows), ncols(x.ncols) { }

  template<typename T>
  explicit matrix(const valarray<T>& x)
  : m(x.size( ) + 1), nrows(x.size( )), ncols(1)
  {
    for (int i=0; i<x.size( ); ++i) m[i] = x[i];
  }

  // allow construction from matricies of other types
  template<typename T>
  explicit matrix(const matrix<T>& x)
  : m(x.size( ) + 1), nrows(x.nrows), ncols(x.ncols)
  {
    copy(x.begin( ), x.end( ), m.begin( ));
  }

  // public functions
  int rows( ) const { return nrows; }
  int cols( ) const { return ncols; }
  int size( ) const { return nrows * ncols; }

  // element access
  row_type row_begin(int n) { return &m[n * cols( )]; }
  row_type row_end(int n) { return row_begin( ) + cols( ); }
  col_type col_begin(int n) { return col_type(&m[n], cols( )); }
  col_type col_end(int n) { return col_begin(n) + cols( ); }
  const_row_type row_begin(int n) const { return &m[n * cols( )]; }
  const_row_type row_end(int n) const { return row_begin( ) + cols( ); }
  const_col_type col_begin(int n) const { return col_type(&m[n], cols( )); }
  const_col_type col_end(int n) const { return col_begin( ) + cols( ); }
  iterator begin( ) { return &m[0]; }
  iterator end( ) { return begin( ) + size( ); }
  const_iterator begin( ) const { return &m[0]; }
  const_iterator end( ) const { return begin( ) + size( ); }

  // operators
  self& operator=(const self& x) {
    m = x.m; nrows = x.nrows; ncols = x.ncols; return *this;
  }
  self& operator=(value_type x) { m = x; return *this; }
  row_type operator[](int n) { return row_begin(n); }
  const_row_type operator[](int n) const { return row_begin(n); }
  self& operator+=(const self& x) { m += x.m; return *this; }
  self& operator-=(const self& x) { m -= x.m; return *this; }
  self& operator+=(value_type x) { m += x; return *this; }
  self& operator-=(value_type x) { m -= x; return *this; }
  self& operator*=(value_type x) { m *= x; return *this; }
  self& operator/=(value_type x) { m /= x; return *this; }
  self& operator%=(value_type x) { m %= x; return *this; }
  self operator-( ) { return -m; }
  self operator+( ) { return +m; }
  self operator!( ) { return !m; }
  self operator~( ) { return ~m; }

  // friend operators
  friend self operator+(const self& x, const self& y) { return self(x) += y; }
  friend self operator-(const self& x, const self& y) { return self(x) -= y; }
  friend self operator+(const self& x, value_type y) { return self(x) += y; }
  friend self operator-(const self& x, value_type y) { return self(x) -= y; }
  friend self operator*(const self& x, value_type y) { return self(x) *= y; }
  friend self operator/(const self& x, value_type y) { return self(x) /= y; }
  friend self operator%(const self& x, value_type y) { return self(x) %= y; }
private:
  mutable valarray<Value_T> m;
  int nrows;
  int ncols;
};

#endif

Example 11-29 shows how you might use the matrix template class.

Example 11-29. Using the matrix template

#include "matrix.hpp"

#include <iostream>

using namespace std;

int main( ) {
  matrix<int> m(2,2);
  m = 0;
  m[0][0] = 1;
  m[1][1] = 1;
  m *= 2;
  cout << "(" << m[0][0] << "," << m[0][1] << ")" << endl;
  cout << "(" << m[1][0] << "," << m[1][1] << ")" << endl;
}

The program in Example 11-29 produces the following output:

(2,0)
(0,2)

Discussion

The design of the matrix template in Example 11-28 is heavily inspired by Bjarne Stroustrup's matrix template from The C++ Programming Language, Third Edition (Addison Wesley). Stroustrup's implementation differs in that its iterator uses slice and a pointer to the valarray for indexing. The matrix implementation in Example 11-27 uses instead the stride iterator from Recipe 11.12, making the iterators more compact and, on some implementations, more efficient.

The matrix template class allows indexing of the element ith row and jth column using a double subscripting operation. For example:

matrix<int> m(100,100);
cout << "the element at row 24 and column 42 is " << m[24][42] << endl;

The matrix template class also provides begin and end member functions, which means that it can be used easily with the various STL algorithms.

There is a line of code in Example 11-28 that might have caused you to raise your eyebrows. That is the declaration:

mutable valarray<Value_T> m;

The declaration of the member field m as being mutable was a necessary evil. If it wasn't for this line I would not have been able to provide const iterators, because you can't create an iterator to a const valarray.