C++11 templates, determining return type

Question

I am building a matrix library and I am trying to use the policy-based design. So my base classes are classes that provide a storage method and some access functions. I also have a function matrix which provides the mathematical functions. This works great, but there is a major problem with the operator* because of the return type. I will explain it with some code.

Base class that provides a stack storage :

template < typename T, unsigned int rows, unsigned int cols>
class denseStackMatrix {
public:
    typedef T value_type;

private:
    value_type grid[rows][cols];
    const unsigned int rowSize;
    const unsigned int colSize;

Then I have my matrix class which provides mathematical functionality :

template <typename MatrixContainer >
class matrix : public MatrixContainer {
public:
    typedef MatrixContainer Mcontainer;

    matrix<Mcontainer>& operator +(const matrix<Mcontainer>&);
    matrix<Mcontainer>& operator *(const matrix<Mcontainer>&);

operator+ always works, operator* only works for square matrix. So we still need one for all matrices. And that's were it goes wrong. I have already tried few things, but nothings works. I look for something like this, with the help of c++0x (usage of c++0x is not a requirement) you shall notice the "???" :)

friend auto operator * (const matrix<T1>& matrix1, const matrix<T2>& matrix2)
-> decltype(matrix<???>);

An example of the problem

matrix<denseStackMatrix<int,3,2> > matrix1;
matrix<denseStackMatrix<int,2,4> > matrix2;
matrix<denseStackMatrix<int,3,4> > matrix3 = matrix1 * matrix2;

Here it will complain about the type, because it does not match any of the two parameter types. But the compiler needs to know the type at compile-time and I do not know how to provide it.

I know there are other options for the design, but I am really looking for a solution for this scenario..

Thank you !

Barrybarrymore

@ildjarn, don't ninja-edit right before me! – Faze

@Faze : D-; (yay character limit) – Revivify

@Beremboy: Uhm.. what exactly is your problem? I think you need to clarify. – Faze

@Faze : Maybe this makes it more clear, please tell me if it does not. – Barrybarrymore

Sounds like the templated type for the return value of operator* depends is a new type dependent on the template parameters of the arguments to operator*. Is that right? – Supervisor

@Supervisor : yes the return type depends on the parameters, but is a different type than the parameters, it only needs information about the sizes of the input matrices. – Barrybarrymore

Btw, rowSize and colSize should be static and initialized inside the class body as my answer shows, as they can't ever change between instances. – Faze

why are you returning a reference matrix<Mcontainer>& ? – Ultrasonic

Answer 1

Picking up on the idea of @hammar, but with partial specialization to allow the normal syntax like the question shows:

template<class MatrixContainer>
class matrix;

template<
  template<class,int,int> class MatrixContainer,
  class T, int rows, int cols
>
class matrix< MatrixContainer<T,rows,cols> >{
  typedef MatrixContainer<T,rows,cols> Mcontainer;
  typedef matrix<Mcontainer> this_type;
  static int const MyRows = rows;
  static int const MyCols = cols;

public:
  template<int OtherCols>
  matrix<MatrixContainer<T,MyRows,OtherColls> > operator*(matrix<MatrixContainer<T,MyCols,OtherCols> > const& other){
    typedef matrix<MatrixContainer<T,MyCols,OtherCols> > other_type;
    typedef matrix<MatrixContainer<T,MyRows,OtherCols> > result_type;
    // ...
  }
};

Edit: As you said in your comment, you can also use this to create a matrix that doesn't use a MatrixContainer which has row and column size as template parameters:

template<
  template<class> class MatrixContainer,
  class T
>
class matrix< MatrixContainer<T> >{
  typedef MatrixContainer<T> Mcontainer;
  typedef matrix<Mcontainer> this_type;

public:
  // normal matrix multiplication, return type is not a problem
  this_type operator*(this_type const& other){
    // ensure correct row and column sizes, e.g. with assert
  }

  // multiply dynamic matrix with stack-based one:
  template<
    template<class,int,int> class OtherContainer,
    int Rows, int Cols
  >
  this_type operator*(matrix<OtherContainer<T,Rows,Cols> > const& other){
    // ensure correct row and column sizes, e.g. with assert
  }
};

Usage:

// stack-based example
matrix<DenseStackMatrix<int,3,2> > m1;
matrix<DenseStackMatrix<int,2,4> > m2;
matrix<DenseStackMatrix<int,3,4> > m3 = m1 * m2;

// heap-based example
matrix<DenseHeapMatrix<int> > m1(3,2);
matrix<DenseHeapMatrix<int> > m2(2,4);
matrix<DenseHeapMatrix<int> > m3 = m1 * m2;

Faze

@Xeo/@Hammar : I really like both solutions !! Now the most correct answer actually is that of Xeo because he provides the design I asked for.. But maybe I will step over to the the idea of Hammar. Which design is the best, you (Xeo,Hammar) think ? – Barrybarrymore

@Beremboy: Both are the same, they just have a different syntax. :) Namely, I allow the "more natural" syntax. You can also accept one answer but use another. I'd accept @hammars answer, as I expanded on his idea and only added the partial specialization, so credit goes to him. – Faze

@Faze That is gentle of you :) But are both designs really the same ? I think your design let us make a MatrixContainer without row en col template arguments, or am I wrong ? And Hammar always expects row en col information in the template arguments, so then you always have compile time checking ? – Barrybarrymore

@Beremboy: Currently, my design also enforces matrix containers with row and size template parameters, as you can see. Gimme 5 minutes to make one which allows stack-based and heap-based matrix containers to be multiplied. :) – Faze

@Beremboy: No wait, you're right. You just need to partially specialize on a matrix container that only takes a type parameter. Lemme edit that in. :) – Faze

@Faze Really nice also ! Now I am really doubting between the compile-time checking and more freedom.. I guess if I choose freedom, that the user can plugin whatever he wants, so he can choose compile-time .. So I am going for your design I think ! btw, are you really 19 :p ? – Barrybarrymore

Because you are really good with templates and I consider (good) template programming as advanced stuff so.. that's nice at your age :) ! – Barrybarrymore

@Beremboy: Heh, thanks. :) I'm just really interested in template metaprogramming (TMP), so that might be a reason. – Faze

@Faze That will probably be the reason indeed, so which design do you prefer ? Always require information about size or just freedom :) ? – Barrybarrymore

@Beremboy: Why not have both? This allows full decision on the user. You can also implement stack x stack, stack x heap, heap x stack and stack x stack multiplication. In all cases involving a heap matrix though, you'd need to assert that the row and column sizes match. – Faze

@Faze : Yeah indeed, the assert thing is a good idea, and I also generate some exceptions. Many thanks for making my first stackoverflow experience (as a registered user) a real succes :) ! Also thanks to @Hammar ! – Barrybarrymore

@Faze template<template<class> class MatrixContainer,class T> class matrix<MatrixContainer<T> > { typedef MatrixContainer<T> Mcontainer; typedef matrix<Mcontainer> this_type; }; This does not compile :s It is the class declaration of your edit. Sorry for the lay-out – Barrybarrymore

@Faze CLASS definition :‘matrix’ is not a template && provided for ‘template<template<class> class MatrixContainer, class T> class matrix’ |other line| : Typdef this_type : wrong number of template arguments (1, should be 2) – Barrybarrymore

@Beremboy: I hope you included that template<class T> class matrix; at the top of the answer? This whole answer is based on partial specialization. – Faze

Answer 2

How about changing MatrixContainer to be a template template parameter?

template <class T, int Rows, int Cols>
class DenseStackMatrix {
public:
    typedef T value_type;

private:
    value_type grid[Rows][Cols];
};

template <class T, int Rows, int Cols, template<class, int, int> class MatrixContainer>
class Matrix : public MatrixContainer<T, Rows, Cols> {
public:
    template <int ResultCols>
    Matrix<T, Rows, ResultCols, MatrixContainer> & operator*(const Matrix<T, Cols, ResultCols, MatrixContainer> &);
};

int main() {
    Matrix<int, 3, 2, DenseStackMatrix> matrix1;
    Matrix<int, 2, 4, DenseStackMatrix> matrix2;
    Matrix<int, 3, 4, DenseStackMatrix> matrix3 = matrix1 * matrix2;
}

This way you not only get compile time dimensions checking, but you can also extend this to allow multiplications between matrices of different container types.

Mccall

I think mixing the container types is bad. Also, you're missing that the rows of the 2nd matrix not need to be the columns in the first matrix, it can be completely different. – Faze

@Xeo: The product of a m×p matrix by a p×n matrix is a m×n matrix. The inner dimensions (cols of first matrix, rows of second) must be equal. It is the columns of the second matrix that can be anything. – Mccall

Our heap based implementation does not require the row en col size. Because it does not need it and it keeps it flexible for maybe resizing ? Although a matrix actually does not need a resize i guess.. Maybe we will require that every MatrixContainer has his size declared at compile time ! But is it also possible without it ? – Barrybarrymore

@Beremboy: If you don't require compile time checking of the dimensions, you can just make operator * be a template over the container type of the second matrix in your original code. – Mccall

@Hammar Sorry, but what do you exactly mean with "a template over the container type" ? – Barrybarrymore

@Beremboy: I mean something like template <OtherContainer> matrix<Mcontainer>& operator +(const matrix<OtherContainer>&);. – Mccall

Answer 3

Just because I worked on it before finding all the answers here:

template <typename T, unsigned int M, unsigned int N>
struct Matrix
{
};

template <typename T, unsigned int M, unsigned int MN, unsigned int N>
Matrix<T, M, N> operator*(Matrix<T, M, MN> const & lhs, Matrix<T, MN, N> const & rhs)
{
    return Matrix<T, M, N>();
}

int main()
{
    Matrix<int, 3, 4> prod = Matrix<int, 3, 2>() * Matrix<int, 2, 4>();

    // Fails to compile as desired
    // g++ gives:
    //matrix.cpp: In function 'int main()':
    //matrix.cpp:20: error: no match for 'operator*' in 'Matrix<int, 3u, 2u>() * Matrix<int, 3u, 4u>()'
    Matrix<int, 3, 4> prod1 = Matrix<int, 3, 2>() * Matrix<int, 3, 4>();
}

This solution may not fit your design pattern, but uses a free function implementation of operator* to infer (and check) the template arguments, resulting in a compile-time error if the constraints of matrix multiply are not met.

Supervisor

Answer 4

just a random idea, what if you include in you base class a way to get a container of the same type but of different size ? something on the lines of:

template<typename T, unsigned int Rows, unsigned int Cols>
class denseStackMatrix {
public:
  static const int rows = Rows;
  static const int cols = Cols;

  template<unsigned int R, unsigned int C>
  struct resize {
    typedef denseStackMatrix<T, R, C> type;
  };

  // ....
}

and then you can do

template <typename MatrixContainer >
class matrix : public MatrixContainer {
  using MatrixContainer::resize;

public:

  template<typename RHSMcontainer>
  matrix<typename resize<rows, RHSMcontainer::cols>::type>
  operator *(const matrix<RHSMcontainer>&)
  {
    static_assert(cols == RHSMcontainer::rows, "incompatible sizes");
    // ...
  }

  // ....
}

btw, I'm not sure I got the scoping of MatrixContainer::resize right ...

my 2c

Ultrasonic

Answer 5

In your post I read you would like to use policy-based design. In that case you first need to define your policy classes. Thus, you first need to decide which classes you want that your users can provide by their own. Which classes you take, is up to you. You can for use for instances the policies Storage and Shape.

You can make something like

class Diagonal  {
public:
    // the default storage facility of a Diagonal matrix
    typedef Stack default_storage;
};

template <typename T, typename Shape = Dense, typename Storage = Stack, unsigned Row, unsigned Col>
class Matrix : public Storage, Shape {   // policy classes Storage and Shape
public:
    template <typename T1, typename Shape1, typename Storage1, unsigned Row1, unsigned Col1>
    friend Matrix<T1,Shape1,Storage1,Row1,Col1>& operator += (Matrix<T1,Shape1,Storage1,Row1,Col1> matrix1,Matrix<T,Shape,Storage,Row,Col> matrix2);

    template <typename T1, typename Shape1, typename Storage1, unsigned Row1, unsigned Col1>
    friend Matrix<T1,Diagonal,Storage1,Row1,Col1>& operator += (Matrix<T1,Diagonal,Storage1,Row1,Col1> matrix1,Matrix<T,Diagonal,Storage,Row,Col> matrix2);

    template <typename T1, typename Shape1, typename Storage1, unsigned Row1, unsigned Col1>
    friend Matrix<T,Shape,Storage,Row,Col>& operator + (Matrix<T,Shape,Storage,Row,Col> matrix1, Matrix<T,Shape,Storage,Row,Col> matrix2);

    template <typename T1, typename Shape1, typename Storage1, unsigned Row1, unsigned Col1>
    friend Matrix<T,Diagonal,Storage,Row,Col>& operator + (Matrix<T,Diagonal,Storage,Row,Col> matrix1, Matrix<T,Diagonal,Storage,Row,Col> matrix2);

// general template function
template <typename T, typename Shape, typename Storage, unsigned Row, unsigned Col>
Matrix<T,Shape,Storage,Row,Col>& operator + (Matrix<T,Shape,Storage,Row,Col> matrix1, Matrix<T,Shape,Storage,Row,Col> matrix2) {
    Matrix<T,Shape,Storage,Row,Col>* result = new Matrix<T,Shape,Storage,Row,Col>();
    for (unsigned i = 0; i < matrix1.getRowSize(); i++) {           // getRowSize is a member function of policy class Storage
        for (unsigned j = 0; j < matrix1.getRowSize(); j++) {
            (*result)(i,j) = matrix1.getValue(i,j) + matrix2.getValue(i,j);
        }
    }
    return *result;
}

// overloaded template function
template <typename T, typename Shape, typename Storage, unsigned Row, unsigned Col>
Matrix<T,Diagonal,Storage,Row,Col>& operator + (Matrix<T,Diagonal,Storage,Row,Col> matrix1, Matrix<T,Diagonal,Storage,Row,Col> matrix2) {
    Matrix<T,Shape,Storage,Row,Col>* result = new Matrix<T,Shape,Storage,Row,Col>();
    for (unsigned i = 0; i < matrix1.getRowSize(); i++) {
        (*result)(i,i) = matrix1.getValue(i,i) + matrix2.getValue(i,i);
    }
    return *result;
}

// general template function
template <typename T, typename Shape, typename Storage, unsigned Row, unsigned Col>
Matrix<T,Shape,Storage,Row,Col>& operator += (Matrix<T,Shape,Storage,Row,Col> matrix1,Matrix<T,Shape,Storage,Row,Col> matrix2)  {
    Matrix<T,Shape,Storage,Row,Col>* result = new Matrix<T,Shape,Storage,Row,Col>(matrix1); // copy constructor
    for (unsigned i = 0; i < matrix1.getRowSize(); i++) {
        for (unsigned j = 0; j < matrix1.getRowSize(); j++) {
            (*result)(i,j) = matrix1.getValue(i,j) + matrix2.getValue(i,j);
        }
    }
    return *result;
}

// overloaded template function
template <typename T, typename Shape, typename Storage, unsigned Row, unsigned Col>
Matrix<T,Diagonal,Storage,Row,Col>& operator += (Matrix<T,Diagonal,Storage,Row,Col> matrix1,Matrix<T,Diagonal,Storage,Row,Col> matrix2) {
    Matrix<T,Shape,Storage,Row,Col>* result = new Matrix<T,Shape,Storage,Row,Col>(matrix1); // copy constructor
    for (unsigned i = 0; i < matrix1.getRowSize(); i++) {
        (*result)(i,i) = matrix1.getValue(i,i) + matrix2.getValue(i,i);
    }
    return *result;
}

As you can see, you can also easily add two different Matrix types now. You just need to overload the general template function. An advantage of using policies is that your users can now for instance easily provide their own storage facilities.

One last note. As you can use C++0x you can also make some shortcuts for your users. You can do for instance things like

template<typename T, unsigned Row, unsigned Col>
using DenseStackMatrix = Matrix<T, Dense, Stack, Row, Col>;

template<typename T>
using DenseHeapMatrix = Matrix<T, Dense, Heap, 0, 0>;

Acetometer