4

这段代码有什么问题？

#include <iostream>

template<unsigned int N, unsigned int P=0>
constexpr unsigned int Log2() {
    return (N <= 1) ? P : Log2<N/2,P+1>();
}

int main()
{
    std::cout << "Log2(8) = " << Log2<8>() << std::endl;
    return 0;
}

使用 编译时gcc version 4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)，出现以下错误：

log2.cpp: In function ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1023u]’:
log2.cpp:5:38: error: template instantiation depth exceeds maximum of 1024 (use -ftemplate-depth= to increase the maximum) instantiating ‘constexpr unsigned int Log2() [with unsigned int N = 0u, unsigned int P = 1024u]’
log2.cpp:5:38:   recursively instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 4u, unsigned int P = 1u]’
log2.cpp:5:38:   instantiated from ‘constexpr unsigned int Log2() [with unsigned int N = 8u, unsigned int P = 0u]’
log2.cpp:10:37:   instantiated from here
4

2 回答 2

18

Consexpr 不是那样工作的。

简而言之，constexpr 函数也必须可用作运行时函数。想象一下，您将 constexpr 从函数中取出。然后想想为什么它不可能工作。

原因是编译器必须完全实例化函数体；它不能根据?:不实例化一侧的条件来决定。所以它总是必须实例化递归调用，导致无限递归。

无论如何，您使用 constexpr 是错误的。当 constexpr 打算替换它时，您正在使用旧的模板元编程计算技术（将东西作为模板参数传递）。只需使用普通参数即可。

constexpr unsigned Log2(unsigned n, unsigned p = 0) {
    return (n <= 1) ? p : Log2(n / 2, p + 1);
}

std::cout << "Log2(8) = " << Log2(8) << std::endl;

编辑：我将尝试详细说明这是如何工作的。

当编译器遇到您的代码时，它会解析模板函数并将其存储为模板形式。（编译器之间的工作方式不同。）到目前为止，一切都很好。

接下来，在 中main，编译器看到调用Log2<8>()。它看到它必须实例化模板，所以它继续做这件事：它实例化Log2<8, 0>. 函数模板的主体是这样的：

return (N <= 1) ? P : Log2<N/2,P+1>();

好的，编译器看到了这一点，但它不会尝试评估它。为什么会呢？它当前正在实例化模板，而不是计算值。它只是替换提供的值：

return (8 <= 1) ? 0 : Log2<8/2,0+1>();

呵呵，这里还有一个模板实例化。它在条件表达式中，或者左侧可以知道并不重要。模板实例化必须完成。所以它继续计算新实例化的值，然后实例化Log2<4, 1>：

return (4 <= 1) ? 1 : Log2<4/2,1+1>();

游戏又开始了。那里有一个模板实例化，它是Log2<2, 2>：

return (2 <= 1) ? 2 : Log2<2/2,2+1>();

再次，Log2<1,3>()：

return (1 <= 1) ? 3 : Log2<1/2,3+1>();

我有没有提到编译器不关心这些东西的语义？它只是另一个要实例化的模板Log2<0,4>：

return (0 <= 1) ? 4 : Log2<0/2,4+1>();

然后Log2<0,5>：

return (0 <= 1) ? 5 : Log2<0/2,5+1>();

等等等等。在某些时候，编译器意识到它永远不会停止并放弃。但它绝不会说，“等等，那个三元运算符的条件是假的，我不需要实例化右手边。” 那是因为 C++ 标准不允许这样做。函数体必须完全实例化。

现在看看我的解决方案。没有模板。只有一个功能。编译器看到它并说：“嘿，这是一个函数。太棒了，让我在这里调用那个函数。” 然后在某个时候（可能是立即，也可能是很久以后，取决于编译器），它可能（但在这种情况下不是被迫）说，“嘿，等等，这个函数是constexpr，我知道参数值，让我评估一下。” 现在它继续并评估Log2(8, 0). 记住身体：

return (n <= 1) ? p : Log2(n / 2, p + 1);

“OK”，编译器说，“我只是想知道这个函数返回什么。让我们看看，8 <= 1是假的，所以看右边。Log2(4, 1)，嗯？让我看看。好吧，4 <= 1也是假的，所以它必须" _ Log2(2, 2)_ 2 <= 1_ _ _Log2(1, 3)1 <= 13

所以它得出了答案 3。它不会进行无休止的递归，因为它是在对值和语义有充分了解的情况下评估函数，而不仅仅是愚蠢地构建 AST。

我希望这会有所帮助。

于 2013-08-14T12:23:11.583 回答
5

正如其他人已经说过的那样：编译器不会评估条件表达式，例如if/else或三元运算符?:。但是，仍然有一种方法可以使这个条件表达式编译时：

#include <cstddef>     // size_t is shorter than unsigned int, it's a matter of taste in this case
#include <iostream>    // to show our results
#include <type_traits> // needed for the mighty std::enable_if

template<size_t N, size_t P = 0>
constexpr typename std::enable_if<(N <= 1), size_t>::type Log2()
{
   return P;
}

template<size_t N, size_t P = 0>
constexpr typename std::enable_if<!(N <= 1), size_t>::type Log2()
{
   return Log2<N / 2, P + 1>();
}

int main()
{
   std::cout << Log2<1>() << "\n";
   std::cout << Log2<2>() << "\n";
   std::cout << Log2<4>() << "\n";
   std::cout << Log2<8>() << "\n";
   std::cout << Log2<16>() << "\n";
}

这样做是相当明显的：如果N <= 1，则应该评估第一个分支，因此Log2<0, P>()并且Log2<1, P>()应该评估为P。如果N <= 1，则启用上层方法，因为此函数头有效。对于其他一切，即N >= 2or !(N <= 1)，我们需要递归，这是通过第二种方法完成的。

于 2013-08-14T13:25:03.920 回答