这个求平方根的模板元程序有什么问题？

Question

我尝试使用 C++ 中的模板元编程编写 O(N) 解决方案以求出完美平方数的平方根。算法：

algorithm sqrt(N, start):
     if(start*start == N)
            return start
     else
            return sqrt(N, start+1)

即：

template<int value, int N>
struct sqrt
{
    enum { val = ((value*value == N) ? value : (sqrt<(value+1), N>::val)) };
};

并在 main() 中实例化 sqrt<1, 4>。

我运行遇到“模板实例化深度超过最大值 900”错误，即使它必须停止尝试并在值为 2 时实例化？

我是否遗漏了一些特定于模板元编程的内容？无论条件如何，它都会执行三元运算符的两边吗？请帮我解决这个问题？

Answer 1

sqrt<X,N> 实例化 sqrt<X+1,N> 实例化 sqrt<X+2,N> 等等。它永远不会停止。

两个分支都由编译器计算，即使只采用其中一个。编译器不够聪明，无法在某些时候看到条件为假，然后 sqrt<value+1,N> 不需要实例化。你必须更明确地告诉它。（实际上更正确：编译器确实需要知道 : 的两边以确定它们的公共类型，因为这就是条件运算符的类型）。

从 C++17 开始，您可以使用 constexpr if 来丢弃 false-branch：

#include <iostream>


template<int value, int N>
int sqrt(){
    if constexpr (value*value == N) { 
        return value;
    } else {
        return sqrt<value+1,N>();
    }
    
};

int main()
{
    std::cout << sqrt<1,4>();
}

在 C++17 之前，您可以使用模板特化作为递归的停止条件：

#include <iostream>


template<int value, int N>
struct sqrt
{
    enum { val = ((value*value == N) ? value : (sqrt<(value+1), N>::val)) };
};

template <int value>
struct sqrt<value,value*value> {
    enum { val = value };
};


int main()
{
    std::cout << sqrt<1,4>::val;
}

但是，当 N 不是平方数时，两者都会失败。您应该将条件更改为 value*value >= N 以确保递归始终停止（并另外检查是否 N == value*value）。

此外，我建议交换参数的顺序，这样您就可以使用默认的 1 代替 value。 enum 这个东西看起来也有点过时了。我不记得要克服什么限制。无论如何，您可以简单地使用 static const val = ... 代替。

这个求平方根的模板元程序有什么问题？

what is wrong with this template metaprogram to find square root?

c++

template-meta-programming