在C++ 11中编写递归lambda函数有一个经常重复的"技巧",如下所示:
std::function<int(int)> factorial;
factorial = [&factorial](int n)
{ return n < 2 ? 1 : n * factorial(n - 1); };
assert( factorial(5) == 120 );
(例如,C++ 0x中的递归lambda函数.)
这种技术有两个直接的缺点:std::function<Sig>对象的目标(通过引用捕获)与非常特定的std::function<Sig>对象(此处factorial)相关联.这意味着通常无法从函数返回生成的仿函数,否则引用将保持悬空状态.
另一个(尽管不那么直接)问题是使用std::function通常会阻止编译器优化,这是在其实现中需要类型擦除的副作用.这不是假设,可以很容易地进行测试.
在假设的情况下,递归lambda表达式真的很方便,有没有办法解决这些问题？
Luc*_*ton 61
问题的关键在于,在C++ lambda表达式中,隐式 this参数将始终引用表达式的封闭上下文的对象(如果存在的话),而不是lambda表达式产生的仿函数对象.
借用匿名递归(有时也称为"开放递归")的叶子,我们可以使用C++ 14的通用lambda表达式重新引入一个显式参数来引用我们想要的递归仿函数:
auto f = [](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(/* hold on */); };
呼叫者现在有一个新的负担,即调用表格,例如f(f, 5).由于我们的lambda表达式是自引用的,它实际上是一个自己的调用者,因此我们应该有return n < 2 ? 1 : n * self(self, n - 1);.
由于在第一个位置显式传递仿函数对象本身的模式是可预测的,我们可以重构这个丑陋的疣:
template<typename Functor>
struct fix_type {
Functor functor;
template<typename... Args>
decltype(auto) operator()(Args&&... args) const&
{ return functor(functor, std::forward<Args>(args)...); }
/* other cv- and ref-qualified overloads of operator() omitted for brevity */
};
template<typename Functor>
fix_type<typename std::decay<Functor>::type> fix(Functor&& functor)
{ return { std::forward<Functor>(functor) }; }
这允许人们写:
auto factorial = fix([](auto&& self, int n) -> int
{ return n < 2 ? 1 : n * self(self, n - 1); });
assert( factorial(5) == 120 );
我们成功了吗？由于fix_type<F>对象包含它自己的函子,它为每次调用传递给它,因此不存在悬空引用的风险.因此,我们的factorial对象可以真正无限制地复制,移入,移出和移出函数.
除了......虽然"外部"调用者可以随时调用表单factorial(5),但事实证明,在我们的lambda表达式中,递归调用看起来仍然如此self(self, /* actual interesting args */).我们可以通过更改fix_type为不传递functor给自己来改进,而是通过传递*this来改进.也就是说,我们传入fix_type负责在第一个位置传递正确的"隐式显式"参数的对象:return functor(*this, std::forward<Args>(args)...);.然后递归变为n * self(n - 1)应有的.
最后,这是一个所生成的代码main,使用return factorial(5);代替断言(对于任一风味fix_type):
00000000004005e0 <main>:
4005e0: b8 78 00 00 00 mov eax,0x78
4005e5: c3 ret
4005e6: 66 90 xchg ax,ax
编译器能够优化所有内容,就像使用run-off-the-mill递归函数一样.
精明的读者可能已经注意到一个奇怪的细节.在从非泛型变为泛型lambda的过程中,我添加了一个显式返回类型(即-> int).怎么会？
这与要推导的返回类型是条件表达式的类型这一事实有关,该类型取决于调用self,推断出哪种类型.快速阅读正常函数的返回类型推导会建议重写lambda表达式如下:
[](auto&& self, int n)
{
if(n < 2) return 1; // return type is deduced here
else return n * self(/* args */); // this has no impact
}
事实上,GCC将只接受第一种形式的代码fix_type(通过的代码functor).我无法确定抱怨另一种形式(*this通过哪里)是否正确.我留给读者选择做出的权衡:减少类型推导,或者不那么丑陋的递归调用(当然也完全可以访问任何一种风格).
Mar*_*utz 12
它不是lambda表达式,但几乎没有代码,适用于C++ 98,并且可以递归:
struct {
int operator()(int n) const {
return n < 2 ? 1 : n * (*this)(n-1);
}
} fact;
return fact(5);
根据[class.local]/1它,它可以访问封闭函数可以访问的所有名称,这对于成员函数中的私有名称很重要.
当然,不是lambda,如果要捕获函数对象外的状态,则必须编写构造函数.