跳转到内容

06 · STL 容器与迭代器

定位:STL 是 C++ 八股第三大块,vector/map/unordered_map 的底层实现、迭代器失效、扩容是必考。 学完标准:能把 7 大容器“底层结构/复杂度/迭代器是否失效/适用场景”做成一张表讲出来。


容器 底层结构 查找 插入/删除 随机访问 迭代器失效 内存
vector 动态连续数组 O(n) 尾 O(1)★,中间 O(n) ✅ O(1) push_back 扩容全失效;insert/erase 插入点/被删点及其后失效 连续
deque 分段连续(中控器) O(n) 头尾 O(1)★ ✅ O(1) 头尾插入:迭代器全失效、引用不失效;中间插入/删除:全失效 多段
list 双向链表 O(n) O(1)(已知位置) ❌ 除被删元素外不失效 节点分散
forward_list 单向链表 O(n) O(1) ❌ 同上 节点分散
set/multiset 红黑树 O(log n) O(log n) ❌ 不失效(节点式) 节点分散
map/multimap 红黑树 O(log n) O(log n) ❌ 不失效 节点分散
unordered_set/map 哈希表(链地址) 平均 O(1) 平均 O(1) ❌ rehash 时全失效 桶数组+节点

★ = 摊还复杂度。

选择金句:

  • 需要随机访问 + 频繁尾部增删 → vector
  • 需要头尾插入(队列)→ deque
  • 需要大量中间插入/删除 → list
  • 需要有序且查找快 → map/set(红黑树)
  • 只查快、不在乎顺序 → unordered_map
  • 元素唯一 → set/map;可重复 → multiset/multimap

struct vector {
T* start; // 首元素
T* finish; // 尾后(size)
T* end_of_storage; // 容量边界(capacity)
};

连续内存,三个指针管理 size 和 capacity。

std::vector<int> v;
for (int i = 0; i < 100; i++) v.push_back(i);
// 容量变化示例(GCC 增长因子 2):1,2,4,8,16,32,64,128;(MSVC 1.5):1,2,3,4,6,9,13,19

流程:容量满了 → 分配 2 倍新内存 → 把旧元素移动/拷贝到新内存 → 释放旧内存 → 更新指针。

  • 增长因子:GCC 2 倍,MSVC 1.5 倍。
  • 摊还复杂度 O(1):n 次 push_back 总拷贝次数是 O(n),平均每次 O(1)。
  • 扩容时迭代器/指针/引用全部失效(内存搬家了)。
  • 为什么指数增长? 保证摊还 O(1);线性增长(+固定大小)总代价 O(n²)。

一句话区别:push_back 要的是已经构造好的对象,emplace_back 要的是构造这个对象所需的参数 —— 后者直接在容器内存上原地构造,省掉“临时对象 + 一次移动/拷贝”。

// 签名对比
void push_back(const T& value); // 拷贝
void push_back(T&& value); // 移动
template <class... Args>
reference emplace_back(Args&&... args); // 完美转发 → 原地构造;C++17 起返回新元素引用

开销推演(T 有移动构造):

struct Point { Point(float, float); Point(Point&&) noexcept; };
std::vector<Point> v;
v.push_back(Point(1, 2)); // ① 构造临时 Point → ② 移动进容器 → ③ 析构临时
// = 1 次构造 + 1 次移动 + 1 次析构
v.emplace_back(1, 2); // 直接在容器尾部内存上 placement-new Point(1,2)
// = 只有 1 次构造,无临时、无移动

若 T 没有移动构造(只能拷贝,例如自己写了拷贝构造没写移动),push_back 那行就退化成“构造 + 拷贝 + 析构”,差距更大。

三种“emplace 不一定更好”的情况(这才是面试加分点):

  1. 参数已经是现成对象 → 没区别
Point p(1, 2);
v.push_back(p); // 拷贝构造 1 次
v.emplace_back(p); // 也是拷贝构造 1 次(把 p 转发给 Point 的拷贝构造),没省任何东西
  1. 花括号列表推不出类型(最经典的坑)
std::vector<std::vector<int>> vv;
vv.push_back({1, 2, 3}); // ✅ OK:{1,2,3} 先构成 vector<int>
vv.emplace_back({1, 2, 3}); // ❌ 编译错误:Args 无法从 {1,2,3} 推导出类型
vv.emplace_back(std::initializer_list<int>{1, 2, 3}); // ✅ 必须显式写出类型

原因:emplace_back 是模板,参数包 Args&&... 对花括号初始化列表无法做类型推导({1,2,3} 本身没有类型)。

  1. 能调用 explicit 构造函数 = 双刃剑
std::vector<std::unique_ptr<int>> v;
v.push_back(new int(5)); // ❌ 编译错误(unique_ptr 构造是 explicit)—— 编译器替你挡了一次
v.emplace_back(new int(5)); // ✅ 合法,但若中途抛异常,裸指针会泄漏
v.push_back(std::make_unique<int>(5)); // ✅ 推荐写法

什么时候用哪个:

场景 建议
T 构造/移动代价大(大结构体、std::string、含堆对象的类) emplace_back 省一次构造+移动
T 是 int/double 等平凡类型 两者几乎无差别,编译器常生成同样代码
参数已经是 T 对象 用 push_back(语义更直白)
要传 {...} 列表/聚合初始化 用 push_back(emplace 会编译失败)
想明确避免临时对象,且能直接给出构造参数 用 emplace_back

必须一起答的两点(否则会被追问):

  • 两者都是尾部插入、都摊还 O(1)、触发扩容时都会让全部迭代器/指针/引用失效。
  • emplace_back 返回的是新元素的引用(C++17 起),但扩容已发生后这个引用才有效——别拿着它再触发扩容。

面试话术(背这段): “push_back 的参数类型就是 T,得先有对象再移动/拷贝进容器;emplace_back 是可变参数模板,把参数完美转发到容器内存上直接构造,省掉一次临时对象构造 + 一次移动(或拷贝)。但参数已是现成对象时两者开销一样,而且 emplace_back({1,2}) 因为参数包无法从花括号列表推导类型会编译失败 —— 所以不能无脑用 emplace。”

同一个道理适用于 emplace_front、emplace、map::try_emplace 等所有 emplace 系列。

v.reserve(100); // 只扩 capacity=100,size 不变,不构造元素(快)
v.resize(100); // 改变 size=100,多余元素默认构造(默认值填充)
v.shrink_to_fit(); // 把 capacity 缩到 size

金句:reserve 提前申请内存避免多次扩容;resize 改变元素数量。知道要加 n 个元素 → reserve + push_back。

操作 迭代器/指针/引用情况
push_back 触发扩容 全部失效(内存搬走)
push_back 未触发扩容 已有元素的迭代器/引用不失效(end() 失效)
insert 插入点及之后全部失效(元素后移)
erase 被删元素及之后全部失效
尾部 pop_back 被删元素的迭代器/引用和 end() 失效
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) it = v.erase(it); // erase 返回下一个有效迭代器
else ++it;
}
// 注意:不要在 for 里用 v.erase(it) 然后 it++ —— erase 后 it 已失效!

  • 每个节点独立分配(Node = 数据 + prev/next 指针)。
  • 插入/删除(已知位置)O(1),迭代器不失效(除非删除该节点本身)。
  • 缺点:无随机访问、缓存不友好(节点分散,遍历命中率低)、内存碎片。
  • splice(O(1) 拼接另一个 list 的一段)是 list 独有操作。
  • 分段连续:多段定长连续缓冲区 + 中控器(map,存各段首地址的指针数组)。
  • 支持 operator[](先定位段再定位元素,两次间接,比 vector 稍慢)。
  • 头尾插入 O(1),中间插入 O(n)。
  • 头尾插入:所有迭代器失效,但元素引用不失效(元素不搬家);删除头/尾只失效被删元素和 end();中间插入/删除:迭代器和引用全失效。
  • 应用:作为 std::queue、std::stack 的默认底层。

  • 自平衡二叉搜索树:任意节点红黑染色 + 5 条性质保证最长路径 ≤ 2×最短路径。
  • 所有操作 O(log n),有序(中序遍历有序)。
  • 为什么用红黑树而不是 AVL?
    • AVL 更严格平衡(左右子树高度差 ≤ 1),查询略快但插入/删除旋转多;
    • 红黑树平衡要求松,插入/删除旋转次数少、常数小,整体统计性能好。通用容器选红黑树。
  • key 有序,要求 key 支持 <(或提供比较器)。
  • 迭代器指向 pair<const Key, T>,key 不可修改(改 key 会破坏红黑树性质)。
  • operator[]:key 不存在会插入默认值(副作用)!判断存在用 find/contains(C++20)。
std::map<std::string, int> m;
m["a"] = 1; // 不存在 → 插入 "a" 再赋值
if (m.count("b")) { } // count 返回 0/1(检查存在)
auto it = m.find("b"); // 找不到返回 end()
  • set:有序唯一集合(插入已有元素不插入)。
  • multiset/multimap:允许重复 key(用 equal_range 取所有重复)。

  • 哈希表 + 链地址法:一个桶数组(bucket array),每个桶挂链表。主流标准库实现是“贯穿所有节点的单链表 + 桶指针数组”;桶内转红黑树是 Java 8 HashMap 的行为,C++ 没有。
  • 平均 O(1) 查找:hash(key) → 定位桶 → 桶内线性比较。
  • 要求 key 提供 hash 函数 + ==(自定义类型需自己提供)。
解决方式 说明
链地址法(separate chaining) 冲突的元素挂同一桶的链表上,std::unordered_map 用这个
开放寻址(open addressing) 冲突后按探测序列找下一个空位(线性/二次探测、双重哈希)

负载因子(load factor) = 元素数 / 桶数。超过阈值(std 默认 1.0)→ rehash:扩容桶数组并重新计算所有元素的桶位置(O(n),全迭代器失效)。

5.3 map vs unordered_map 选择(必背)

Section titled “5.3 map vs unordered_map 选择(必背)”
map unordered_map
底层 红黑树 哈希表
复杂度 O(log n) 稳定 平均 O(1),最坏 O(n)(冲突多时)
有序性 有序(中序遍历) 无序
key 要求 <(或比较器) hash + ==
常数 每次操作 O(log n) 稳定、无最坏退化 平均 O(1) 常数小,但 hash 计算有开销、最坏 O(n)
适用 需要有序遍历/范围查询、元素少 大量查找、无需有序、key 好 hash

金句:元素少时 map 可能更快(红黑树 O(log n) 稳定、无退化),元素多且查找频繁用 unordered_map。


类别 能力 代表
输入/输出迭代器 单向读写一次 istream_iterator
前向迭代器 单向多次遍历 forward_list
双向迭代器 可 ++ – list/set/map
随机访问迭代器 +n、-n、[]、比较 vector/deque/array
连续迭代器(C++20) 保证内存连续 vector

用模板时按最弱需求声明参数类型(算法只依赖需要的类别,提高复用性)。


Q1:vector 扩容机制?增长因子? 容量满 → 分配新内存(GCC 2 倍、MSVC 1.5 倍)→ 移动/拷贝元素 → 释放旧内存。摊还 O(1)。指数增长保证摊还复杂度。

Q2:为什么 vector 扩容不线性增长? 线性增长总拷贝是 O(n²);指数增长摊还 O(1)。

Q3:vector 迭代器什么时候失效? 扩容后全部失效;insert/erase 至少使插入点/被删元素及其后失效(扩容则全部);注意“先 erase 再 ++“的经典错误。

Q4:map 为什么用红黑树? 自平衡 + 有序 + 插入删除常数比 AVL 好,整体统计性能最优。

Q5:unordered_map 冲突怎么解决?负载因子是什么? 链地址法;负载因子 = 元素/桶数,超过阈值 rehash(全失效)。

Q6:emplace_back 和 push_back? emplace 原地构造省一次临时对象拷贝/移动。

Q7:reserve 和 resize? reserve 只扩容量不建元素;resize 改变元素个数并构造。

Q8:map 的 operator[] 有什么坑? 不存在的 key 会被插入默认值;只查不用 find/contains。

Q9:list 和 vector 场景选择? list 频繁中间插入、迭代器稳定;vector 随机访问、缓存友好、尾部增删。

Q10:为什么 vector 比 list 遍历快? 连续内存缓存命中率高(顺序预取);list 节点分散,每次访问都缓存未命中。

Q11:vector 存对象 vs 存指针? 存对象:连续、缓存好、但移动/拷贝元素成本高、插入删除搬移对象;存指针:搬移成本低但缓存差 + 管理生命周期。性能关键型存对象。

Q12:如何避免 vector 频繁扩容? reserve 预估容量。


1. 写出 vector 扩容的完整流程(含迭代器失效)。

2. map 和 unordered_map 各举一个选它的场景。

3. 为什么红黑树而不是 AVL?

4. `for(auto it=v.begin(); it!=v.end(); ++it){ v.erase(it); }` 有什么问题?怎么改?

5. unordered_map 什么时候 rehash?

我的原答:rehash 后迭代器会怎样?

6. emplace_back 省了什么?

7. deque 为什么叫"分段连续"?

8. map 里迭代器指向的 key 为什么不能改?

9. list 的迭代器为什么 insert 后不失效?

10. vector 为什么比 list 快(遍历)?

11. 什么情况用 vector 存指针更好?

12. `std::array` 和 vector 区别?

📖 答案提示(先自己答完再展开)
  1. 扩容 → 全失效(搬内存);见 2.2。
  2. map:需要有序/范围查询;unordered_map:海量查找、无序、好 hash。
  3. 平衡度要求松 → 旋转少、常数小,统计性能好。
  4. erase 后迭代器失效 → 用 it = v.erase(it)。
  5. 负载因子超阈值 → rehash → 全部迭代器失效。
  6. 省临时对象的构造 + 拷贝/移动。
  7. 多段定长连续缓冲区 + 中控器指针数组。
  8. key 是 const,改 key 会破坏红黑树有序性质。
  9. 节点式结构,插入只改指针,内存地址不变。
  10. 连续内存缓存友好。
  11. 对象太大、移动昂贵、需要稳定地址时(指针本身搬移便宜)。
  12. array 是固定大小的内嵌数组、不动态分配;vector 动态扩容、元素在堆上。

## 9. 进阶追问
  • 自定义类型作为 unordered_map 的 key 要提供什么?(std::hash<T> 特化 + operator==)
  • vector<bool> 为什么特殊?(按位压缩,operator[] 返回 proxy 不是 bool&)
  • 什么是 allocator?游戏引擎怎么自定义分配器让 STL 用内存池?(std::allocator 接口)
  • std::map 的 emplace_hint、lower_bound/upper_bound/equal_range 的用途?