How can I efficiently generate a tuple of all types from a nested expression?

Question

Suppose I have a template expression that contains an arrangement of types, in which case they are from an Abstract syntax tree :

template <typename... Children>                                                    
struct Branch                                                                      
{                                                                                  
};                                                                                 

template <int param>                                                               
struct Leaf                                                                        
{                                                                                  
};

The input expression can be any nested combination of types Branchand Leaf, but to simplify it, I will create a linear AST containing one Leafwrapped Nlayer deep in the Branchtypes:

using Expression =
  Branch<
    Branch<
      Leaf>>; // N = 2

For this question, I created a function that generates these expressions on the fly, so I can demonstrate the problem that I have with graphs. So, here is the function that I will use to generate my expressions:

// wrap Leaf in Branch N number of times:
template <int N, typename T = Leaf>
struct Nest
{
    using type = typename Nest<N-1, Branch<T>>::type;
};

template <typename T>
struct Nest<0, T>
{
    using type = T;
};

Live example for N = 25

, , / , , Nest. Nest, , . , , Branch?

, N == 2, , :

std::tuple<
  Branch<Branch<Leaf>>,
  Branch<Leaf>>;

, , , boost::mpl , , Boost 1.56. .

:

namespace detail
{

// a container of types
template <typename... T> struct Types {};

template <typename T, typename Enabled = void>
struct UnfoldImpl;

template <template <typename...> class Branch, typename... Children>
struct UnfoldImpl<
    Types<Branch<Children...>>,
    typename std::enable_if<Branch<Children...>::IsBranch::value>::type>
{
    using type = typename TupleCat<
        std::tuple<Types<Branch<Children...>>>,
        typename UnfoldImpl<Types<Children...>>::type>::type;
};

template <typename Leaf>
struct UnfoldImpl<
    Types<Leaf>,
    typename std::enable_if<!Leaf::IsBranch::value>::type>
{
    using type = std::tuple<>;
};

template <typename FirstBranch, typename... OtherBranches>
struct UnfoldImpl<Types<FirstBranch, OtherBranches...>,typename std::enable_if<sizeof...(OtherBranches)>::type>
{
    using type = typename TupleCat<
        typename UnfoldImpl<Types<FirstBranch>>::type,
        typename UnfoldImpl<Types<OtherBranches...>>::type>::type;
};

}

// Take an expression containing some combination of branch and leaf classes, and extract every
// type that is a template instantiation of Branch and place it into a tuple.
template <typename Expression>
struct Unfold : detail::UnfoldImpl<detail::Types<Expression>> {};

, , , .

Unfold , , , . GCC 4.9.1 std=c++11, time -v g++ -std=c++11 main.cpp:

( time -v gcc ...) (.. Nest<N>::type main()), Unfold<Expression>::type, Expression - Nest<N>.

, , , , , . , , , - , Nlog(N) .

: Unfold - , O (N ^ 2)?

( ?), .

Answer 1

- . tuple.

template <typename...> struct type_list {using type = type_list;};

template<typename...>
struct cat_type_list;

template<typename T>
struct cat_type_list<T> : T {};

template<typename... T, typename... U, typename... R>
struct cat_type_list<type_list<T...>, type_list<U...>, R...> :
    cat_type_list<type_list<T..., U...>, R...> {};


template <typename... AllBranches>
struct Unfold
{
    using type = typename cat_type_list<
        typename Unfold<AllBranches>::type...>::type;
};

template <typename T>
struct Unfold<T>
{
    using type = type_list<>;
};

template <template <typename...> class Branch, typename... Children>
struct Unfold<Branch<Children...>>
{
    using type = typename cat_type_list<
        type_list<Branch<Children...>>,
        typename Unfold<Children...>::type>::type;
};

. , 150 320 , N ~ 500 50.

, GCC - for lim in {5..800..5}; do /usr/local/bin/time -f"%M" g++ -DLIMIT=$lim -std=c++11 ~/Programming/Saves/TEMPS/TEMP2.cxx; done:

.