c++ 11中的递归lambda函数

我是c++ 11的新手。我正在写下面的递归lambda函数，但它不能编译。

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:错误:' ((<lambda(int, int)>*)this)-><lambda(int, int)>::sum '不能用作函数

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);
};

有人能解释一下吗?

当前回答

我使用std::function<>捕获方法运行了一个基准测试，比较递归函数和递归lambda函数。在clang版本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获取输入的版本，以消除编译时计算)

Clang还会产生一个编译器警告:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

这是意料之中的，也是安全的，但应该注意。

在我们的工具中有一个解决方案是很好的，但我认为如果要与当前的方法相比，该语言需要更好的方法来处理这种情况。

注意:

正如一位评论者指出的那样，最新版本的vc++似乎已经找到了一种方法来优化这一点，以达到同等的性能。也许我们不需要更好的方法来处理这个问题(除了语法糖)。

另外，正如最近几周其他一些SO帖子所概述的那样，std::function<>本身的性能可能是导致直接调用function速度变慢的原因，至少当lambda捕获太大而无法放入一些库优化的空间时(我猜有点像各种短字符串优化?)

2013-01-29 20:34:35

其他回答

要使lambda递归而不使用外部类和函数(如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}}});
}

打印:

注意，lambda的结果类型应该显式指定。

2017-08-22 18:41:55

这是一个稍微简单的固定点操作符的实现，这使得它更明显地发生了什么。

#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';
    }
}

2013-01-29 01:22:22

c++ 14: 这是lambdas的递归匿名无状态/无捕获泛型集输出从1,20开始的所有数字

([](auto f, auto n, auto m) {
    f(f, n, m);
})(
    [](auto f, auto n, auto m) -> void
{
    cout << typeid(n).name() << el;
    cout << n << el;
    if (n<m)
        f(f, ++n, m);
},
    1, 20);

如果我没理解错，这是用y组合子解

这是(n, m)的和

auto sum = [](auto n, auto m) {
    return ([](auto f, auto n, auto m) {
        int res = f(f, n, m);
        return res;
    })(
        [](auto f, auto n, auto m) -> int
        {
            if (n > m)
                return 0;
            else {
                int sum = n + f(f, n + 1, m);
                return sum;
            }
        },
        n, m); };

auto result = sum(1, 10); //result == 55

2018-03-09 21:35:12

我使用std::function<>捕获方法运行了一个基准测试，比较递归函数和递归lambda函数。在clang版本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获取输入的版本，以消除编译时计算)

Clang还会产生一个编译器警告:

main.cc:10:29: warning: variable 'sum2' is uninitialized when used within its own initialization [-Wuninitialized]

这是意料之中的，也是安全的，但应该注意。

在我们的工具中有一个解决方案是很好的，但我认为如果要与当前的方法相比，该语言需要更好的方法来处理这种情况。

注意:

2013-01-29 20:34:35

这里是op的最终答案。无论如何，Visual Studio 2010不支持捕获全局变量。您不需要捕获它们，因为全局变量可以通过define全局访问。下面的答案使用局部变量代替。

#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;
}

2011-06-23 13:20:08

c++ 11中的递归lambda函数

推荐文章

最新文章

标签