C++ 11:具有对数评估深度的编译时数组

Question

应用程序图像的实现具有通过由编译器计算其指数的函数初始化它的元素,并已存储在数据部分的结果的C++ 11阵列的一种方式(.RODATA)是使用模板,部分特和constexpr如下:

#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的大值:

error: constexpr evaluation depth exceeds maximum of 512 

这是因为递归模板评估的头尾风格,其在N方面具有线性深度.

有没有办法做到这一点,使得评价的深度是对数为N的,而不是线性的？(因此会避免默认的深度限制)

Answer 1

如果你在代码中使用的是一个奇怪的索引技巧形式,这里是一个具有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>());
}

实例.