How can I use Variadic templates to flatten a tree of types?

Question

I have a construct like this:

template<typename... Ts>
struct List {}

typedef List<char,List<int,float,List<int,unsigned char>>,List<unsigned,short>> MyList;

and I want to essentially flatten it to one list. What is the best way? I think I could make something with recursion if I fiddle with it long enough but something tells me there should be a better way.

What I want as a result of the above tree should be similar to this:

typedef List<char,int,float,int,unsigned char,unsigned,short> FlattenedList;

Here is my first attempt:

template<typename... Ts>
struct List{};

template<typename... Ts>
struct FlattenTree{
    typedef List<Ts...> Type;
};
template<typename... Ts, typename... Us, typename... Vs>
struct FlattenTree<Ts...,List<Us...>,Vs...>{
    typedef typename FlattenTree<Ts..., Us..., Vs...>::Type Type;
};

but it results in this error: error C3515: if an argument for a class template partial specialization is a pack expansion it shall be the last argument

rici pointed out here what MSVC2013 is complaining about, so no compiler bug here:

§ 14.8.2.5 (Deducing template arguments from a type) paragraph 5 lists the contexts in which template arguments cannot be deduced. The relevant one is the last one in the list:

— A function parameter pack that does not occur at the end of the parameter-declaration-clause.

Update:

I guess one could put in a dummy parameter at the very end, keep moving the first argument to the end or expanding it to the front if its a List and specialize on the first parameter being my dummy to stop recursion. That seems like a lot of work for the compiler just to flatten a list though.

namespace Detail{
    struct MyMagicType {};
    template<typename T, typename... Ts>
    struct FlattenTree{
        typedef typename FlattenTree<Ts..., T>::Type Type;
    };
    template<typename... Ts>
    struct FlattenTree<MyMagicType,Ts...>{      //termination case
        typedef List<Ts...> Type;
    };
    template<typename... Ts, typename... Us>
    struct FlattenTree<List<Ts...>, Us...>{
        typedef typename FlattenTree<Ts..., Us...>::Type Type;
    };              //expand Ts to front because they may hold more nested Lists
}

template<typename... Ts>
struct FlattenTree{
    typedef typename Detail::FlattenTree<Ts...,Detail::MyMagicType>::Type Type;
};

This works on MSVC2013 but I don't think its the best way possible since I needed a dummy type and it puts a lot of load on the compiler. I want to use it with lists containing 500+ elements.

Answer 1

Another approach is to use a helper class and an accumulator list instead of MyMagicType. We start with an empty List<> and then fill it with types from the input list:

#include <type_traits>

template <class... Ts> struct List {};

// first parameter - accumulator
// second parameter - input list
template <class T, class U>
struct flatten_helper;

// first case - the head of the List is List too
// expand this List and continue
template <class... Ts, class... Heads, class... Tail>
struct flatten_helper<List<Ts...>, List<List<Heads...>, Tail...>> {
    using type = typename flatten_helper<List<Ts...>, List<Heads..., Tail...>>::type;
};

// second case - the head of the List is not a List
// append it to our new, flattened list
template <class... Ts, class Head, class... Tail>
struct flatten_helper<List<Ts...>, List<Head, Tail...>> {
    using type = typename flatten_helper<List<Ts..., Head>, List<Tail...>>::type;
};

// base case - input List is empty
// return our flattened list
template <class... Ts>
struct flatten_helper<List<Ts...>, List<>> {
    using type = List<Ts...>;
};

// wrapper around flatten_helper
template <class T> struct flatten;

// start with an empty accumulator
template <class... Ts>
struct flatten<List<Ts...>> {
    using type = typename flatten_helper<List<>, List<Ts...>>::type;
};

auto main() -> int {
    using Types = List<int, List<float, List<double, List<char>>>>;
    using Flat = flatten<Types>::type;

    static_assert(std::is_same<Flat, List<int, float, double, char>>::value, "Not the same");
}

Answer 2

Your solution is quite elegant IMO, here's another one off the top of my head:

// the tuple-like class we want to flatten
// (i.e. the node of the tree, with several children as template parameters)
template<class... TT>
struct List
{};


// a join metafunction. Joins multiple Lists into a single List
// e.g.    List<TT1...>, List<TT2...>, etc., List<TTN...>
//      => List<TT1..., TT2..., etc., TTN...>
// requires: all template arguments are `List<..>`s
template<class... TT>
struct join
{
    using type = List<>; // end recursion for no parameters
};

template<class... TT>
struct join<List<TT...>>
{
    using type = List<TT...>; // end recursion for a single parameter
};

template<class... TT0, class... TT1, class... TT2>
struct join<List<TT0...>, List<TT1...>, TT2...>
{
    // join two adjacent lists into one, recurse
    // by joining the two lists `List<TT0...>` and `List<TT1...>`,
    // we get one template argument less for the next instantiation of `join`
    // this recurs until there's only one argument left, which then
    // matches the specialization `struct join<List<TT...>>`
    using type = typename join< List<TT0..., TT1...>, TT2... > :: type;
};


// the flatten metafunction
// guarantees (all specializations): the nested `type` is a flat `List<..>`
template<class T>
struct flatten
{
    // because of the partial specialization below,
    // this primary template is only used if `T` is not a `List<..>`
    using type = List<T>; // wrap the argument in a `List`
};

template<class... TT>
struct flatten<List<TT...>> // if the argument is a `List` of multiple elements
{
    // then flatten each element of the `List` argument
    // and join the resulting `List<..>`s
    using type = typename join<typename flatten<TT>::type...>::type;

    // ex. the argument is `List<List<int>, List<double>>`
    // then `TT...` is deduced to `List<int>, List<double>`
    // `List<int>` flattened is `List<int>`, similarly for `List<double>`
    // `join< List<int>, List<double> >` yields `List<int, double>`
};

Usage and test code:

#include <iostream>
template<class T>
void print(T)
{
    std::cout << __PRETTY_FUNCTION__ << "\n"; // NON-STANDARD
}

int main()
{
    typedef List<char,List<int,float,List<int,unsigned char>>,
                 List<unsigned,short>> MyList;
    print( flatten<MyList>::type{} );
}

I'm sure the simplest way is to use boost::MPL ;)