GMa*_*ckG 43 c++ templates runtime metaprogramming
考虑以下:
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
};
};
这是一个常见的例子,我们可以将Fibonacci数的值作为编译时常量:
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不是编译时常量.
所以我的问题是:
在运行时查看此表的最佳方法是什么？最明显的解决方案(和"解决方案"应该掉以轻心),是有一个大的switch语句:
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语句？
提前致谢.
rlb*_*ond 28
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';
}
经过深思熟虑后,我想出了这个解决方案.当然,您仍然必须在运行时将值添加到容器中,但(重要的是)它们不会在运行时计算.
作为旁注,重要的是不要在Fibonacci<1>上面定义Fibonacci<0>,否则编译器在解析调用时会非常困惑Fibonacci<0>::add_values,因为Fibonacci<0>没有指定模板特化.
当然,TMP有其局限性:您需要预先计算的最大值,并且在运行时获取值需要递归(因为模板是递归定义的).
mad*_*oki 17
我知道这个问题很老,但它引起了我的兴趣,我不得不在运行时填充动态容器:
#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,堆栈上存在正常的运行时递归,其中N是模板实例化中使用的TableSize.但是,一旦你低于TableSize,生成的代码将替换在编译时计算的常量,或者在最坏的情况下通过删除跳转表(在gcc中使用-c -g -Wa,-adhlns = main编译)来"计算". s并检查列表),就像我认为你的显式switch语句一样.
当像这样使用时:
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
即它在递归直到它在"表"中找到一个值.(通过逐行逐步调试调试器中的反汇编验证,也可以通过随机数替换测试整数<= 45)
递归部分也可以用线性迭代解决方案代替:
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;
}
}
}