因为懒得写引用传递

󰃭 2025-02-17

起因：懒得写递归函数并手动传参

今天刷 LeetCode 时又遇到了 DFS 等递归函数时，因为懒得显式定义递归函数并传递引用参数，尝试直接用 lambda 来写递归逻辑。

第一次尝试：auto 推断递归 lambda

vector<vector<int>> graph = {{1, 2}, {3}, {3}, {}};
vector<bool> visited(4, false);

auto dfs = [&](int u) {
    visited[u] = true;
    for (auto v : graph[u]) {
        // error: variable 'dfs' declared with deduced type 'auto' cannot appear in its own initializer
        if (!visited[v]) dfs(v);  
    }
};

dfs(0);

lambda 表达式的类型是编译器生成的匿名闭包类型，而 auto 推断的类型需要在编译期确定。而在 auto 推断时，dfs 需要引用自己，但它自身的类型尚未推断完成，因此无法通过编译。

第二次尝试：使用 std::function

为了解决这个问题，引入 std::function：

vector<vector<int>> graph = {{1, 2}, {3}, {3}, {}};
vector<bool> visited(4, false);

function<void(int)> dfs = [&](int u) {
    visited[u] = true;
    for (auto v : graph[u]) {
        if (!visited[v]) dfs(v);
    }
};

dfs(0);

编译过了, 代码AC了, 但性能比别人的差. 究其原因是因为 std::function 并不是简单的 auto lambda 的显式声明.

std::function 的类型擦除

为了保证 std::function 可以兼容函数, lambda, bind(), 仿函数等多种可调用, 其内部使用了类型擦除技术，通过 void* 指针和虚函数表来存储和调用不同的可调用对象。这会带来性能损耗，尤其在递归频繁调用的场景下。

类型擦除的内部机制：

  • std::function 会在内部保存一个 void* 指针，指向目标可调用对象。
  • 调用时通过虚表调用 operator()，这引入了额外的间接调用开销。
  • 对于捕获的变量，通常需要动态分配内存，增加了堆内存分配和管理的负担。

这就是为什么在性能敏感的递归调用场景中，使用 std::function 可能带来较大性能损耗。

第三次尝试：auto&& self —— 灵活高效的递归写法

但懒癌晚期难以根治, 所以想了这么个狗屁写法.

vector<vector<int>> graph = {{1, 2}, {3}, {3}, {}};
vector<bool> visited(4, false);

auto dfs = [&](int u, auto&& self) {
    visited[u] = true;
    for (auto v : graph[u]) {
        if (!visited[v]) self(v, self);
    }
};

dfs(0, dfs);

关于这里的 auto&&:

  • 当 auto&& 出现在模板参数或 lambda 参数时，它是转发引用，能自动推导左值或右值引用。
  • 调用 dfs(0, dfs) 时，self 被推导为 lambda 的左值引用。

示例：

template<typename T>
void check(T&& x) {
    if constexpr (std::is_lvalue_reference_v<T>) {
        cout << "Lvalue reference\n";
    } else {
        cout << "Rvalue reference\n";
    }
}

int x = 42;
check(x);   // Lvalue reference
check(42);  // Rvalue reference

性能对比

写法 性能 可读性 灵活性
std::function 较慢 易读 灵活
显式递归函数 最快 一般 性能最佳
auto&& self 接近最快 较复杂 高效灵活

总结： 懒惰是程序员的美德.

Tags: #bar #foo