使用模板元编程计算数据编译时间

Question

假设我们有这样的代码。它运行良好并预先计算前 5 个斐波那契数。

#include <iostream>

template <int T>
struct fib;

template <>
struct fib<0>{
    constexpr static int value = 1;
};

template <>
struct fib<1>{
   constexpr static int value = 1;
};

template <int I>
struct fib{
   constexpr static int value = fib<I - 1>::value + fib<I - 2>::value;
};

int main(){
    std::cout << fib<0>::value << std::endl;
    std::cout << fib<1>::value << std::endl;
    std::cout << fib<2>::value << std::endl;
    std::cout << fib<3>::value << std::endl;
    std::cout << fib<4>::value << std::endl;
    std::cout << fib<5>::value << std::endl;
}

但是有 "small" 个问题。

如果我们需要将其用于编译时未知的值怎么办？

对于少数值，我们可以这样做：

const int max = 5;

int getData(){
   return 5; // return value between 0 and max.
}

int something(){
   switch(getData()){
      case 0: return fib<0>::value;
      case 1: return fib<1>::value;
      case 2: return fib<2>::value;
      case 3: return fib<3>::value;
      case 4: return fib<4>::value;
      case 5: return fib<5>::value;
   }
}

这对 5 个值都有效，但是如果我们有 150 或 300 个呢？
改300行的代码真的不是很认真...

这里有什么解决方法？

Answer 1

模板是在编译时评估的，因此没有在运行时工作的模板解决方案。

您可以制作一个 constexpr 函数，可以在编译时对其求值，具体取决于传递的值。显然，运行时值可能不会在编译时计算，因为它在编译时是未知的。

Answer 2

如果您需要在运行时使用编译时未知的值，则无法在编译时计算它。显而易见。

但是...如果您可以将最高值强加给所需的值，则可以在编译时计算所有值（从零到最高）并将它们存储在 std::array.

在下面的示例中，我修改了您的 fib 结构（为值使用 std::size_t 索引和模板类型（默认为 unsigned long））并且我添加了一个模板化的 struct fibVals，其中包含一个 std::array，使用 fib<n>::value

初始化

下面的 main() 表明可以定义一个 constexpr fibvals<N>（在示例中使用 N == 20）来计算（在编译时）所有 fib<n> 值范围 [0,N[.

#include <array>
#include <utility>
#include <iostream>

template <std::size_t, typename T = unsigned long>
struct fib;

template <typename T>
struct fib<0U, T>
 { constexpr static T value { T(1) }; };

template <typename T>
struct fib<1U, T>
 { constexpr static T value { T(1) }; };

template <std::size_t I, typename T>
struct fib
 { constexpr static T value { fib<I-1U>::value + fib<I-2U>::value }; };

template <std::size_t I, typename T = unsigned long>
struct fibVals
 {
   const std::array<T, I>  vals;

   template <std::size_t ... Is>
   constexpr fibVals ( std::index_sequence<Is...> const & )
      : vals { { fib<Is, T>::value ... } }
    { }

   constexpr fibVals () : fibVals { std::make_index_sequence<I> { } }
    { }
 };


int main()
 {
   constexpr fibVals<20>  fv;

   for ( auto ui = 0U ; ui < fv.vals.size() ; ++ui )
      std::cout << "fib(" << ui << ") = " << fv.vals[ui] << std::endl;
 }

不幸的是，这个例子使用了 C++14 特性的 std::make_index_sequence<I> 和 std::index_sequence<Is...>。

如果你想在 C++11 中实现 struct fibVals，你可以实现以下结构 struct indexSeq 和 struct indexSeqHelper，以替代 std::index_sequence<Is...> 和 std::make_index_sequence<I>

template <std::size_t ...>
struct indexSeq
 { };

template <std::size_t N, std::size_t ... Next>
struct indexSeqHelper
 { using type = typename indexSeqHelper<N-1U, N-1U, Next ... >::type; };

template <std::size_t ... Next >
struct indexSeqHelper<0U, Next ... >
 { using type = indexSeq<Next ... >; };

并实现 fibVals 构造函数如下

template <std::size_t ... Is>
constexpr fibVals ( indexSeq<Is...> const & )
   : vals { { fib<Is, T>::value ... } }
 { }

constexpr fibVals () : fibVals { typename indexSeqHelper<I>::type { } }
 { }

使用模板元编程计算数据编译时间

calculating data compile time with template metaprogramming

c++

templates

template-specialization

template-meta-programming

c++11