1. 核心概念#
1.1 基本定义#
#include <utility>
std::pair<int, int> p = {1, 2};cpp竞赛常用写法:
#include <bits/stdc++.h>
using namespace std;
pair<int, int> p = {1, 2};cpp两个公开成员:
p.first = 10; // 第一个值
p.second = 20; // 第二个值cpp注意:first 和 second 是成员变量,不是成员函数,没有括号。
cout << p.first << ' ' << p.second;
// p.first(); // 错误
// p.second(); // 错误cpp1.2 两个值的类型可以不同#
pair<string, int> student = {"Alice", 90};
pair<long long, int> state = {distance, node};
pair<int, string> item = {1, "abc"};cpppair<T1, T2> 只负责把两个值放在一起,不会自动堆排序、不会自动管理键值映射,也不会动态增长。
1.3 常用类型别名#
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
using PLI = pair<long long, int>;
using PSI = pair<string, int>;cpp别名能显著减少竞赛代码中的重复类型名,但看到别名时必须明确两个成员的实际类型。
2. 创建与初始化#
2.1 常见写法#
pair<int, int> a; // 默认构造
pair<int, int> b{}; // 值初始化,两个 int 都为 0
pair<int, int> c(1, 2); // {1, 2}
pair<int, int> d = {3, 4}; // {3, 4}
pair<int, int> e = make_pair(5, 6);
pair<int, int> f(c); // 拷贝构造cpp竞赛中推荐直接写:
PII p = {x, y};cpp2.2 修改与整体赋值#
p.first = x;
p.second = y;
p = {x + 1, y + 1};cpp2.3 C++17 类模板参数推导#
pair p1(1, 2); // pair<int, int>
pair p2(string("a"), 3); // pair<string, int>cpp在需要明确类型、接口声明或跨标准兼容时,仍建议写出完整类型或使用别名。
2.4 make_pair 的类型推导#
auto p = make_pair(x, y);cppmake_pair 会对参数类型进行推导和 decay(退化),并不总是得到你想象的类型:
auto p1 = make_pair(1, 2); // pair<int, int>
auto p2 = make_pair("abc", 1); // 通常得到 const char* 与 int,而不是 stringcpp需要拥有字符串内容时明确构造:
pair<string, int> p = {"abc", 1};cppmake_pair 默认生成值成员,不会自动保存普通引用。确需引用包装时可使用 std::ref / std::cref,但竞赛中通常直接传引用或使用指针更清晰。
3. 访问、拷贝与交换#
3.1 直接访问#
int x = p.first;
int y = p.second;cpp3.2 std::get#
pair 也支持 tuple 风格访问:
int x = get<0>(p);
int y = get<1>(p);
get<0>(p) = 10;cpp竞赛中最常用的是 first/second 和结构化绑定;get 在泛型代码或嵌套模板中更有价值。
3.3 拷贝是成员级复制#
PII a = {1, 2};
PII b = a;
b.first = 100;
// a.first 仍为 1cpppair 本身不会额外申请一段动态数组,但成员如果是 string、vector 等类型,复制 pair 就会复制这些成员,成本由成员类型决定。
3.4 交换#
a.swap(b);
// 或 swap(a, b);cpp交换两个 pair 的全部成员。
4. 结构化绑定与 tie#
4.1 C++17 结构化绑定:最常用#
PII p = {3, 4};
auto [x, y] = p;
cout << x << ' ' << y;cpp默认 auto [x, y] 会复制两个成员。若需要修改原 pair:
auto &[x, y] = p;
x = 10;
y = 20;cpp只读且避免复制:
const auto &[x, y] = p;cpp4.2 遍历时使用结构化绑定#
vector<PII> a = {{1, 2}, {3, 4}};
for (const auto &[x, y] : a) {
cout << x << ' ' << y << '\n';
}
for (auto &[x, y] : a) {
cin >> x >> y;
}cpp以下写法会复制 pair,修改不会影响原数组:
for (auto [x, y] : a) {
x = 10; // 只修改副本
}cpp4.3 std::tie:给已有变量赋值#
int x, y;
tie(x, y) = p;cpp忽略某个返回值:
tie(x, ignore) = p;cpp结构化绑定会声明新变量;tie 使用已经存在的变量。竞赛新代码通常优先结构化绑定。
5. 比较规则:字典序#
pair 的关系运算按字典序进行:
- 先比较
first。 - 只有
first相等,才比较second。
PII a = {1, 9};
PII b = {2, 0};
PII c = {2, 3};
cout << (a < b) << '\n'; // 1,因为 1 < 2
cout << (b < c) << '\n'; // 1,因为 first 相等,0 < 3
cout << (b == PII{2, 0}) << '\n'; // 1cpp常见应用:
- 按第一关键字、第二关键字排序。
- 同时维护“最优值 + 编号”。
- 让堆按第一关键字,再按第二关键字决定优先级。
- 用 pair 表示可比较状态。
示例:寻找最小值,若相同则取编号较小者:
PII best = {a[0], 0};
for (int i = 1; i < (int)a.size(); ++i) {
best = min(best, PII{a[i], i});
}cpp因为 pair 默认先比较值,再比较编号,所以一次 min 就完成了两级规则。
6. pair 与排序#
6.1 默认排序#
vector<PII> a = {{2, 3}, {1, 5}, {2, 1}};
sort(a.begin(), a.end());cpp结果:
(1,5) (2,1) (2,3)text默认规则是:先按 first 升序,再按 second 升序。
6.2 按 second 排序#
sort(a.begin(), a.end(), [](const PII &x, const PII &y) {
if (x.second != y.second) return x.second < y.second;
return x.first < y.first;
});cpp表示先按第二关键字升序,相同再按第一关键字升序。
6.3 降序#
sort(a.begin(), a.end(), [](const PII &x, const PII &y) {
if (x.first != y.first) return x.first > y.first;
return x.second > y.second;
});cpp不要使用减法代替比较:
// return x.first - y.first < 0; // 可能整数溢出,不推荐
return x.first < y.first; // 正确cpp6.4 greater<PII>#
sort(a.begin(), a.end(), greater<PII>());cpp得到完整字典序降序:先按 first 降序,再按 second 降序。它不是“只按 first 降序”。
6.5 稳定性#
sort 不稳定。若两个元素在自定义规则下等价,并要求保留输入顺序,可使用 stable_sort,或把原编号作为额外比较关键字。
7. pair 与 vector:最常见的组合#
7.1 存储坐标、区间、边#
vector<PII> point(n); // {x, y}
vector<PII> segment(n); // {l, r}
vector<PII> edge(m); // {u, v}cpp读入:
for (auto &[x, y] : point) cin >> x >> y;cpp访问:
cout << point[i].first << ' ' << point[i].second;cpp7.2 带权邻接表#
int n, m;
cin >> n >> m;
vector<vector<PII>> g(n + 1);
for (int i = 0; i < m; ++i) {
int u, v, w;
cin >> u >> v >> w;
g[u].push_back({v, w});
// g[v].push_back({u, w}); // 无向图再加反向边
}cpp遍历:
for (auto [v, w] : g[u]) {
// 边 u -> v,权值 w
}cpp这里 {v, w} 的成员含义由程序员约定,编译器不知道 first 是节点还是权值。全队必须保持统一约定,例如始终使用 {to, weight}。
7.3 添加元素#
vector<PII> a;
a.push_back({x, y});
a.emplace_back(x, y);
a.push_back(make_pair(x, y));cpp对 pair<int,int>,三者通常没有值得关注的性能差别;push_back({x,y}) 最简洁。
8. pair 与 priority_queue#
8.1 默认大根堆#
priority_queue<PII> pq;
pq.push({3, 10});
pq.push({5, 2});
pq.push({5, 1});
auto [value, id] = pq.top(); // {5,2}cpp默认按字典序取最大值:first 大者优先;first 相同则 second 大者优先。
8.2 小根堆#
priority_queue<PII, vector<PII>, greater<PII>> pq;cpp此时 first 小者优先;first 相同则 second 小者优先。
8.3 常见状态设计#
pair<long long, int>{distance, node} // 最短路:距离 + 节点
pair<int, int>{priority, id} // 优先级 + 编号
pair<int, int>{value, index} // 数值 + 原下标cpp把最重要的排序键放在 first,可以直接利用默认比较规则。
8.4 Dijkstra 中的典型应用#
using State = pair<long long, int>; // {dist, node}
int n, m, s;
// g 为 vector<vector<PII>>,每条边为 {v, w}
vector<long long> dist(n + 1, LLONG_MAX / 4);
priority_queue<State, vector<State>, greater<State>> pq;
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if (d != dist[u]) continue; // 丢弃过期堆状态
for (auto [v, w] : g[u]) {
if (d + w < dist[v]) {
dist[v] = d + w;
pq.push({dist[v], v});
}
}
}cpp这里 pair 的第一成员是距离,因此 greater<State> 可以直接构造按距离的小根堆。第二成员相同距离下的节点编号顺序通常不影响最短路结果。
9. pair 与 map、set#
9.1 map 的键值对#
map<Key, T> 的元素类型为:
pair<const Key, T>cpp因此:
map<string, int> mp;
mp["a"] = 1;
mp.insert({"b", 2});
for (const auto &[key, value] : mp) {
cout << key << ' ' << value << '\n';
}cppkey 是 const,不能通过遍历修改:
for (auto &p : mp) {
// p.first = "new"; // 错误:key 为 const
p.second = 100; // 可以修改 mapped value
}cpp9.2 insert 的返回值#
auto [it, inserted] = mp.insert({"a", 10});cpp返回类型为 pair<iterator, bool>:
it指向插入的新元素或已存在的同 key 元素。inserted表示是否真正插入。
如果 key 已存在,map::insert 不会覆盖旧 value。
9.3 pair 作为 set/map 的键#
set<PII> st;
st.insert({x, y});
map<PII, int> mp;
mp[{x, y}] = 1;cpppair 自带字典序比较,所以可作为有序容器键。二维坐标去重、状态集合、边集合都可以这样表示。
set<PII> 中遍历元素得到的是 const pair,不允许原地修改 key;需要修改时通常先删除旧值再插入新值。
10. 用 pair 返回两个结果#
PII getMinMax(const vector<int> &a) {
int mn = a[0], mx = a[0];
for (int x : a) {
mn = min(mn, x);
mx = max(mx, x);
}
return {mn, mx};
}
auto [mn, mx] = getMinMax(a);cpp优点:
- 不必通过两个输出参数返回。
- 调用处可直接结构化绑定。
- pair 的比较规则还能表达组合最优解。
该函数示例要求 a 非空;真实代码需先处理空数组。
标准库中也有返回 pair 的接口,例如:
auto [mnIt, mxIt] = minmax_element(a.begin(), a.end());cpp返回的是两个迭代器组成的 pair;空区间时不要解引用。
11. 嵌套 pair 与 tuple 的选择#
可以嵌套:
pair<int, PII> p = {1, {2, 3}};
cout << p.first;
cout << p.second.first;
cout << p.second.second;cpp但多层嵌套可读性较差:
pair<PII, PII> rect = {{x1, y1}, {x2, y2}};cpp三个及以上值通常优先考虑:
tuple<int, int, int> t = {x, y, z};
auto [a, b, c] = t;cpp或自定义结构体:
struct Edge {
int u, v, w;
};cpp选择建议:
- 两个通用值且成员语义直观:pair。
- 三个及以上通用值:tuple。
- 字段有明确业务含义、需要函数或更清晰的代码:struct。
- 坐标、最短路堆状态、
{to, weight}:pair 在竞赛中非常方便。
12. 复杂度与性能#
pair 本身没有动态长度,也没有类似 vector/string 的扩容机制。
| 操作 | 成本 |
|---|---|
构造、读取 first/second |
通常为 O(1),另加成员构造/读取成本 |
| 拷贝 pair | 两个成员的复制成本 |
| 移动 pair | 两个成员的移动成本 |
| 比较 pair | 最坏比较两个成员 |
swap |
两个成员的交换成本 |
| 排序 n 个 pair | 通常 O(n log n) 次比较 |
| 作为堆元素 push/pop | 堆操作为 O(log n),另加元素操作成本 |
pair<int,int> 通常只是两个 int 的组合,复制成本很低。pair<string, vector<int>> 的复制可能很贵,只读传参和遍历应使用 const 引用:
void f(const pair<string, vector<int>> &p);cpppair 的内存布局、大小和对齐由编译器及成员类型决定,不要假定它一定恰好等于两个成员大小之和,因为可能存在对齐填充。
13. 高频错误与避坑清单#
13.1 给 first/second 加括号#
// p.first(); // 错
p.first; // 对cpp13.2 误以为默认排序只看 first#
默认排序是完整字典序:first 相同时还会比较 second。若只想按 first,或第二关键字有不同规则,应自定义比较器。
13.3 忘记 priority_queue 默认是大根堆#
priority_queue<PII> pq1; // 大根堆
priority_queue<PII, vector<PII>, greater<PII>> pq2; // 小根堆cpp13.4 结构化绑定意外复制#
for (auto [x, y] : a) {
x = 0; // 不影响 a
}
for (auto &[x, y] : a) {
x = 0; // 修改 a
}cpp13.5 混淆 first 与 second 的含义#
例如带权边 {v,w} 与 {w,v} 都可以编译,但意义完全不同。选择一种约定并始终一致,必要时使用结构体减少歧义。
13.6 通过 map/set 的元素修改 key#
有序关联容器的 key 不可直接修改。map 可以修改 second,不能修改 first。
13.7 比较器写错或发生溢出#
// return x.second - y.second < 0; // 不推荐
return x.second < y.second; // 正确cpp比较器必须满足严格弱序;不能对相等元素返回 true,例如升序比较器应写 <,不能写 <=。
13.8 make_pair 推导出非预期类型#
尤其是字符串字面量、数组和需要引用的场景。需要明确类型时直接写 pair<T1,T2>{x,y}。
13.9 不同 pair 类型不能混作同一别名#
pair<int, long long>
pair<long long, int>cpp虽然有时可以转换构造,但它们是不同类型,成员顺序也不同。不要依赖隐式转换掩盖设计错误。
14. 一页速记#
#include <utility>
using PII = pair<int, int>;
using PLL = pair<long long, long long>;
PII p{}; // {0,0}
PII q = {1, 2};
auto r = make_pair(3, 4);
p.first = 10; // 成员变量,无括号
p.second = 20;
p = {x, y};
q.swap(p);
auto [x, y] = q; // 拷贝
auto &[rx, ry] = q; // 引用,可修改 q
const auto &[cx, cy] = q; // 只读引用
int a = get<0>(q);
q < p; // 先 first,再 second
q == p;
vector<PII> v(n);
v.push_back({x, y});
v.emplace_back(x, y);
for (auto &[x, y] : v) cin >> x >> y;
sort(v.begin(), v.end()); // first 升序,再 second 升序
sort(v.begin(), v.end(), greater<PII>()); // 完整字典序降序
sort(v.begin(), v.end(), [](const PII &a, const PII &b) {
if (a.second != b.second) return a.second < b.second;
return a.first < b.first;
});
vector<vector<PII>> g(n + 1); // 带权邻接表
g[u].push_back({v, w});
for (auto [to, weight] : g[u]) {}
priority_queue<PII> maxHeap;
priority_queue<PII, vector<PII>, greater<PII>> minHeap;
maxHeap.push({value, id});
auto [value2, id2] = maxHeap.top();
maxHeap.pop();
map<string, int> mp;
for (const auto &[key, value] : mp) {}
auto [it, inserted] = mp.insert({key, value});cpp最终必须牢牢记住:
- pair 是两个值的组合,
first/second是成员变量。 - 默认比较和排序先 first,后 second。
priority_queue<pair<...>>默认是大根堆。- 结构化绑定加
auto&才能通过绑定修改原 pair。 - 带权图、坐标等场景要明确两个成员的语义顺序。
- 三个及以上值通常考虑 tuple;字段语义复杂时考虑 struct。
- map 的元素是
pair<const Key,T>,key 不能原地修改。 - 排序比较器使用
</>,不要用可能溢出的减法。