c++ - C++11: Compile-time Array with Logarithmic Evaluation Depth

Question

One way to implement a C++11 array that has its elements initialized by a function of their index calculated by the compiler and have the results stored in the data section (.rodata) of the application image is to use templates, partial specialization and constexpr as follows:

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

This doesn't work for large values of N:

error: constexpr evaluation depth exceeds maximum of 512 

This is because of the head-tail style of recursive template evaluation, that has linear depth in terms of N.

Is there a way to do it such that the evaluation depth is logarithmic in terms of N, rather than linear? (and hence would avoid the default depth limit)

Answer 1

If what you're using in the code is a weird form of the indices trick, here's an implementation that has O(log N) instantiations:

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