Metaprogramming pattern: why flat type of malfunction

Question

I want to flatten a tree type to a flat type. Example:

typedef std::tuple<int,std::tuple<int,long>,int> tup; Flat<tup>::type=>std::tuple<int,int,long,int> 

I use:

 template<typename T> struct Flat { using type=T; }; template <template <typename ...> class C,typename...ARGS> struct Flat<C<ARGS...> > { using type=C<ARGS...>; }; template <template <typename ...> class C,typename ...ARGS0,typename...ARGS1,typename ...ARGS2> struct Flat<C<ARGS0...,C<ARGS1...>,ARGS2...> > :Flat<C<ARGS0...,ARGS1...,ARGS2...> > { }; void test(){ typedef std::tuple<int,std::tuple<int,long>,int> tup; static_assert(std::is_same<typename Flat<tup>::type,std::tuple<int,int,long,int> >::value,""); } 

but I get std::tuple<int,std::tuple<int,long>,int> more ... I use gcc 4.8.1

Answer 1

Here is my hit. I tried to document what is happening to make it clear:

Let's start with Flatten. Type required. We will specialize in it below:

 template<typename T> struct Flatten; 

Here is our workhorse. Accepts Src and aligns its contents and adds it to Dest:

 template<typename Dest, typename Src> struct Flatten_append; 

An empty bag on the right side means returning the left side:

 template<template<typename...>class Pack, typename... LHS> struct Flatten_append< Pack<LHS...>, Pack<> > { typedef Pack<LHS...> type; }; 

The right side, the first argument of which is the <...> package, should be flattened before processing:

 template<template<typename...>class Pack, typename... LHS, typename... RHS0, typename... RHSrest> struct Flatten_append< Pack<LHS...>, Pack<Pack<RHS0...>, RHSrest... > >: Flatten_append< Pack<LHS...>, Pack< RHS0..., RHSrest... > > {}; 

Otherwise, a non-empty package on the right side should have its first element moved to the left side: (this will be weaker than indicated above, since it is less specialized)

 template<template<typename...>class Pack, typename... LHS, typename RHS0, typename... RHSrest> struct Flatten_append< Pack<LHS...>, Pack<RHS0, RHSrest... > >: Flatten_append< Pack<LHS..., RHS0>, Pack< RHSrest... > > {}; 

Embed Flatten in terms of Flatten_append in an empty package:

 template<template<typename...>class Pack, typename... Ts> struct Flatten< Pack<Ts...> >:Flatten_append< Pack<>, Pack<Ts...> > {}; 

The goal was to make it as clear as possible what was happening.

Now you will notice that the disadvantage of this design is that it will smooth out any template that will contain only types. We will probably want to go into the package we want to smooth out.

 template<template<typename...>class Pack, typename T> struct Flatten; template<template<typename...>class Pack, typename Dest, typename Src> struct Flatten_append; template<template<typename...>class Pack, typename... Ts> struct Flatten< Pack<Ts...> > : Flatten_append< Pack, Pack<>, Pack<Ts...> > {}; 

and then change each specialization of Flatten_append< blah, blah, blah > to Flatten_append< Pack, blah, blah, blah > .

This means that you pass in the template that you want to flatten explicitly, and the code only aligns the value of template .

In practice, this may not be necessary, since the Pack type is inferred from the left type passed to.

Answer 2

First explain how it works:

This is a forward declaration so we can use flatten with one type.

 template<class T> struct flatten; 

Then we specialize flatten to accept any type of template. C is a template template parameter, so we can get the type of the surrounding template. For example. if you use flatten with the parameter std::tuple<int, double> , then C will be std::tuple .

FArgs is used to retrieve the parameter list of the passed pattern. In the case of the example I just talked about, that would be int, double

 template< template< typename ... > class C, typename ...FArgs> struct flatten<C<FArgs...>> 

In the rest of the flatten implementation, the C shell type and the FArgs argument list are now always available.

Forward the declaration for append , which adds the B parameter to the list of elements in the Target parameter

  template< typename Target, typename B > struct append; 

An append specialization that retrieves a list of types from Target (see above). Note that C is still std::tuple .

So, we add another element to the list and create a new type using the previous Args1 argument list and then adding T

  template< typename ...Args1, typename T > struct append<C<Args1...>, T> { using type = C<Args1..., T>; }; 

Forward declaration inner and inner2

inner used to iterate over the list of provided arguments and applies inner2 to each of them, which in turn applies inner to the type again if the type is a different template with parameters. This pattern must match pattern C

  template< typename Target, typename ...Args > struct inner; template< typename Target, typename T > struct inner2; 

This inner2 processes all types of C template types and iterates through its parameter list recursively using inner

  template< typename Target, typename ...Args> struct inner2<Target, C<Args...>> { using type = typename inner<Target, Args...>::type; }; 

If this specialization inner2 used, the type will be added to the final result.

  template< typename Target, typename T > struct inner2 { using type = typename append<Target, T>::type; }; 

Returns template parameters by inheritance and application for each parameter inner2

  template< typename Target, typename T, typename ...Args> struct inner<Target, T, Args...> : inner<typename inner2<Target, T>::type, Args...> {}; 

The final condition for recursion.

  template< typename Target, typename T > struct inner<Target, T> { using type = typename inner2<Target, T>::type; }; 

This whole thing is generated from above, C<> indicates that Target and FArgs are arguments highlighted by the flatten specialization.

  using type = typename inner<C<>, FArgs...>::type; }; 

---

And here is the whole code:

 #include <tuple> #include <string> template<class T> struct flatten; template< template< typename ... > class C, typename ...FArgs> struct flatten<C<FArgs...>> { template< typename Target, typename ...B > struct append; template< typename ...Args1, typename T > struct append<C<Args1...>, T> { using type = C<Args1..., T>; }; template< typename Target, typename ...Args > struct inner; template< typename Target, typename T > struct inner2; template< typename Target, typename ...Args> struct inner2<Target, C<Args...>> { using type = typename inner<Target, Args...>::type; }; template< typename Target, typename T > struct inner2 { using type = typename append<Target, T>::type; }; template< typename Target, typename T, typename ...Args> struct inner<Target, T, Args...> : inner<typename inner2<Target, T>::type, Args...> {}; template< typename Target, typename T > struct inner<Target, T> { using type = typename inner2<Target, T>::type; }; using type = typename inner<C<>, FArgs...>::type; }; int main() { typedef flatten<std::tuple<int, float, double>>::type first; static_assert(std::is_same<first, std::tuple<int, float, double>>::value, "First not the same"); typedef flatten<std::tuple<int, std::tuple<float, double>>>::type second; static_assert(std::is_same<second, std::tuple<int, float, double>>::value, "Second not the same"); typedef flatten<std::tuple<int, std::tuple<char const *>, std::tuple<std::tuple<float, int>, double>>>::type third; static_assert(std::is_same<third, std::tuple<int, char const *, float, int, double>>::value, "Third not the same"); typedef flatten<std::tuple<int, std::tuple<std::tuple<std::tuple<std::tuple<char const *>>>>, std::tuple<std::tuple<float, int>, double>>>::type fourth; static_assert(std::is_same<fourth, std::tuple<int, char const *, float, int, double>>::value, "Fourth not the same"); typedef flatten<std::tuple<int, std::tuple<std::tuple<std::tuple<std::tuple<std::string>>>>, std::tuple<std::tuple<float, int>, double>>>::type fifth; static_assert(std::is_same<fifth, std::tuple<int, std::string, float, int, double>>::value, "Fifth not the same"); } 

Edit: I rewrote the implementation to make it more readable and shorter (inspired by @DyP) Edit2: explained the code