如何*有效*從嵌套表達式生成所有類型的元組？

Question

假設我有一個包含的類型安排一些模板表達，在這種情況下，他們從Abstract Syntax Tree：

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

template <int param>                
struct Leaf                   
{                     
}; 

輸入表達式可能是Branch和Leaf類型的任何嵌套組合，但要保持它的簡單我「會在深類型Branch創建包含單個Leaf包裹N層的線性AST：

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：從

紅線代表彙編（如通過time -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?），但我很難將這些解決方案應用到這個特殊情況下，並希望得到一些指導。

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到320ms。

這裏是展示編譯程序時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收集值：

空間複雜度似乎線性給我。