当前位置：首页 > article >正文

C++ 中如何优雅地返回一个递归闭包函数？

article 2025/1/6 5:47:22

在刷Leetcode时，我遇到了一道题目（详见Leetcode 第426场周赛分析总结Q3），需要对两棵树建图，然后以每个节点作为根节点进行DFS遍历。一般的实现方法是将重复的逻辑封装起来，写两个函数，一个负责建图，另一个负责DFS，然后将建图后的返回值作为参数传递给DFS。

在Python、JavaScript等高级语言中，有一种叫做闭包函数的编程技巧，能够简化这种逻辑。闭包本质上是一个函数A返回另一个函数B，而函数B捕获了函数A的局部变量，从而使函数B拥有状态信息。在C++中，我们也可以利用闭包函数，将建图与DFS的逻辑绑定，从而避免显式地在调用时传递参数。

以下是该问题的C++实现：

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        // 建立一个闭包函数，用于返回DFS函数
        auto get_dfs = [](decltype(edges1) edges) -> auto {
            int n = edges.size() + 1;
            vector graph(n, vector<int>());
            for (auto &&edge : edges) {
                auto u = edge[0], v = edge[1];
                graph[u].push_back(v);
                graph[v].push_back(u);
            }
            function<int(int, int, int)> dfs;
            dfs = [graph = std::move(graph), &dfs](int u, int fa, int d) -> int {
                if (d < 0) return 0;
                int ans = 1;
                for (auto v : graph[u]) {
                    if (v == fa) continue;
                    ans += dfs(v, u, d - 1);
                }
                return ans;
            };
            return dfs;
        };

        // 对第二棵树进行DFS，计算其最大目标节点数
        int maxn2 = 0;
        if (k > 0) {
            auto dfs = get_dfs(edges2);
            int n = edges2.size() + 1;
            for (int i = 0; i < n; ++i) {
                maxn2 = max(maxn2, dfs(i, -1, k - 1));
            }
        }

        // 对第一棵树进行DFS，结合第二棵树的结果计算答案
        auto dfs = get_dfs(edges1);
        int n = edges1.size() + 1;
        vector<int> ans(n, 0);
        for (int i = 0; i < n; ++i) {
            ans[i] = dfs(i, -1, k) + maxn2;
        }
        return ans;
    }
};

闭包函数的核心原理

在C++中，闭包（Closure）是通过lambda表达式实现的一种语法特性。闭包可以捕获外部上下文中的变量，将其绑定到返回的函数中，从而避免显式传递参数。在上面的代码中，get_dfs函数返回了一个DFS函数，这个DFS函数通过捕获将graph变量绑定到其作用域中。

以下是闭包函数的几项核心要点：

变量捕获：
- 值捕获（by value）：将外部变量的值拷贝到闭包中，闭包对这些变量的修改不会影响外部变量。
- 引用捕获（by reference）：闭包捕获外部变量的引用，闭包对变量的修改会影响外部变量。
- C++14后的移动捕获（move capture）：通过std::move，可以将大对象的所有权转移到闭包中，避免拷贝的开销。
闭包的生命周期：
- 在C++中，闭包的生命周期由捕获的变量决定。如果捕获的变量是局部变量，需确保这些变量在闭包的使用过程中始终有效。

实现中的关键点

1. 移动捕获`graph`

在get_dfs函数中，我们通过std::move(graph)将图的所有权转移到闭包中：

dfs = [graph = std::move(graph), &dfs](int u, int fa, int d) -> int { ... };

为什么要使用移动捕获？

如果使用值捕获，graph会被拷贝，可能造成性能开销，特别是在graph较大时。
如果使用引用捕获，get_dfs函数返回后，graph的生命周期结束，闭包中的引用将变为悬挂指针，导致未定义行为。
移动捕获通过转移所有权将graph绑定到闭包中，使其生命周期与闭包一致，既避免了拷贝开销，又保证了安全性。
需要注意的是，移动捕获会使闭包与捕获的资源绑定，可能导致资源生命周期难以管理。在更复杂的场景下，可以考虑将 graph 提前封装到一个辅助类中，避免直接捕获大对象。

2. 引用捕获自身`dfs`

在递归的实现中，dfs函数需要捕获自身。这通过引用捕获实现：

dfs = [graph = std::move(graph), &dfs](int u, int fa, int d) -> int { ... };

如果进行值捕获（[dfs]），编译器会尝试拷贝 dfs，但在捕获时 dfs 仍未完全定义（不完全类型），因此会报错。

为什么捕获dfs可以使用引用？

返回闭包时，dfs作为函数的返回值，在返回值优化（RVO）的作用下，其内存不会被销毁。因此，引用捕获dfs是安全的。
RVO 是一种编译器优化技术，用于避免对象的临时拷贝或移动。其核心思想是：在函数返回对象时，直接在调用方的内存中构造返回值，跳过临时对象的拷贝或移动操作。
需要注意的是，在不支持 RVO 的情况下，引用捕获 dfs 是不安全的。这时就需要把dfs作为参数进行传递，或者在内层再使用std::function进行包裹。