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、返回类型、函数体以及泛型 LambdaC14、显式对象形参C23等进阶特性并结合仓库内docs/dp、docs/graph、docs/ds、docs/math等目录下的真实竞赛代码展示 Lambda 在排序谓词、区间计算、图算法一般图最大匹配、动态规划优化中的高频用法以及递归场景下的四种正确写法。读完本文你将能够在算法竞赛中熟练、正确地书写与优化 Lambda 表达式。考虑到算法竞赛的实际情况本文不会全面研究语法只讲述在算法竞赛中可能会应用到的部分。语法参照C11标准其他高版本的标准语法视情况提及并会特别标注。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 带初始化的捕获C14自 C14 起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 520s]() { return val; }; // OK, C14 起需要 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::vectorint(3, 6)]() { return val; }; // OK, 定义 val 类型为 std::vectorint大小为 3元素填充 6返回值类型 // std::vectorint 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: 520val也可以是一个引用类型可以引用一个外部变量通过这种方式可以为通过引用捕获的外部变量取个别名例如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声明的参数C14后若参数使用auto声明类型那么会构造一个泛型 Lambda 表达式。显式对象形参C23C23起显式对象形参可以在 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]; };泛型 LambdaC14使用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::functionvoid(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_castunsigned (*)(unsigned)(lambda); return 0; }(); cout lambda(10);仓库代码印证在需要带状态的 DFS 递归场景如欧拉游览树 ETT 的子树操作实现 ett_connectivity.cpp中采用的是std::function包装[]捕获的 Lambdastd::functionvoid(Node*) dfs { ... };而在 math/code 目录下的连分数类实现如 mod-mod-mod.cpp 与 sum-floor.cpp中则大量采用无捕获 Lambdaauto picks [](int y1, int y2, int dx, int a) - int { ... };无捕获 Lambda 可以隐式转换为函数指针便于作为独立函数传递给其他算法组件同时避免了捕获带来的额外状态开销。Lambda 表达式的应用作为标准库算法的 Predicate谓词从大到小排序std::vectorint v {1, 2, 3, 4, 5}; std::sort(v.begin(), v.end(), [](int a, int b) { return a b; });使用std::find_if查找第一个大于 3 的元素std::vectorint 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 vectorint input) { int b [] { vectorint 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之后中间数组立即析构从而显著降低峰值内存占用。小结语法部件作用竞赛高频要点[capture]指定捕获的变量与方式[]默认引用捕获最常用[]值捕获带初始化捕获C14可声明新变量(parameters)形参列表可省略C14 起可用auto构成泛型 LambdaC23 起可写this auto selfmutable允许修改值捕获的变量值捕获成员在展开类中是const的- return-type后置返回类型省略时自动推导多返回值类型不一致会编译错误{statement}函数体可访问捕获变量、参数与全局变量参考文献与延伸阅读本文语法细节以 cppreference 的 lambda 词条为准包含各版本标准的完整语法与示例。关于std::function的额外开销可参考 Stack Overflow 上关于 Overhead with std::function 的回答其解释了类型擦除、堆分配与间接调用带来的性能损失。仓库内可继续阅读docs/lang/new.md函数对象与std::function的详细说明、docs/lang/reference.md引用语义、docs/lang/optimizations.mdC 优化技巧。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考