c – 如何从嵌套表达式*高效*生成所有类型的元组？

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

template <int param>                                                               
struct Leaf                                                                        
{                                                                                  
};

输入表达式可以是Branch和Leaf类型的任何嵌套组合,但为了保持简单,我将创建一个线性AST,其中包含一个Leaf包含N个深层的Branch类型：

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

为了这个问题,我已经创建了一个动态生成这些表达式的函数,所以我可以用图解来证明我遇到的问题.所以这是我将用于生成表达式的函数：

// 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>>;

它不一定是一个元组,它可以是任何东西,但它必须能够接受任何数量的类型而没有严重的hackery,所以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>> {};

完整的程序,它实例化表达式,然后是分支类型,can be seen here.

我对Unfold的实现有效,但似乎效率极低.下面是使用GCC 4.9.1进行编译时的总驻留内存,只有std = c 11标志,使用命令time -v g -std = c 11 main.cpp：

红线表示编译期间的峰值驻留内存(通过时间-v gcc测量…)仅从生成表达式(即,在main()中实例化类型Nest< N> :: type)和蓝线表示向其添加类型Unfold< Expression> :: type的实例化,其中Expression是Nest< N>的输出.

我很高兴红线看起来不变,这表明编译器可能在这里做得不错.然而,蓝线显然是多项式的,我想知道是否有任何简单的方法将其降低,理想情况下是线性的,尽管Nlog(N)也会很棒.

我的问题是：如何将Unfold的效率提高到比O(N ^ 2)更好的效果？

我已经问过这个问题的一般形式(How can I reduce the compile-time memory footprint of large templates?),但我在将这些解决方案应用于这个特定情况时遇到了麻烦,并希望得到一些指导.