04.9.2 STL 容器与迭代器失效
所属:全栈开发面试题库 / 04 后端语言与运行时 / 04.9 C 与 C++
覆盖范围
- sequence 容器:vector、list、deque 的底层与时间复杂度
- associative 容器:map、set、multimap、multiset 的红黑树实现
- unordered 容器:unordered_map、unordered_set 的哈希表实现
- 迭代器失效规则:哪些操作会使哪些迭代器失效
- 容器选型:时间复杂度、空间开销、cache 友好度
高频题速览
| 编号 | 题目 | 难度 | 频率 |
|---|---|---|---|
| 04.9.2-001 | vector 的底层实现 | 基础 | ★★★★★ |
| 04.9.2-002 | vector 扩容时迭代器为什么失效 | 进阶 | ★★★★★ |
| 04.9.2-003 | list 和 vector 怎么选 | 基础 | ★★★★★ |
| 04.9.2-004 | map 底层为什么用红黑树 | 进阶 | ★★★★☆ |
| 04.9.2-005 | map vs unordered_map 选型 | 进阶 | ★★★★★ |
| 04.9.2-006 | deque 的底层实现 | 进阶 | ★★★★☆ |
| 04.9.2-007 | 迭代器失效的完整规则 | 高级 | ★★★★★ |
| 04.9.2-008 | erase 时正确删除元素的写法 | 进阶 | ★★★★★ |
04.9.2-001 vector 的底层实现是什么?为什么用连续数组?
频率 ★★★★★ | 难度 基础
一句话结论
vector 底层是动态分配的连续数组,支持随机访问 O(1),尾部插入摊销 O(1),扩容时按 capacity 倍增(通常 1.5 或 2 倍)重新分配并拷贝/移动全部元素。
概念解释
- vector 内部维护三个指针:start、finish(当前大小 end)、end_of_storage(容量 end)。
- size() = finish - start,capacity() = end_of_storage - start。
- 连续数组意味着 cache 友好,遍历速度极快。
- 扩容时重新申请一块更大的内存,把旧元素拷贝/移动过去,再释放旧内存。
原理流程
- push_back 时先检查 size < capacity,如果是直接在 finish 位置构造元素。
- 如果 size == capacity,按当前 capacity 的倍数(GCC 通常 2 倍,MSVC 通常 1.5 倍)申请新内存。
- 把旧数组的所有元素移动(或拷贝)到新数组,释放旧数组。
- 扩容是 O(n) 操作,但因为是摊销到多次 push_back,所以单次 push_back 摊销 O(1)。
代码 / 示例
#include <vector>
int main() {
std::vector<int> v;
v.reserve(100); // 预分配 100 个空间,避免多次扩容
for (int i = 0; i < 100; i++) {
v.push_back(i); // 不触发扩容
}
// size() = 100, capacity() = 100
v.push_back(100); // 触发扩容,capacity 变成 150 或 200
return 0;
}
常见误区
- 误区:vector 扩容是每次加一个元素的大小?正解:按倍数扩容,1.5 或 2 倍,这样摊销复杂度才是 O(1)。
- 误区:vector 中间插入很快?正解:中间插入需要移动后面所有元素,O(n),不推荐频繁中间插入。
追问 / 延伸
- 为什么 vector 的 size 和 capacity 不一样?答:capacity 是已分配的总空间,size 是实际用了多少,多余的空间是为了下次 push_back 不用立刻扩容。
- shrink_to_fit 是什么?答:请求把 capacity 缩小到和 size 一样,释放多余内存。
04.9.2-002 vector 扩容时为什么迭代器会失效?
频率 ★★★★★ | 难度 进阶
一句话结论
vector 扩容时会重新分配一块新的连续内存,把旧元素移动过去,然后释放旧内存——所有指向旧内存的迭代器、指针、引用全部失效,因为它们指向的内存已经还给操作系统了。
概念解释
- vector 的迭代器本质上就是 T* 指针。
- 扩容 = 新分配一块更大的数组 + 把旧元素搬过去 + 释放旧数组。
- 旧数组的地址变了,所有指向旧数组的指针自然都失效了。
原理流程
- 迭代器 it = v.begin() 指向旧数组的第一个元素。
- push_back 触发扩容,v 内部数组搬到了新地址。
- 原来的 it 还指向旧地址,那块内存已经被释放。
- 继续解引用 it 就是访问已释放内存,未定义行为。
代码 / 示例
std::vector<int> v = {1, 2, 3};
auto it = v.begin();
v.push_back(4); // 如果 capacity == 3,触发扩容
// it 现在是悬空的!
// *it = 10; // 未定义行为
// 正确做法:扩容后重新获取迭代器
v.push_back(4);
it = v.begin(); // 重新获取
常见误区
- 误区:vector 扩容后迭代器只是"可能"失效?正解:只要触发了扩容(重新分配),所有迭代器全部失效,没有例外。
- 误区:reserve 之后就永远不会失效?正解:reserve 只是让 capacity 变大,只要不超过 capacity 就不会扩容;一旦超过,还是会全部失效。
追问 / 延伸
- 除了扩容,还有什么操作会让 vector 的迭代器失效?答:insert/erase 中间位置会让插入点/删除点之后的迭代器全部失效(因为元素移动了);push_back 不触发扩容时只有尾后迭代器 end() 会失效。
- list 的迭代器会失效吗?答:list 是链表,erase 某个元素时只有被删的那个迭代器失效,其他迭代器不受影响。
04.9.2-003 list 和 vector 怎么选?
频率 ★★★★★ | 难度 基础
一句话结论
绝大多数场景选 vector:连续内存 cache 友好、随机访问 O(1)、内存开销小;list 只在需要频繁在中间插入/删除且不关心遍历性能时才考虑,实际开发中很少用。
概念解释
- vector:连续数组,随机访问 O(1),尾部插入摊销 O(1),中间插入 O(n)。
- list:双向链表,随机访问 O(n),已知节点位置插入/删除 O(1)。
- vector 的内存开销:每个元素就是一个 T,没有额外指针。
- list 的内存开销:每个节点除了存 T,还要存 prev 和 next 两个指针(64 位下多 16 字节)。
原理流程
- 遍历场景:vector 连续内存,cache line 一次加载多个元素,速度极快;list 每个节点在堆上随机分布,cache miss 严重。
- 中间插入:vector 需要移动后面所有元素 O(n);list 已知节点位置时只改指针 O(1)。
- 但 list 要"知道节点位置"本身就需要遍历找到它,定位成本 O(n)。
- 综合下来,只有当插入/删除的位置已经通过其他方式拿到(比如遍历过程中记住了节点指针),list 才有优势。
代码 / 示例
#include <vector>
#include <list>
#include <chrono>
int main() {
// 遍历性能对比:vector 远快于 list
std::vector<int> v(1000000);
std::list<int> l(1000000);
auto t1 = std::chrono::steady_clock::now();
long long sum1 = 0;
for (int x : v) sum1 += x; // vector 遍历快很多
auto t2 = std::chrono::steady_clock::now();
long long sum2 = 0;
for (int x : l) sum2 += x; // list 遍历慢很多
auto t3 = std::chrono::steady_clock::now();
return 0;
}
常见误区
- 误区:list 插入删除总是 O(1)?正解:O(1) 的前提是已经知道节点位置;找到节点本身就是 O(n)。
- 误区:vector 比 list 慢因为 vector 要扩容?正解:reserve 预分配后 vector 插入尾部很快,且遍历性能远好于 list。
追问 / 延伸
- deque 是什么?答:分段连续数组,头尾插入都是 O(1),但中间操作慢,cache 不友好。
- 什么场景用 list?答:需要频繁在已知节点位置插入删除,且很少遍历,比如 LRU 缓存的链表部分。
04.9.2-004 map 底层为什么用红黑树?
频率 ★★★★☆ | 难度 进阶
一句话结论
map 需要保持 key 有序,红黑树是一种平衡二叉搜索树,插入/删除/查找都是 O(log n),且通过颜色约束保证树不会退化成链表,平衡成本比 AVL 低。
概念解释
- 红黑树性质:节点是红或黑;根是黑;叶子(NIL)是黑;红节点的子节点是黑;任意节点到叶子的所有路径包含相同数量的黑节点。
- 这些性质保证了从根到最远叶子的路径不超过最短路径的两倍,树高 O(log n)。
- AVL 树是严格平衡,每次插入删除可能需要多次旋转;红黑树是近似平衡,旋转次数更少。
原理流程
- map 插入时按 key 大小搜索插入位置,像二叉搜索树一样插入。
- 插入后检查是否违反红黑树性质,如果违反就做旋转和变色修复。
- 查找时从根开始,比当前节点小走左子树,大走右子树,O(log n)。
- 遍历 map 得到的是 key 有序的序列(中序遍历)。
代码 / 示例
#include <map>
#include <iostream>
int main() {
std::map<int, const char*> m;
m[3] = "three";
m[1] = "one";
m[2] = "two";
// 遍历是按 key 从小到大:1, 2, 3
for (auto& [k, v] : m) {
std::cout << k << " => " << v << std::endl;
}
auto it = m.find(2); // O(log n)
if (it != m.end()) {
std::cout << it->second << std::endl; // "two"
}
return 0;
}
常见误区
- 误区:map 查找是 O(1)?正解:map 是红黑树,查找 O(log n);unordered_map 才是哈希表,平均 O(1)。
- 误区:红黑树和 AVL 一样严格平衡?正解:红黑树是近似平衡,高度可能比 AVL 高一点,但插入删除旋转更少,综合性能更好。
追问 / 延伸
- 为什么 map 插入时迭代器不会失效?答:红黑树是节点在堆上独立分配的,插入新节点不会移动已有节点,所以所有已有迭代器都有效。
- multimap 和 map 的区别?答:multimap 允许 key 重复,operator[] 被删除,因为有多个值不确定取哪个。
04.9.2-005 map 和 unordered_map 怎么选?
频率 ★★★★★ | 难度 进阶
一句话结论
需要 key 有序或需要范围查询(lower_bound/upper_bound)时用 map;只需要按键查找、不关心顺序时用 unordered_map,平均 O(1) 查找更快,但最坏 O(n) 且有哈希碰撞。
概念解释
- map:红黑树,O(log n) 查找,key 有序,内存开销大(每个节点有左右指针和颜色)。
- unordered_map:哈希表(桶数组 + 链表/红黑树解决冲突),平均 O(1) 查找,key 无序,内存开销小但有负载因子和 rehash 开销。
原理流程
- unordered_map 内部维护一个桶数组,每个 key 通过哈希函数算出桶编号。
- 同一个桶里的元素用链表(或长到一定程度后转红黑树)串起来。
- 查找时先算哈希找到桶,再在桶里逐个比较。
- 当元素数量超过桶数 * 负载因子时,触发 rehash:桶数翻倍,所有元素重新分配到新桶。
代码 / 示例
#include <unordered_map>
#include <map>
// 场景一:需要按 key 顺序遍历
std::map<int, std::string> ordered;
for (auto& [k, v] : ordered) {
// k 是从小到大的
}
// 场景二:只需要按键查找
std::unordered_map<int, std::string> hash_map;
hash_map[1] = "one";
auto it = hash_map.find(1); // 平均 O(1)
// 注意:unordered_map 的 key 需要哈希函数
// 自定义类型作为 key 需要写 std::hash 特化
struct Point { int x; int y; };
struct PointHash {
size_t operator()(const Point& p) const {
return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
}
};
std::unordered_map<Point, std::string, PointHash> point_map;
常见误区
- 误区:unordered_map 一定比 map 快?正解:小数据量下 map 可能更快,因为红黑树常数小、没有哈希计算开销;大数据量且查找密集时 unordered_map 优势明显。
- 误区:unordered_map 遍历时顺序稳定?正解:顺序由哈希值和桶数决定,rehash 后顺序会变,不能依赖。
追问 / 延伸
- 什么是哈希碰撞?答:两个不同的 key 算出同一个桶编号,需要用链表或红黑树在桶里区分。
- unordered_map 的 load_factor 是什么?答:平均每个桶里的元素个数,默认 1.0,超过就 rehash。
04.9.2-006 deque 的底层实现是什么?和 vector/list 有什么区别?
频率 ★★★★☆ | 难度 进阶
一句话结论
deque(double-ended queue)底层是一段段连续的小块内存(通过 map 数组串联),头尾插入删除都是 O(1),支持随机访问,但随机访问需要两次跳转(先找块,再找块内位置),cache 不友好。
概念解释
- deque 不是完全连续的,而是由多个固定大小的连续块组成。
- 内部有一个 map(不是 std::map),是一个指针数组,每个元素指向一块连续内存。
- 头尾插入时:如果当前块还有空间,直接在块里放;如果满了,在 map 前面/后面再加一块。
- 随机访问:先算在第几个块,再算块内偏移,O(1) 但常数比 vector 大。
原理流程
- deque 中间是一个中控数组(map),数组里每个元素指向一块连续内存块。
- 头部插入:如果头部块还有空位,直接放;否则在中控数组前面加一个新块。
- 尾部插入:同理,尾部块有空间就直接放,没有就加新块。
- 中间插入/删除:需要移动元素,成本 O(n),比 vector 还慢。
代码 / 示例
#include <deque>
int main() {
std::deque<int> dq;
dq.push_back(1); // 尾部
dq.push_front(0); // 头部,O(1)
dq.push_back(2);
// dq = [0, 1, 2]
std::cout << dq[1] << std::endl; // 1,随机访问 O(1) 但常数大
dq.pop_front(); // O(1)
dq.pop_back(); // O(1)
return 0;
}
常见误区
- 误区:deque 是连续的?正解:deque 是分段连续的,不是整块连续,所以 cache 不友好。
- 误区:deque 中间插入快?正解:中间插入需要移动元素,O(n),比 vector 还慢,因为块结构更复杂。
追问 / 延伸
- STL 中 queue 和 stack 默认用什么实现?答:默认是 deque,因为头尾操作都 O(1)。
- 什么时候用 deque?答:需要频繁在头尾插入删除,且不怎么中间操作,也不怎么遍历的时候。
04.9.2-007 迭代器失效的完整规则是什么?
频率 ★★★★★ | 难度 高级
一句话结论
不同容器的迭代器失效规则不同:vector 扩容时全部失效,插入/删除中间位置时该位置之后全部失效;list 只有被删的元素迭代器失效;map/set 只有被删的元素迭代器失效;deque 头尾操作可能让全部迭代器失效。
概念解释
- vector:
- push_back 不触发扩容:只有 end() 失效。
- push_back 触发扩容:所有迭代器、指针、引用全部失效。
- insert/erase 中间位置:插入/删除点之后的所有迭代器失效。
- list:
- erase 某个元素:只有被删元素的迭代器失效,其他都有效。
- insert:所有迭代器都有效。
- map/set/multimap/multiset:
- erase 某个元素:只有被删元素的迭代器失效,其他都有效。
- insert:所有迭代器都有效。
- deque:
- 头尾插入/删除:所有迭代器可能失效,但指针和引用不一定。
- 中间插入/删除:所有迭代器失效。
原理流程
- 迭代器失效的本质是:容器底层结构变了,迭代器指向的内存要么被释放了,要么元素位置移动了。
- vector 是连续数组,插入/删除中间元素会移动后面所有元素,所以后面的迭代器都失效。
- list/map 是节点式结构,每个节点在堆上独立分配,删除一个节点不会移动其他节点,所以其他节点的迭代器不受影响。
代码 / 示例
// vector erase 正确写法
std::vector<int> v = {1, 2, 3, 4, 5};
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it); // erase 返回下一个有效迭代器
} else {
++it;
}
}
// list erase 正确写法
std::list<int> l = {1, 2, 3, 4, 5};
for (auto it = l.begin(); it != l.end(); ) {
if (*it % 2 == 0) {
it = l.erase(it); // list 的 erase 也返回下一个迭代器
} else {
++it;
}
}
// map erase 正确写法
std::map<int, int> m = {{1,1}, {2,2}, {3,3}};
for (auto it = m.begin(); it != m.end(); ) {
if (it->first % 2 == 0) {
it = m.erase(it); // C++11 起 erase 返回下一个迭代器
} else {
++it;
}
}
常见误区
- 误区:erase 之后迭代器自动变成下一个?正解:C++11 之前 STL 容器的 erase 返回 void,需要自己写 it = container.erase(it);C++11 起所有容器的 erase 都返回下一个迭代器。
- 误区:只要不扩容 vector 的迭代器就不会失效?正解:中间 insert/erase 也会让后面的迭代器失效,因为元素移动了。
追问 / 延伸
- 为什么 vector 的 erase 要返回下一个迭代器?答:因为 erase 之后当前位置已经被删了,而且后面的元素都往前移了,原来的 it 已经指向了下一个元素,直接返回 it 就可以继续遍历。
- 怎么记住这些规则?答:看底层结构——连续数组的插入删除会移动元素,所以后面的迭代器失效;节点式的插入删除不移动其他节点,所以其他迭代器有效。
04.9.2-008 遍历容器并删除元素的正确写法是什么?
频率 ★★★★★ | 难度 进阶
一句话结论
遍历时删除元素必须用 it = container.erase(it) 的写法,不能在 erase 之后直接 ++it,因为 erase 已经让当前迭代器失效了;C++20 有 erase_if 算法更简洁。
概念解释
- 错误写法:
for(it = begin; it != end; ++it) { if(cond) erase(it); }— erase 之后 it 已经失效,再 ++it 是未定义行为。 - 正确写法:erase 会返回被删元素的下一个有效迭代器,直接用这个返回值继续循环。
- C++20 提供了 erase_if(container, pred) 算法,一行搞定。
原理流程
- 进入循环,it 指向某个元素。
- 如果满足删除条件,调用 erase(it),it 指向的元素被删除。
- erase 返回下一个元素的迭代器,把它赋给 it。
- 如果不满足条件,才 ++it 走到下一个元素。
代码 / 示例
#include <vector>
#include <list>
#include <map>
int main() {
// vector 正确写法
std::vector<int> v = {1, 2, 3, 4, 5, 6};
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it); // erase 返回下一个迭代器
} else {
++it;
}
}
// v = {1, 3, 5}
// C++20 更简洁
std::erase_if(v, [](int x) { return x % 2 == 0; });
// map 正确写法
std::map<int, int> m = {{1,1}, {2,2}, {3,3}, {4,4}};
for (auto it = m.begin(); it != m.end(); ) {
if (it->first % 2 == 0) {
it = m.erase(it);
} else {
++it;
}
}
// m = {{1,1}, {3,3}}
return 0;
}
常见误区
- 误区:erase 之后 it 自动指向下一个?正解:C++11 之前不是,C++11 起是;但为了可移植性,永远写
it = erase(it)。 - 误区:用 range-based for 可以边遍历边删除?正解:不行,range-based for 底层用迭代器,删除后迭代器失效,行为未定义。
追问 / 延伸
- list 的 remove_if 是什么?答:list 自带的成员函数,直接删除满足条件的元素,O(n),比通用算法更快(因为不用移动元素)。
- erase_if 和 remove + erase 有什么区别?答:remove + erase 是两步,先把要删的元素移到末尾,再 erase;erase_if 一步到位,语义更清晰。
待整理清单
- [ ] 各容器时间复杂度对比表完整版
- [ ] 自定义类型作为 unordered_map key 的哈希函数写法
- [ ] 红黑树插入删除旋转详解
- [ ] 短路迭代器与 vector
的坑