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.
