c++ - 模板作为递归函数

Question

我找到了这段代码，想知道我是否真的应该在我的真实项目中实现这样的东西。

让我困惑的是

1. 这会花费更多的编译时间，但我不应该为此烦恼编译时间以运行时间为代价。

2. 如果 N 真的变得非常大怎么办？有文件吗源代码中的大小限制？

还是知道而不是实现的好东西？

#include <iostream>
using namespace std;

template<int N>
class Factorial {
public:
    static const int value = N * Factorial<N-1>::value;
};
template <>
class Factorial<1> {
public:
    static const int value = 1;
};

int main() {
  Factorial<5L> f;
  cout << "5! = " << f.value << endl;

    }

输出:

5! = 120

有问题的轻微修改，因为我正在玩代码，发现

  Factorial<12> f1;  // works  
  Factorial<13> f2;  // doesn't work

错误:

undefined reference to `Factorial<13>::value'

是否可以达到 12 深度？

Answer 1

1 的答案取决于，template meta programming本质上涉及在编译时进行计算与不必在运行时进行计算之间的权衡。一般来说，这种技术会导致难以阅读和维护代码。因此，答案最终取决于您对更快的运行时性能的需求，而不是更慢的编译时间和可能更难维护的代码。

文章Want speed? Use constexpr meta-programming! 解释了如何在现代 C++ 中使用 constexpr functions多次作为模板元编程的替代品。这通常会导致代码更具可读性并且可能更快。将此模板元编程方法与 constexpr 示例进行比较:

constexpr int factorial( int n )
{
   return ( n == 0 ? 1 : n*factorial(n-1) ) ;
}

哪个更简洁，可读性更强，将被执行at compile time对于常量表达式的参数，尽管正如链接的答案所解释的那样，标准实际上并没有说它必须是，但在实践中，当前的实现肯定是这样。

还值得注意的是，由于结果会很快溢出 value，因此 constexpr 的另一个优点是 undefined behavior is not a valid constant expression至少 gcc 和 clang 的当前实现在大多数情况下会将 constexpr 中的未定义行为变成错误。例如:

constexpr int n = factorial(13) ;

对我来说会产生以下错误:

error: constexpr variable 'n' must be initialized by a constant expression
constexpr int n = factorial(13) ;
              ^   ~~~~~~~~~~~~~
note: value 6227020800 is outside the range of representable values of type 'int'
return ( n == 0 ? 1 : n*factorial(n-1) ) ;
                       ^

这也是你举例的原因:

Factorial<13> f2;

失败是因为需要一个常量表达式并且gcc 4.9给出了一个有用的错误:

error: overflow in constant expression [-fpermissive]
 static const int value = N * Factorial<N-1>::value;
                  ^

尽管 gcc 的旧版本给您带来了您所看到的无用的错误。

对于问题 2，编译器有一个模板递归限制，通常可以对其进行配置，但最终您会耗尽系统资源。例如，gcc 的标志将是 -ftemplate-depth=n :

Set the maximum instantiation depth for template classes to n. A limit on the template instantiation depth is needed to detect endless recursions during template class instantiation. ANSI/ISO C++ conforming programs must not rely on a maximum depth greater than 17 (changed to 1024 in C++11). The default value is 900, as the compiler can run out of stack space before hitting 1024 in some situations.

在您的特定问题中，您需要担心有符号整数溢出，这是在您遇到系统资源问题之前未定义的行为。