为什么C++模板计算如此之快？

Question

我想知道下一个代码.

#include <iostream>
using std::cout;
template<int N> struct Fib {
    enum { v = Fib<N - 1>::v + Fib<N - 2>::v };
};
template<> struct Fib<0> {
    enum { v = 0 };
};
template<> struct Fib<1> {
    enum { v = 1 };
};
int fib(int n) {
    return n < 2 ? n : fib(n - 1) + fib(n - 2);
}
int main() {
    cout << Fib<46>::v << '\n';
//    cout << fib(46) << '\n';
    return 0;
}

它在编译时计算结果,没有任何明显的延迟.这怎么可能？如果我们使用对fib(46)的调用,我们将不得不等待几秒钟,即使使用最快的PC.该模板使用相同的计算模式,并立即生成.我也对使用模板生成的可执行文件的大小几乎与没有模板的大小相同这一事实感到惊讶.我用过GCC.

Answer 1

这是由于模板解决方案中固有的memoization.

在编译期间,每个实例化(如Fib<1>,Fib<2>等)仅由(由编译器)执行一次并被记住.

当您运行fib(n),另一方面,fib(1),fib(2),等计算多次.该解决方案可以是memoize的话,即记住每个结果fib在地图或数组调用和返回,如果结果已经存在.