C++ 11 constexpr函数编译器错误与三元条件运算符(？:)

Question

这段代码有什么问题？

#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

Answer 1

Constexpr不会那样工作.

简而言之,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 <= 1是的,所以让我把3它拿回来.一直到调用堆栈."

所以它提出了答案3.它不会进入无限递归,因为它正在充分了解值和语义来评估函数,而不仅仅是愚蠢地构建AST.

我希望有所帮助.

Answer 2

正如其他人已经说过的那样:编译器不会评估条件表达式,例如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,则启用upper方法,因为此函数头有效.对于其他一切,即N >= 2或者!(N <= 1),我们需要递归,这是由第二种方法完成的.