麦地

Back

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();  // 错误
cpp

1.2 两个值的类型可以不同#

pair<string, int> student = {"Alice", 90};
pair<long long, int> state = {distance, node};
pair<int, string> item = {1, "abc"};
cpp

pair<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};
cpp

2.2 修改与整体赋值#

p.first = x;
p.second = y;
p = {x + 1, y + 1};
cpp

2.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);
cpp

make_pair 会对参数类型进行推导和 decay(退化),并不总是得到你想象的类型:

auto p1 = make_pair(1, 2);      // pair<int, int>
auto p2 = make_pair("abc", 1);  // 通常得到 const char* 与 int,而不是 string
cpp

需要拥有字符串内容时明确构造:

pair<string, int> p = {"abc", 1};
cpp

make_pair 默认生成值成员,不会自动保存普通引用。确需引用包装时可使用 std::ref / std::cref,但竞赛中通常直接传引用或使用指针更清晰。


3. 访问、拷贝与交换#

3.1 直接访问#

int x = p.first;
int y = p.second;
cpp

3.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 仍为 1
cpp

pair 本身不会额外申请一段动态数组,但成员如果是 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;
cpp

4.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; // 只修改副本
}
cpp

4.3 std::tie:给已有变量赋值#

int x, y;
tie(x, y) = p;
cpp

忽略某个返回值:

tie(x, ignore) = p;
cpp

结构化绑定会声明新变量;tie 使用已经存在的变量。竞赛新代码通常优先结构化绑定。


5. 比较规则:字典序#

pair 的关系运算按字典序进行:

  1. 先比较 first。
  2. 只有 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'; // 1
cpp

常见应用:

  • 按第一关键字、第二关键字排序。
  • 同时维护“最优值 + 编号”。
  • 让堆按第一关键字,再按第二关键字决定优先级。
  • 用 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;        // 正确
cpp

6.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;
cpp

7.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 中的典型应用#

这里 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';
}
cpp

key 是 const,不能通过遍历修改:

for (auto &p : mp) {
    // p.first = "new"; // 错误:key 为 const
    p.second = 100;     // 可以修改 mapped value
}
cpp

9.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;
cpp

pair 自带字典序比较,所以可作为有序容器键。二维坐标去重、状态集合、边集合都可以这样表示。

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);
cpp

pair 的内存布局、大小和对齐由编译器及成员类型决定,不要假定它一定恰好等于两个成员大小之和,因为可能存在对齐填充。


13. 高频错误与避坑清单#

13.1 给 first/second 加括号#

// p.first(); // 错
p.first;      // 对
cpp

13.2 误以为默认排序只看 first#

默认排序是完整字典序:first 相同时还会比较 second。若只想按 first,或第二关键字有不同规则,应自定义比较器。

13.3 忘记 priority_queue 默认是大根堆#

priority_queue<PII> pq1; // 大根堆
priority_queue<PII, vector<PII>, greater<PII>> pq2; // 小根堆
cpp

13.4 结构化绑定意外复制#

for (auto [x, y] : a) {
    x = 0; // 不影响 a
}

for (auto &[x, y] : a) {
    x = 0; // 修改 a
}
cpp

13.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. 一页速记#

最终必须牢牢记住:

  1. pair 是两个值的组合,first/second 是成员变量。
  2. 默认比较和排序先 first,后 second。
  3. priority_queue<pair<...>> 默认是大根堆。
  4. 结构化绑定加 auto& 才能通过绑定修改原 pair。
  5. 带权图、坐标等场景要明确两个成员的语义顺序。
  6. 三个及以上值通常考虑 tuple;字段语义复杂时考虑 struct。
  7. map 的元素是 pair<const Key,T>,key 不能原地修改。
  8. 排序比较器使用 </>,不要用可能溢出的减法。
Comment seems to stuck. Try to refresh?✨