元整数平方根中的无限递归 [英] Infinite Recursion in Meta Integer Square Root
问题描述
美好的一天,
我的一个朋友正在询问有关将整数平方根函数转换为元函数的问题.这是原始功能:
A friend of mine is asking about transforming an integer square root function into a meta-function. Here is the original function:
unsigned isqrt(unsigned value)
{
unsigned sq = 1, dlt = 3;
while(sq<=value)
{
sq += dlt;
dlt += 2;
}
return (dlt>>1) - 1;
}
我使用constexpr
编写了元版本,但他说由于某些原因他不能使用该新功能:
I wrote a meta version using constexpr
, but he said he can't use the new feature for some reason:
constexpr std::size_t isqrt_impl
(std::size_t sq, std::size_t dlt, std::size_t value){
return sq <= value ?
isqrt_impl(sq+dlt, dlt+2, value) : (dlt >> 1) - 1;
}
constexpr std::size_t isqrt(std::size_t value){
return isqrt_impl(1, 3, value);
}
因此,我认为将其转换为可自我递归调用的模板结构并不难:
So I thought it shouldn't be that hard to transform that into template struct that calls it self recursively:
template <std::size_t value, std::size_t sq, std::size_t dlt>
struct isqrt_impl{
static const std::size_t square_root =
sq <= value ?
isqrt_impl<value, sq+dlt, dlt+2>::square_root :
(dlt >> 1) - 1;
};
template <std::size_t value>
struct isqrt{
static const std::size_t square_root =
isqrt_impl<value, 1, 3>::square_root;
};
不幸的是,这导致了无限递归(在GCC 4.6.1上),我无法弄清楚代码出了什么问题.这是错误:
Unfortunately, this is causing infinite recursion(on GCC 4.6.1) and I am unable to figure out what is wrong with the code. Here is the error:
C:\test>g++ -Wall test.cpp
test.cpp:6:119: error: template instantiation depth exceeds maximum of 1024 (use
-ftemplate-depth= to increase the maximum) instantiating 'struct isqrt_impl<25u
, 1048576u, 2049u>'
test.cpp:6:119: recursively instantiated from 'const size_t isqrt_impl<25u, 4u
, 5u>::square_root'
test.cpp:6:119: instantiated from 'const size_t isqrt_impl<25u, 1u, 3u>::squar
e_root'
test.cpp:11:69: instantiated from 'const size_t isqrt<25u>::square_root'
test.cpp:15:29: instantiated from here
test.cpp:6:119: error: incomplete type 'isqrt_impl<25u, 1048576u, 2049u>' used i
n nested name specifier
谢谢,
推荐答案
默认情况下,模板评估不是惰性的.
Template evaluation isn't lazy by default.
static const std::size_t square_root =
sq <= value ?
isqrt_impl<value, sq+dlt, dlt+2>::square_root :
(dlt >> 1) - 1;
无论条件如何,总是会实例化模板.您需要boost::mpl::eval_if
或类似的东西才能使该解决方案生效.
will always instantiate the template, no matter what the condition. You need boost::mpl::eval_if
or something equivalent to get that solution to work.
或者,您可以有一个基本情况下的局部模板专门化,如果满足条件,则可以停止递归,就像在K-ballos答案中一样.
Alternatively you can have a base case partial template specialization that stops the recursion if the condition is met, like in K-ballos answer.
实际上,与部分专业化相比,我更喜欢使用某种形式的惰性求值的代码,因为我觉得它更易于理解,并且可以降低模板所带来的噪音.
I'd actually prefer code that uses some form of lazy evaluation over partial specialization because I feel it is easier to comprehend and keeps the noise that comes with templates lower.
这篇关于元整数平方根中的无限递归的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!