Why does the following code failed to compile (C++ lambda problem)

December 20, 2021

Well I’m coding a function in which I used recursive lambda in C++ (GNU C++14). So I tried the y_combinator method, beginning with a declaration outside the main() function (I’ve used using namespace std; before this).

#include <bits/stdc++.h>

using namespace std;

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(ref(*this), forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}

int main () {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;
    vector<int> adj[N+1];
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> d(N+1);
    auto dfs = y_combinator([&](auto dfs, int u, int p, int &r) {
        if (u == p) d[u] = 0;
        if (d[u] > d[r]) r = u;
        for (auto &v : adj[u]) {
            if (v != p) {
                d[v] = d[u]+1;
                dfs(v, u, r);
            }
        }
    });
}

Now I have a simple, easy to understand question for you guys : What make this lambda function failed to even compile (this happen inside the main function)?

The thing is, when I’m trying to compile it, I received this catastrophic message :

test1.cpp: In function 'int main()':
test1.cpp:36:29: error: use of deleted function 'main()::<lambda(auto:1, int, int, int&)>::~<lambda>()'
   36 |     auto dfs = y_combinator([&](auto dfs, int u, int p, int &r) {
      |                             ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
   37 |         if (u == p) d[u] = 0;
      |         ~~~~~~~~~~~~~~~~~~~~~
   38 |         if (d[u] > d[r]) r = u;
      |         ~~~~~~~~~~~~~~~~~~~~~~~
   39 |         for (auto &v : adj[u]) {
      |         ~~~~~~~~~~~~~~~~~~~~~~~~
   40 |             if (v != p) {
      |             ~~~~~~~~~~~~~
   41 |                 d[v] = d[u]+1;
      |                 ~~~~~~~~~~~~~~
   42 |                 dfs(v, u, r);
      |                 ~~~~~~~~~~~~~
   43 |             }
      |             ~
   44 |         }
      |         ~
   45 |     });
      |     ~
test1.cpp:36:31: note: 'main()::<lambda(auto:1, int, int, int&)>::~<lambda>()' is implicitly deleted because the default definition would be ill-formed:
   36 |     auto dfs = y_combinator([&](auto dfs, int u, int p, int &r) {
      |                               ^

So I try a small fix by capturing 2 vector name d and adj

#include <bits/stdc++.h>

using namespace std;

template<class Fun>
class y_combinator_result {
    Fun fun_;
public:
    template<class T>
    explicit y_combinator_result(T &&fun): fun_(forward<T>(fun)) {}

    template<class ...Args>
    decltype(auto) operator()(Args &&...args) {
        return fun_(ref(*this), forward<Args>(args)...);
    }
};

template<class Fun>
decltype(auto) y_combinator(Fun &&fun) {
    return y_combinator_result<decay_t<Fun>>(forward<Fun>(fun));
}

int main () {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;
    vector<int> adj[N+1];
    for (int i = 0; i < N-1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> d(N+1);
    auto dfs = y_combinator([&d, &adj](auto dfs, int u, int p, int &r) { // I changed this line
        if (u == p) d[u] = 0;
        if (d[u] > d[r]) r = u;
        for (auto &v : adj[u]) {
            if (v != p) {
                d[v] = d[u]+1;
                dfs(v, u, r);
            }
        }
    });
}

and the program compiled as intended …
Obviously there is a very big question from my perspective : Why did the first piece of code that I used [&] to capture everything in side the main() function failed, but the second one work ? Is there any way around this, cuz I don’t want to spend time capturing variables …

P/s : forgive me for my bad english. I’m not a native speaker.