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

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

但是它有一个“小”问题。

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

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

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

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

但是...如果您可以将最高值强加给所需的值，则可以在编译时计算所有 值(从零到最高)并将它们存储在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;
 }

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

如果你想实现struct fibVals在 C++11 中，您可以实现以下结构 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 { } }
 { }