Get submatrix of matrix with smaller size

algorithm, boost, c++, stl

Solution

It is possible to efficiently share data between matrices and submatrices. The trick is to track three variables in your class.

- row_stride

- start

- data

The `data` needs to be a `shared_ptr` like structure so that the underlying data can be destroyed once you are done with it. `start` will be a pointer into the data referenced by `data`, `row_stride` tells you how far to move to get to the next row.

Additional things you might like to track are

- column stride (This can allow you to take other interesting views into the matrix, and to support transpose efficiently).

- row and column length - these can be handy for debugging or if you want to make your loops, and multiplies easier to work with.

Here's how this might look for a non-bit based approach (I've omitted much .. but hopefully you get the gist).

template<typename T>
struct MatrixData
{
   T * data;
   explicit MatrixData( size_t N ) { new T[N]; }
   ~MatrixData() { delete [] data; }
private:
    MatrixData( const MatrixData & );
    MatrixData& operator=( const MatrixData & );
};

template<typename T>
class Matrix
{
    Matrix(size_t nni, size_t nnj) :
      data( new MatrixData( nni*nnj ) ),
      ni(nni),
      nj(nnj),
      row_stride(ni),
      col_stride(1)
    {
    }

    T operator()( size_t i, size_t j)
    {
       assert( i < ni );
       assert( j < nj );
       return start + i * col_stride + j * row_stride;
    }

    Matrix submatrix( size_t i_start, size_t j_start, size_t new_ni, size_t new_nj )
    {
       assert( i_start + new_ni < ni );
       assert( j_start + new_nj < nj );

       Matrix retval(*this);
       retval.start += i_start * col_stride + j_start * row_stride;
       retval.ni = new_ni;
       retval.nj = new_nj;
       return retval;
    }

    Matrix transpose()
    {
       Matrix retval(*this);
       std::swap(retval.ni,retval.nj);
       std::swap(retval.row_stride,retval.col_stride);
    }

  private:
    shared_ptr<MatrixData> data;
    T* start;
    size_t ni;
    size_t nj;
    size_t row_stride;
    size_t col_stride;

};

Making this work for a bit based version would mean changing the `MatrixData` to hold one of the bot based structures, changing `start` to be an index into the structure and changing your `operator()` to access the data correctly.

Problem

Original source