在运行时获取模板元编程时间常量
背景
考虑以下：
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来生成斐波纳契数字。 还是我错过了什么？
