我是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捕获太大而无法放入一些库优化的空间时(我猜有点像各种短字符串优化?)

其他回答

这个答案不如扬克斯的,但还是这样:

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

您正在尝试捕获正在定义的变量(sum)。那可不太好。

我不认为真正的自递归c++ 0x是可能的。不过,您应该能够捕获其他lambda。

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

考虑一下自动版本和完全指定类型版本之间的区别。auto关键字从初始化它的对象推断它的类型,但是初始化它的对象需要知道它的类型(在本例中,lambda闭包需要知道它捕获的类型)。有点像鸡生蛋还是蛋生鸡的问题。

另一方面,完全指定的函数对象的类型不需要“知道”任何被赋值给它的内容,因此lambda闭包同样可以完全知道它捕获的类型。

考虑一下对代码的轻微修改,它可能更有意义:

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

显然,这在auto中行不通。递归lambda函数工作得非常好(至少它们在MSVC中是这样的,我在MSVC中有使用它们的经验),只是它们与类型推断并不真正兼容。

在c++ 14中,现在很容易创建一个有效的递归lambda,而不必引起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.
        return f(*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)};
}

你原来的求和尝试变成:

auto sum = make_y_combinator([term,next](auto sum, int a, int b) -> int {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
});

在c++ 17中,使用CTAD,我们可以添加演绎指南:

template <class F> y_combinator(F) -> y_combinator<F>;

这样就不需要辅助函数了。我们可以写y_combinator{[](auto self,…){…直接}}。


在c++ 20中,使用CTAD进行聚合,就不需要演绎指南了。


在c++ 23中,通过演绎,你根本不需要y组合子:

auto sum = [term,next](this auto const& sum, int a, int b) -> int {
  if (a>b) {
    return 0;
  }
  else {
    return term(a) + sum(next(a),b);
  }
}