在 C++11 中编写递归 lambda 函数有一个经常重复的“技巧”,如下所示:
std::function<int(int)> factorial;
factorial = [&factorial](int n)
{ return n < 2 ? 1 : n * factorial(n - 1); };
assert( factorial(5) == 120 );
(例如 Recursive lambda functions in C++0x 。)
这种技术有两个直接的缺点:std::function<Sig>
的目标对象(通过引用捕获)绑定(bind)到一个非常特殊的 std::function<Sig>
对象(此处为 factorial
)。这意味着生成的仿函数通常不能从函数返回,否则引用将悬空。
另一个(虽然不那么直接)的问题是使用 std::function
通常会阻止编译器优化,这是其实现中需要类型删除的副作用。这不是假设,可以很容易地进行测试。
在递归 lambda 表达式真的很方便的假设情况下,有没有办法解决这些问题?
最佳答案
问题的症结在于,在 C++ lambda 表达式中,隐式 this
参数将始终引用表达式的封闭上下文的对象(如果存在),而不是由 lambda 表达式产生的仿函数对象。
从 anonymous recursion 借一片叶子(有时也称为“开放递归”),我们可以使用 C++14 的通用 lambda 表达式重新引入 explicit 参数来引用我们可能的递归仿函数:
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
编译器能够优化所有内容,就像使用普通的递归函数一样。
费用是多少?
精明的读者可能已经注意到一个奇怪的细节。在从非泛型到泛型 lambda 的转变中,我添加了一个显式返回类型(即 -> int
)。怎么会?
这与要推导的返回类型是条件表达式的类型有关,该类型取决于对 self
的调用。 , 推断出哪种类型。快速阅读Return type deduction for normal functions建议按如下方式重写 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
)。我留给读者选择要做出的权衡:更少的类型推导,或者更少丑陋的递归调用(当然也完全有可能访问任何一种风格)。
GCC 4.9 示例
关于c++ - C++14 中的递归 lambda 函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18085331/