c++ - 我怎样才能*有效地*从嵌套表达式生成所有类型的元组？

Question

假设我有一些包含类型排列的模板表达式，在本例中它们来自 Abstract Syntax Tree :

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

template <int param>                                                               
struct Leaf                                                                        
{                                                                                  
};

输入表达式可以是 Branch 的任意嵌套组合和 Leaf类型，但为了简单起见，我将创建一个包含单个 Leaf 的线性 AST包裹 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>>;

它不一定是元组，它可以是任何东西，但它确实必须能够接受任意数量的类型而无需认真的黑客攻击，所以 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 :

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

我很高兴红线显示不变，表明编译器可能在这里做得不错。然而，蓝线显然是多项式的，我想知道是否有任何简单的方法可以降低它，最好是线性的，尽管 Nlog(N)也会很棒。

我的问题是:如何提高Unfold的效率？比 O(N^2) 更好的东西？

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

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

Demo .一旦我将 N 设为 ~500 而不是 50，编译所需的时间从 ~150 毫秒增加到 320 毫秒。

这是一个很棒的图表，显示了编译程序时 GCC 的内存使用峰值 - 值由 for lim in {5..800..5} 收集；做/usr/local/bin/time -f"%M"g++ -DLIMIT=$lim -std=c++11 ~/Programming/Saves/TEMPS/TEMP2.cxx;完成:

空间复杂度对我来说似乎是线性的。