目录
一、核心容器
1. 序列式容器
(1) vector（动态数组）
(2) string（字符串）
2. 关联式容器
(1) map/unordered_map（键值对）
(2) set/unordered_set（集合）
3. 容器适配器（专用场景）
(1) stack（栈）
(2) queue（队列）
(3) priority_queue（优先队列 / 堆）
二、核心算法（ 头文件）
三、常用工具
1. pair（二元组）
2. bitset（位集）
![]()
一、核心容器
1. 序列式容器
(1) vector（动态数组）
竞赛中最常用的容器，替代普通数组，支持动态扩容，随机访问效率高。
#include <vector> #include <algorithm> using namespace std; int main() { // 1. 初始化 vector<int> v1; // 空向量 vector<int> v2(5, 0); // 5个元素，初始值0 vector<int> v3 = {1, 3, 2, 5, 4}; // 直接初始化 // 2. 核心操作（竞赛高频） v1.push_back(6); // 尾部添加元素（O(1) 均摊） v1.pop_back(); // 尾部删除元素（O(1)） v1.size(); // 获取元素个数 v1.empty(); // 判断是否为空 v1.clear(); // 清空 // 3. 排序（结合算法） sort(v3.begin(), v3.end()); // 升序排序（默认） sort(v3.begin(), v3.end(), greater<int>()); // 降序排序 // 4. 查找（有序vector可用） if (binary_search(v3.begin(), v3.end(), 3)) { // 二分查找元素是否存在（O(logn)） } // 5. 遍历（三种方式） for (int i = 0; i < v3.size(); i++) {} // 下标遍历 for (auto &x : v3) {} // 范围for（推荐） for (auto it = v3.begin(); it != v3.end(); it++) {} // 迭代器 return 0; }竞赛场景：存储输入数据、临时结果、图的邻接表等。
(2) string（字符串）
替代 char 数组，内置大量字符串操作，避免手动处理内存。
#include <string> using namespace std; int main() { string s1 = "abcde"; string s2 = "123"; // 核心操作 s1 += s2; // 拼接："abcde123" s1.length(); // 长度（等价于size()） s1.substr(1, 3); // 子串：从索引1开始，长度3 → "bcd" s1.find("cd"); // 查找子串位置，返回索引（找不到返回string::npos） s1.erase(2, 1); // 删除：从索引2开始，长度1 → "abde123" reverse(s1.begin(), s1.end()); // 反转字符串 // 字符访问 char c = s1[0]; // 下标访问（O(1)） return 0; }竞赛场景：字符串处理题（反转、匹配、拼接、子串）。
2. 关联式容器
(1) map/unordered_map（键值对）
map：红黑树实现，键有序，查找 / 插入 O (logn)；unordered_map：哈希表实现，键无序，平均查找 / 插入 O (1)（竞赛优先用）。
#include <map> #include <unordered_map> using namespace std; int main() { unordered_map<string, int> mp; // 核心操作 mp["apple"] = 5; // 插入键值对 mp.insert({"banana", 3}); // 另一种插入方式 // 查找键是否存在（竞赛核心） if (mp.find("apple") != mp.end()) { // 方式1：find int val = mp["apple"]; // 获取值 } // C++20+ 可用 mp.contains("apple") // 遍历 for (auto &p : mp) { // p.first 是键，p.second 是值 } mp.erase("banana"); // 删除指定键 mp.clear(); // 清空 return 0; }竞赛场景：统计元素出现次数、哈希映射（如字符串→数字、节点→权值）。
(2) set/unordered_set（集合）
set：有序无重复，红黑树实现；unordered_set：无序无重复，哈希表实现（竞赛优先）。
#include <unordered_set> using namespace std; int main() { unordered_set<int> st; st.insert(1); // 插入（自动去重） st.insert(2); st.insert(1); // 重复插入无效 // 查找元素 if (st.count(2)) { // count返回0/1，判断是否存在（推荐） // 元素存在 } st.erase(1); // 删除元素 return 0; }竞赛场景：去重、快速判断元素是否存在（如判断某个数是否在集合中）。
3. 容器适配器（专用场景）
(1) stack（栈）
后进先出（LIFO），核心操作push/pop/top。
#include <stack> using namespace std; int main() { stack<int> stk; stk.push(1); // 入栈 stk.push(2); stk.top(); // 获取栈顶元素（2） stk.pop(); // 出栈（无返回值） stk.empty(); // 判断是否为空 return 0; }竞赛场景：括号匹配、DFS 非递归实现、单调栈（求 Next Greater Element）。
(2) queue（队列）
先进先出（FIFO），核心操作push/pop/front/back。
#include <queue> using namespace std; int main() { queue<int> q; q.push(1); // 入队 q.push(2); q.front(); // 队首（1） q.back(); // 队尾（2） q.pop(); // 出队（无返回值） return 0; }(3) priority_queue（优先队列 / 堆）
默认大顶堆，可改为小顶堆，核心操作push/pop/top。
#include <queue> using namespace std; int main() { // 大顶堆（默认）：堆顶是最大值 priority_queue<int> max_heap; max_heap.push(3); max_heap.push(1); max_heap.top(); // 3 // 小顶堆：堆顶是最小值（竞赛高频） priority_queue<int, vector<int>, greater<int>> min_heap; min_heap.push(3); min_heap.push(1); min_heap.top(); // 1 max_heap.pop(); // 弹出堆顶 return 0; }竞赛场景：堆排序、TopK 问题（如找前 k 大 / 小元素）、贪心算法。
二、核心算法（<algorithm> 头文件）
竞赛中无需手动实现基础算法，直接调用 STL 算法，以下是高频用法：
| 算法函数 | 功能 | 时间复杂度 | 适用场景 |
|---|---|---|---|
| sort | 排序 | O(nlogn) | 所有序列式容器（vector/string） |
| reverse | 反转序列 | O(n) | 字符串 / 数组反转 |
| binary_search | 二分查找（有序序列） | O(logn) | 判断元素是否存在 |
| lower_bound/upper_bound | 有序序列找下界 / 上界 | O(logn) | 找第一个≥x / 第一个 > x 的位置 |
| max/min | 找两个数的最大 / 最小值 | O(1) | 快速比较 |
| max_element/min_element | 找序列最大 / 最小值 | O(n) | 找数组 /vector 的最值 |
| swap | 交换两个变量的值 | O(1) | 数据交换 |
示例：lower_bound/upper_bound
#include <vector> #include <algorithm> using namespace std; int main() { vector<int> v = {1, 2, 3, 3, 4, 5}; // 必须先排序 // lower_bound：第一个≥3的位置 → 索引2 auto it1 = lower_bound(v.begin(), v.end(), 3); // upper_bound：第一个>3的位置 → 索引4 auto it2 = upper_bound(v.begin(), v.end(), 3); // 统计3的个数：it2 - it1 → 2 return 0; }三、常用工具
1. pair（二元组）
存储一对值，无需手动定义结构体，竞赛中常用作返回值、临时存储。
#include <utility> using namespace std; int main() { pair<int, string> p1 = {1, "apple"}; pair<int, int> p2 = make_pair(2, 3); // 另一种初始化 // 访问 int a = p1.first; // 1 string s = p1.second; // "apple" // 排序：默认先比first，再比second vector<pair<int, int>> vp = {{3, 2}, {1, 5}, {3, 1}}; sort(vp.begin(), vp.end()); // 结果：(1,5), (3,1), (3,2) return 0; }竞赛场景：存储坐标（x,y）、带权值的元素（值，权）等。
2. bitset（位集）
高效处理二进制位操作，节省空间（1 位占 1bit，而非 1 字节）。
#include <bitset> using namespace std; int main() { bitset<8> bs; // 8位的位集，初始全0 bs.set(2); // 第2位设为1（00000100） bs.reset(2); // 第2位设为0 bs.flip(); // 所有位取反 bool b = bs.test(3); // 判断第3位是否为1 return 0; }竞赛场景：状态压缩、位运算优化（如状压 DP）。
