如何有效地从嵌套表达式生成所有类型的元组？

假设我有一些包含类型排列的模板表达式，在这种情况下，它们来自抽象语法树：

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

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>::typein中的main()）时在编译过程中的峰值驻留内存（由衡量），蓝线表示将类型的实例添加到Unfold<Expression>::type其中，其中Expression的输出是Nest<N>。

我很高兴红线显示为常数，这表明编译器在这里可能做得不错。但是，蓝线显然是多项式，我想知道是否有任何简便的方法可以将其降低，理想情况下降低为线性，尽管Nlog(N)也很好。

我的问题是：如何将效率提高Unfold到比O（N ^ 2）好？

我已经问过这个问题的一般形式（如何减少大型模板的编译时内存占用量？），但是我在将这些解决方案应用于这种特殊情况时遇到了麻烦，希望能获得一些指导。