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

概述假设我有一些包含类型排列的模板表达式,在这种情况下它们来自 Abstract Syntax Tree： template <typename... Children> struct Branch 假设我有一些包含类型排列的模板表达式,在这种情况下它们来自 Abstract Syntax Tree：

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 typestemplate <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?),但我在将这些解决方案应用于这个特定情况时遇到了麻烦,并希望得到一些指导.

解决方法 黄金法则是简化.并且不要使用元组.

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.编辑双倍所需的时间从大约150到320毫秒,我把N取为500而不是50.

这是一个精彩的图表,显示了编译程序时GCC的峰值内存使用情况 – 值由{5..800 … 5}中的for lim收集; do /usr/local/bin / time -f“％M”g -DliMIT = $lim -std = c 11~ / Programming / Saves / TEMPS / TEMP2.cxx;完成：

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

总结

以上是内存溢出为你收集整理的c – 如何从嵌套表达式*高效*生成所有类型的元组？全部内容，希望文章能够帮你解决c – 如何从嵌套表达式*高效*生成所有类型的元组？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。