OI-wiki 算法竞赛 C 新特性实战指南从 C11 到 C20 的现代写法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本指南以 OI-wiki 的docs/lang/new.md为骨架系统梳理算法竞赛中最常用、最高频的 C11 至 C20 新特性类型推导auto/decltype、常量表达式constexpr、范围for、结构化绑定、std::tuple、函数对象、std::function、可变参数模板与 C20 范围库。读完本文你将掌握一套既减少样板代码又避免性能损耗的现代 C 竞赛写法并能结合仓库内大量真实代码如 radix-sort 代码、WQS 二分代码理解这些特性在实际解题中的落地方式。适用范围说明考虑到算法竞赛的实际情况本文不会全面研究语法只讲述竞赛中可能应用到的部分。本文语法参照C11标准语义不同的以C11为标准C14、C17 等更高版本的语法视情况提及并会特别标注。auto类型说明符auto类型说明符用于自动推导变量等的类型其推导结果与初始化表达式的静态类型完全一致auto a 1; // a 是 int 类型 auto b a 0.1; // b 是 double 类型在竞赛代码中auto最常见的价值体现在三处避免冗长的类型名std::mapstd::string, std::vectorint::iterator这类写法可以用auto直接替代配合基于范围的for与结构化绑定下文详述承接 Lambda 表达式Lambda 的类型是编译器生成的匿名类只能通过auto或std::function承接见docs/lang/lambda.md。注意auto会去除引用auto推导时会剥离引用限定如果不希望出现拷贝开销需要手动指定int a 1; int b a; auto c b; // c 是 int 类型有拷贝开销 auto e a; // e 是 int 类型没有拷贝开销这一点在遍历大容器如std::vector中的结构体时尤为关键误用auto会引入大量不必要的拷贝导致超时。decltype 说明符decltype可以根据实体或表达式推断类型但两者推导方式不同对实体变量名推导得到该实体声明时的类型对表达式推导得到表达式求值结果的类型且带括号的变量名会推导为引用类型decltype((a))是int错误使用可能造成悬垂引用。#include iostream #include vector int main() { int a 1926; decltype(a) b; // 根据实体推断b 是 int 类型 decltype(1 1) c; // 根据表达式推断c 是 int 类型 decltype((a)) d a; // 根据表达式推断d 是 int 类型 std::vectordecltype(b) vec; // 根据实体推断vec 是 std::vectorint 类型 return 0; }竞赛中decltype并不常用更多出现在泛型代码模板库、排序比较器封装中用于推导与某个表达式相同类型的变量。constexpr编译期常量表达式C11常量表达式是指编译时能计算出结果的表达式constexpr则要求编译器在编译时求得函数或变量的值。更直观的理解是把const理解成只读把constexpr理解成不可变。完整讲解见 常量表达式 constexprC11。constexpr与const的关键区别在于constexpr修饰的变量一旦满足常量表达式的条件就强制编译器在编译期求出结果而非留到运行时。编译期计算允许更好的优化比如将结果硬编码到汇编中消除运行时计算开销constexpr int a 10; // 直接定义常量 constexpr int FivePlus(int x) { return 5 x; } void test(const int x) { std::arrayint, x c1; // 错误x 在编译时不可知 std::arrayint, FivePlus(6) c2; // 可行FivePlus 编译时可知 }原文档给出的斐波那契对比能直观说明差异constexpr unsigned fib0(unsigned n)在调用处使用常量参数时整个函数仅在编译期运行编译器甚至不会为它生成汇编代码而普通unsigned fib1(unsigned n)在运行时递归计算反汇编可见v0已被最终计算结果 55 替代v1仍为运行时函数调用。竞赛中的应用constexpr可以用来替换宏定义的常量规避宏定义的风险算法题中可以用它存储数据规模较小的变量消除运行时计算开销尤为常见于「打表」技巧——用constexpr修饰数组等容器直接存储答案见 docs/contest/dictionary.md。仓库中大量竞赛代码采用了这一写法例如 radix-sort_1.cpp 使用constexpr声明输入规模常量lcs.cpp、lis-1.cpp 也均以constexpr定义数组大小等编译期常量。使用限制编译器会限制编译时计算的开销例如 Clang 默认约束constexpr求值递归深度不超过 512 层计算量过大会导致编译错误此时应退回使用const详见 const.md。基于范围的for循环范围for用于遍历可迭代对象与使用迭代器遍历的效率相同二者效率一般优于按索引遍历——因为索引遍历需要根据索引寻址而迭代器遍历直接持有指针/迭代器位置。基本语法for (item_declaration : range_initializer) statement例如std::arrayint, 4 arr {1, 2, 3, 4}; for (int x : arr) { std::cout x std::endl; }上述语法产生的代码效果等价于std::arrayint, 4 arr {1, 2, 3, 4}; for (auto px arr.begin(), ed arr.end(); px ! ed; px) { std::cout *px std::endl; }item-declaration 项声明声明一个变量用于接受右侧容器中的元素变量类型要与容器内子元素类型一致。可以用auto自动推导类型复杂类型常用auto防止拷贝开销。range-initializer 范围初始化器范围初始化器可以是任何一种可迭代的对象比如数组或定义了begin和end成员函数的类对象。如果放入表达式表达式也只会计算一次。例如int a[] {1, 1, 4, 5, 1, 4}; std::vectorint b{1, 1, 4, 5, 1, 4}; std::mapstd::string, int c{{114, 114}, {514, 514}}; for (int i : a) std::cout i; for (auto i : b) std::cout i; // 下方 i 的类型是 std::pairconst std::string, int for (auto i : c) std::cout i.first i.second; for (auto i : {1, 1, 4, 5, 1, 4}) std::cout i;注意遍历std::map时元素类型是std::pairconst std::string, int——键自带const修饰用auto引用不会产生拷贝这是竞赛中遍历map的推荐写法。自定义类型支持范围 for只需提供begin和end成员函数返回类型需要支持比较、自增和解引用*运算符#include iostream struct C { int a[4]; int* begin() { return a; } int* end() { return a 4; } }; int main() { C c {1, 9, 2, 6}; for (auto i : c) std::cout i ; std::cout std::endl; // output: 1 9 2 6 return 0; }初始化语句C20C20 起基于范围的for可以带初始化语句init-statement用于声明循环计数器等仅在循环内部使用的变量避免污染外层作用域#include iostream #include vector int main() { std::vectorint v {0, 1, 2, 3, 4, 5}; for (int counter 0; auto i : v) // the init-statement (C20) std::cout counter i std::endl; }结构化绑定C17结构化绑定Structured binding是 C17 提供的语法糖可以方便地提取子元素或子元素的引用struct C { int x{1}, y{2}; }; int arr[]{4, 5, 6}; auto [c1, c2] C{}; // c11, c22; int 类型 auto [a1, a2, a3] arr; // a1arr[0], a2arr[1], a3arr[2]; int 类型使用注意左侧声明的变量数和右侧对象的子元素数必须一致类型声明需要使用auto可以使用修饰获取引用避免拷贝。遍历map时配合结构化绑定是 C17 下的标准写法std::mapstd::string, int m {{k1, 1}, {k2, 2}}; // 使用 auto没有拷贝开销 for (auto [k, v] : m) { // k 的类型是 const std::string因为键自带 const 修饰 // v 的类型是 int std::cout k v std::endl; }仓库中已有代码大量使用这一特性例如 ett.md 与 mdst.md 中的示例代码black-white-mst-1.cpp 等 WQS 二分模板代码也在边处理中通过结构化绑定解包std::tuple或自定义结构。std::tuple 元组元组定义于头文件tuple是std::pair的推广可以存储多个不同类型的值#include iostream #include tuple #include vector constexpr auto expr 4 - 1; // expr 3 int main() { std::vectorint vec {1, 9, 2, 6, 0}; std::tupleint, int, std::string, std::vectorint tup std::make_tuple(817, 114, 514, vec); // 使用 get 获取子元素尖括号内必须是整型常量表达式 for (auto i : std::getexpr(tup)) std::cout i ; // 首元素编号为 0故我们 std::get3 得到了一个 std::vectorint return 0; }这里演示了两个要点std::getI的模板实参I必须是编译期整型常量因此可以用constexpr变量且下标从 0 开始。C17 之后可以使用结构化绑定提取值比std::get逐元素取出更加直观std::vectorint vec {1, 9, 2, 6, 0}; std::tupleint, int, std::string, std::vectorint tup std::make_tuple(817, 114, 514, vec); auto [a, b, c, d] tup; // C17 Structured binding std::cout a b c std::endl; std::cout d.size() d[2] std::endl;成员函数函数作用operator赋值一个tuple的内容给另一个swap交换两个tuple的内容constexpr std::tupleint, int tup {1, 2}; std::tupleint, int tupA {2, 3}, tupB; tupB tup; tupB.swap(tupA);非成员函数函数作用make_tuple创建一个tuple对象其类型根据各实参类型定义std::get元组式访问指定的元素std::tie将元组中的值赋值到已有变量operator等按字典顺序比较tuple中的值std::swap特化的std::swap算法std::tupleint, int tupA {2, 3}, tupB; tupB std::make_tuple(1, 2); std::swap(tupA, tupB); std::cout std::get1(tupA) std::endl; int x; std::tie(x, std::ignore) tupB; std::cout x std::endl;std::tie将元组元素赋值给已有变量可以使用std::ignore跳过不需要的元素而结构化绑定是直接声明新变量支持值/引用绑定必须接受所有元素。两者适用场景互补已有变量用std::tie新声明变量用结构化绑定。函数对象可以使用函数调用运算符operator()的对象称为函数对象FunctionObject。它不是一个语言特性而是一种概念或要求在标准库中广泛应用例如所有排序、查找算法的比较器参数。函数对象大致分两类函数指针重载了operator()运算符的类对象。Lambda 就是典型的第二类函数对象——编译器会将捕获的内容存为成员变量并重载函数调用运算符完整机制见 Lambda 表达式。竞赛中最常见的函数对象使用场景是排序std::sort的第三个参数既可以传函数指针如cmp、函数对象如std::greaterint()也可以传 Lambda见 stl-sort.md 中的自定义比较章节。Lambda 表达式Lambda 表达式内容十分丰富完整讲解请参考 Lambda 表达式 页面。与本文主题相关需要牢记的要点Lambda 的基本语法为[capture] (parameters) mutable - return-type {statement}捕获子句可用引用捕获、值捕获以及带初始化的捕获C14[val 520]泛型 LambdaC14用auto参数构造模板化的operator()空捕获列表的 Lambda 可隐式转换为函数指针Lambda 中的递归有多种实现方式用std::function承接、把自身作为参数传入auto self、手动展开 Lambda 类、或利用无捕获 Lambda 的函数指针特性Lambda 常作为标准库算法的谓词例如std::sort(v.begin(), v.end(), [](int a, int b) { return a b; })Lambda 还常用于控制中间变量的生命周期——用一个立即执行的 Lambda 承接一段复杂的初始化逻辑其内部的临时大对象会在表达式结束时析构降低峰值内存。std::functionstd::function是通用函数封装器定义于头文件functional。它的实例能存储、复制及调用任何可调用对象包括 Lambda 表达式、成员函数指针或其他函数对象。若std::function不含任何可调用对象比如默认构造调用时将抛出std::bad_function_call异常。#include functional #include iostream struct Foo { Foo(int num) : num_(num) {} void print_add(int i) const { std::cout num_ i \n; } int num_; }; void print_num(int i) { std::cout i \n; } struct PrintNum { void operator()(int i) const { std::cout i \n; } }; int main() { // 存储自由函数 std::functionvoid(int) f_display print_num; f_display(-9); // 存储 Lambda std::functionvoid() f_display_42 []() { print_num(42); }; f_display_42(); // 存储到成员函数的调用 std::functionvoid(const Foo, int) f_add_display Foo::print_add; const Foo foo(314159); f_add_display(foo, 1); f_add_display(314159, 1); // 存储到数据成员访问器的调用 std::functionint(Foo const) f_num Foo::num_; std::cout num_: f_num(foo) \n; // 存储到函数对象的调用 std::functionvoid(int) f_display_obj PrintNum(); f_display_obj(18); }请注意性能开销std::function会引入一定的性能开销经 Benchmark 测试通常会造成 2 到 3 倍以上的性能损失。因为它使用了类型擦除技术而这通常借由虚函数机制实现调用虚函数会引入额外的开销。在追求极致性能的竞赛代码中请优先考虑使用 Lambda 表达式或函数对象代替std::function。std::function的合理使用场景是需要递归 Lambda自身类型未知或需要在容器中统一存储多种可调用对象时。可变参数函数模板在 C11 之前类模板和函数模板都只能接受固定数目的模板参数。C11 起允许任意个数、任意类型的模板参数。这里简要介绍可变参数函数模板template typename... Clazz void fun(Clazz... paras) {}paras是一个函数参数包function parameter pack接受 0 个或多个函数实参Clazz是一个模板参数包template parameter pack接受 0 个或多个模板实参非类型、类型或模板以typename标记时只接受类型。可以简单理解为模板参数包通常是一些类型名但也可以使用编译期常量或模板名函数参数包通常是一些变量名。于是可以这样调用fun(); fun(1); fun(1, 2, 3); fun(1, 0.0, abc);参数包展开参数包展开非常简单使用...即可将自动使用,分隔template class A, class... C void func(A arg1, C... arg2) { // C 是模板参数包 tupleA, C...(); // 展开成 tupleint, int, double, bool(); // arg2 是函数参数包 func(arg2...); // 展开成 func(2, 1.1, true); } func(1, 2, 1.1, true);参数包展开时还可以附带需要的运算template class A, class... C void func(A arg1, C... arg2) { func((arg2 1)...); // 展开成 func( (21), (1.11), (2.1f1) ); } func(1, 2, 1.1, 2.1f);终止函数上面的函数无法运行因为参数数量不断减少最后变为空参并报错。需要指定终止条件——提供一个零参数的普通函数作为重载参数包耗尽时编译器会匹配到它void func() {} template class A, class... C void func(A arg1, C... arg2) { std::cout arg1 std::endl; func((arg2 1)...); } func(1, 2, 1.1, 2.1f);这样参数数量不为 0 时调用模板版本空参时调用普通函数程序即可正常运行。折叠表达式C17C17 提供了一种简便的语法处理函数参数包其语法如下必须用小括号包裹( pack op ... )会变成(E1 op (... op (EN-1 op EN)))( ... op pack )会变成(((E1 op E2) op ...) op EN)( pack op ... op init )会变成(E1 op (... op (EN−1 op (EN op I))))( init op ... op pack )会变成((((I op E1) op E2) op ...) op EN)简单演示template class... C void func(C... args) { (std::cout ... args) std::endl; // 语法 4等价于 ↓ // ( ( ( std::cout 1 ) 2.1 ) true ) std::endl; // 输出: 12.11 注意 true 输出成了 1因为这里没有指定 boolalpha std::cout (args ...) std::endl; // 语法 1等价于 ↓ // std::cout ( 1 ( 2.1 true ) ) std::endl; // 输出: 1 } func(1, 2.1, true);折叠表达式让对参数包中的每个元素依次施加二元运算符这一高频需求从递归改为一行表达式是 C17 下编写变参工具函数最简洁的手段。缩写函数模板C20C20 起可以直接使用auto ...作为参数类型实现函数模板的缩写void func(auto... args) { (std::cout ... args) std::endl; }注意它本质上仍然是函数模板与下面的写法等价template class... T void func(T... args) { (std::cout ... args) std::endl; }范围库C20范围库是对迭代器和泛型算法库的一个扩展使得迭代器和算法可以通过组合变得更强大并且减少错误。范围range即可以遍历的序列包括数组、容器、视图等。在需要对容器等范围进行复杂操作时范围库可以使得算法编写更加容易和清晰。View 视图视图是一种轻量对象通过特定机制如自定义迭代器来实现一些算法给范围提供了更多的遍历方式。范围库中已实现了一些常用的视图大致分两种范围工厂用于构造一些特殊的范围使用这类工厂可以省去手动构造容器的步骤降低开销直接生成一个范围范围适配器提供多种多样的遍历支持既能像函数一样调用也可以通过管道运算符|连接实现链式调用。范围适配器作为范围适配器闭包对象也属于函数对象——它们重载了operator|使得它们能够像管道一样拼装起来。管道运算符此处的|应理解成管道运算符而非按位或运算符这个用法来源于 Linux 中的管道Unix pipeline。在复杂操作下范围适配器组合能保持良好的可读性若 A、B、C 为一些范围适配器闭包对象R 为某个范围其他字母为可能的有效参数表达式R | A(a) | B(b) | C(c, d)等价于C(B(A(R, a), b), c, d)下面以ranges::take_view与ranges::iota_view为例#include iostream #include ranges int main() { const auto even [](int i) { return 0 i % 2; }; for (int i : std::views::iota(0, 6) | std::views::filter(even)) std::cout i ; }范围工厂std::views::iota(0, 6)生成了从 0 到 5 的整数序列的范围范围适配器std::views::filter(even)过滤前一个范围生成了一个只剩下偶数的范围两个操作使用管道运算符链接。上述代码不需要额外分配堆空间存储每步生成的范围实际的生成和过滤运算发生在遍历操作中更具体而言内部的迭代器构造、自增和解引用也就是零开销Zero Overhead。生命周期与悬垂风险外部输入的范围的生命周期等同于范围适配器的内部元素的生命周期。如果外部范围比如容器、范围工厂已经销毁那么再对这些视图遍历其效果与解引用悬垂指针一致属于未定义行为#include iostream #include ranges #include vector using namespace std; int main() { auto view [] { vectorint vec{1, 2, 3, 4, 5}; return vec | std::views::filter([](int i) { return 0 i % 2; }); }(); for (int i : view) cout i ; // runtime undefined behavior return 0; }为了避免这种情况应严格要求适配器的生命周期位于其使用的任何范围的生命周期内。Constrained Algorithm 受约束的算法C20 在命名空间std::ranges中提供大多数算法的受约束版本可以用迭代器-哨位对或单个 range 作为实参来指定范围并且支持投影和指向成员指针的可调用对象另外还更改了大多数算法的返回类型以返回算法执行过程中计算的所有潜在有用信息。这些算法可以理解成旧标准库算法的改良版本均为函数对象提供更友好的重载和入参类型检查基于concept约束。以std::sort和ranges::sort的对比为例#include algorithm #include iostream #include vector using namespace std; int main() { vectorint vec{4, 2, 5, 3, 1}; sort(vec.begin(), vec.end()); // {1, 2, 3, 4, 5} for (const int i : vec) cout i , ; cout \n; ranges::sort(vec, ranges::greater{}); // {5, 4, 3, 2, 1} for (const int i : vec) cout i , ; return 0; }ranges::sort和sort的算法实现相同但提供了基于范围的重载使传参更为简洁。其他std命名空间下的算法多数也有对应的范围重载版本位于ranges命名空间中。使用范围入参再结合视图能在复杂操作中保持代码可读性。下面是一个综合示例——生成整数序列、分块、求笛卡尔积并折叠求和#include algorithm #include array #include iostream #include ranges using namespace std; int main() { const auto inputs views::iota(0u, 9u); // 生产 0 到 8 的整数序列 const auto chunks inputs | views::chunk(3); // 将序列分块每块 3 个元素 const auto cartesian_product views::cartesian_product(chunks, chunks); // 对块自身进行笛卡尔积 for (const auto [l_chunk, r_chunk] : cartesian_product) // 计算笛卡尔积下的两个块整数的和 cout ranges::fold_left(l_chunk, 0u, plus{}) ranges::fold_left(r_chunk, 0u, plus{}) ; }输出6 15 24 15 24 33 24 33 42。该示例综合运用了本文多个主题范围工厂iota、范围适配器chunk与cartesian_product、结构化绑定auto [l_chunk, r_chunk]、折叠fold_left与函数对象plus{}——可见 C20 的新特性在竞赛代码中是相互配合、整体使用的。参考本文主体内容基于 OI-wiki 的 new.md 整理扩充相关主题可进一步查阅Lambda 表达式Lambda 语法、捕获机制、递归与性能对比的完整讲解常量表达式 constexprC11const与constexpr的完整辨析与汇编级证据STL 排序函数对象作为排序比较器的实际应用打表技巧constexpr在竞赛打表中的典型用法仓库内的竞赛代码是学习这些新特性的最佳参考答案例如 WQS 二分系列代码std::tuple与结构化绑定、ETT 示例代码元组解包、基数排序代码constexpr常量以及 lsd.cpp范围for遍历等。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
