C++ 11：具有對數評估深度的編譯時數組

一種實現C++ 11數組的方法，該數組的元素通過編譯器計算其索引的函數進行初始化，並將結果存儲在數據段中應用程序圖像的（.RODATA）如下使用模板，部分特和constexpr：C++ 11：具有對數評估深度的編譯時數組

error: constexpr evaluation depth exceeds maximum of 512

這是因爲：

#include <iostream> 
#include <array> 
using namespace std; 

constexpr int N = 1000000; 
constexpr int f(int x) { return x*2; } 

typedef array<int, N> A; 

template<int... i> constexpr A fs() { return A{{ f(i)... }}; } 

template<int...> struct S; 

template<int... i> struct S<0,i...> 
{ static constexpr A gs() { return fs<0,i...>(); } }; 

template<int i, int... j> struct S<i,j...> 
{ static constexpr A gs() { return S<i-1,i,j...>::gs(); } }; 

constexpr auto X = S<N-1>::gs(); 

int main() 
{ 
     cout << X[3] << endl; 
}

這並不適用於大的N值的工作頭尾樣式的遞歸模板評估，它具有線性深度N的有效值。

有沒有辦法做到這樣的評估深度是對數的N而不是線性？（並且因此將避免默認深度限制）

來源

2012-10-25 Andrew Tomazos

相關：http://stackoverflow.com/questions/12108390/c11-compile-time-calculation-of-array –

相關：http://stackoverflow.com/questions/13102996/c11-workaround-use-of -this-incomplete-type-error –

如果您使用的代碼是什麼指數招一個奇怪的形式，這裏有O(log N)實例的實現：

// using aliases for cleaner syntax 
template<class T> using Invoke = typename T::type; 

template<unsigned...> struct seq{ using type = seq; }; 

template<class S1, class S2> struct concat; 

template<unsigned... I1, unsigned... I2> 
struct concat<seq<I1...>, seq<I2...>> 
    : seq<I1..., (sizeof...(I1)+I2)...>{}; 

template<class S1, class S2> 
using Concat = Invoke<concat<S1, S2>>; 

template<unsigned N> struct gen_seq; 
template<unsigned N> using GenSeq = Invoke<gen_seq<N>>; 

template<unsigned N> 
struct gen_seq : Concat<GenSeq<N/2>, GenSeq<N - N/2>>{}; 

template<> struct gen_seq<0> : seq<>{}; 
template<> struct gen_seq<1> : seq<0>{}; 

// example 

template<unsigned... Is> 
void f(seq<Is...>); 

int main(){ 
    f(gen_seq<6>()); 
}

Live example.

來源

2012-10-25 16:27:36 Xeo

爲了說明問題，使用我的特定編譯器和機器，我可以在觸發模板實例化限制之前將OP的程序編譯爲'N = 510'。使用這種技術，我可以在'12000'附近碰到'N'，並且限制因素變成記憶 - 我已經看到一臺機器能夠在'25000'附近處理'N'。顯然與「1000000」相差甚遠，但幾個數量級的淨改善。 –

@LucDanton：FYI事實證明GCC存在大N的問題，但是我有一個報告說clang/llvm沒有任何問題（例如，clang可以處理N = 10^6）。不知道msvc。 –

使用帶有18GB或RAM的'g ++ - 4.8'我在內存不足時使用'N'到'75000' – SirGuy

唯一的尾部遞歸模板是造成線性模板實例化深度的模板參數列表中的整數列表S。

這可以在對數實例化深度來完成，你的建議：

template <int ... Ints> struct seq; 

template <int Start, int End> 
struct range 
{ 
    typedef concat_seq<range<Start, Start+(End-Start)/2>::type, range<Start+(End-Start)/2, End>::type>::type type; 
}; 

template<int Singleton> 
struct range<Singleton, Singleton+1> 
{ 
    typedef seq<Singleton> type; 
}; 

template <int NoSingleton> 
struct range<NoSinleton, NoSingleton> 
{ 
    typedef seq<> type; 
};

添加了一堆typename S其中適當，實現concat_seq（容易），從range<0, N>::type提取fs參數列表中有你走。

來源

2012-10-25 16:21:15 jpalecek

在C++ 14一般constexpression函數不需要任何序列，make_sequence

static constexpr int f(int i) noexcept { return i * 2; } 

template< int N, typename F > 
static constexpr std::array<int,N> generate_array(F fo) noexcept 
{ 
    std::array< int, N > result{}; // init with zero 
    int i = 0; 
    for(auto& x : result) x = fo(++i); 

    return result; 
} 

// test 
constexpr auto arr = generate_array<10>(f);

只有一個問題，沒有編譯器可以編譯它:)

來源

2013-11-18 08:01:45 Khurshid

實際上C++ 1y模式中的鏗鏘樹幹功能完全針對最新草稿。 –

C++ 11：具有對數評估深度的編譯時數組

回答

相關問題