OI-wiki 实战指南深入理解 C STLstd::pair的初始化、比较与典型应用【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wikistd::pair是 C 标准库STL中用于将两个变量捆绑为一个「对」的类模板两个成员的数据类型可以不同。在 OI / ICPC 竞赛代码中pair几乎无处不在堆优化 Dijkstra 的距离与节点编号、离散化时的数值与下标、map的键值对、set::insert的返回值等都需要用它来承载「一组关联数据」。本文以 OI-wiki 的docs/lang/csl/pair.md为骨架结合仓库内竞赛代码与相邻章节系统讲解pair的定义、初始化、访问、比较、赋值与交换并给出离散化、Dijkstra、map三大实战范式帮助你写出更简洁、不易出错的竞赛代码。什么是std::pairstd::pair是定义在标准库utility头文件中的类模板在竞赛代码中通常随iostream、algorithm、queue等头文件间接引入。它将两个变量关联在一起组成一个「对」而且两个变量的数据类型可以是不同的例如pairint, double可以同时保存一个整数和一个浮点数。类模板class template说明类模板本身不是一个类而是可以根据不同数据类型产生不同类的「模板」。在使用时编译器会根据传入的数据类型产生对应的类再创建对应实例。模板属于 C 较为高级的语言特性在信息学竞赛中几乎不会要求手写模板如果对此感兴趣可以进一步阅读《C Primer》以学习更深层次的 C 知识。与自定义的struct相比pair不需要额外定义结构与重载运算符因此使用起来更加简便。OI-wiki 相关章节如 关联式容器、容器适配器大量以pair作为容器元素类型。同时也要知道它的局限自定义struct的变量命名往往更加清晰——pair只能使用first与second访问包含的两个变量如果需要将两个以上的变量进行关联自定义struct会更加合适此时pair只能通过嵌套如pairpairint,int,int实现可读性差。头文件与基本声明虽然pair正式定义于utility但在竞赛环境中几乎所有常用头文件都会间接包含它。为了可移植与规范建议显式引入#include utility声明一个pair的基本形式为std::pairType1, Type2 p;其中Type1、Type2可以是任意类型包括int、double、string甚至其他容器或自定义类型。仓库中的竞赛代码也大量使用类型别名来简化书写例如 Steiner 树代码 中#define mp make_pair using P pairint, int; using PP pairP, int;这里用using P pairint, int;为二维坐标建别名再用PP表示「坐标 状态」的复合对正是对pair灵活组合的典型使用。三种初始化方式1. 定义时直接初始化pairint, double p0(1, 2.0);构造函数直接接收两个参数first为1second为2.0。2. 先定义后赋值pairint, double p1; p1.first 1; p1.second 2.0;先调用默认构造函数生成一个空的pair再通过成员first、second逐一赋值。3. 使用std::make_pairstd::make_pair接受两个变量并返回由这两个变量组成的pair且可以自动推导类型pairint, double p2 make_pair(1, 2.0);一种在竞赛圈非常常用的写法是使用宏定义缩短调用#define mp make_pair之后即可写mp(1, 2.0)。仓库内不少代码采用这种风格例如 Steiner 树 SPFA 部分 中的P v mp(u.first dx[d], u.second dy[d]);在状态转移记录前驱时也直接使用pre[dv][s] mp(u, s);见同文件L43。C11 之后的auto搭配在 C11 以及之后的版本中make_pair可以配合auto使用以避免显式声明数据类型auto p3 make_pair(1, 2.0);此时p3的类型被自动推导为pairint, double。关于auto在信息学竞赛中的使用参见 迭代器 部分的说明该章节提到 NOI 系列比赛使用 C14已完整支持auto。成员访问first与second通过成员变量first与second可以访问pair中包含的两个变量int i p0.first; double d p0.second;也可以直接对其进行修改p1.first;在pair嵌套的场景中逐层访问的语义依然清晰例如PPpairP, int的u.first是一个坐标Pu.first.first才是坐标的横坐标这在 Steiner 树代码 的legal(u)、num(u)等函数中均有体现。内置比较运算符与字典序规则pair已经预先定义了所有的比较运算符包括、、、、、!。当然这需要组成pair的两个变量所属的数据类型定义了和/或运算符。比较规则为、、、四个运算符会先比较两个pair中的第一个变量在第一个变量相等的情况下再比较第二个变量、!要求两个变量分别相等对应地要求成员类型支持。例如if (p2 p3) { cout do something here endl; }这一内置的字典序比较规则是pair能被sort、priority_queue直接使用的根基。从 容器共同点 一节可知STL 容器间的比较本身也按字典序进行而map的每个元素在比较时可视为setpairkey, value这正说明pair的字典序语义与 STL 的整体设计一致。与 STL 容器 / 算法的配合由于pair定义了 STL 常用的与它能够很好地与其他 STL 函数或数据结构配合例如直接作为priority_queue的数据类型priority_queuepairint, double q;关于优先队列的完整用法底层容器、比较器、复杂度参见 容器适配器 中优先队列部分的说明默认top()返回最大值若希望返回最小值可将比较类型设为greaterTypeName不可跳过底层容器直接传入比较器。在 算法函数 中列出的sort、unique、lower_bound、upper_bound等函数都接受迭代器区间而pair数组或vectorpair...天然满足这些要求。此外set、map等关联式容器的insert返回值本身就是pairiterator, bool——其中迭代器指向已插入或已存在的元素bool表示是否插入成功详见 关联式容器 中的说明。赋值与交换可以将pair的值赋给另一个类型一致的pairp0 p1;也可以使用swap函数交换两个pair的值std::swap的自由函数形式和成员函数形式都可以swap(p0, p1); p2.swap(p3);应用举例离散化pair可以轻松实现离散化创建一个pair数组将原始数据的值作为每个pair的第一个变量将原始数据的位置作为第二个变量排序后将原始数据值的排名该值排序后所在的位置赋给该值原本所在的位置即可。// a为原始数据 pairint, int a[MAXN]; // ai为离散化后的数据 int ai[MAXN]; for (int i 0; i n; i) { // first为原始数据的值second为原始数据的位置 scanf(%d, a[i].first); a[i].second i; } // 排序 sort(a, a n); for (int i 0; i n; i) { // 将该值的排名赋给该值原本所在的位置 ai[a[i].second] i; }这里直接对pair数组调用sort(a, a n)正是利用了pair先比first、再比second的字典序规则——排序后每个pair的first升序second仍记录着原始下标从而一次性完成「按值排序 保留位置」两个需求。更精炼的同类场景在仓库中也有体现例如 环计数代码 中的make_pair(E[i].size(), i) make_pair(E[j].size(), j)通过把「主键 次键」打包进pair来实现自定义排序。堆优化 Dijkstra如前所述pair可以作为priority_queue的数据类型。在 Dijkstra 算法的堆优化中可以使用pair与priority_queue维护节点将节点当前到起点的距离作为第一个变量将节点编号作为第二个变量。由于pair先比较firstgreaterpairint,int会保证距离最小的节点先出堆。priority_queuepairint, int, std::vectorpairint, int, std::greaterpairint, int q; ... while (!q.empty()) { // dis为入堆时节点到起点的距离i为节点编号 int dis q.top().first, i q.top().second; q.pop(); ... }两点实践提示把距离放在first是因为比较优先级更高若想按节点编号优先只需交换first/second的存放内容入堆时务必使用「当前松弛后的距离」dis[u] w而取出时若发现q.top().first大于记录的dis[i]说明该元素是旧版本应跳过这是常见的防重入堆写法。pair 与 mapmap是 C 中存储键值对的数据结构。很多情况下map中存储的键值对通过pair向外暴露——向map插入元素的标准方式之一就是插入一个pairmapint, double m; m.insert(make_pair(1, 2.0));需要注意m.insert(...)在键已存在时会插入失败并返回false可通过返回的pairiterator, bool判断而使用下标m[key] value在键不存在时会自动插入一个新元素值为默认值频繁使用下标访问可能在容器中累积无意义元素影响效率因此高频查询场景更推荐find()详见 关联式容器。关于map更多的内容请见 关联式容器 与 无序关联式容器 中相关部分。仓库中也有直接以mappairint, int, int为数据结构的实例例如 二分图匹配代码以pair作为键存储计数。小结std::pair将两个任意类型的值捆绑为「对」通过first/second访问三种初始化方式构造、逐成员赋值、make_pair各有适用场景内置的字典序比较使pair可直接用于sort、priority_queue、set/map等 STL 组件离散化、堆优化 Dijkstra、map键值对是竞赛中最经典的三个pair应用场景建议结合 迭代器、关联式容器、容器适配器 等相邻章节综合掌握。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考