numero - C++ 11: Arreglo de tiempo de compilación con profundidad de evaluación logarítmica

logaritmos explicacion desde el principio

Question

Una forma de implementar una matriz C ++ 11 que tiene sus elementos inicializados por una función de su índice calculada por el compilador y tiene 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 <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;
}

Esto no funciona para grandes valores de N:

error: constexpr evaluation depth exceeds maximum of 512 

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

¿Hay una manera de hacerlo de tal manera 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)

Answer 1

En c ++ 14 con función de constexpression general no necesita ninguna secuencia, 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 );

Solo tiene un problema, no hay compilador que pueda compilarlo :)

Answer 2

La única plantilla recursiva de cola, que está causando la profundidad de creación de instancias de la 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 logarítmica de instanciación, como sugiere:

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

Agregue un montón de typename de typename de typename cuando sea apropiado, implemente concat_seq (fácil), extraiga la lista de argumentos para fs del range<0, N>::type y listo.

Answer 3

Si lo que estás usando en el código es una forma extraña del truco de índices, aquí hay una implementación que tiene instancias de 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>());
}

Ejemplo vivo.