主题
C++ STL
一、STL 整体概念
1. 六大组件
Q: STL 由哪六大组件构成?
| 组件 | 作用 | 典型代表 |
|---|---|---|
| 容器 | 存储数据 | vector, list, map, set |
| 算法 | 处理数据 | sort, find, for_each |
| 迭代器 | 连接容器与算法的桥梁 | begin(), end() |
| 适配器 | 改造接口 | stack, queue, priority_queue |
| 仿函数 | 像函数一样被调用的对象 | less<T>, greater<T> |
| 空间配置器 | 管理内存分配/释放 | allocator<T> |
2. 核心设计思想
Q: STL 的核心设计思想是什么?
| 思想 | 说明 |
|---|---|
| 算法与容器分离 | 算法通过迭代器访问容器,不直接依赖具体容器类型 |
| 迭代器 = 粘合剂 | vector 的迭代器是原生指针,list/map 的迭代器是封装的类对象 |
| 泛型编程 | 模板使得同一套代码可以作用于不同数据类型 |
二、序列容器
1. vector(最高频考点)
(1) 底层结构
Q: vector 的底层是怎么实现的?
连续内存数组,由三个指针管理:
| 指针 | 含义 | 关系 |
|---|---|---|
_start | 起始地址 | — |
_finish | 有效元素末尾 | _finish - _start = size() |
_end_of_storage | 容量末尾 | _end_of_storage - _start = capacity() |
cpp
// vector 内存布局示意
// [_start ........ _finish ........ _end_of_storage]
// |<- size() ->| |
// |<------- capacity() ---------->|(2) 为什么 vector 高效?
| 原因 | 说明 |
|---|---|
| 连续内存 | CPU 缓存友好,相邻元素被预取到缓存,缓存命中率接近 100% |
| 随机访问 O(1) | v[i] 等价于 *(start + i),一次指针运算 + 一次解引用 |
| 尾部操作摊还 O(1) | 偶尔扩容 O(n),但均摊下来每次 push_back 仍是常数时间 |
(3) 扩容机制(必考)
Q: vector 的扩容过程是怎样的?增长因子是多少?
触发条件:当 size() == capacity() 时,下次插入触发扩容。
扩容过程:
- 分配一块更大的新连续内存(大小 = 旧容量 × 增长因子)
- 将旧元素移动(若移动构造为
noexcept)或拷贝到新内存 - 析构旧内存中的元素
- 释放旧内存
- 更新三个内部指针
增长因子:
| 编译器 | 增长因子 |
|---|---|
| GCC / Clang (Linux) | 2 倍 |
| MSVC (Windows) | 1.5 倍 |
Q: 为什么 MSVC 选 1.5 倍而不是 2 倍?
关键在于内存复用。假设容量从 1 开始:
- 2 倍:1→2→4→8→16→32→64…,之前释放的所有内存加起来永远小于下一次需要的,旧块无法复用 → 内存碎片
- 1.5 倍:1→2→3→4→6→9→14→21→31→47…,大约第 6 次后,之前释放的内存块之和已超过下一次需求,
malloc可直接复用
数学上,当增长因子 **< φ(黄金比例 ≈ 1.618)**时,之前释放的内存可以被复用。
(4) reserve vs resize
Q: reserve 和 resize 的区别?
reserve(n) | resize(n) | |
|---|---|---|
改变 size()? | 否 | 是(新增元素值初始化) |
改变 capacity()? | 若 n > capacity 才会 | 若 n > capacity 才会 |
| 会构造元素吗? | 否 | 是,新元素用默认构造 |
| 使用场景 | 预分配,避免反复扩容 | 真正改变元素个数 |
cpp
vector<int> v;
v.reserve(1000); // capacity = 1000, size = 0
v.resize(500); // size = 500, 新增 500 个 0(5) push_back vs emplace_back
Q: push_back 和 emplace_back 的区别?
| 方式 | 构造过程 | 性能 |
|---|---|---|
push_back(x) | 先构造临时对象 → 拷贝/移动到容器 | 多一次构造 + 析构 |
emplace_back(args...) | 在容器末尾就地构造,参数完美转发 | 零拷贝 |
cpp
struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} };
vector<Point> v;
v.push_back(Point(1, 2)); // 构造临时对象 + 移动
v.emplace_back(1, 2); // 直接构造,无临时对象(6) 迭代器失效(必问核心)
Q: vector 什么时候迭代器失效?
| 操作 | 失效范围 |
|---|---|
push_back / emplace_back 触发扩容 | 全部迭代器、指针、引用 |
push_back / emplace_back 不扩容 | 仅 end() 失效 |
insert(触发扩容) | 全部迭代器 |
insert(不扩容) | 插入点及之后的所有迭代器 |
erase | 删除点及之后的所有迭代器 |
clear() | 全部失效 |
reserve / resize 导致扩容 | 全部失效 |
记忆口诀:扩容 = 全死;中间插入/删除 = 当前位置及后面都死。
(7) 安全删除元素
cpp
// ❌ 错误:迭代器失效!
for (auto it = v.begin(); it != v.end(); ++it) {
if (condition(*it)) v.erase(it); // it 已失效,++it 是 UB
}
// ✅ 方式一:用 erase 返回值
for (auto it = v.begin(); it != v.end(); ) {
if (condition(*it))
it = v.erase(it); // erase 返回下一个有效迭代器
else
++it;
}
// ✅ 方式二:Erase-Remove 惯用法(推荐)
v.erase(std::remove_if(v.begin(), v.end(), condition), v.end());(8) clear 不会释放内存
Q: clear() 会释放内存吗?
**不会!**只析构元素、置 size = 0,capacity 不变。
cpp
vector<int> v(1000000);
v.clear(); // size = 0,但 capacity 仍为 1000000!
v.shrink_to_fit(); // 请求释放多余容量(非强制)
// 强制释放:与空 vector 交换
vector<int>().swap(v); // 临时对象析构时带走旧内存(9) vector<bool> 的陷阱
Q: vector<bool> 有什么问题?
vector<bool> 是特化版本,每个 bool 只用 1 bit,导致:
v[0]返回的不是bool&,而是代理对象vector<bool>::reference- 不能取地址:
&v[0]编译错误
建议:用
vector<char>、deque<bool>或bitset替代。
2. list
(1) 底层结构
双向循环链表,每个节点包含:数据 + prev 指针 + next 指针。64 位系统下每节点额外开销 16 字节。
(2) 核心特性
| 特性 | 说明 |
|---|---|
| 插入/删除 | 任意位置 O(1)(已知迭代器位置) |
| 随机访问 | ❌ 不支持 l[i] |
| 迭代器安全 | 插入不影响任何迭代器,删除仅被删节点失效 |
| splice | O(1) 将另一个 list 的整段节点嫁接过来 |
(3) 为什么 list 不能用 std::sort?
Q: 为什么 list 不能用 std::sort?
std::sort 要求随机访问迭代器,list 只提供双向迭代器(不支持 it + n)。应使用 list::sort(),内部通常使用归并排序。
(4) vector vs list(经典对比)
Q: vector 和 list 的区别?什么时候用哪个?(高频)
| 维度 | vector | list |
|---|---|---|
| 内存结构 | 连续数组 | 分散的链表节点 |
| 随机访问 | O(1) | O(n) |
| 尾部插入/删除 | 摊还 O(1) | O(1) |
| 中间插入/删除 | O(n)(移动元素) | O(1) |
| 缓存命中率 | 极高 | 极低(每次解引用都可能 Cache Miss) |
| 迭代器安全 | 扩容/插入/删除都可能失效 | 插入不影响,删除仅被删节点失效 |
| 内存额外开销 | 几乎为零 | 每节点两个指针(64 位下 16 字节) |
经验法则:能用 vector 就不要用 list。现代 CPU 缓存层级下,连续内存的优势碾压一切。
3. deque
(1) 底层结构
Q: deque 的底层是怎么实现的?
分段连续内存 + 中控数组(map of buffers):
- 中控数组是一段连续内存,存储指向多个固定大小缓冲区的指针
- 每个缓冲区大小固定(通常 512 或 4096 字节,取决于元素类型)
[buffer0] [buffer1] [buffer2] [buffer3] [buffer4]
↑ ↑ ↑ ↑ ↑
└─────────┴──── map 数组 ────┴─────────┘(2) 设计优势
| 特性 | 说明 |
|---|---|
| 头/尾插入 O(1) | 在两端分配新 buffer,不移动已有元素 |
| 支持随机访问 | 两次间接寻址(查 map → 查 buffer) |
| 扩容不移动已有元素 | 核心优势:元素地址稳定 |
| 随机访问比 vector 慢 | 需要两次寻址 |
(3) deque 迭代器
deque 的迭代器是智能迭代器,包含四个指针:
| 指针 | 含义 |
|---|---|
cur | 当前元素位置 |
first | 当前 buffer 起始 |
last | 当前 buffer 末尾 |
node | 指向中控数组中对应项 |
(4) 为什么 stack/queue 默认用 deque?
Q: 为什么 stack 和 queue 默认用 deque 而不是 vector?
| 原因 | 说明 |
|---|---|
| 扩容不移动已有元素 | 引用/指针不失效 |
| 可动态释放 buffer | vector 的 capacity 只增不减 |
| 头尾操作更高效 | 两端都 O(1) |
4. string
Q: std::string 的底层和常用优化?
- 底层:连续内存(字符数组),类似
vector<char> - 现代
std::string采用深拷贝(旧版 COW 已在 C++11 废弃) c_str()返回const char*,保证以\0结尾substr()是 O(n),返回新 string(会分配内存)data()返回底层指针(C++17 起非 const 版本可修改)
cpp
// 优化:预分配 + 链式 append
string s;
s.reserve(1024);
s.append(s1).append(s2).append(s3); // 避免多次临时对象string_view(C++17):非拥有、只读的字符串视图,函数参数首选。
cpp
void process(std::string_view sv) {
if (sv.starts_with("http")) { ... }
}
process("hello"); // 零开销,无需构造临时 string注意:
string_view不拥有数据,不要返回局部变量的string_view(悬垂引用)。
三、关联容器
1. map / set(红黑树)
(1) 底层结构
Q: map 和 set 的底层是什么?红黑树有什么性质?(高频)
底层是红黑树——一种自平衡二叉搜索树。元素按 key 自动排序(默认升序)。
红黑树五大性质:
| # | 性质 |
|---|---|
| 1 | 每个节点是红色或黑色 |
| 2 | 根节点必须是黑色 |
| 3 | 所有叶子节点(NIL) 为黑色 |
| 4 | 红色节点的两个子节点必须都是黑色(不连红) |
| 5 | 从任意节点到其每个叶子节点的路径上,黑色节点数量相同 |
性质 4 + 5 保证 "最长路径 ≤ 2 × 最短路径",实现弱平衡。
(2) 红黑树 vs AVL 树
Q: STL 为什么用红黑树而不用 AVL 树?(高频)
| 维度 | 红黑树 | AVL 树 |
|---|---|---|
| 平衡要求 | 弱平衡(最长 ≤ 2× 最短) | 严格平衡(高度差 ≤ 1) |
| 插入/删除旋转 | 少,O(1) 摊还 | 多,O(log n) |
| 查找速度 | O(log n),稍慢 | O(log n),稍快 |
| 额外空间 | 1 bit(颜色) | 需存高度差 |
| 适用场景 | 增删频繁 | 查询频繁 |
STL 设计者认为实际工程中插入/删除同样频繁,红黑树综合性能更优。
(3) 核心特性
- 查找/插入/删除 O(log n)
- 迭代器遍历是中序遍历,结果有序
- 不能修改 key(会破坏红黑树结构)
- set 的 value 也不能修改(value 就是 key)
(4) map vs set(高频对比)
Q: map 和 set 有什么区别?(高频)
| 维度 | map | set |
|---|---|---|
| 存储内容 | 键值对 pair<const K, V> | 仅单一 key(元素本身就是 key) |
| 用途 | 通过 key 关联/存储一个 value | 判断"元素是否存在"(去重 / 集合) |
| 底层结构 | 红黑树 | 红黑树(完全相同) |
| 查找 | find 返回 pair 迭代器,it->second 取值 | find 返回元素迭代器,*it 即元素 |
| 修改 | key 不可改,value 可改 | 元素不可改(value 就是 key,改了破坏红黑树) |
operator[] | ✅ m[k](key 不存在时自动插入) | ❌ 没有 |
| 内存占用 | 节点多存一个 value | 节点只存 key,更省内存 |
| 重复元素 | key 唯一(multimap 可重复) | 元素唯一(multiset 可重复) |
| 典型场景 | 字典、计数、ID→对象映射 | 去重、集合运算、存在性判断 |
cpp
map<string, int> m; // 存键值对
m["a"] = 1; // 通过 key 关联 value
set<int> s = {3, 1, 2};
s.insert(3); // 已存在,插入无效 → 常用于去重
// 集合运算(手写题常见)
std::vector<int> v;
std::set_intersection(s1.begin(), s1.end(),
s2.begin(), s2.end(), back_inserter(v));记忆点:set 可以看作"只要 key 的 map"。二者底层同为红黑树,查找/插入/删除复杂度相同(O(log n))。
(5) operator[] vs insert vs at vs find
Q: map 的 operator[] 有什么陷阱?
| 方式 | key 不存在时 | key 存在时 | const map 可用? |
|---|---|---|---|
m[k] | 自动插入默认值 | 返回引用 | ❌ |
m.at(k) | 抛出 std::out_of_range | 返回引用 | ✅ |
m.insert({k,v}) | 插入,返回 pair | 不修改 | ✅ |
m.find(k) | 返回 end() | 返回迭代器 | ✅ |
常见陷阱:operator[] 会在 key 不存在时静默插入!
cpp
// ❌ 只想检查,却意外插入了
if (m[key] == 0) { ... } // 如果 key 不存在,会插入 {key, 0}
// ✅ 正确
if (m.find(key) != m.end()) { ... }
// C++20
if (m.contains(key)) { ... }(6) multimap / multiset
- 允许重复 key
- 没有
operator[](不知道该返回哪个值) equal_range(k)返回 key 对应的一组值的迭代器区间
2. unordered_map / unordered_set(哈希表)
(1) 底层结构
Q: unordered_map 的底层是什么?
链地址法(Separate Chaining)哈希表:
- 桶数组:连续内存,每个桶指向一个链表头
- 节点:包含 key、value、缓存的 hash 值(避免 rehash 时重复计算)、next 指针
- 哈希函数:
std::hash<Key>将 key 映射为size_t - 相等判断:
std::equal_to<Key>(默认operator==)
(2) 负载因子与 Rehash
| 概念 | 说明 |
|---|---|
| 负载因子 | size() / bucket_count() |
| 触发 rehash | 当 load_factor > max_load_factor()(默认 1.0) |
| rehash 过程 | 分配新桶数组 → 逐个重新计算哈希迁移 → O(n) |
| rehash 后果 | 所有迭代器失效 |
cpp
unordered_map<int, string> um;
um.reserve(10000); // 预分配桶数量,避免频繁 rehash(3) map vs unordered_map(必问)
Q: map 和 unordered_map 的区别?怎么选?(高频)
| 维度 | map | unordered_map |
|---|---|---|
| 底层 | 红黑树 | 哈希表 |
| 有序性 | 有序(自动排序) | 无序 |
| 查找/插入/删除 | O(log n)(稳定) | 平均 O(1),最坏 O(n) |
| 内存占用 | 存父子指针 + 颜色 | 哈希桶 + 链表指针 + 缓存 hash |
| 迭代器安全 | erase 仅被删节点失效 | rehash 时全部失效 |
| key 要求 | 支持 < | 需要 hash 函数 + == |
| 遍历 | 有序(中序) | 无序(按桶序) |
| 范围查询 | ✅ lower_bound | ❌ |
选型决策:
- 需要有序遍历 / 范围查询 → map
- 追求查询速度 → unordered_map
- 不确定时用
unordered_map,大部分场景查找频率远高于遍历频率
(4) 自定义类型作为 key
unordered_map 需要:
- 哈希函数:特化
std::hash或提供自定义仿函数 - 相等比较:
operator==或自定义仿函数
cpp
struct Person {
string name;
int id;
bool operator==(const Person& o) const {
return name == o.name && id == o.id;
}
};
struct PersonHash {
size_t operator()(const Person& p) const {
return hash<string>{}(p.name) ^ (hash<int>{}(p.id) << 1);
}
};
unordered_map<Person, int, PersonHash> um;(5) 哈希冲突解决方法
| 方法 | 说明 | 使用情况 |
|---|---|---|
| 链地址法 | 冲突元素挂链表 | STL unordered_map 采用 |
| 开放地址法 | 冲突时找下一个空位 | 谷歌 dense_hash_map 等 |
| 再哈希法 | 用第二个哈希函数 | 较少单独使用 |
(6) 实战:线程池中为什么用 unordered_map 存储线程?
线程池项目中,工作线程存储在 std::unordered_map<int, std::unique_ptr<Thread>> 中,选型理由如下:
| 方案 | 问题 |
|---|---|
vector<Thread> | Thread 含 std::thread 成员,不可拷贝;vector 扩容时会移动元素 → 线程绑定的 this 指针失效 → 崩溃 |
vector<Thread*> | 扩容时移动指针(8字节)是安全的,但查线程需要 O(n) 遍历 |
vector<unique_ptr<Thread>> | 同原生指针,但自动管理内存;查找仍然 O(n) |
unordered_map<int, unique_ptr<Thread>> | O(1) 精确查找 + 自动内存管理 + 方便动态删除 |
关键需求:Cached 模式下,需要根据线程 ID 频繁回收空闲线程。unordered_map::erase(threadId) 可以 O(1) 精准删除,而 vector 删除中间元素会导致后续全部移动。
为什么存指针而不存对象?
| 原因 | 说明 |
|---|---|
| 不可拷贝 | std::thread 对象不可拷贝,存值对象 vector 扩容时无法搬移 |
| 地址稳定性 | 线程创建时通过 std::bind 绑定了 this。对象在堆上地址不变,容器只搬指针 |
| 独占所有权 | unique_ptr 明确表达"线程对象只属于这个线程池" |
(7) 实战:emplace_back 在线程池中的应用
已在 vector 部分详述 emplace_back vs push_back。在线程池的 Cached 模式下,可能频繁创建/销毁 Thread 对象:
cpp// push_back:临时对象 → 移动到容器 → 析构临时对象(三步) threads_.push_back(std::make_unique<Thread>(func)); // emplace_back:直接在容器内存中构造(一步) threads_.emplace_back(std::make_unique<Thread>(func));高并发海量任务场景下,省去中间临时对象的构造/析构开销。对于
unique_ptr这种只能移动不能拷贝的类型,emplace也更优雅。
四、容器适配器
1. stack / queue
Q: 什么是容器适配器?
stack 和 queue 不是真正的容器,而是寄生在底层容器上、限制接口的适配器。
| 适配器 | 默认底层 | 行为 | 可替代底层 |
|---|---|---|---|
stack | deque<T> | LIFO(后进先出) | vector<T>, list<T> |
queue | deque<T> | FIFO(先进先出) | list<T> |
priority_queue | vector<T> | 优先级队列 | deque<T> |
- 不支持迭代器,不可遍历
- 只能访问顶部:stack →
top(),queue →front()/back()
2. priority_queue(高频)
(1) 本质
cpp
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue;- 物理结构:数组(vector)
- 逻辑结构:完全二叉树(堆)
- 默认大顶堆(最大值优先)
父子关系(数组下标):
parent = (child - 1) / 2left = parent * 2 + 1right = parent * 2 + 2
(2) Less 为什么是大顶堆?(高频陷阱)
Q: priority_queue 用
less<T>为什么是大顶堆?
堆调整的判断条件是:if (comp(parent, child)) → 成立就交换。
less<T>→parent < child时交换 → 大的被推上去 → 大顶堆greater<T>→parent > child时交换 → 小的被推上去 → 小顶堆
记结论:
less= "父小于子时交换" → 结果形成大堆。
cpp
// 默认大顶堆
priority_queue<int> pq1; // less<int>
// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq2; // greater<int>(3) 建堆为什么是 O(n)?
直观感觉每个元素向上调整 O(log n),n 个元素 = O(n log n)。但数学上:
- n/2 个叶子(高度 0):不调整
- n/4 节点高度 1:最多调整 1 次
- n/8 节点高度 2:最多调整 2 次
- 总操作数:n/4 + 2n/8 + 3n/16 + … < n × 常数 → O(n)
(4) 典型应用
| 问题 | 策略 | 复杂度 |
|---|---|---|
| 求前 K 大 | 小顶堆(维护 K 个,堆顶最小) | O(n log k) |
| 求前 K 小 | 大顶堆(维护 K 个,堆顶最大) | O(n log k) |
| 数据流中位数 | 双堆法(大顶堆存较小半 + 小顶堆存较大半) | O(log n) / 次 |
五、迭代器
1. 什么是迭代器(本质)
Q: 什么是迭代器?为什么需要它?
迭代器是连接容器与算法的"粘合剂":算法只操作迭代器接口(*it、++it),不关心容器底层是什么结构,所以同一套 std::sort、std::find 能适配不同容器。
本质:迭代器是一个轻量小对象,内部封装"指向容器元素的指针"。节点里不存迭代器,节点只存数据和维持结构的指针。
生命周期——"遍历时才创建,用完自动销毁":
- 迭代器不是容器"带"的:不用迭代器时,容器里也真的没有任何迭代器对象
- 它是遍历代码里声明的局部变量(栈对象):执行到声明语句才自动创建,离开作用域自动销毁,无堆分配、无资源释放,零负担
begin()只是按值返回一个临时迭代器,拷贝进你的变量后,临时对象随即消失
cpp
// ① 不用迭代器:容器里真的没有任何迭代器对象
for (size_t i = 0; i < v.size(); ++i) cout << v[i];
// ② 生命周期示例
{
auto it = v.begin(); // ← 这行代码执行时,it 才在栈上"诞生"(自动创建)
*it = 42; // 使用 it
} // ← 离开作用域,it 自动销毁(析构就是"消失")
// ③ for 循环里 it 只创建一次,++it 只是改它内部指针的值,it 本身一直活着
for (auto it = v.begin(); it != v.end(); ++it) { ... }| 容器 | 迭代器本质 | 对象大小 |
|---|---|---|
vector / string / array | 原生指针 T* | 8 字节 |
list / map / set | 封装节点指针的类 | 8 字节 |
deque | 封装 4 个指针的智能迭代器 | 32 字节 |
cpp
for (auto it = v.begin(); it != v.end(); ++it) {
cout << *it; // it 的类型是 vector<int>::iterator,内部就是一个 int*
}一个容器只有一套迭代器类型,但可以同时存在任意多个实例(像多张书签,都指向不同位置)。
2. 迭代器分类:5 种能力,由弱到强(高频)
Q: 迭代器分哪几种?每种能做什么?
记忆方法:分类 = 能力清单,后一种包含前一种的全部能力。
| 类型 | 能做什么 | 代表 |
|---|---|---|
| 输出 Output | 只写、单向、单次遍历 | ostream_iterator、back_inserter(写端) |
| 输入 Input | 只读、单向、单次遍历 | istream_iterator(读端) |
| 前向 Forward | 读写、单向、可多次遍历 | forward_list、unordered_map |
| 双向 Bidirectional | 前向 + 支持 -- 反向遍历 | list、map、set |
| 随机访问 RandomAccess | 双向 + 支持 it+n / it[i] / 比较 | vector、deque、string |
只写单向(Output) ──┐
├──► 前向(读写单向) ──► 双向(可倒退) ──► 随机访问(可跳跃)
只读单向(Input) ───┘各容器对应关系:
| 容器 | 迭代器类型 | 本质 |
|---|---|---|
ostream_iterator / back_inserter 等 | 输出(写端,非容器) | 写流 / 插入适配器 |
vector / string / array | 随机访问 | 原生指针(C++20 起称连续迭代器) |
deque | 随机访问 | 智能迭代器类(4 指针) |
list | 双向 | 封装的节点指针类 |
map / set | 双向 | 封装的节点指针类 |
unordered_map / unordered_set | 前向 | 封装的节点指针类 |
stack / queue | 不支持迭代器 | — |
要点:
std::sort要求随机访问迭代器——快排需要it + n跳跃寻址;list只有双向迭代器,所以不能用std::sort,只能用list::sort()。
3. 迭代器失效总结(高频)
Q: 各容器的迭代器什么时候失效?(高频)
| 操作 | vector | deque | list | map | unordered_map |
|---|---|---|---|---|---|
| 尾插(不扩容) | end 失效 | end 失效 | 无 | 无 | 无 |
| 尾插(扩容/rehash) | 全部 | — | — | — | 全部迭代器 |
| 中间插入 | 插入点+之后 | 插入点+之后 | 无 | 无 | 无(不 rehash) |
| erase | 删除点+之后 | 删除点+之后 | 仅被删 | 仅被删 | 仅被删 |
| clear | 全部 | 全部 | 全部 | 全部 | 全部 |
记忆口诀:"搬家全死,删谁死谁"——连续内存容器(vector/deque)扩容或中间增删导致元素"搬家",受影响位置之后的迭代器全失效;链表/树(list/map)元素地址不变,只有被删的那个迭代器失效。
4. 迭代器适配器(补充)
有些"迭代器"不是容器给的,而是算法输出/输入端的适配器,来自 <iterator> 库:
| 适配器 | 作用 | 示例 |
|---|---|---|
back_inserter(v) | 把赋值的元素 push_back 进容器 | copy(a.begin(), a.end(), back_inserter(v)) |
ostream_iterator<T>(cout, " ") | 把元素写入输出流 | copy(v.begin(), v.end(), ostream_iterator<int>(cout, " ")) |
istream_iterator<T>(cin) | 从输入流读取元素 | copy(istream_iterator<int>(cin), {}, back_inserter(v)) |
reverse_iterator | 反向遍历(rbegin() / rend() 返回) | for (auto it = v.rbegin(); it != v.rend(); ++it) |
它们属于输出/输入迭代器类别。这也解释了为什么容器表格里看不到输出迭代器——它不来自容器,来自算法库。
六、算法
1. sort 内部原理(必问)
Q: std::sort 的底层实现?为什么这么快?(高频)
std::sort 不是纯快排,而是内省排序(Introsort)——混合算法:
主体 (快排):
├─ 元素数 ≤ 16:退出,交给插入排序
├─ 递归深度 > 2·log₂n:切换到堆排序(防止退化 O(n²))
└─ 正常:三数取中选 pivot → 快排分区 → 单边递归优化
收尾 (插入排序):
└─ 此时数据已基本有序,插入排序接近 O(n)| 算法 | 使用场景 | 特点 |
|---|---|---|
| 快速排序 | 主体 | 平均最快 O(n log n),可能退化 O(n²) |
| 堆排序 | 递归过深时 | 稳定 O(n log n),常数因子大 |
| 插入排序 | 子区间 ≤ 16 或收尾 | 小规模/基本有序时近乎 O(n) |
核心优化:
- 三数取中选 pivot:避免选到极值导致退化
- 单边递归优化:只递归右半,左半迭代处理,省一半函数调用
- 无边界检查分区:三数取中保证 pivot 在范围内,省去边界判断
std::sort是不稳定排序,要求随机访问迭代器,复杂度 O(n log n)。
2. lower_bound / upper_bound
Q: lower_bound 和 upper_bound 的区别?
| 函数 | 含义 | 数组 {1,2,2,2,3} |
|---|---|---|
lower_bound(v, 2) | 第一个 ≥ 2 的位置 | 下标 1 |
upper_bound(v, 2) | 第一个 > 2 的位置 | 下标 4 |
| 区间 | [lower_bound, upper_bound) | 下标 1~3(三个 2) |
要求有序,底层二分查找,O(log n)。
3. 常用算法速查
| 算法 | 作用 | 复杂度 | 要求 |
|---|---|---|---|
sort | 排序(不稳定) | O(n log n) | 随机访问迭代器 |
stable_sort | 稳定排序 | O(n log n) | 随机访问迭代器 |
nth_element | 第 n 大到位 | 平均 O(n) | 随机访问迭代器 |
find | 顺序查找 | O(n) | — |
binary_search | 二分查找 | O(log n) | 有序 |
lower_bound | 第一个 ≥ x | O(log n) | 有序 |
upper_bound | 第一个 > x | O(log n) | 有序 |
reverse | 反转 | O(n) | 双向迭代器 |
for_each | 逐元素执行 | O(n) | — |
count | 计数 | O(n) | — |
unique | 去重(配合 erase) | O(n) | 需先排序 |
partition | 按条件分区 | O(n) | 双向迭代器 |
merge | 合并两有序序列 | O(n+m) | 有序 |
next_permutation | 下一个排列 | O(n) | 双向迭代器 |
fill | 填充 | O(n) | — |
copy / move | 拷贝/移动 | O(n) | — |
七、仿函数(Functor)
Q: 什么是仿函数?为什么用它而不用函数指针?
如果直接写一个 bool myCompare(int a, int b)函数,然后把函数名传进去,此时它依然会退化成函数指针
仿函数是重载了 operator() 的类,其对象可以像函数一样被调用。
cpp
template<class T>
struct Less {
bool operator()(const T& a, const T& b) const { return a < b; }
};
int main() {
Less<int> isLess;
int x = 10, y = 20;
// 实际上调用了 isLess.operator()(x, y)
if (isLess(x, y))
std::cout << x << " 小于 " << y << std::endl;
// 使用 Less<int> 实例进行升序排序
std::vector<int> nums = {5, 2, 8, 1, 9};
std::sort(nums.begin(), nums.end(), Less<int>());
return 0;
}① 性能更高(编译器优化/内联)
- 函数指针:是一个指向代码段地址的变量。在运行时,编译器通过地址跳转去执行函数。编译器在编译期间只知道这是一个地址,不知道具体要执行哪段代码,编译器很难对其进行内联优化。
- 仿函数:是一个具体的类类型。当把仿函数传递给
std::sort等模板函数时,模板会根据这个具体的类生成一份专门的代码。编译器清楚地知道调用的是哪个类的 operator(),从而能极高概率地进行内联优化,消除函数调用的开销。
② 可以拥有“状态”(State)
- 函数指针:函数本身不保存状态,只能访问全局变量或传入的参数。有安全性问题
- 仿函数:**对象本身可以拥有成员变量。**它能“记住”配置信息、计数器、上下文等。
- 例子:可以创建一个 Add(5) 仿函数和一个 Add(10) 仿函数。它们虽然类型相同,但内部“状态”不同。
3 其他。。。。
仿函数带状态的例子:
状态一般是通过构造时,通过传参记录状态
cpp
struct SumFunctor {
int total = 0; // 这就是“状态” (State)
// 每调用一次,都会改变内部的状态
int operator()(int x) {
total += x;
return total;
}
};
int main() {
SumFunctor s1; // 创建第一个累加器
std::cout << s1(10) << std::endl; // 输出 10 (total变成了10)
std::cout << s1(20) << std::endl; // 输出 30 (total变成了30)
SumFunctor s2; // 创建第二个累加器(状态独立)
std::cout << s2(5) << std::endl; // 输出 5 (s2有自己的total)
return 0;
}函数指针指向的是一段纯粹的代码。代码段在程序运行期间是只读的、固定的。
- 没有存储空间:普通函数没有像类那样的“成员变量”来存储每个实例特有的数据。
- 无法个性化定制:函数逻辑是写死的。如果你想写一个“加 5 的函数”和一个“加 10 的函数”,你必须写两个不同的函数名。
常见内置仿函数及其应用位置:
| 仿函数 | 应用位置 |
|---|---|
less<T> | std::sort 默认(升序)、set/map 默认排序、priority_queue 默认(但形成大顶堆) |
greater<T> | 小顶堆 priority_queue、降序排序的比较器参数 |
equal_to<T> | unordered_map 的相等判断(默认 operator==) |
plus/minus/multiplies | 数值算法(如 std::accumulate 的累加器) |
Lambda 与仿函数:Lambda 的底层实现就是一个仿函数类(编译器展开生成),兼具仿函数的性能和函数指针的简洁。
为什么无状态 Lambda 能转函数指针,有状态的不能?(高频追问)
- 无状态 lambda = 没有捕获成员的"空仿函数类",调用不依赖任何对象数据 → 可退化为普通函数指针
- 有状态 lambda = 类里有捕获的成员变量,调用依赖对象中的数据 → 函数指针没有对象,无法转换
cpp
auto f1 = [](int x) { return x * 2; }; // 无捕获 → 空类
int (*fp)(int) = f1; // ✅ 可转函数指针
int base = 5;
auto f2 = [base](int x) { return base + x; }; // 捕获 base → 有成员
int (*fp2)(int) = f2; // ❌ 编译错误
std::function<int(int)> sf = f2; // ✅ 用 std::function 包装(类型擦除)为 set / map 自定义排序规则:
cpp
struct Person
{
string name;
int age;
};
// 方式一:自定义仿函数作为第三个模板参数
struct ByAge {
bool operator()(const Person& a, const Person& b) const {
return a.age < b.age; // 语义:"a 是否排在 b 前面"(严格弱序)
}
};
set<Person, ByAge> s; // 按年龄排序
map<Person, int, ByAge> m; // map 的第三个模板参数同理
// 方式二:lambda + decltype(注意构造时要传比较器对象)
auto cmp = [](const Person& a, const Person& b) { return a.age < b.age; };
set<Person, decltype(cmp)> s2(cmp);八、空间配置器(Allocator)
1. 定位与职责
Q: 空间配置器的作用是什么?
将内存管理与对象构造彻底分离:
| 操作 | 职责 | 底层 |
|---|---|---|
allocate(n) | 分配 n 字节原始内存 | malloc |
deallocate(p, n) | 释放原始内存 | free |
construct(p, args...) | 在内存上构造对象 | placement new |
destroy(p) | 析构对象 | 显式调用析构函数 |
new=operator new(分配) + 构造;delete= 析构 +operator delete(释放)
2. SGI STL 两级配置器(核心考点)
以 128 字节为分界:
| 级别 | 范围 | 策略 |
|---|---|---|
| 第一级 | > 128 字节 | 直接封装 malloc/free,提供 OOM 处理 |
| 第二级 | ≤ 128 字节 | 内存池 + 自由链表 |
第二级详细机制:less<T>
| 组件 | 说明 |
|---|---|
| 自由链表 | 16 条链表,管理 8/16/24/…/128 字节的块,分配/释放 O(1) |
| 内存池 | 链表空时批量为链表补充 20 个块,减少 malloc 调用 |
| Union 优化 | 节点用 union 复用空间,分配给用户后不浪费指针字节 |
| 优点 | 缺点 |
|---|---|
| 小块分配极快(O(1)) | 内部碎片(对齐到 8 倍数) |
| 减少外部碎片 | 内存不归还 OS(进程结束才释放) |
| 减少系统调用 | 额外管理逻辑复杂 |
为什么 vector 不能原地扩容?Allocator 接口缺少
realloc,且内存池中相邻地址可能已被其他链表占用。
3. 使用空间配置器的好处
Q: 为什么要空间配置器?直接用 new/malloc 不行吗?
| 好处 | 说明 |
|---|---|
| 减少系统调用 | 二级配置器的内存池批量向 OS 申请,小块分配不再触发 malloc/free |
| 减少内存碎片 | 小内存对齐到 8 的倍数统一管理,释放的小块可被复用 |
| 分配极快 | 自由链表取块 O(1) |
| 构造与分配分离 | allocate 只拿内存、construct 才构造对象,避免无谓的对象构造/析构 |
| 可替换性 | 自定义 allocator(内存池、TLS 等)可无缝替换,容器代码不用改 |
一句话总结:空间配置器把**"内存获取"与"对象构造"解耦**,用内存池 + 自由链表规避频繁系统调用和内存碎片——这正是内存池项目的理论根基。
九、实战避坑
1. 容器选型决策树
需要随机访问?
├─ 是 → 主要尾部操作?→ vector(首选)
│ └─ 需要两端操作?→ deque
└─ 否 → 按键查找?
├─ 需要有序/范围查询?→ map/set
└─ 无序 → unordered_map/set
└─ 频繁中间插入/删除且不查找?→ list(极少用)默认用
vector,特殊需求再换。
2. 最常见性能陷阱
| # | 陷阱 | 错误做法 | 正确做法 |
|---|---|---|---|
| ① | vector 频繁扩容 | 不预分配 | v.reserve(n) |
| ② | 遍历时拷贝元素 | for (auto p : map) | for (const auto& p : map) |
| ③ | map[k] 意外插入 | if (m[k] == 0) | m.find(k) != m.end() 或 m.contains(k) |
| ④ | 循环内反复创建容器 | 每次 new 临时容器 | 循环外创建,clear() 复用 |
| ⑤ | 删除时迭代器失效 | v.erase(it); ++it; | it = v.erase(it); 或 Erase-Remove |
| ⑥ | 无脑用 map | 不需要有序也用 map | 无序场景用 unordered_map(快 3~5 倍) |
| ⑦ | 大对象用 push_back | 产生临时对象 | 用 emplace_back |
| ⑧ | vector<bool> 取地址 | bool* p = &v[0] | 用 vector<char> 或 deque<bool> |
4. 实战:std::array vs std::vector 选型分析
Q: 什么时候用 std::array 而不是 std::vector?
内存池项目中大量使用 std::array,如自由链表数组 std::array<void*, 32768>。选型依据:
| 维度 | std::array<T, N> | std::vector<T> | C 数组 T[N] |
|---|---|---|---|
| 内存位置 | 栈 / 静态区 | 堆(动态分配) | 栈 / 静态区 |
| 大小 | 编译期固定 | 运行时可变 | 编译期固定 |
| 堆分配开销 | ❌ 无 | ✅ 有(new/malloc) | ❌ 无 |
| STL 接口 | ✅ size(), at(), 迭代器 | ✅ 完整 | ❌ 几乎没有 |
| 边界检查 | at() 有检查 | at() 有检查 | ❌ 无 |
内存池为什么选 std::array?
cpp
// ThreadCache 的自由链表:编译期就知道是 32768 个槽位
std::array<void*, 32768> freeList_; // 约 256KB,在 TLS 中
std::array<size_t, 32768> freeListSize_; // 约 256KB
// 如果改用 vector:
// std::vector<void*> freeList_(32768); // 堆分配!内存池自身先产生堆碎片| 考量 | 说明 |
|---|---|
| 避免递归依赖 | 内存池的目的是管理堆内存,如果自身用 vector(堆分配),等于"用堆管理堆"——逻辑矛盾 |
| 性能 | 栈上分配 vs 堆分配:array 构造时零开销,vector 需要 new |
| 确定性 | 编译期固定大小,访问 O(1),无扩容担忧 |
| 缓存局部性 | 连续内存(同 C 数组),CPU 预取高效 |
代价评估:32768 × sizeof(void*) = 256KB(每个 ThreadCache 的自由链表),100 个线程约 50MB。相比 pthread 默认 8MB 栈空间,这是可接受的代价。
选型原则:编译期能确定大小 →
std::array;运行时大小可变 →std::vector。内存池、线程池中固定大小的表结构是std::array的典型应用场景。
3. 多线程环境
Q: STL 容器是线程安全的吗?
**不是!**并发写需要外部加锁:
- 可以多线程同时读同一容器
- 任何写操作必须由调用方自行加锁
- 迭代器生命周期内,容器必须保持不被修改
cpp
std::mutex mtx;
std::vector<int> v;
// 线程安全写法
{
std::lock_guard<std::mutex> lock(mtx);
v.push_back(42);
}deque 在多线程日志系统中优势:扩容不移动已有元素,不影响消费者持有的指针。
十、手写实现类题目
以下为常见的手写题框架,考察对 STL 底层原理的理解。
1. vector 简化实现
cpp
template<typename T>
class MyVector {
T* _start = nullptr;
T* _finish = nullptr;
T* _end_of_storage = nullptr;
public:
MyVector() = default;
~MyVector() {
clear();
::operator delete(_start);
}
MyVector(const MyVector& other) { // 深拷贝
reserve(other.size());
for (size_t i = 0; i < other.size(); ++i)
new(_start + i) T(other[i]);
_finish = _start + other.size();
}
void reserve(size_t n) {
if (n > capacity()) {
size_t old_size = size();
T* new_data = static_cast<T*>(::operator new(n * sizeof(T)));
for (size_t i = 0; i < old_size; ++i)
new(new_data + i) T(std::move(_start[i])); // 移动旧元素
for (size_t i = 0; i < old_size; ++i)
_start[i].~T(); // 析构旧元素
::operator delete(_start);
_start = new_data;
_finish = _start + old_size;
_end_of_storage = _start + n;
}
}
void push_back(const T& val) {
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 1 : capacity() * 2);
new(_finish) T(val);
++_finish;
}
template<typename... Args>
void emplace_back(Args&&... args) {
if (_finish == _end_of_storage)
reserve(capacity() == 0 ? 1 : capacity() * 2);
new(_finish) T(std::forward<Args>(args)...);
++_finish;
}
void pop_back() { --_finish; _finish->~T(); }
void clear() {
for (size_t i = 0; i < size(); ++i) _start[i].~T();
_finish = _start;
}
size_t size() const { return _finish - _start; }
size_t capacity() const { return _end_of_storage - _start; }
T& operator[](size_t i) { return _start[i]; }
T* begin() { return _start; }
T* end() { return _finish; }
};考点:三指针管理、深拷贝、移动语义、placement new、完美转发。
2. LRU Cache(list + unordered_map 经典组合)
cpp
class LRUCache {
int _capacity;
list<pair<int, int>> _list; // 存 {key, value}
unordered_map<int, list<pair<int, int>>::iterator> _map; // key → 链表位置
public:
LRUCache(int cap) : _capacity(cap) {}
int get(int key) {
auto it = _map.find(key);
if (it == _map.end()) return -1;
_list.splice(_list.begin(), _list, it->second); // O(1) 移到头部
return it->second->second;
}
void put(int key, int value) {
auto it = _map.find(key);
if (it != _map.end()) {
it->second->second = value;
_list.splice(_list.begin(), _list, it->second);
return;
}
if (_list.size() == _capacity) {
_map.erase(_list.back().first);
_list.pop_back();
}
_list.push_front({key, value});
_map[key] = _list.begin();
}
};考点:splice O(1) 链表嫁接、两个容器组合使用、迭代器稳定性的利用。
十一、高频问答
Q1: vector 扩容机制?迭代器什么时候失效?
扩容 = 新分配 + 移动/拷贝 + 释放旧内存 + 更新指针。扩容 → 全部迭代器失效;中间插入/删除 → 当前位置及之后失效。
Q2: vector 和 list 区别?
vector 连续内存,O(1) 随机访问,缓存友好;list 链表,O(1) 任意位置增删,迭代器稳定。默认选 vector。
Q3: map 和 unordered_map 区别?
map 红黑树,有序,O(log n) 稳定;unordered_map 哈希表,无序,平均 O(1)。需要有序 → map,追求速度 → unordered_map。
Q4: 红黑树为什么不用 AVL?
红黑树弱平衡,插入删除旋转次数少(摊还 O(1)),实际工程增删和查找同样频繁。
Q5: sort 底层实现?
内省排序:快排主体 + 递归过深转堆排 + 小区间插入排序。
Q6: priority_queue 用
less为什么是大顶堆?判断条件是
comp(parent, child),less= parent < child 时交换,大的上浮 → 大顶堆。
Q7: emplace_back 和 push_back 区别?
emplace_back 原地构造,省去临时对象的构造和移动开销。对大对象和有参构造优先用 emplace_back。
Q8: reserve 和 resize 区别?
reserve 只改 capacity,不改 size,不构造元素;resize 改 size,会构造/析构元素。
Q9: clear() 会释放内存吗?
不会!只析构元素、size=0,capacity 不变。释放用
shrink_to_fit()或swap(空容器)。
Q10: 为什么 list 不能用 std::sort?
std::sort要求随机访问迭代器,list 只提供双向迭代器。应使用list::sort()。
Q11: vector<bool> 有什么问题?
特化版本每个 bool 占 1 bit,
v[0]返回代理对象,不能取地址。用vector<char>替代。
Q12: deque 和 vector 最主要的区别?
deque 扩容不移动已有元素(分段存储),vector 扩容所有元素移到新地址。元素地址稳定性是 deque 的核心优势。
Q13: unordered_map 负载因子是什么?
size() / bucket_count(),超过max_load_factor()(默认 1.0)触发 rehash → O(n) 且迭代器全失效。
Q14: map 的 operator[] 陷阱?
key 不存在时会静默插入默认值。检查存在性用
find()或contains()(C++20)。
Q15: STL 容器线程安全吗?
不是!多线程写必须外部加锁。可多线程同时读。