1
场景 → 结构:
2

3
"我需要根据 key 快速查 value"
4
  → 无序? → unordered_map (O(1))
5
  → 有序? → map (O(log n))
6

7
"我需要判断元素是否存在"
8
  → 无序? → unordered_set (O(1))
9
  → 有序? → set (O(log n))
10

11
"我需要按优先级取元素"
12
  → 只需最大/最小? → priority_queue (O(log n))
13
  → 需要修改优先级? → 手写堆 / std::set 模拟
14

15
"我需要维护一个滑动窗口的最值"
16
  → 单调队列 (deque) (O(1) 每次)
17

18
"我需要频繁在中间插入/删除"
19
  → 已知位置? → list (O(1))
20
  → 需要查找? → 跳表或平衡树 (O(log n))
21

22
"我需要后进先出"
23
  → stack
24

25
"我需要先进先出"
26
  → queue
27

28
"我需要两端都能操作"
29
  → deque
30

31
"我需要判断两个东西是否在同一组"
32
  → 并查集 (O(α(n)) ≈ O(1))
33

34
"我需要前缀搜索/自动补全"
35
  → Trie (O(m))
36

37
"我需要最短路径"
38
  → 无权图? → BFS
39
  → 有权图? → Dijkstra / A*
40
  → 有负权? → Bellman-Ford
41

42
"我需要连通所有节点"
43
  → MST: Kruskal / Prim
44

45
"我需要依赖排序"
46
  → 拓扑排序 (Kahn / DFS)

1
// ===== std::vector =====
2
#include <vector>
3
std::vector<int> v = {1, 2, 3};
4
v.push_back(4);          // 尾部追加 O(1) 均摊
5
v.pop_back();             // 尾部删除 O(1)
6
v[2];                     // 随机访问 O(1)
7
v.insert(v.begin(), 0);  // 头部插入 O(n) ← 慢!
8
v.erase(v.begin());      // 头部删除 O(n)
9
v.size(); v.empty();      // O(1)
10
v.reserve(1000);          // 预分配, 避免多次扩容
11
v.shrink_to_fit();        // 释放多余内存
12

13
// ===== std::deque =====
14
#include <deque>
15
std::deque<int> dq;
16
dq.push_front(1);        // 头部插入 O(1)
17
dq.push_back(2);          // 尾部插入 O(1)
18
dq.pop_front();           // 头部删除 O(1)
19
dq[0];                    // 随机访问 O(1) (但常数比 vector 大)
20

21
// ===== std::list =====
22
#include <list>
23
std::list<int> lst = {1, 2, 3};
24
lst.push_front(0);        // 头部插入 O(1)
25
lst.push_back(4);         // 尾部插入 O(1)
26
auto it = lst.begin();
27
lst.insert(it, 99);       // 任意位置插入 O(1)
28
lst.erase(it);            // 任意位置删除 O(1)
29
lst.splice(lst.begin(), lst, it);  // 移动节点 O(1)
30
// ❌ lst[0] → 不支持随机访问!
31

32
// ===== std::array =====
33
#include <array>
34
std::array<int, 5> arr = {1, 2, 3, 4, 5};  // 固定大小, 栈上
35
arr[2];                   // O(1), 和原生数组一样快
36
arr.size();               // 编译期常量, O(1)

1
// ===== std::map / std::set (红黑树, 有序) =====
2
#include <map>
3
#include <set>
4
std::map<std::string, int> m;
5
m["hello"] = 42;                     // 插入/更新 O(log n)
6
m.find("hello");                      // 查找 O(log n)
7
m.erase("hello");                     // 删除 O(log n)
8
m.lower_bound("h"); m.upper_bound("i"); // 范围查询 O(log n)
9
for (auto& [k, v] : m) { /* 有序遍历 */ }
10

11
std::set<int> s = {3, 1, 4, 1, 5};   // {1, 3, 4, 5} 自动排序去重
12

13
// ===== std::unordered_map / std::unordered_set (哈希, 无序) =====
14
#include <unordered_map>
15
#include <unordered_set>
16
std::unordered_map<std::string, int> um;
17
um["hello"] = 42;                     // 插入/更新 O(1) 均摊
18
um.find("hello");                      // 查找 O(1)
19
um.count("hello");                     // 0 或 1, O(1)
20
um.erase("hello");                     // 删除 O(1)
21
um.reserve(10000);                     // 预分配桶, 避免 rehash
22
// ❌ 不支持有序遍历和范围查询!
23

24
// ===== std::multimap / std::multiset (允许重复 key) =====
25
std::multiset<int> ms = {1, 1, 2, 3, 3, 3};
26
ms.count(3);  // 3

1
// ===== std::stack =====
2
#include <stack>
3
std::stack<int> stk;      // 底层默认 deque
4
stk.push(1);              // 入栈 O(1)
5
stk.top();                // 查看栈顶 O(1)
6
stk.pop();                // 出栈 O(1)
7

8
// ===== std::queue =====
9
#include <queue>
10
std::queue<int> q;        // 底层默认 deque
11
q.push(1);                // 入队 O(1)
12
q.front();                // 查看队头 O(1)
13
q.pop();                  // 出队 O(1)
14

15
// ===== std::priority_queue =====
16
#include <queue>
17
// 最大堆 (默认)
18
std::priority_queue<int> max_pq;
19
max_pq.push(3); max_pq.push(1); max_pq.push(4);
20
max_pq.top();   // 4 (最大值)
21

22
// 最小堆
23
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
24
min_pq.push(3); min_pq.push(1); min_pq.push(4);
25
min_pq.top();   // 1 (最小值)
26

27
// 自定义比较
28
auto cmp = [](const auto& a, const auto& b) { return a.cost > b.cost; };
29
std::priority_queue<Node, std::vector<Node>, decltype(cmp)> pq(cmp);