模板工作作为递归函数 [英] template work as recursive function
问题描述
我发现这个代码,想知道我是否应该在我的真正的项目中真的实现这样的东西。
令人困惑的是
-
-
如果N真的是一个非常大的数字,那么我不应该花费
编译时间。 ?在源代码中是否有任何文件
大小限制?
,不实现?
#include< iostream>
using namespace std;
template< int N>
class Factorial {
public:
static const int value = N * Factorial< N-1> :: value;
};
模板<>
class Factorial< 1> {
public:
static const int value = 1;
};
int main(){
Factorial< 5L> F;
cout<< 5!=<< f.value<< endl
}
outPut:
5! = 120
稍微修改一下问题,因为我在玩代码,发现因子<12> f1; // works
Factorial< 13> f 2; //不工作
错误:
未定义引用`Factorial< 13> :: value'
是否可以上升到
12
深度不再?解决方案
1
的答案是它取决于模板元编程本质上涉及在编译时进行计算之间的权衡,其益处是不必在运行时进行。一般来说,这种技术可能导致难以阅读和维护代码。因此,答案最终取决于您在更慢的编译器时间以及可能更难维护代码时需要更快的运行时性能。
文章想要速度?使用constexpr元编程! 解释了如何在现代C ++中使用 constexpr函数多次替换模板元编程。这通常导致代码更可读,也许更快。将此模板元编程方法与constexpr示例进行比较:
constexpr int factorial(int n)
{
return(n == 0?1:n * factorial(n-1));
}
这更简洁,可读,并且会被执行在编译时为常量表达式的参数,虽然作为链接的答案解释标准实际上并不说它必须是但是
这也是值得注意的,因为结果会很快溢出
value
constexpr 的优点是,未定义的行为不是有效的常量表达式,至少当前的实现的gcc
和clang
会将 constexpr 内的未定义行为转换为错误。例如:constexpr int n = factorial
会产生以下错误:
错误:constexpr变量'n'必须由常量表达式初始化
constexpr int n = factorial(13);
^ ~~~~~~~~~~~~~~
注意:值6227020800在类型int的可表示值的范围之外
return(n == 0?1 :n * factorial(n-1));
^
这也是为什么你的例子:
因子< 13> f 2;
失败,因为需要一个常量表达式 gcc 4.9 提供了一个有用的错误:
错误:在常量表达式中溢出[-fpermissive] $ b static const int value = N * Factorial< N-1> :: value;虽然较旧版本的
gcc $ c $>,但
^
对于问题
2
,编译器有一个模板递归限制,通常可以配置,但最终你会耗尽系统资源。例如gcc
的标志为 - ftemplate-depth = n :
将模板类的最大实例化深度设置为n。需要在模板实例化深度上限制
以在模板类实例化期间检测无止境的
递归。 ANSI / ISO C ++
合格程序不能依赖于最大深度大于17
(在C ++ 11中更改为1024)。默认值为900,因为在某些情况下,编译器
可能会超出堆栈空间,在达到1024之前。
在你的具体问题,你将需要担心有符号整数溢出,这是未定义的行为,你有系统资源问题之前。
I found this code, and wondering whether I should really implement something like this in my real project or not.
And things confusing me are
It will take more compile time, but I should not bother about compile time at the cost of run time.
And what if N gets really a very big number then? Is there any file size limit in source code?
or its something good to know, not to implement?
#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; }
outPut:
5! = 120
slight modification in question, as i was playing with the code, found that
Factorial<12> f1; // works Factorial<13> f2; // doesn't work
error:
undefined reference to `Factorial<13>::value'
is it like, can go up-to
12
depth not further?解决方案The answer to
1
is that it depends, template meta programming essentially involves a trade-off between doing the calculation at compile-time with the benefit that it does not have to be done at run-time. In general this technique can lead to hard to read and maintain code. So the answer ultimately depends on your need for faster run-time performance over slower compiler times and possibly harder to maintain code.The article Want speed? Use constexpr meta-programming! explains how in modern C++ you can use constexpr functions many times as a replacement for template meta programming. This in general leads to code that is more readable and perhaps faster. Compare this template meta programming method to the constexpr example:
constexpr int factorial( int n ) { return ( n == 0 ? 1 : n*factorial(n-1) ) ; }
which is more concise, readable and will be executed at compile time for arguments that are constant expressions although as the linked answer explains the standard does not actually say it must be but in practice current implementations definitely do.
It is also worth noting that since the result will quickly overflow
value
that another advantage of constexpr is that undefined behavior is not a valid constant expression and at least the current implementations ofgcc
andclang
will turn undefined behavior within a constexpr into an error for most cases. For example:constexpr int n = factorial(13) ;
for me generates the following error:
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) ) ; ^
This is also why you example:
Factorial<13> f2;
fails because a constant expression is required and
gcc 4.9
gives a useful error:error: overflow in constant expression [-fpermissive] static const int value = N * Factorial<N-1>::value; ^
although older versions of
gcc
give you the less than helpful error you are seeing.For question
2
, compilers have a template recursion limit, which can usually be configured but eventually you will run out of system resources. For example the flag forgcc
would be -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.
As in your specific problem you will need to worry about signed integer overflow, which is undefined behavior before you have system resource issues.
这篇关于模板工作作为递归函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!