Create transpose matrix function based on template C++

Question

I am trying to create my first template using this amazing guide, but I run into the trouble for which I do not know how to handle multiple nested arguments:

The original function I created was implemented as follows:

QVector< QVector<double> > transpose(QVector< QVector<double> > &matrix)
{
    int pre_numcols = matrix.size();
    int pre_numrows = matrix[0].size();
    QVector< QVector<double> > transposed(pre_numrows);
    QVector<double> newcols(pre_numcols);
    qFill(newcols.begin(), newcols.end(), 0.0);
    qFill(transposed.begin(), transposed.end(), newcols);
    qDebug()<<transposed.size();
    qDebug()<<transposed[0].size();
    for (int i = 0; i < pre_numcols; ++i)
    {
        for (int j = 0; j < pre_numrows; ++j)
        {
            transposed[j][i] = matrix[i][j];
        }
    }
    return transposed;
}

Considering I am only reshuffling the points, many types would be possible.

QVector could be replaced by a std::vector, double could be replaced even by string.

I got this far:

template<class T>
T transpose(T &matrix)
{
    int pre_numcols = matrix.size();
    int pre_numrows = matrix[0].size();
    T transposed(pre_numrows);
    QVector<double> newcols(pre_numcols);  // How to do this one?

If I read T as "container holding container holding some small type", how can I can declare the newcols variable, given that it is a subset?

Note: I will edit the qFill() part to suit other cases such as std:: later on.

Answer 1

You can use templates as a template parameter:

template <
    template <typename> class Container,
    typename ValueType
>
void foo(Container<ValueType> const & c);

So your template would become:

template <
    template <typename> class Container,
    typename ValueType
>
Container< Container<ValueType> > transpose(Container< Container<ValueType> > & matrix)
{
    int pre_numcols = matrix.size();
    int pre_numrows = matrix[0].size();
    Container< Container<ValueType> > transposed(pre_numrows);
    Container<ValueType> newcols(pre_numcols);
    // ...
    return transposed;
}

That would be neat if it worked like that. But, as always in reality, new problems arise! std::vector is not template <typename T> class vector but

template <
    typename T,
    typename Allocator = allocator<T>
>
class vector

So we would have to change our function to

template <
    template <typename, typename> class C,
    typename T,
    template <typename> class A = std::allocator,
    typename InnerType = C< T, A<T> >,
    typename OuterType = C< InnerType, A<InnerType> >
>
OuterType transpose(OuterType & matrix)
{
    int pre_numcols = matrix.size();
    int pre_numrows = matrix[0].size();
    OuterType transposed(pre_numrows);
    InnerType newcols(pre_numcols);
    // ...
    return transposed;
}

which is a lot less neat, and I'm not sure whether the Qt containers are compatible to that.

Since you said that C++11 is possible to use for you, you could be going with the first function (using the template <typename> class Container) and using template aliases for standard containers:

template <typename T> using vector = std::vector<T, std::allocator<T>>;
vector<vector<int>> v;
auto vprime = transpose<vector>(v);

---

This is another possible solution which uses a helper template metafunction, and I think it's cleaner than the previous ones:

namespace
{
    template <typename T> struct get_inner_i {};

    template <template <typename> class T, typename Inner> 
    struct get_inner_i<T<Inner>> { typedef Inner type; };

    template <
        template <typename, typename> class T, 
        typename Inner,
        template <typename> class Allocator
    > struct get_inner_i<T<Inner, Allocator<Inner>>> { typedef Inner type; };

    template <typename T> using get_inner = typename get_inner_i<T>::type;
}

template <typename MatrixType>
MatrixType transpose(MatrixType const & matrix)
{
    auto const nrows = matrix.size();
    auto const ncols = nrows > 0 ? matrix[0].size() : 0;

    MatrixType transposed(ncols, get_inner<MatrixType>(nrows));
    for(auto k = 0; k < nrows; ++k)
        for(auto j = 0; j < ncols; ++j)
            transposed[j][k] = matrix[k][j];

    return transposed;
}

Why is this far more verbose solution superior? It's not about how much code we have to write, but how easy and intuitive our function is for the user. In this version, we again have only T as a template argument, so explicitly specifying a template argument to the function is not necessary.

Furthermore, our metafunction can deduce whether it is a container with a custom allocator parameter or not, and the user does not have to perform the using template alias trick mentioned above.

---

This is another solution, again superior to the previous ones, that uses std::begin to determine the value type of a container without regard to its template parameters, or whether it even is a template, as long as it provides begin and end iterators, or is a C style array:

namespace
{
    template <typename Container>
    struct value_type_i
    {
        typedef typename std::decay<
            decltype(*std::begin(std::declval<
                Container const &
            >()))
        >::type type;
    };

    template <typename Container>
    using value_type = typename value_type_i<Container>::type;
}

template <typename MatrixType>
MatrixType transpose(MatrixType const & matrix)
{
    auto const nrows = matrix.size();
    auto const ncols = nrows > 0 ? matrix[0].size() : 0;

    MatrixType transposed(ncols, value_type<MatrixType>(nrows));
    for(auto k = 0; k < nrows; ++k)
        for(auto j = 0; j < ncols; ++j)
            transposed[j][k] = matrix[k][j];

    return transposed;
}

You can see it working here: http://ideone.com/cCAyFD