| 操作 | 用法 | 时间 |
|---|
| 尾插 | v.push_back(x) | O(1) 均摊 |
| 尾删 | v.pop_back() | O(1) |
| 插入 | v.insert(it, x) | O(n) |
| 删除 | v.erase(it) | O(n) |
| 访问 | v[i] / v.at(i) | O(1) |
| 大小 | v.size() / v.capacity() | O(1) |
| 清空 | v.clear() | O(n) |
| 预留 | v.reserve(n) | O(n) |
特点： 连续内存，随机访问快，中间插入慢，尾插最快
| 操作 | 用法 |
|---|
| 头插 | dq.push_front(x) |
| 头删 | dq.pop_front() |
| 尾插 | dq.push_back(x) |
| 尾删 | dq.pop_back() |
| 访问 | dq[i] |
特点： 头尾都能 O(1) 插入删除，随机访问比 vector 慢一点
| 操作 | 用法 |
|---|
| 插入 | lst.insert(it, x) |
| 删除 | lst.erase(it) |
| 头插 | lst.push_front(x) |
| 尾插 | lst.push_back(x) |
| 排序 | lst.sort() |
| 反转 | lst.reverse() |
特点： 任意位置 O(1) 插入删除，但不能随机访问，用得少
| 特性 | map | unordered_map |
|---|
| 底层 | 红黑树 | 哈希表 |
| 有序 | ✅ 按 key 排序 | ❌ 无序 |
| 插入 | O(log n) | O(1) 均摊 |
| 查询 | O(log n) | O(1) 均摊 |
| 遍历 | 有序输出 | 无序 |
常用操作：
1
2
3
4
5
| mp[key] = val; // 插入/修改
mp.count(key); // 是否存在
mp.find(key); // 返回迭代器
mp.erase(key); // 删除
for (auto& [k, v] : mp) { } // C++17 结构化绑定
|
| 特性 | set | unordered_set |
|---|
| 底层 | 红黑树 | 哈希表 |
| 有序 | ✅ | ❌ |
| 去重 | ✅ | ✅ |
常用操作：
1
2
3
4
| st.insert(x);
st.erase(x);
st.count(x); // 0 或 1
st.size();
|
允许重复 key 的版本，用法基本一样。
multiset 注意： erase(val) 会删掉所有等于 val 的元素，删单个要用 erase(iterator)
1
2
| auto it = ms.find(val);
if (it != ms.end()) ms.erase(it); // 只删一个
|
1
2
3
4
5
6
| stack<int> st;
st.push(x); // 压栈
st.pop(); // 弹栈（无返回值）
st.top(); // 栈顶
st.empty();
st.size();
|
底层默认是 deque。
1
2
3
4
5
6
7
| queue<int> q;
q.push(x); // 入队
q.pop(); // 出队（无返回值）
q.front(); // 队首
q.back(); // 队尾
q.empty();
q.size();
|
1
2
3
4
5
6
7
8
9
10
11
| // 默认大顶堆
priority_queue<int> pq;
// 小顶堆
priority_queue<int, vector<int>, greater<int>> minHeap;
pq.push(x); // 插入
pq.pop(); // 弹出堆顶
pq.top(); // 堆顶元素
pq.empty();
pq.size();
|
默认是大顶堆，用 less<int> 比较。
| 需求 | 推荐容器 |
|---|
| 随机访问多，尾插尾删 | vector |
| 头尾都要插入删除 | deque |
| 频繁中间插入删除 | list（很少用） |
| key-value 查找，需要有序 | map |
| key-value 查找，追求速度 | unordered_map |
| 去重 + 有序 | set |
| 去重 + 速度 | unordered_set |
| 栈操作 | stack |
| 队列操作 | queue |
| 求最大/最小值 | priority_queue |
1
2
3
4
5
6
7
8
9
10
11
12
13
| #include <algorithm>
sort(v.begin(), v.end()); // 排序
sort(v.rbegin(), v.rend()); // 降序
reverse(v.begin(), v.end()); // 反转
swap(a, b); // 交换
*max_element(v.begin(), v.end()); // 最大值
*min_element(v.begin(), v.end()); // 最小值
accumulate(v.begin(), v.end(), 0); // 求和（需 include <numeric>）
lower_bound(v.begin(), v.end(), x); // 第一个 >= x
upper_bound(v.begin(), v.end(), x); // 第一个 > x
next_permutation(v.begin(), v.end()); // 下一个排列
fill(v.begin(), v.end(), val); // 填充
|
| 容器 | 插入 | 删除 |
|---|
| vector | 扩容全部失效；否则插入点之后失效 | 删除点及之后失效 |
| deque | 头尾插入只失效所有迭代器，引用不失效；中间插入全部失效 | 中间删除全部失效；头尾删除对应端失效 |
| list / map / set | 不失效 | 只有被删的失效 |