C++ STL 常用数据结构与函数整理
这份笔记按常见 STL 容器分类整理，适合在刷题和复习时快速查阅。
1.vector
1.1 特点
- 底层是动态数组
- 支持随机访问
- 尾部插入、删除效率高
- 中间插入、删除效率低
1.2 常用定义
vector<int>v;vector<int>v(5);// 5 个 0vector<int>v(5,10);// 5 个 10vector<int>v2(v);// 拷贝vector<int>v={1,2,3};
1.3 常用函数
| 函数 | 作用 |
|---|
v.size() | 返回元素个数 |
v.empty() | 判断是否为空 |
v.push_back(x) | 尾部插入 |
v.pop_back() | 删除最后一个元素 |
v.back() | 访问最后一个元素 |
v.front() | 访问第一个元素 |
v[i] | 访问下标为i的元素 |
v.at(i) | 访问下标为i的元素，越界会检查 |
v.clear() | 清空 |
v.begin() | 首元素迭代器 |
v.end() | 尾后迭代器 |
v.insert(pos, x) | 在pos前插入 |
v.erase(pos) | 删除pos位置元素 |
v.erase(l, r) | 删除区间[l, r) |
v.resize(n) | 调整大小 |
v.reserve(n) | 预留容量 |
1.4 常见写法
vector<int>v={3,1,4};v.push_back(10);v.pop_back();for(inti=0;i<(int)v.size();i++){cout<<v[i]<<" ";}for(intx:v){cout<<x<<" ";}
1.5 常用算法配合
sort(v.begin(),v.end());// 升序sort(v.begin(),v.end(),greater<int>());// 降序reverse(v.begin(),v.end());// 反转
2.deque
2.1 特点
- 双端队列
- 头尾都可以高效插入删除
- 支持随机访问
- 常用于单调队列、滑动窗口
2.2 常用定义
deque<int>dq;deque<int>dq={1,2,3};
2.3 常用函数
| 函数 | 作用 |
|---|
dq.push_back(x) | 尾插 |
dq.push_front(x) | 头插 |
dq.pop_back() | 尾删 |
dq.pop_front() | 头删 |
dq.back() | 访问队尾 |
dq.front() | 访问队头 |
dq.size() | 元素个数 |
dq.empty() | 是否为空 |
dq.clear() | 清空 |
dq[i] | 随机访问 |
2.4 示例
deque<int>dq;dq.push_back(1);dq.push_front(2);cout<<dq.front()<<endl;cout<<dq.back()<<endl;
2.5 易错点
- 和
vector一样，访问前要确保非空 - 虽然支持随机访问，但一般更常用在队头队尾操作
3.stack
3.1 特点
- 栈，后进先出
- 只能访问栈顶元素
- 默认底层一般是
deque
3.2 常用定义
stack<int>st;
3.3 常用函数
| 函数 | 作用 |
|---|
st.push(x) | 入栈 |
st.pop() | 出栈 |
st.top() | 访问栈顶 |
st.size() | 元素个数 |
st.empty() | 是否为空 |
3.4 示例
stack<int>st;st.push(10);st.push(20);cout<<st.top()<<endl;// 20st.pop();
3.5 易错点
pop()没有返回值- 想取出栈顶元素要先
top()，再pop()
4.queue
4.1 特点
4.2 常用定义
queue<int>q;
4.3 常用函数
| 函数 | 作用 |
|---|
q.push(x) | 入队 |
q.pop() | 出队 |
q.front() | 访问队头 |
q.back() | 访问队尾 |
q.size() | 元素个数 |
q.empty() | 是否为空 |
4.4 示例
queue<int>q;q.push(1);q.push(2);cout<<q.front()<<endl;// 1q.pop();
4.5 易错点
pop()也没有返回值- 访问
front()和back()前要保证队列非空
5.priority_queue
5.1 特点
- 优先队列，本质是堆
- 默认是大根堆
- 不能像普通容器那样遍历
5.2 常用定义
priority_queue<int>pq;// 大根堆
小根堆写法：
priority_queue<int,vector<int>,greater<int>>pq;
5.3 常用函数
| 函数 | 作用 |
|---|
pq.push(x) | 插入元素 |
pq.pop() | 删除堆顶 |
pq.top() | 访问堆顶 |
pq.size() | 元素个数 |
pq.empty() | 是否为空 |
5.4 示例
priority_queue<int>pq;pq.push(3);pq.push(10);pq.push(5);cout<<pq.top()<<endl;// 10pq.pop();
5.5 易错点
- 默认是大根堆，不是小根堆
pop()不返回堆顶元素- 如果要取最小值，记得用
greater<int>
6.set
6.1 特点
- 内部元素自动有序
- 元素不重复
- 底层一般是红黑树
- 查找、插入、删除通常是
O(log n)
6.2 常用定义
set<int>s;set<int>s={3,1,2};
6.3 常用函数
| 函数 | 作用 |
|---|
s.insert(x) | 插入元素 |
s.erase(x) | 删除值为x的元素 |
s.find(x) | 查找元素，返回迭代器 |
s.count(x) | 是否存在，结果是0或1 |
s.size() | 元素个数 |
s.empty() | 是否为空 |
s.clear() | 清空 |
s.begin() | 指向最小元素 |
s.end() | 尾后迭代器 |
s.lower_bound(x) | 第一个大于等于x的位置 |
s.upper_bound(x) | 第一个大于x的位置 |
6.4 示例
set<int>s;s.insert(3);s.insert(1);s.insert(3);// 重复元素不会插入if(s.count(1)){cout<<"found"<<endl;}for(intx:s){cout<<x<<" ";}
6.5 易错点
set中元素不能通过迭代器直接修改- 元素会自动排序，不会保持插入顺序
7.unordered_set
7.1 特点
- 无序集合
- 元素不重复
- 底层是哈希表
- 平均查找、插入、删除是
O(1)
7.2 常用定义
unordered_set<int>us;
7.3 常用函数
| 函数 | 作用 |
|---|
us.insert(x) | 插入 |
us.erase(x) | 删除 |
us.find(x) | 查找 |
us.count(x) | 判断是否存在 |
us.size() | 元素个数 |
us.empty() | 是否为空 |
us.clear() | 清空 |
7.4 示例
unordered_set<int>us;us.insert(10);us.insert(20);if(us.find(10)!=us.end()){cout<<"yes"<<endl;}
7.5 易错点
- 元素是无序的
- 最坏情况下复杂度可能退化
- 不能使用
lower_bound()、upper_bound()
8.map
8.1 特点
- 键值对容器
- 按 key 自动升序排列
- key 不重复
- 底层一般是红黑树
8.2 常用定义
map<string,int>mp;
8.3 常用函数
| 函数 | 作用 |
|---|
mp[key] | 访问或插入 key 对应的值 |
mp.insert({key, value}) | 插入键值对 |
mp.erase(key) | 删除 key |
mp.find(key) | 查找 key |
mp.count(key) | 判断 key 是否存在 |
mp.size() | 元素个数 |
mp.empty() | 是否为空 |
mp.clear() | 清空 |
mp.begin() | 首元素迭代器 |
mp.lower_bound(key) | 第一个大于等于 key 的位置 |
mp.upper_bound(key) | 第一个大于 key 的位置 |
8.4 示例
map<string,int>mp;mp["alice"]=95;mp["bob"]=88;cout<<mp["alice"]<<endl;for(auto[k,v]:mp){cout<<k<<" "<<v<<endl;}
8.5 易错点
mp[key]如果 key 不存在，会自动创建- 如果只是判断是否存在，优先用
find()或count()
9.unordered_map
9.1 特点
- 无序键值对容器
- key 不重复
- 底层是哈希表
- 平均复杂度接近
O(1)
9.2 常用定义
unordered_map<string,int>ump;
9.3 常用函数
| 函数 | 作用 |
|---|
ump[key] | 访问或插入 |
ump.insert({key, value}) | 插入 |
ump.erase(key) | 删除 |
ump.find(key) | 查找 |
ump.count(key) | 判断是否存在 |
ump.size() | 元素个数 |
ump.empty() | 是否为空 |
ump.clear() | 清空 |
9.4 示例
unordered_map<string,int>ump;ump["cat"]=2;ump["dog"]=3;if(ump.count("cat")){cout<<ump["cat"]<<endl;}
9.5 易错点
- 无序，遍历结果不固定
ump[key]也会自动创建新 key- 自定义类型做 key 时，通常需要自定义哈希函数
10. 常用遍历方式总结
10.1 下标遍历
适用于：vector、deque
for(inti=0;i<(int)v.size();i++){cout<<v[i]<<" ";}
10.2 范围for
适用于：大多数容器
for(intx:v){cout<<x<<" ";}
10.3 迭代器遍历
for(autoit=s.begin();it!=s.end();it++){cout<<*it<<" ";}
10.4 遍历map
for(autoit=mp.begin();it!=mp.end();it++){cout<<it->first<<" "<<it->second<<endl;}for(auto[k,v]:mp){cout<<k<<" "<<v<<endl;}
11. 常见使用场景速记
| 容器 | 适合场景 |
|---|
vector | 最常用，存一组数据，支持随机访问 |
deque | 需要双端操作 |
stack | 括号匹配、单调栈、DFS 辅助 |
queue | BFS、层序遍历 |
priority_queue | 堆、Top K、最值维护 |
set | 去重 + 有序 |
unordered_set | 快速去重、快速查找 |
map | 统计映射关系且需要有序 |
unordered_map | 计数、哈希映射、频率统计 |
12. 学 STL 时最值得记住的几点
12.1 先记“是否有序”
set、map是有序的unordered_set、unordered_map是无序的
12.2 先记“是否允许重复”
set、unordered_set不允许重复map、unordered_map的 key 不允许重复
12.3 先记“是否支持下标”
vector、deque支持下标set、map不支持像数组那样按位置访问
12.4 先记“默认堆类型”
12.5 先记“pop()是否返回值”
stack、queue、priority_queue的pop()都没有返回值
13. 刷题最常用模板
13.1vector排序
vector<int>v={4,2,5,1};sort(v.begin(),v.end());
13.2unordered_map计数
unordered_map<int,int>cnt;for(intx:nums){cnt[x]++;}
13.3set去重
set<int>s(nums.begin(),nums.end());
13.4 小根堆
priority_queue<int,vector<int>,greater<int>>pq;
13.5 队列 BFS
queue<int>q;q.push(start);while(!q.empty()){intx=q.front();q.pop();}
