企业官网建设流程全解析

OI-wiki 实战指南：深入理解 C++ STLstd::pair的初始化、比较与典型应用

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

std::pair是 C++ 标准库（STL）中用于将两个变量捆绑为一个「对」的类模板，两个成员的数据类型可以不同。在 OI / ICPC 竞赛代码中，pair几乎无处不在：堆优化 Dijkstra 的距离与节点编号、离散化时的数值与下标、map的键值对、set::insert的返回值等，都需要用它来承载「一组关联数据」。本文以 OI-wiki 的docs/lang/csl/pair.md为骨架，结合仓库内竞赛代码与相邻章节，系统讲解pair的定义、初始化、访问、比较、赋值与交换，并给出离散化、Dijkstra、map三大实战范式，帮助你写出更简洁、不易出错的竞赛代码。

什么是std::pair

std::pair是定义在标准库<utility>头文件中的类模板（在竞赛代码中通常随<iostream>、<algorithm>、<queue>等头文件间接引入）。它将两个变量关联在一起组成一个「对」，而且两个变量的数据类型可以是不同的，例如pair<int, double>可以同时保存一个整数和一个浮点数。

类模板（class template）说明：类模板本身不是一个类，而是可以根据不同数据类型产生不同类的「模板」。在使用时，编译器会根据传入的数据类型产生对应的类，再创建对应实例。模板属于 C++ 较为高级的语言特性，在信息学竞赛中几乎不会要求手写模板；如果对此感兴趣，可以进一步阅读《C++ Primer》以学习更深层次的 C++ 知识。

与自定义的struct相比，pair不需要额外定义结构与重载运算符，因此使用起来更加简便。OI-wiki 相关章节（如 关联式容器、容器适配器）大量以pair作为容器元素类型。同时也要知道它的局限：

• 自定义struct的变量命名往往更加清晰——pair只能使用first与second访问包含的两个变量；
• 如果需要将两个以上的变量进行关联，自定义struct会更加合适（此时pair只能通过嵌套如pair<pair<int,int>,int>实现，可读性差）。

头文件与基本声明

虽然pair正式定义于<utility>，但在竞赛环境中，几乎所有常用头文件都会间接包含它。为了可移植与规范，建议显式引入：

#include <utility>

声明一个pair的基本形式为：

std::pair<Type1, Type2> p;

其中Type1、Type2可以是任意类型，包括int、double、string，甚至其他容器或自定义类型。仓库中的竞赛代码也大量使用类型别名来简化书写，例如 Steiner 树代码 中：

#define mp make_pair using P = pair<int, int>; using PP = pair<P, int>;

这里用using P = pair<int, int>;为二维坐标建别名，再用PP表示「坐标 + 状态」的复合对，正是对pair灵活组合的典型使用。

三种初始化方式

1. 定义时直接初始化

pair<int, double> p0(1, 2.0);

构造函数直接接收两个参数，first为1，second为2.0。

2. 先定义后赋值

pair<int, double> p1; p1.first = 1; p1.second = 2.0;

先调用默认构造函数生成一个空的pair，再通过成员first、second逐一赋值。

3. 使用std::make_pair

std::make_pair接受两个变量，并返回由这两个变量组成的pair，且可以自动推导类型：

pair<int, 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）。

C++11 之后的auto搭配

在 C++11 以及之后的版本中，make_pair可以配合auto使用，以避免显式声明数据类型：

auto p3 = make_pair(1, 2.0);

此时p3的类型被自动推导为pair<int, double>。关于auto在信息学竞赛中的使用，参见 迭代器 部分的说明（该章节提到 NOI 系列比赛使用 C++14，已完整支持auto）。

成员访问：first与second

通过成员变量first与second，可以访问pair中包含的两个变量：

int i = p0.first; double d = p0.second;

也可以直接对其进行修改：

p1.first++;

在pair嵌套的场景中，逐层访问的语义依然清晰：例如PP（pair<P, int>）的u.first是一个坐标P，u.first.first才是坐标的横坐标，这在 Steiner 树代码 的legal(u)、num(u)等函数中均有体现。

内置比较运算符与字典序规则

pair已经预先定义了所有的比较运算符，包括<、>、<=、>=、==、!=。当然，这需要组成pair的两个变量所属的数据类型定义了==和/或<运算符。

比较规则为：

• <、>、<=、>=四个运算符会先比较两个pair中的第一个变量，在第一个变量相等的情况下再比较第二个变量；
• ==、!=要求两个变量分别相等（对应地要求成员类型支持==）。

例如：

if (p2 >= p3) { cout << "do something here" << endl; }

这一内置的字典序比较规则是pair能被sort、priority_queue直接使用的根基。从 容器共同点 一节可知，STL 容器间的比较本身也按字典序进行，而map的每个元素在比较时可视为set<pair<key, value>>，这正说明pair的字典序语义与 STL 的整体设计一致。

与 STL 容器 / 算法的配合

由于pair定义了 STL 常用的<与==，它能够很好地与其他 STL 函数或数据结构配合，例如直接作为priority_queue的数据类型：

priority_queue<pair<int, double>> q;

关于优先队列的完整用法（底层容器、比较器、复杂度），参见 容器适配器 中优先队列部分的说明：默认top()返回最大值，若希望返回最小值可将比较类型设为greater<TypeName>；不可跳过底层容器直接传入比较器。

在 算法函数 中列出的sort、unique、lower_bound、upper_bound等函数都接受迭代器区间，而pair数组或vector<pair<...>>天然满足这些要求。此外，set、map等关联式容器的insert返回值本身就是pair<iterator, bool>——其中迭代器指向已插入（或已存在）的元素，bool表示是否插入成功，详见 关联式容器 中的说明。

赋值与交换

可以将pair的值赋给另一个类型一致的pair：

p0 = p1;

也可以使用swap函数交换两个pair的值，std::swap的自由函数形式和成员函数形式都可以：

swap(p0, p1); p2.swap(p3);

应用举例

离散化

pair可以轻松实现离散化：创建一个pair数组，将原始数据的值作为每个pair的第一个变量，将原始数据的位置作为第二个变量；排序后，将原始数据值的排名（该值排序后所在的位置）赋给该值原本所在的位置即可。

// a为原始数据 pair<int, 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先比较first，greater<pair<int,int>>会保证距离最小的节点先出堆。

priority_queue<pair<int, int>, std::vector<pair<int, int>>, std::greater<pair<int, 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 与 map

map是 C++ 中存储键值对的数据结构。很多情况下，map中存储的键值对通过pair向外暴露——向map插入元素的标准方式之一就是插入一个pair：

map<int, double> m; m.insert(make_pair(1, 2.0));

需要注意：m.insert(...)在键已存在时会插入失败并返回false（可通过返回的pair<iterator, bool>判断）；而使用下标m[key] = value在键不存在时会自动插入一个新元素（值为默认值），频繁使用下标访问可能在容器中累积无意义元素，影响效率，因此高频查询场景更推荐find()，详见 关联式容器。

关于map更多的内容，请见 关联式容器 与 无序关联式容器 中相关部分。仓库中也有直接以map<pair<int, 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