0

我想我理解如何在 C++ 中懒惰地评估模板，例如递归替换和扩展的最终简化。这通常会限制可用的递归深度。我想知道是否使用 C++11 中的新功能（例如可变参数模板或模板包）或使用一些 Boost 可以强制执行严格的模板评估。或者这在 C++ 中原则上是不可能的？

例如，考虑一个对所有整数值求和的模板0..n：

template <int n>
struct sumAll { enum { value = n + sumAll<n-1>::value }; };

template <>
struct sumAll<0> { enum { value = 0 }; };

#include <iostream>
int main() { std::cout << sumAll<10000>::value << std::endl; }

这里sumAll<10>::value将扩展为

sumAll<10>::value = 10 + sumAll<9>::value
                  = 10 + 9 + sumAll<8>::value
                  = 10 + 9 + 8 + sumAll<7>::value
                  = ...
                  = 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

并且只有在模板完全展开后才会执行最终的求和。如果最终展开变得太长（例如在具有许多项的复杂级数展开中），编译器最终将耗尽存储附加项的空间。

我的问题本质上是是否有一种方法可以更早地进行简化（如上面的求和）。

4

2 回答 2

1

您自己决定递归深度。就像普通递归会导致堆栈溢出一样，模板递归也可以。但这通常可以通过更好的递归算法来解决。琐碎：

template <int n>
struct sumAll { enum { value = n + n-1 + sumAll<n-2>::value }; };

template <>
struct sumAll<1> { enum { value = 0 }; };

template <>
struct sumAll<0> { enum { value = 0 }; };

更智能：

template <int n>
struct sumAll { enum { value = (n*n+2)/2; };

当然，你可能会抱怨后者太傻了，实际例子更复杂。但这不是问题的全部吗？编译器无法神奇地为您消除这种复杂性。

于 2012-10-12T08:39:59.013 回答
1

C++ 模板是图灵完备的，这意味着您可以在编译时使用它们来评估每个可计算函数。然后由停止定理得出

  1. 通常，您无法提前计算编译 C++ 程序所需的内存量。（即，没有可计算的函数将每个 C++ 程序映射到其编译的内存绑定）
  2. 通常，您无法决定编译器是否会完成模板的实例化，或者会永远继续下去。

因此，虽然在某些情况下您可能能够调整编译器以使用更少的内存，但您无法解决它有时会耗尽内存的一般问题。

于 2012-10-12T11:25:15.270 回答