OI-wiki 语言篇：C++ Lambda 表达式在算法竞赛中的完整实战指南

OI-wiki 语言篇：C++ Lambda 表达式在算法竞赛中的完整实战指南

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

导读：本文以 OI-wiki docs/lang/lambda.md 为主体，系统讲解 C++ Lambda 表达式的语法构成（捕获子句、参数列表、mutable、返回类型、函数体）以及泛型 Lambda（C++14）、显式对象形参（C++23）等进阶特性，并结合仓库内docs/dp、docs/graph、docs/ds、docs/math等目录下的真实竞赛代码，展示 Lambda 在排序谓词、区间计算、图算法（一般图最大匹配）、动态规划优化中的高频用法，以及递归场景下的四种正确写法。读完本文，你将能够在算法竞赛中熟练、正确地书写与优化 Lambda 表达式。

考虑到算法竞赛的实际情况，本文不会全面研究语法，只讲述在算法竞赛中可能会应用到的部分。语法参照C++11标准，其他高版本的标准语法视情况提及并会特别标注。

Lambda 表达式是什么

Lambda 表达式因数学中的 $\lambda$ 演算得名，直接对应于其中的 lambda 抽象。编译器在编译时会根据语法生成一个匿名的函数对象，以捕获的变量作为其成员，参数和函数体用于实现operator()重载。

??? note "函数对象（Function Object）" 函数对象是一种类对象，一般通过重载operator()实现，所以能像函数一样调用。相较于使用普通的函数，函数对象有很多优点，例如可以保存状态，可以作为参数传递给其他函数等。

Lambda 的一种语法如下：

[capture] (parameters) mutable -> return-type {statement}

Lambda 表达式本身是一个类，展开后如以下形式：

class Lambda_1 { private: Lambda_1() : capture-list(init-value) { } public: return-type operator()(parameters) const { statement } private: mutable capture-list };

空的 capture 可以隐式转换为函数指针，例如：

void (*f)(int, int) = [](int, int) -> void {};

下面我们分别对语法中的各部分进行介绍。

statement 函数体

Lambda 表达式的函数体与普通函数的函数体类似，除了能访问参数和全局变量等，还可访问捕获的变量。

capture 捕获子句

Lambda 以 capture 子句开头，它指定哪些变量被捕获。捕获列表可为空，或指定捕获方式：有&符号前缀的变量通过引用访问，没有该前缀的变量通过值访问。

我们也可以使用默认捕获模式，捕获 Lambda 中提及的所有变量：&表示捕获到的所有变量都通过引用访问，=表示捕获到的所有变量都通过值访问。在默认捕获之后，仍然可以为特定的变量显式指定捕获模式。

如果需要引用访问外部变量a，并通过值访问外部变量b，那么以下捕获子句都可以做到：

• [&a, b]
• [b, &a]
• [&, b]
• [b, &]
• [=, &a]

同时捕获列表也可以用于声明变量，类型由初始化器推导，类似于使用auto声明变量。以下是一些常见的例子：

int a = 0; auto f0 = []() { return a * 9; }; // Error, 无法访问 'a' auto f1 = [a]() { return a * 9; }; // OK, 'a' 被值「捕获」 auto f2 = [&a]() { return a++; }; // OK, 'a' 被引用「捕获」 auto f3 = [v = a + 1]() { return v + 1; }; // OK, 使用初始化器声明变量 v，类型与 a 相同 // 注意，使用引用捕获时，请保证被调用时 a 没有被销毁 auto b = f2(); // f2 从捕获列表里获得 a 的值，无需通过参数传入 a

从源码结构看，OI-wiki 仓库中的竞赛实现大量使用[&]默认引用捕获。例如一般图最大匹配模板 general-match_1.cpp 中连续定义了lca、blossom、augment、bfs、greedy五个相互调用的 Lambda，它们通过[&]共享外部的匹配数组、并查集数组、队列与标记时间戳等状态，避免了为每个子过程单独传参：

auto lca = & { ... }; // 求环上 LCA auto blossom = & { ... }; // 缩花 auto augment = & { ... }; // 增广 auto bfs = & { ... }; // BFS 找增广路 auto greedy = [&]() { ... }; // 贪心初始化匹配

generalized capture 带初始化的捕获（C++14）

自 C++14 起，capture 不仅可以用来捕获外部变量，还可用于声明新的变量并初始化，例如：

auto f1 = [val = 520]() { return val; }; // OK, 定义 val 类型为 int，初始值为 520，返回值类型 int auto f2 = [val = 520LL]() { return val; }; // OK, 定义 val 类型为 long long，初始值为 520，返回值类型 long long auto f3 = [val = "520"]() { return val; }; // OK, 定义 val 类型为 const char*，初始值为 "520"，返回值类型 const char* auto f4 = [val = "520"s]() { return val; }; // OK, C++14 起，需要 using namespace std; 或 using namespace std::literals; // 定义 val 类型为 std::string，初始值为 std::string("520")，返回值类型 // std::string auto f5 = [val = std::string("520")]() { return val; }; // OK, 定义 val 类型为 std::string，初始值为 std::string("520")，返回值类型 // std::string auto f6 = [val = std::vector<int>(3, 6)]() { return val; }; // OK, 定义 val 类型为 std::vector<int>，大小为 3，元素填充 6，返回值类型 // std::vector<int> auto f7 = [val = 520]() -> int { return val; }; // OK, 定义 val 类型为 int，初始值为 520，返回值类型 int auto f8 = [val = 520]() -> long long { return val; }; // OK, 定义 val 类型为 int，初始值为 520，返回值类型 long long

定义新的变量不可以省略初始值，变量的类型由初始值的类型决定，相当于：

auto val = init-value;

以下是错误的写法：

auto f = [val]() { return val; }; // Error: 'val' was not declared in this // scope, identifier "val" is undefined

初始化值也可以是外部变量，例如：

int value = 520; auto f = [val = value]() { return val; }; std::cout << f(); // Output: 520

val也可以是一个引用类型，可以引用一个外部变量，通过这种方式可以为通过引用捕获的外部变量取个别名，例如：

int value = 520; auto f = [&val = value]() { return val; }; // OK, 定义 val 类型为 int&，返回值类型 int，相当于 int& val = value; std::cout << f() << '\n'; // Output: 520 value = 1314; std::cout << f() << '\n'; // Output: 1314

捕获外部变量和定义新变量可以同时使用。

如果你想在 Lambda 表达式内修改 capture 中定义的新变量，需要使用mutable关键字，如果是引用则不需要，例如：

int value = 520; { auto f = [val = value]() mutable -> int { return val = 1314; }; // 需要 mutable auto val_f = f(); std::cout << value << ' ' << val_f << std::endl; // Output: 520 1314 } { auto f = [&val = value]() -> int { return val = 1314; }; // 不需要 mutable auto val_f = f(); std::cout << value << ' ' << val_f << std::endl; // Output: 1314 1314 }

详见 mutable 可变规范。

在 capture 中定义的变量的生命周期跟随 Lambda 表达式的接收方，在以上几个示例中为变量f。因为 Lambda 本身其实是一个类，capture 中的所有内容都是这个类的private成员变量，例如：

int main() { auto f = [val = 0]() mutable -> int { return ++val; }; // val 被构造和初始化 std::cout << f() << '\n'; // Output: 1 std::cout << f() << '\n'; // Output: 2 std::cout << f() << '\n'; // Output: 3 } // val 跟随 f 被销毁

parameters 参数列表

大多数情况下类似于函数的参数列表，例如：

int x[] = {5, 1, 7, 6, 1, 4, 2}; std::sort(x, x + 7, [](int a, int b) { return (a > b); }); for (auto i : x) std::cout << i << " ";

这将打印出x数组从大到小排序后的结果。

由于parameters 参数列表是可选的，如果不将参数传递给 lambda，并且其声明不包含 mutable，且没有后置返回值类型，则可以省略空括号。

??? note "使用auto声明的参数"C++14后，若参数使用auto声明类型，那么会构造一个泛型 Lambda 表达式。

显式对象形参（C++23）

C++23起，显式对象形参可以在 lambda 的参数中使用。这一特性允许 Lambda 直接引用自身对象（this self），是实现无捕获递归的又一途径：

auto nth_fibonacci = [](this auto self, unsigned n) -> unsigned { return n < 2 ? n : self(n - 1) + self(n - 2); }; cout << nth_fibonacci(10u);

mutable 可变规范

使得函数体可以修改通过值捕获的变量。

int a = 0; auto by_value = [a]() mutable { ++a; }; auto by_ref = [&a] { ++a; }; by_value(); by_ref();

在执行完by_value()后，by_value的捕获成员a为 1，但外部的变量a依然为 0。而在执行完by_ref()后，外部a的值变为 1。

这一差异的根源在于 Lambda 展开后的类结构：值捕获的变量是operator() const的普通成员，mutable会取消const限制；而引用捕获的成员本身就是引用，修改引用指向的对象不违反const，因此无需mutable。

return-type 返回类型

用于指定 lambda 表达式的返回类型。如果省略，则返回类型将被自动推断（行为与用auto声明返回值的函数一致）。

多个return语句且推导类型不一致时，将产生编译错误。

auto lam = [](int a, int b) -> int { return 0; }; auto x1 = [](int i) { return i; }; auto x2 = [](bool condition) { if (condition) return 1; return 1.0; }; // Error, 推导类型不一致

在仓库中，显式声明返回类型的写法非常常见，尤其是在返回类型无法直接推导或希望避免推导歧义时。例如 WQS 二分模板 black-white-mst-2.cpp 中：

auto calc = & -> int { // 用 Kruskal 计算 h(k) = min_x f(x) - k * g(x) ... };

四边形不等式优化的邮局问题实现 post-office-1.cpp 则用模板类型参数标注返回类型：

auto w = & -> ValueT { return ww(j, i) + f[j - 1]; };

泛型 Lambda（C++14）

使用auto作为参数类型，可以构造泛型 lambda。

auto add = [](auto a, auto b) { return a + b; };

编译器生成的lambda类定义相当于：

class add_lambda { public: template <class T, class U> auto operator()(T a, U b) const { return a + b; } }; add_lambda add{};

add两个参数声明均使用了auto，对应为add_lambda类的operator()函数模板的两个模板参数T和U。泛型 Lambda 的本质是成员函数模板，因此它可以在被调用时才进行实例化——这一点正是"通过传参实现 Lambda 递归"方案的基石。

仓库中的真实应用示例：K 维树（KD-Tree）实现 kdt_3.cpp 在排序时使用值捕获与泛型参数结合的比较器：

dep { return t[x].x[dep] < t[y].x[dep]; }

而 WQS 二分模板 black-white-mst-2.cpp 中则同时使用了引用捕获与auto参数，比较两个边结构体：

std::sort(edges[0].begin(), edges[0].end(), & -> bool { return lhs[2] < rhs[2]; });

Lambda 中的递归

先来看一个编译失败的例子：

int n = 10; auto dfs = & -> void { if (i == n) return; else dfs(i + 1); // Error: a variable declared with an auto type specifier // cannot appear in its own initializer };

我们这里尝试在捕获列表中捕获dfs，但是有一个问题：dfs的类型为auto，要等待等号右边的类型推导完成后才会推导出dfs的类型，而 Lambda 要捕获dfs就必须要确定dfs的类型后才能创建它的引用变量——这陷入了一个套娃过程。

怎么解决这个问题呢？有四种方案：

方案一：显式指定dfs的类型，使用std::function替代。

int n = 10; std::function<void(int)> dfs = & -> void { if (i == n) return; else dfs(i + 1); // OK }; dfs(1);

??? warning "不建议使用std::function实现的递归"std::function的类型擦除通常需要分配额外内存，同时间接调用带来的寻址操作会进一步降低性能。在官方 Benchmark 测试中，使用 Clang 17 编译器、libc++ 作为标准库，std::function实现比 Lambda 实现的递归慢了约 2.5 倍。

测试代码大致为：分别用 `std::function` 包装的递归与"把自身作为参数传入"的泛型 Lambda 递归计算斐波那契数，使用 Google Benchmark 测量，并对 `res` 调用 `DoNotOptimize` 防止编译器优化掉计算。

方案二：不通过捕获的方式获取dfs，而是通过函数传参的方式。

int n = 10; // 参数列表中有参数类型为 auto，则这个 Lambda 类中的 operator() // 函数将被定义为模板函数，模板函数可以在稍后被调用时再进行实例化 auto dfs = & -> void // [&] 只会捕获用到的变量，所以不会捕获 auto dfs { if (i == n) return; else self(self, i + 1); // OK }; dfs(dfs, 1);

???+ note "auto self、auto& self和auto&& self的区别"auto& self和auto&& self理论上都只会使用 8 个字节（指针的大小）用作传参，不会发生其他的拷贝，具体要看编译器对 Lambda 的实现方式和对应的优化。而使用auto self会发生对象拷贝，拷贝的大小取决于捕获列表中的元素，因为它们都是这个 Lambda 类中的私有成员变量。

方案三：手动展开 Lambda 类，直接声明dfs的类型。

int n = 10; class Lambda_1 { public: auto operator()(int i) const -> void { if (i == n) return; else (*this)(i + 1); // OK } explicit Lambda_1(int& __n) : n(__n) {} private: int& n; } dfs(n); dfs(1);

方案四：利用空捕获 Lambda 到函数指针的隐式转换。

如果 lambda 没有捕获任何变量，那么它可以隐式转换为函数指针。同时 lambda 此时也可以声明为static，函数指针类型也可以声明为static。如此，lambda 可以不需要捕获就能访问函数指针，从而实现递归。

static unsigned (*fptr)(unsigned); static const auto lambda = [](const unsigned a) { return a < 2 ? a : (*fptr)(a - 2) + (*fptr)(a - 1); }; static auto init = [] { fptr = +lambda; // Or // fptr = static_cast<unsigned (*)(unsigned)>(lambda); return 0; }(); cout << lambda(10);

仓库代码印证：在需要"带状态的 DFS 递归"场景（如欧拉游览树 ETT 的子树操作实现 ett_connectivity.cpp）中，采用的是std::function包装[&]捕获的 Lambda：

std::function<void(Node*)> dfs = & { ... };

而在 math/code 目录下的连分数类实现（如 mod-mod-mod.cpp 与 sum-floor.cpp）中，则大量采用无捕获 Lambda：

auto picks = [](int y1, int y2, int dx, int a) -> int { ... };

无捕获 Lambda 可以隐式转换为函数指针，便于作为独立函数传递给其他算法组件，同时避免了捕获带来的额外状态开销。

Lambda 表达式的应用

作为标准库算法的 Predicate（谓词）

从大到小排序：

std::vector<int> v = {1, 2, 3, 4, 5}; std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; });

使用std::find_if查找第一个大于 3 的元素：

std::vector<int> v = {1, 2, 3, 4, 5}; auto it = std::find_if(v.begin(), v.end(), [](int a) { return a > 3; });

这种"谓词就地书写"的模式在整个仓库的标准库排序调用中反复出现：KD-Tree 按维度排序 kdt_3.cpp、WQS 二分中按边权排序 black-white-mst-2.cpp，都是将比较逻辑直接内联在std::sort的第三个参数处，免去定义全局比较函数或重载operator<的样板代码。

控制中间变量的生命周期

在算法竞赛中，我们会遇到这样的场景：一个变量的初始化需要使用之前声明的变量，其初始化过程又生成占用空间较大的中间变量。我们希望能尽快析构这些中间变量，以降低内存消耗。此时，我们可以使用 lambda 来控制这些中间变量的生命周期。

void solution(const vector<int>& input) { int b = [&] { vector<int> large_objects(input.size()); int c = 0; for (int i = 0; i < large_objects.size(); ++i) large_objects[i] = i + input[i]; for (int i = 0; i < input.size(); ++i) c += large_objects[input[i]]; return c; }(); // ... }

相较于使用块作用域，lambda 可以允许我们使用返回值，使得代码更加简洁；相较于函数，我们不需要额外起名和声明被捕获的各种参数，使得代码更加紧凑。这是一个"立即调用 Lambda 表达式"（IIFE 风格）的典型模式，将large_objects的生命周期严格限制在初始化表达式中，计算完b之后中间数组立即析构，从而显著降低峰值内存占用。

小结

参考文献与延伸阅读

• 本文语法细节以 cppreference 的 lambda 词条为准，包含各版本标准的完整语法与示例。
• 关于std::function的额外开销，可参考 Stack Overflow 上关于 "Overhead with std::function" 的回答，其解释了类型擦除、堆分配与间接调用带来的性能损失。
• 仓库内可继续阅读：docs/lang/new.md（函数对象与std::function的详细说明）、docs/lang/reference.md（引用语义）、docs/lang/optimizations.md（C++ 优化技巧）。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki