How can I use Variadic templates to flatten a tree of types?
c++, c++11, metaprogramming, templates, variadic-templates
Solution
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");
}
Problem
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.