C++ 11: Tablica czasu kompilacji z logarytmiczną głębokością oceny

Question

Jednym ze sposobów zaimplementowania tablicy C++ 11, której elementy zostały zainicjowane przez funkcję indeksu obliczoną przez kompilator i mają wyniki zapisane w sekcji danych (.rodata) obrazu aplikacji jest użycie szablonów, częściowej specjalizacji i constexpr następująco:

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

ta nie działa w przypadku dużych wartości N:

error: constexpr evaluation depth exceeds maximum of 512 

to dlatego, że z styl rekurencyjnej oceny szablonu, który ma liniową głębokość w te rms N.

Czy istnieje sposób, aby to zrobić, aby głębokość oceny była logarytmiczna pod względem N, a nie liniowa? (i tym samym uniknęłoby domyślnego limitu głębokości)

Answer 1

Jeśli używasz w kodzie to dziwne formy trick indeksów, oto implementacja że ma O(log N) dawałaby:

// 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.

Answer 2

Jedynym szablonem rekurencyjnym, który powoduje liniową głębokość tworzenia instancji szablonu, jest konstrukcja listy liczb całkowitych na liście parametrów szablonu S.

Można to zrobić w logarytmicznej głębokości konkretyzacji, jak sugerujesz:

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

Dodaj pęczek typename s stosownych przypadkach, wprowadzania concat_seq (łatwe), wyodrębnić listę argumentów dla fs z range<0, N>::type i tam udać się.

Answer 3

w C++ 14 z ogólnej constexpression funkcja nie musi mieć żadnej sekwencji, 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); 

Ma tylko jeden problem, nie ma kompilatora, który mógłby go skompilować :)