C ++ 11中的recursionlambda函数
我是C ++ 11的新手。 我正在写下面的recursionlambda函数，但它不能编译。
sum.cpp
#include <iostream> #include <functional> auto term = [](int a)->int { return a*a; }; auto next = [](int a)->int { return ++a; }; auto sum = [term,next,&sum](int a, int b)mutable ->int { if(a>b) return 0; else return term(a) + sum(next(a),b); }; int main(){ std::cout<<sum(1,10)<<std::endl; return 0; } 编译错误：
vimal @ linux-718q：〜/ Study / 09C ++ / c ++ 0x / lambda> g ++ -std = c ++ 0x sum.cpp
sum.cpp：在lambda函数中：sum.cpp：18：36：error：' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum '不能使用作为一个function
gcc版本
gcc版本4.5.0 20091231（实验）（GCC）
但是，如果我改变sum()的声明如下，它的工作原理：
std::function<int(int,int)> sum = [term,next,&sum](int a, int b)->int { if(a>b) return 0; else return term(a) + sum(next(a),b); };
有人可以抛出这个光？
想想汽车版本和完全指定的版本之间的区别。 auto关键字从它的初始化types推断出它的types，但是你初始化它的types需要知道它的types是什么（在这种情况下，lambdaclosures需要知道它捕获的types）。 鸡蛋和鸡蛋的问题。
另一方面，一个完全指定的函数对象的types不需要“知道”分配给它的任何东西，所以lambda的闭包同样可以完全了解它捕获的types。
考虑一下你的代码的细微修改，这可能会更有意义：
std::function<int(int,int)> sum; sum = [term,next,&sum](int a, int b)->int { if(a>b) return 0; else return term(a) + sum(next(a),b); };
显然，这不适用于汽车 。 recursionlambda函数工作得非常好（至less他们在MSVC中，我有他们的经验），这只是他们不是真的与types推断兼容。
我有另一个解决scheme，但只与无状态lambdas工作：
void f() { static int (*self)(int) = [](int i)->int { return i>0 ? self(i-1)*i : 1; }; std::cout<<self(10); }
这里的诀窍是lambda可以访问静态variables，并且可以将无状态variables转换为函数指针。
你可以使用它与标准的lambdaexpression式：
void g() { int sum; auto rec = [&sum](int i) -> int { static int (*inner)(int&, int) = [](int& _sum, int i)->int { _sum += i; return i>0 ? inner(_sum, i-1)*i : 1; }; return inner(sum, i); }; }
它在GCC 4.7中的工作
诀窍是将lambda实现作为参数提供给自己，而不是捕获。
const auto sum = [term,next](int a, int b) { auto sum_impl=[term,next](int a,int b,auto& sum_ref) mutable { if(a>b) return 0; else return term(a) + sum_ref(next(a),b,sum_ref); }; return sum_impl(a,b,sum_impl); };
计算机科学中的所有问题都可以通过另一个间接的层面来解决 。 我首先在http://pedromelendez.com/recursive-lambdas-in-c14/上find了这个简单的技巧;
它确实需要C ++ 14，而问题是在C ++ 11上，但也许最有趣的。
你可以recursion地调用一个lambda函数。 你唯一需要做的就是通过一个函数包装器来引用它，以便编译器知道它是返回值和参数types（你不能捕获一个variables – lambda本身 – 尚未定义） 。
function<int (int)> f; f = [&f](int x) { if (x == 0) return 0; return x + f(x-1); }; printf("%d\n", f(10));
要非常小心，不要超出包装f的范围。
使用C ++ 14，现在很容易做出一个有效的recursionlambda，而不用额外的开销std::function ，只需要几行代码（从原始的一个小的编辑，以防止用户采取意外的副本）：
template <class F> struct y_combinator { F f; // the lambda will be stored here // a forwarding operator(): template <class... Args> decltype(auto) operator()(Args&&... args) const { // we pass ourselves to f, then the arguments. // [edit: Barry] pass in std::ref(*this) instead of *this return f(std::ref(*this), std::forward<Args>(args)...); } }; // helper function that deduces the type of the lambda: template <class F> y_combinator<std::decay_t<F>> make_y_combinator(F&& f) { return {std::forward<F>(f)}; }
与您原来的sum尝试成为：
auto sum = make_y_combinator([term,next](auto sum, int a, int b) { if (a>b) { return 0; } else { return term(a) + sum(next(a),b); } });
我使用std::function<>捕获方法运行了一个比较recursion函数和recursionlambda函数的基准testing。 在铿锵4.1版上启用完全优化后，lambda版本运行速度明显变慢。
#include <iostream> #include <functional> #include <chrono> uint64_t sum1(int n) { return (n <= 1) ? 1 : n + sum1(n - 1); } std::function<uint64_t(int)> sum2 = [&] (int n) { return (n <= 1) ? 1 : n + sum2(n - 1); }; auto const ITERATIONS = 10000; auto const DEPTH = 100000; template <class Func, class Input> void benchmark(Func&& func, Input&& input) { auto t1 = std::chrono::high_resolution_clock::now(); for (auto i = 0; i != ITERATIONS; ++i) { func(input); } auto t2 = std::chrono::high_resolution_clock::now(); auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(t2-t1).count(); std::cout << "Duration: " << duration << std::endl; } int main() { benchmark(sum1, DEPTH); benchmark(sum2, DEPTH); }
产生结果：
Duration: 0 // regular function Duration: 4027 // lambda function
（注意：我也用一个版本来确认cin的input，以免编译时间评估）
Clang也会产生一个编译器警告：
main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]
这是预期的，安全的，但应该注意。
在我们的工具带中有一个解决scheme是非常好的，但是我认为，如果性能要与当前的方法相媲美，那么语言将需要更好的方法来处理这种情况。
注意：
正如一位评论者指出的，似乎VC ++的最新版本已经find了一种方法来优化这个到相同的性能点。 毕竟，我们不需要更好的方法来处理这个问题（语法糖除外）。
另外，正如其他SOpost最近几周所概述的， std::function<>本身的性能本身可能是直接调用函数的原因，至less当lambda捕获太大而不适合某些库优化时空间std::function用于小函子（我猜有点像各种短string优化？）。
要使用lambdarecursion而不使用外部类和函数（如std::function或者定点组合器），可以使用C ++ 14（ 现场示例 ）中的以下构造：
#include <utility> #include <list> #include <memory> #include <iostream> int main() { struct tree { int payload; std::list< tree > children = {}; // std::list of incomplete type is allowed }; std::size_t indent = 0; // indication of result type here is essential const auto print = [&] (const auto & self, const tree & node) -> void { std::cout << std::string(indent, ' ') << node.payload << '\n'; ++indent; for (const tree & t : node.children) { self(self, t); } --indent; }; print(print, {1, {{2, {{8}}}, {3, {{5, {{7}}}, {6}}}, {4}}}); }
打印：
1 2 8 3 5 7 6 4
请注意，lambda的结果types应明确指定。
这是一个稍微简单的fixpoint操作符的实现，它使得它更清楚地发生了什么。
#include <iostream> #include <functional> using namespace std; template<typename T, typename... Args> struct fixpoint { typedef function<T(Args...)> effective_type; typedef function<T(const effective_type&, Args...)> function_type; function_type f_nonr; T operator()(Args... args) const { return f_nonr(*this, args...); } fixpoint(const function_type& p_f) : f_nonr(p_f) { } }; int main() { auto fib_nonr = [](const function<int(int)>& f, int n) -> int { return n < 2 ? n : f(n-1) + f(n-2); }; auto fib = fixpoint<int,int>(fib_nonr); for (int i = 0; i < 6; ++i) { cout << fib(i) << '\n'; } }
你正试图捕获一个variables（总和），你正在定义中。 那不好。
我不认为真正的自recursionC ++ 0x lambdas是可能的。 不过，你应该可以捕捉到其他的lambdaexpression式。
这是OP的最终答案。 无论如何，Visual Studio 2010不支持捕获全局variables。 而且您不需要捕获它们，因为全局variables可以通过define全局访问。 下面的答案使用局部variables。
#include <functional> #include <iostream> template<typename T> struct t2t { typedef T t; }; template<typename R, typename V1, typename V2> struct fixpoint { typedef std::function<R (V1, V2)> func_t; typedef std::function<func_t (func_t)> tfunc_t; typedef std::function<func_t (tfunc_t)> yfunc_t; class loopfunc_t { public: func_t operator()(loopfunc_t v)const { return func(v); } template<typename L> loopfunc_t(const L &l):func(l){} typedef V1 Parameter1_t; typedef V2 Parameter2_t; private: std::function<func_t (loopfunc_t)> func; }; static yfunc_t fix; }; template<typename R, typename V1, typename V2> typename fixpoint<R, V1, V2>::yfunc_t fixpoint<R, V1, V2>::fix = [](tfunc_t f) -> func_t { return [f](fixpoint<R, V1, V2>::loopfunc_t x){ return f(x(x)); } ([f](fixpoint<R, V1, V2>::loopfunc_t x) -> fixpoint<R, V1, V2>::func_t{ auto &ff = f; return [ff, x](t2t<decltype(x)>::t::Parameter1_t v1, t2t<decltype(x)>::t::Parameter1_t v2){ return ff(x(x))(v1, v2); }; }); }; int _tmain(int argc, _TCHAR* argv[]) { auto term = [](int a)->int { return a*a; }; auto next = [](int a)->int { return ++a; }; auto sum = fixpoint<int, int, int>::fix( [term,next](std::function<int (int, int)> sum1) -> std::function<int (int, int)>{ auto &term1 = term; auto &next1 = next; return [term1, next1, sum1](int a, int b)mutable ->int { if(a>b) return 0; else return term1(a) + sum1(next1(a),b); }; }); std::cout<<sum(1,10)<<std::endl; //385 return 0; }
你需要一个定点组合器。 看到这个
或者看下面的代码：
//As decltype(variable)::member_name is invalid currently, //the following template is a workaround. //Usage: t2t<decltype(variable)>::t::member_name template<typename T> struct t2t { typedef T t; }; template<typename R, typename V> struct fixpoint { typedef std::function<R (V)> func_t; typedef std::function<func_t (func_t)> tfunc_t; typedef std::function<func_t (tfunc_t)> yfunc_t; class loopfunc_t { public: func_t operator()(loopfunc_t v)const { return func(v); } template<typename L> loopfunc_t(const L &l):func(l){} typedef V Parameter_t; private: std::function<func_t (loopfunc_t)> func; }; static yfunc_t fix; }; template<typename R, typename V> typename fixpoint<R, V>::yfunc_t fixpoint<R, V>::fix = [](fixpoint<R, V>::tfunc_t f) -> fixpoint<R, V>::func_t { fixpoint<R, V>::loopfunc_t l = [f](fixpoint<R, V>::loopfunc_t x) -> fixpoint<R, V>::func_t{ //f cannot be captured since it is not a local variable //of this scope. We need a new reference to it. auto &ff = f; //We need struct t2t because template parameter //V is not accessable in this level. return [ff, x](t2t<decltype(x)>::t::Parameter_t v){ return ff(x(x))(v); }; }; return l(l); }; int _tmain(int argc, _TCHAR* argv[]) { int v = 0; std::function<int (int)> fac = fixpoint<int, int>::fix([](std::function<int (int)> f) -> std::function<int (int)>{ return [f](int i) -> int{ if(i==0) return 1; else return i * f(i-1); }; }); int i = fac(10); std::cout << i; //3628800 return 0; }
这个答案不如扬克斯的答案，但仍然是这样的：
using dp_type = void (*)(); using fp_type = void (*)(dp_type, unsigned, unsigned); fp_type fp = [](dp_type dp, unsigned const a, unsigned const b) { ::std::cout << a << ::std::endl; return reinterpret_cast<fp_type>(dp)(dp, b, a + b); }; fp(reinterpret_cast<dp_type>(fp), 0, 1);
