[c++] STL概括

STL 是 C++ 标准库的核心，包含容器、迭代器、算法、函数对象四大组件。对于 OI 竞赛，熟练掌握 STL 可以大幅减少代码量、降低调试难度，是提升代码效率和准确率的关键。

一、常用容器（Container）
1. 序列容器


容器
特点
常用操作
时间复杂度
vector<T>
动态数组，支持随机访问
push_back(), pop_back(), [], size(), resize()
末尾增删 O(1)，中间 O(n)
deque<T>
双端队列，头尾快速增删
push_front(), pop_front(), push_back(), pop_back()
头尾 O(1)
list<T>
双向链表，不支持随机访问
push_back(), push_front(), insert(), erase()
任意位置 O(1)（需迭代器）
array<T,N>
固定大小数组，比原生数组安全
at(), [], size()
O(1)
重点掌握：vector（最常用，替代数组）和 deque（用于滑动窗口等）。
2. 关联容器（基于红黑树，自动排序）


容器
特点
常用操作
时间复杂度
set<T>
有序集合，元素唯一
insert(), erase(), find(), lower_bound(), upper_bound()
O(log n)
multiset<T>
有序集合，允许重复
同上
O(log n)
map<K,V>
有序映射，键唯一
[], insert(), find(), erase()
O(log n)
multimap<K,V>
有序映射，键可重复
不支持 []，其余类似
O(log n)
重点掌握：set（去重、有序维护）、map（键值对，如统计频次）。
3. 无序关联容器（基于哈希表，平均 O(1)）


容器
特点
注意事项
unordered_set<T>
无序集合
需要提供 hash 函数（内置类型已支持）
unordered_map<K,V>
无序映射
同左，常用于 O(1) 查询
竞赛建议：默认用 map/set，除非 TLE 且确认哈希不冲突，再换成 unordered_*。
4. 容器适配器（封装其他容器）


适配器
底层默认容器
常用操作
特点
stack<T>
deque<T>
push(), pop(), top(), empty(), size()
后进先出
queue<T>
deque<T>
push(), pop(), front(), back()
先进先出
priority_queue<T>
vector<T>
push(), pop(), top()
最大堆（默认），可自定义比较
重点掌握：stack（DFS 非递归、括号匹配）、queue（BFS）、priority_queue（Dijkstra、哈夫曼树）。

二、迭代器（Iterator）
迭代器像指针，用于遍历容器中的元素。
常用操作
cpp

复制


下载

vector<int> v = {1,2,3};
for (auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; // 正向迭代
for (auto it = v.rbegin(); it != v.rend(); ++it) cout << *it << " "; // 反向迭代


• begin() / end()：指向首元素和尾后位置
• rbegin() / rend()：反向迭代器
• *it：访问元素
• it++：移动到下一个位置
迭代器失效（重要）
• vector / deque 在插入、删除时可能导致迭代器失效（重新分配内存）。
• 保险做法：插入/删除后重新获取迭代器，或使用下标而非迭代器。

三、常用算法（Algorithm）
<algorithm> 头文件提供了大量通用算法。


函数
作用
示例
sort(beg, end, cmp)
排序（默认升序）
sort(v.begin(), v.end())
reverse(beg, end)
反转
reverse(s.begin(), s.end())
unique(beg, end)
去重（需先排序）
auto it = unique(v.begin(), v.end()); v.erase(it, v.end());
lower_bound(beg, end, val)
第一个 ≥ val 的位置（有序）
int p = lower_bound(v.begin(), v.end(), x) - v.begin();
upper_bound(beg, end, val)
第一个 > val 的位置
同左
binary_search(beg, end, val)
判断是否存在（有序）
if (binary_search(v.begin(), v.end(), x))
max_element(beg, end)
最大值迭代器
int mx = *max_element(v.begin(), v.end());
min_element(beg, end)
最小值迭代器
同左
next_permutation(beg, end)
下一个排列（按字典序）
常用于全排列枚举
重点掌握：sort, lower_bound, upper_bound, unique, reverse。

四、常用技巧与注意事项
1. 初始化
cpp

复制


下载

vector<int> a(10, 0); // 10个0
vector<int> b = {1,2,3}; // C++11 列表初始化
set<int> s = {4,5,6};
map<string, int> mp = {{"a",1}, {"b",2}};


2. 遍历
• C++11 范围 for（只读）：
cpp

复制


下载

for (int x : v) cout << x << " ";


• 需要修改元素时用引用：
cpp

复制


下载

for (int &x : v) x *= 2;


3. 自定义排序
cpp

复制


下载

// 降序
sort(v.begin(), v.end(), greater<int>());

// 自定义比较函数
bool cmp(int a, int b) { return a > b; }
sort(v.begin(), v.end(), cmp);

// 对结构体排序
struct Node { int x, y; };
bool cmp(Node a, Node b) { return a.x < b.x; }


4. 堆（priority_queue）自定义比较
cpp

复制


下载

// 小根堆（最小堆）
priority_queue<int, vector<int>, greater<int>> pq;

// 自定义类型（如按second从小到大）
auto cmp = [](pair<int,int> a, pair<int,int> b) { return a.second > b.second; };
priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp);


5. 常用容器方法速查


操作
vector
set/map
stack/queue
添加元素
push_back()
insert()
push()
删除元素
pop_back()
erase()
pop()
访问首元素
front()
*s.begin()
top() / front()
访问末元素
back()
*s.rbegin()
back()（queue）
是否为空
empty()
empty()
empty()
大小
size()
size()
size()
清空
clear()
clear()
无，重新赋值

五、竞赛中的常见陷阱
1. vector<bool> 是特化，不保证连续内存，慎用。可改用 vector<char>。
2. map[] 会默认构造：如果键不存在，mp[x] 会插入一个默认值（0 或空字符串）。需要判断是否存在时，用 mp.find(x) != mp.end()。
3. set / map 的迭代器不能加减整数（非随机访问），只能用 ++ / --。
4. priority_queue 的 top() 返回 const 引用，不能直接修改。
5. STL 算法要求区间左闭右开：[begin, end)。