C ++ 11: matriz de tiempo de comstackción con profundidad de evaluación logarítmica

Una forma de implementar una matriz de C ++ 11 que tiene sus elementos inicializados por una función de su índice calculada por el comstackdor y tener los resultados almacenados en la sección de datos (.rodata) de la imagen de la aplicación es usar plantillas, especialización parcial y constexpr de la siguiente manera:

#include  #include  using namespace std; constexpr int N = 1000000; constexpr int f(int x) { return x*2; } typedef array A; template constexpr A fs() { return A{{ f(i)... }}; } template struct S; template struct S { static constexpr A gs() { return fs(); } }; template struct S { static constexpr A gs() { return S::gs(); } }; constexpr auto X = S::gs(); int main() { cout << X[3] << endl; } 

Esto no funciona para valores grandes de N:

 error: constexpr evaluation depth exceeds maximum of 512 

Esto se debe al estilo de la cola de la evaluación recursiva de la plantilla, que tiene una profundidad lineal en términos de N.

¿Hay alguna forma de hacerlo tal que la profundidad de la evaluación sea logarítmica en términos de N, en lugar de lineal? (y por lo tanto evitaría el límite de profundidad predeterminado)

Si lo que está utilizando en el código es una forma extraña del truco de los índices, aquí hay una implementación que tiene instancias O(log N) :

 // using aliases for cleaner syntax template using Invoke = typename T::type; template struct seq{ using type = seq; }; template struct concat; template struct concat, seq> : seq{}; template using Concat = Invoke>; template struct gen_seq; template using GenSeq = Invoke>; template struct gen_seq : Concat, GenSeq>{}; template<> struct gen_seq<0> : seq<>{}; template<> struct gen_seq<1> : seq<0>{}; // example template void f(seq); int main(){ f(gen_seq<6>()); } 

Ejemplo en vivo

En c ++ 14 con la función de constexpresión general no es necesaria ninguna secuencia, make_sequence

 static constexpr int f(int i) noexcept { return i * 2; } template< int N, typename F > static constexpr std::array 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 ); 

Solo tiene un problema, no existe un comstackdor que pueda comstackrlo 🙂

La única plantilla recursiva de cola, que está causando la profundidad de instanciación de plantilla lineal, es la construcción de la lista de enteros en la lista de parámetros de plantilla de S

Esto se puede hacer en profundidad de instanciación logarítmica, como sugiere:

 template  struct seq; template  struct range { typedef concat_seq::type, range::type>::type type; }; template struct range { typedef seq type; }; template  struct range { typedef seq<> type; }; 

Agregue un montón de typename s donde corresponda, implemente concat_seq (easy), extraiga la lista de argumentos para fs del range<0, N>::type y listo.