C++ 基础补全（一）
C++ 标准模板库（Standard Template Library, STL）包括容器、算法和迭代器等组件，提供了一系列通用的、可复用的算法和数据结构。
1. vector : 动态数组
vector<int> nums; // 空 vector
vector<int> a = {1, 2, 3}; // 初始化
vector<int> b(5, 0); // 5 个 0
vector<vector<int>> grid(3, vector<int>(4, 0)); // 3 行 4 列
常用操作：
nums.push_back(10); // 尾部添加
nums.pop_back(); // 删除末尾元素
nums.size(); // 元素个数
nums.empty(); // 是否为空
nums[0]; // 下标访问，不检查越界
nums.at(0); // 下标访问，会检查越界
nums.front(); // 第一个元素
nums.back(); // 最后一个元素
遍历：
for (int i = 0; i < nums.size(); ++i) {
cout << nums[i] << " ";
}
for (int x : nums) {
cout << x << " ";
}
}
常见复杂度：按下标访问 O(1)，尾部添加通常为均摊 O(1)，在中间插入或删除通常为 O(n)。
注意：访问 nums[i] 前要保证下标有效。vector 扩容时，之前保存的迭代器、指针或引用可能失效。
2. string : 字符串
string s = "hello";
s.size(); // 长度
s.empty(); // 是否为空
s[0]; // 字符访问
s.push_back('!'); // 末尾追加字符
s.pop_back(); // 删除末尾字符
s.substr(1, 3); // 从下标 1 开始，截取长度为 3 的子串
s.find("ll"); // 查找子串，找不到返回 string::npos
判断子串是否存在：
if (s.find("ll") != string::npos) {
// 找到了
}
遍历字符：
for (char c : s) {
// 处理 c
}
3. pair : 打包两个值
pair 常用于同时保存下标和值，或保存堆中的状态。
pair<int, int> p = {3, 7};
cout << p.first; // 3
cout << p.second; // 7
auto q = make_pair(3, 7);
pair 默认按字典序比较：先比较 first，相同时再比较 second。因此它可以直接用于排序、set 和 priority_queue。
4. unordered_map 和 unordered_set : 哈希表
unordered_map
保存“键 → 值”，常用于计数、记录下标和快速查找。
unordered_map<string, int> count;
count["apple"]++; // 计数
count["banana"] = 3; // 设置值
判断键是否存在：
if (count.find("apple") != count.end()) {
// 存在
}
注意：键不存在时，count[key] 会插入该键，并赋予默认值。因此只查询时优先使用 find；也可以使用 count(key) 判断是否存在。
两数之和示例：
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen; // 数值 -> 下标
for (int i = 0; i < static_cast<int>(nums.size()); ++i) {
int need = target - nums[i];
auto it = seen.find(need);
if (it != seen.end()) {
return {it->second, i};
}
seen[nums[i]] = i;
}
return {};
}
unordered_set
只保存不重复的元素，常用于快速判断元素是否出现过。
unordered_set<int> seen;
seen.insert(5);
seen.count(5); // 存在返回 1，不存在返回 0
seen.erase(5);
哈希表的查找和插入平均为 O(1)，但遍历顺序不固定。需要有序结果时使用 map 或 set。
5. map 和 set : 有序容器
map 和 set 会保持元素有序，查找、插入、删除通常为 O(log n)。
map<int, string> names;
names[2] = "Tom"; // 键 2 对应 "Tom"
set<int> values;
values.insert(10);
values.insert(3);
values.insert(10); // 不会重复存储
map：保存键值对，按键排序。set：保存唯一元素，并按元素排序。unordered_map、unordered_set：通常查找更快，但不保证顺序。
6. stack、queue 和 deque
stack : 后进先出
适合括号匹配、单调栈和模拟递归过程。
stack<int> st;
st.push(10);
st.push(20);
int x = st.top(); // 查看栈顶
st.pop(); // 删除栈顶；pop 不返回元素
st.empty();
st.size();
queue : 先进先出
常用于 BFS（广度优先搜索）。
queue<int> q;
q.push(10);
q.push(20);
int x = q.front(); // 查看队首
q.pop(); // 删除队首
deque : 双端队列
可以在两端增删，滑动窗口题中有时会用到。
deque<int> dq;
dq.push_back(3);
dq.push_front(1);
dq.pop_back();
dq.pop_front();
dq.front();
dq.back();
stack 和 queue 不支持下标访问，也不能像 vector 一样直接遍历内部元素。
7. priority_queue : 堆
默认是大顶堆，top() 返回最大值。
priority_queue<int> pq;
pq.push(3); // 添加元素
pq.push(10);
pq.push(5);
pq.empty(); // 检查堆是否为空
pq.size(); // 返回堆中元素数量
int largest = pq.top(); // 返回堆顶元素的值
pq.pop(); // 移除堆顶元素，不返回值
声明小顶堆：
priority_queue<int, vector<int>, greater<int>> minHeap;
常用于 Top K、合并有序数据和最短路径等问题。
存放 pair 时，小顶堆会按 pair 的默认字典序排列：
priority_queue<
pair<int, int>,
vector<pair<int, int>>,
greater<pair<int, int>>
> pq;
pq.push({5, 2});
pq.push({3, 8});
auto [value, index] = pq.top(); // 先按 value 排序
注意：priority_queue::pop() 只删除堆顶，不返回被删除的值。需要时先读取 top()。
8. 迭代器
begin() 指向容器第一个元素，end() 指向最后一个元素之后的位置，不是最后一个元素。
auto it = nums.begin();
if (it != nums.end()) {
cout << *it; // 解引用，读取迭代器指向的元素
}
许多 STL 算法用“起始迭代器 + 结束迭代器”表示处理范围：
sort(nums.begin(), nums.end());
9. 容器选择速查
| 需求 | 常用 STL |
|---|---|
| 连续数组、动态列表 | vector |
| 字符串 | string |
| 快速查找键和值 | unordered_map |
| 快速判断元素是否存在 | unordered_set |
| 要求元素有序 | map、set |
| 后进先出 | stack |
| 先进先出、BFS | queue |
| 两端增删、滑动窗口 | deque |
| 每次取最大或最小元素 | priority_queue |
10. 头文件和基本写法
本地练习时常见写法：
#include <bits/stdc++.h>
using namespace std;
bits/stdc++.h 会引入几乎所有常用标准库头文件，适合竞赛和练习。正式项目通常按需引入头文件，例如 <vector>、<unordered_map>、<algorithm>。
11. 常见易错点
stack、queue、priority_queue的pop()都不返回元素。unordered_map[key]查询不存在的键时会插入该键。lower_bound、upper_bound、binary_search要求数据已排序。vector下标从0开始；v[v.size()]越界。max_element、min_element返回迭代器，取值时需要解引用*。- 对大数求和或乘积时，注意使用
long long。 unordered_map的遍历顺序不固定，不要依赖它的输出顺序。