C++ STL 常用容器详解：Vector、Pair 到 Map 实战

排序规则

pair 支持比较运算，排序时按字典序进行：以 first 为第一关键字，second 为第二关键字。若需存储三个属性，可嵌套使用，如 pair<int, pair<int, int>>。

String：字符串封装

C++ 对字符串进行了面向对象封装，提供了便捷的接口。

• size()/length(): 返回字符串长度
• substr(起始下标，子串长度): 截取子串
• c_str(): 返回 C 风格字符串指针

线性容器：Queue、Stack、Deque

Queue 队列

遵循先进先出（FIFO）原则。

• push(): 向队尾插入
• pop(): 弹出队头
• front()/back(): 访问队头/队尾

Stack 栈

遵循后进先出（LIFO）原则。

• push(): 向栈顶插入
• pop(): 弹出栈顶
• top(): 返回栈顶元素

Deque 双端队列

deque 是加强版的 vector，支持两端高效插入和删除。虽然功能强大，但在某些极端场景下性能略逊于 vector，实际使用中需根据需求权衡。

Priority Queue：优先队列

优先队列默认是大根堆，即每次弹出的都是当前最大值。其底层通常由 vector 和 heap 算法实现。

构造小根堆

若需要小根堆（每次弹出最小值），有两种常见方式：

1. 插入时直接存入负值。
2. 定义时指定比较函数：

#include <queue>
#include <functional>

// 方法二：使用 greater 定义小根堆
priority_queue<int, vector<int>, greater<int>> q;

Set 与 Map：有序关联容器

set、multiset、map、multimap 基于平衡二叉树（红黑树）实现，动态维护有序序列。

• 时间复杂度：所有操作均为 O(log n)
• 去重性：set/map 不允许重复键，multiset/multimap 允许
• 迭代器：支持 ++/-- 返回前驱和后继
• 查找：lower_bound(x) 返回大于等于 x 的最小元素迭代器；upper_bound(x) 返回大于 x 的最小元素迭代器

#include <map>
map<int, string> m;
m.insert({1, "one"});
// 查找
auto it = m.find(1);
if (it != m.end()) {
    cout << it->second << endl;
}

Unordered 系列：哈希表容器

unordered_set、unordered_map 等基于哈希表实现。

• 优势：增删改查平均时间复杂度为 O(1)
• 劣势：不支持 lower_bound/upper_bound，迭代器不支持 ++/-- 顺序遍历
• 适用场景：对顺序无要求，追求极致查询速度时

常用 API 速查表

掌握这些容器的特性，能帮助你在图论、动态规划等算法场景中做出更优的数据结构设计选择。