C++ STL 常用数据结构与函数整理

这份笔记按常见 STL 容器分类整理，适合在刷题和复习时快速查阅。

---

1. vector

1.1 特点

• 底层是动态数组
• 支持随机访问
• 尾部插入、删除效率高
• 中间插入、删除效率低

1.2 常用定义

vector<int> v;
vector<int> v(5);            // 5 个 0
vector<int> v(5, 10);        // 5 个 10
vector<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 (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}

for (int x : 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;   // 20
st.pop();

3.5 易错点

• pop() 没有返回值
• 想取出栈顶元素要先 top()，再 pop()

---

4. queue

4.1 特点

• 队列，先进先出
• 只能访问队头和队尾
• 常用于 BFS

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;  // 1
q.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;   // 10
pq.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 (int x : 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 (int i = 0; i < (int)v.size(); i++) {
    cout << v[i] << " ";
}

10.2 范围 for

适用于：大多数容器

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

10.3 迭代器遍历

for (auto it = s.begin(); it != s.end(); it++) {
    cout << *it << " ";
}

10.4 遍历 map

for (auto it = 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 先记“默认堆类型”

• priority_queue 默认是大根堆

12.5 先记“pop() 是否返回值”

• stack、queue、priority_queue 的 pop() 都没有返回值

---

13. 刷题最常用模板

13.1 vector 排序

vector<int> v = {4, 2, 5, 1};
sort(v.begin(), v.end());

13.2 unordered_map 计数

unordered_map<int, int> cnt;
for (int x : nums) {
    cnt[x]++;
}

13.3 set 去重

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()) {
    int x = q.front();
    q.pop();
}

---