C ++ 11：具有对数评估深度的编译时间数组 [英] C++11: Compile-time Array with Logarithmic Evaluation Depth

问题描述

一种实现C ++ 11数组的方法是使用模板，该数组的元素由编译器计算的其索引的函数初始化，并且结果存储在应用程序映像的数据段（.rodata）中，部分专门化和constexpr如下：

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

这不适用于大的N值：

error: constexpr evaluation depth exceeds maximum of 512 

这是因为递归模板评估的头尾形式，它具有N的线性深度。

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

有办法做这样的评估深度是对数的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)

推荐答案

如果你在代码中使用的是一个奇怪的形式下面是一个具有 O（log N）实例的实现：

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

实例。

这篇关于C ++ 11：具有对数评估深度的编译时间数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！