# 一、C++ 常用容器总览
| 容器 |
类型 |
底层结构 |
是否有序 |
是否去重 |
主要用途 |
vector |
序列容器 |
动态数组 |
否 |
否 |
动态数组，随机访问 |
deque |
序列容器 |
双端队列（分段连续） |
否 |
否 |
首尾高效插入 |
list |
序列容器 |
双向链表 |
否 |
否 |
频繁中间插入 / 删除 |
forward_list |
序列容器 |
单向链表 |
否 |
否 |
节省内存的链表 |
array |
序列容器 |
静态数组 |
否 |
否 |
固定大小数组 |
stack |
容器适配器 |
deque （默认） |
否 |
否 |
栈（LIFO） |
queue |
容器适配器 |
deque （默认） |
否 |
否 |
队列（FIFO） |
priority_queue |
容器适配器 |
vector （默认） |
是（堆序） |
否 |
优先队列 |
set |
关联容器 |
红黑树 |
是（升序） |
是 |
有序唯一集合 |
multiset |
关联容器 |
红黑树 |
是 |
否 |
有序可重复集合 |
map |
关联容器 |
红黑树 |
是 |
是（按键） |
有序键值对 |
multimap |
关联容器 |
红黑树 |
是 |
否 |
有序可重复键值对 |
unordered_set |
无序关联容器 |
哈希表 |
否 |
是 |
无序唯一集合 |
unordered_multiset |
无序关联容器 |
哈希表 |
否 |
否 |
无序可重复集合 |
unordered_map |
无序关联容器 |
哈希表 |
否 |
是（按键） |
无序键值对 |
unordered_multimap |
无序关联容器 |
哈希表 |
否 |
否 |
无序可重复键值对 |
# 二、各容器操作复杂度对比
# 1. vector<T>
- 底层：动态数组（连续内存）
- 特点：支持随机访问，尾部操作快，中间插入慢。
| 操作 |
复杂度 |
说明 |
push_back() |
平均 O (1)，最坏 O (n) |
扩容时复制 |
pop_back() |
O(1) |
|
insert(it, x) |
O(n) |
中间插入需移动 |
erase(it) |
O(n) |
删除后需移动 |
operator[] / at() |
O(1) |
随机访问 |
size() |
O(1) |
|
begin() / end() |
O(1) |
|
适合：频繁随机访问、尾部增删
不适合：频繁中间插入 / 删除
# 2. deque<T> （双端队列）
- 底层：分段连续数组（多个小数组）
- 特点：首尾操作都快，支持随机访问。
| 操作 |
复杂度 |
说明 |
push_front() / push_back() |
O(1) |
首尾插入都快 |
pop_front() / pop_back() |
O(1) |
|
insert() / erase() （中间） |
O(n) |
|
operator[] / at() |
O(1) |
支持随机访问 |
size() |
O(1) |
|
适合：需要首尾高效插入的场景（如滑动窗口）
注意：迭代器失效规则比 vector 复杂
# 3. list<T> （双向链表）
- 底层：双向链表
- 特点：任意位置插入 / 删除 O (1)，但不支持随机访问。
| 操作 |
复杂度 |
说明 |
push_front() / push_back() |
O(1) |
|
insert(it, x) |
O(1) |
已知位置 |
erase(it) |
O(1) |
已知位置 |
operator[] |
不支持 |
|
find() |
O(n) |
|
size() |
C++11 起 O (1)，之前 O (n) |
|
适合：频繁中间插入 / 删除
不适合：随机访问、缓存不友好
# 4. forward_list<T> （单向链表）
- 底层：单向链表
- 特点：比
list 更省内存，但只能单向遍历。
| 操作 |
复杂度 |
说明 |
push_front() |
O(1) |
|
insert_after() |
O(1) |
|
erase_after() |
O(1) |
|
不支持 push_back() |
— |
|
适合：内存敏感、只需前向遍历的场景
# 5. array<T, N>
- 底层：静态数组（栈上内存）
- 特点：大小固定，性能极高。
| 操作 |
复杂度 |
说明 |
operator[] |
O(1) |
|
at() |
O(1) |
带边界检查 |
size() |
O(1) |
|
| 所有操作 |
O(1) |
固定大小 |
适合：小数据、固定大小、高性能场景
# 6. set<T> / map<K,V>
- 底层：红黑树（自平衡二叉搜索树）
- 特点：自动排序、自动去重（
set 和 map 键唯一）
| 操作 |
复杂度 |
说明 |
insert() |
O(log n) |
|
find() |
O(log n) |
|
erase() |
O(log n) |
|
size() |
O(1) |
|
| 遍历 |
O(n) |
有序输出 |
适合：需要有序、去重、查找的场景
# 7. unordered_set<T> / unordered_map<K,V>
- 底层：哈希表（开链法或开放寻址）
- 特点：平均极快，但无序，最坏 O (n)
| 操作 |
复杂度 |
说明 |
insert() |
平均 O (1)，最坏 O (n) |
哈希冲突时退化 |
find() |
平均 O (1)，最坏 O (n) |
|
erase() |
平均 O (1)，最坏 O (n) |
|
size() |
O(1) |
|
| 负载因子 |
影响性能 |
可调 max_load_factor() |
适合：大数据、高频查找、不在乎顺序
不适合：需要有序输出
# 8. 容器适配器（ stack , queue , priority_queue ）
| 容器 |
默认底层 |
特点 |
操作复杂度 |
stack<T> |
deque |
后进先出（LIFO） |
push / pop / top : O(1) |
queue<T> |
deque |
先进先出（FIFO） |
push / pop / front : O(1) |
priority_queue<T> |
vector + 堆 |
最大 / 最小元素在顶 |
push : O(log n), top : O(1), pop : O(log n) |
它们不是真正容器，而是基于其他容器的封装，接口受限。
# 选择
| 需求 |
推荐容器 |
| 动态数组，随机访问 |
vector |
| 首尾都能高效插入 |
deque |
| 频繁中间插入 / 删除 |
list |
| 固定大小数组 |
array |
| 快速查找、去重（不在乎顺序） |
unordered_set / unordered_map |
| 需要有序输出、去重 |
set / map |
| 栈操作 |
stack |
| 队列操作 |
queue |
| 找最大 / 最小元素（堆） |
priority_queue |
# 总结
| 口诀 |
对应容器 |
| “要快用 unordered” |
unordered_set/map （平均 O (1)） |
| “要序用 set/map” |
set/map （O (log n)，有序） |
| “通用选 vector” |
vector （最常用） |
| “首尾快用 deque” |
deque （双端高效） |
| “中间删用 list” |
list （任意位置 O (1) 删除） |
| “最大最小用堆” |
priority_queue |
LRU：
lru1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
|
struct DNode;
struct DNode {
int key, value;
DNode* pre;
DNode* next;
DNode(): key(-1), value(-1), pre(nullptr), next(nullptr){}
DNode(int key, int val): key(key), value(val), pre(nullptr), next(nullptr) {}
};
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
head = new DNode();
tail = new DNode();
head->next = tail;
tail->pre = head;
this->size = 0;
}
int get(int key) {
if(mp.find(key) != mp.end()){
DNode* pre = mp[key]->pre;
pre->next = mp[key]->next;
mp[key]->next->pre = pre;
DNode* next = head->next;
head->next = mp[key];
mp[key]->pre = head;
mp[key]->next = next;
next->pre = mp[key];
return mp[key]->value;
}else{
return -1;
}
}
void put(int key, int value) {
if(mp.find(key) != mp.end()){
mp[key]->value = value;
DNode* pre = mp[key]->pre;
pre->next = mp[key]->next;
mp[key]->next->pre = pre;
DNode* next = head->next;
head->next = mp[key];
mp[key]->pre = head;
mp[key]->next = next;
next->pre = mp[key];
}else{
if(this->size < this->capacity){
DNode* p = head->next;
DNode* newNode = new DNode(key, value);
head->next = newNode;
newNode->pre = head;
newNode->next = p;
p->pre = newNode;
mp[key] = newNode;
this->size++;
}else{
DNode* remove = tail->pre;
mp.erase(remove->key);
remove->pre->next = tail;
tail->pre = remove->pre;
delete remove;
DNode* newNode = new DNode(key, value);
DNode* nxt = head->next;
head->next = newNode;
newNode->pre = head;
newNode->next = nxt;
nxt->pre = newNode;
mp[key] = newNode;
}
}
return;
}
private:
int capacity;
int size;
unordered_map<int, DNode*> mp;
DNode* head;
DNode* tail;
};
|
反转链表
reverse1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* curr = head;
while (curr != nullptr) {
ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
|
