在运行时获取模板元编程时间常量

背景

考虑以下:

template <unsigned N> struct Fibonacci { enum { value = Fibonacci<N-1>::value + Fibonacci<N-2>::value }; }; template <> struct Fibonacci<1> { enum { value = 1 }; }; template <> struct Fibonacci<0> { enum { value = 0 }; }; 

这是一个常见的例子,我们可以将斐波那契数的值作为编译时常量:

 int main(void) { std::cout << "Fibonacci(15) = "; std::cout << Fibonacci<15>::value; std::cout << std::endl; } 

但是你显然无法在运行时获得这个值:

 int main(void) { std::srand(static_cast<unsigned>(std::time(0))); // ensure the table exists up to a certain size // (even though the rest of the code won't work) static const unsigned fibbMax = 20; Fibonacci<fibbMax>::value; // get index into sequence unsigned fibb = std::rand() % fibbMax; std::cout << "Fibonacci(" << fibb << ") = "; std::cout << Fibonacci<fibb>::value; std::cout << std::endl; } 

因为fibb不是编译时常量。

所以我的问题是:

在运行时窥探此表的最佳方法是什么? 最明显的解决scheme(和“解决scheme”应该是轻率的),是有一个大的开关语句:

 unsigned fibonacci(unsigned index) { switch (index) { case 0: return Fibonacci<0>::value; case 1: return Fibonacci<1>::value; case 2: return Fibonacci<2>::value; . . . case 20: return Fibonacci<20>::value; default: return fibonacci(index - 1) + fibonacci(index - 2); } } int main(void) { std::srand(static_cast<unsigned>(std::time(0))); static const unsigned fibbMax = 20; // get index into sequence unsigned fibb = std::rand() % fibbMax; std::cout << "Fibonacci(" << fibb << ") = "; std::cout << fibonacci(fibb); std::cout << std::endl; } 

但是现在桌子的尺寸是非常难以编码的,40的膨胀并不容易。

我想到的唯一一个类似于查询的方法是这样的:

 template <int TableSize = 40> class FibonacciTable { public: enum { max = TableSize }; static unsigned get(unsigned index) { if (index == TableSize) { return Fibonacci<TableSize>::value; } else { // too far, pass downwards return FibonacciTable<TableSize - 1>::get(index); } } }; template <> class FibonacciTable<0> { public: enum { max = 0 }; static unsigned get(unsigned) { // doesn't matter, no where else to go. // must be 0, or the original value was // not in table return 0; } }; int main(void) { std::srand(static_cast<unsigned>(std::time(0))); // get index into sequence unsigned fibb = std::rand() % FibonacciTable<>::max; std::cout << "Fibonacci(" << fibb << ") = "; std::cout << FibonacciTable<>::get(fibb); std::cout << std::endl; } 

这似乎很好。 我看到的唯一的两个问题是:

  • 由于计算Fibonacci <2>需要我们通过TableMax一直到2,并且:

  • 如果该值在表格之外,则返回零而不是计算该值。

那么有什么我失踪? 看来应该有一个更好的方法来在运行时挑选出这些值。

一个switch语句的模板元编程版本可能会产生一个switch语句直到某个数字?

提前致谢。

 template <unsigned long N> struct Fibonacci { enum { value = Fibonacci<N-1>::value + Fibonacci<N-2>::value }; static void add_values(vector<unsigned long>& v) { Fibonacci<N-1>::add_values(v); v.push_back(value); } }; template <> struct Fibonacci<0> { enum { value = 0 }; static void add_values(vector<unsigned long>& v) { v.push_back(value); } }; template <> struct Fibonacci<1> { enum { value = 1 }; static void add_values(vector<unsigned long>& v) { Fibonacci<0>::add_values(v); v.push_back(value); } }; int main() { vector<unsigned long> fibonacci_seq; Fibonacci<45>::add_values(fibonacci_seq); for (int i = 0; i <= 45; ++i) cout << "F" << i << " is " << fibonacci_seq[i] << '\n'; } 

经过深思熟虑后,我想出了这个解决scheme。 当然,您仍然需要在运行时将这些值添加到容器中,但是(重要的是)它们不会在运行时进行计算

作为一个方面说明,重要的是不要在Fibonacci<0> Fibonacci<1>之上定义Fibonacci<1> ,否则编译器在parsing对Fibonacci<0>::add_values的调用时会变得非常困惑,因为Fibonacci<0>的模板特化没有被指定。

当然,TMP有其局限性:你需要一个预先计算的最大值,在运行时获取值需要recursion(因为模板是recursion定义的)。

我知道这个问题是旧的,但它引起了我的兴趣,我不得不在运行时填充dynamic容器,

 #ifndef _FIBONACCI_HPP #define _FIBONACCI_HPP template <unsigned long N> struct Fibonacci { static const unsigned long long value = Fibonacci<N-1>::value + Fibonacci<N-2>::value; static unsigned long long get_value(unsigned long n) { switch (n) { case N: return value; default: return n < N ? Fibonacci<N-1>::get_value(n) : get_value(n-2) + get_value(n-1); } } }; template <> struct Fibonacci<0> { static const unsigned long long value = 0; static unsigned long long get_value(unsigned long n) { return value; } }; template <> struct Fibonacci<1> { static const unsigned long long value = 1; static unsigned long get_value(unsigned long n) { return value; } }; #endif 

这似乎工作,并在优化编译(不知道如果你打算允许的话),调用堆栈不深入 – 当然,对于值(参数)n> N堆栈正常运行时recursion,其中N是模板实例化中使用的TableSize。 然而,一旦你走到TableSize的下面,生成的代码会replace一个在编译时计算出来的常量,或者最坏的情况是通过跳转表(在gcc中用-c -g -Wa,-adhlns = main编译)来“计算”一个值。 s和检查列表),就像我认为你的显式切换语句会导致。

当使用像这样:

 int main() { std::cout << "F" << 39 << " is " << Fibonacci<40>::get_value(39) << '\n'; std::cout << "F" << 45 << " is " << Fibonacci<40>::get_value(45) << '\n'; } 

在第一种情况下(在编译时计算的值)根本没有调用的计算,在第二种情况下调用堆栈的深度是最差的:

 fibtest.exe!Fibonacci<40>::get_value(unsigned long n=41) Line 18 + 0xe bytes C++ fibtest.exe!Fibonacci<40>::get_value(unsigned long n=42) Line 18 + 0x2c bytes C++ fibtest.exe!Fibonacci<40>::get_value(unsigned long n=43) Line 18 + 0x2c bytes C++ fibtest.exe!Fibonacci<40>::get_value(unsigned long n=45) Line 18 + 0xe bytes C++ fibtest.exe!main() Line 9 + 0x7 bytes C++ fibtest.exe!__tmainCRTStartup() Line 597 + 0x17 bytes C 

即它recursion直到它在“表”中find一个值。 (通过在debugging器中一行一行地逐步进行反汇编来validation,同样通过将随机数<45的testing整数replace)

recursion部分也可以用线性迭代解决scheme代替:

 static unsigned long long get_value(unsigned long n) { switch (n) { case N: return value; default: if (n < N) { return Fibonacci<N-1>::get_value(n); } else { // n > N unsigned long long i = Fibonacci<N-1>::value, j = value, t; for (unsigned long k = N; k < n; k++) { t = i + j; i = j; j = t; } return j; } } } 

如果您有支持可变参数模板(C ++ 0x标准)的C ++编译器,则可以在编译时将斐波那契序列保存在一个元组中。 在运行时你可以通过索引来访问元组中的任何元素。

 #include <tuple> #include <iostream> template<int N> struct Fib { enum { value = Fib<N-1>::value + Fib<N-2>::value }; }; template<> struct Fib<1> { enum { value = 1 }; }; template<> struct Fib<0> { enum { value = 0 }; }; // ---------------------- template<int N, typename Tuple, typename ... Types> struct make_fibtuple_impl; template<int N, typename ... Types> struct make_fibtuple_impl<N, std::tuple<Types...> > { typedef typename make_fibtuple_impl<N-1, std::tuple<Fib<N>, Types... > >::type type; }; template<typename ... Types> struct make_fibtuple_impl<0, std::tuple<Types...> > { typedef std::tuple<Fib<0>, Types... > type; }; template<int N> struct make_fibtuple : make_fibtuple_impl<N, std::tuple<> > {}; int main() { auto tup = typename make_fibtuple<25>::type(); std::cout << std::get<20>(tup).value; std::cout << std::endl; return 0; } 

用C ++ 11:你可以创build一个std::array和一个简单的getter: https : //ideone.com/F0b4D3

 namespace detail { template <std::size_t N> struct Fibo : std::integral_constant<size_t, Fibo<N - 1>::value + Fibo<N - 2>::value> { static_assert(Fibo<N - 1>::value + Fibo<N - 2>::value >= Fibo<N - 1>::value, "overflow"); }; template <> struct Fibo<0u> : std::integral_constant<size_t, 0u> {}; template <> struct Fibo<1u> : std::integral_constant<size_t, 1u> {}; template <std::size_t ... Is> constexpr std::size_t fibo(std::size_t n, index_sequence<Is...>) { return const_cast<const std::array<std::size_t, sizeof...(Is)>&&>( std::array<std::size_t, sizeof...(Is)>{{Fibo<Is>::value...}})[n]; } template <std::size_t N> constexpr std::size_t fibo(std::size_t n) { return n < N ? fibo(n, make_index_sequence<N>()) : throw std::runtime_error("out of bound"); } } // namespace detail constexpr std::size_t fibo(std::size_t n) { // 48u is the highest return detail::fibo<48u>(n); } 

C(以及大多数C ++)的一个基本的前提是你不需要支付你不需要的东西。

查找表的自动生成不是编译器需要为你做的事情。 即使你需要这个function,并不是每个人都必须这样做。

如果你想要一个查找表,写一个程序来做一个。 然后在你的程序中使用这些数据。

如果要在运行时计算值,则不要使用模板元程序,只需使用常规程序计算值即可。

您可以使用预处理器元编程技术生成开关或静态数组。 如果复杂性没有超出该方法的限制,那么这是一个很好的决定,而且您不希望使用额外的步骤生成代码或数据来扩展您的工具链。

这应该做的伎俩…

 template <int N> class EXPAND { public: static const string value; }; template <> class EXPAND<0> { public: static const string value; }; template <int N> const string EXPAND<N>::value = EXPAND<N-1>::value+"t"; const string EXPAND<0>::value = "t"; int main() { cout << EXPAND<5>::value << endl; } 
 unsigned fibonacci(unsigned index) { switch (index) { case 0: return Fibonacci<0>::value; case 1: return Fibonacci<1>::value; default: return fibonacci(index - 1) + fibonacci(index - 2); } } 

这不是解决你的问题吗? 我的意思是这毕竟是一个斐波那契序列。 当然,你不能列出它。 这个“练习”的目的(尽pipe是一个愚蠢的:))必须要指出你可以用模板做什么,在这种情况下应用recursionalgorithm来生成斐波纳契数字。 还是我错过了什么?