14.4 阶段 3 STL 与泛型编程
所属:全栈开发面试题库 / 学习路径 / 14 C++ 与系统开发
本页目录
一、阶段定位
本阶段解决"用标准库写业务代码"。C++ 的 STL(标准模板库)提供了容器、迭代器、算法、函数对象——会用这些,80% 的日常数据结构不用自己造。但 STL 也是面试重灾区:vector 扩容、map 红黑树、迭代器失效、算法复杂度,这些答不上来直接挂。
不掌握本阶段会在后面具体卡在哪:
- 手写链表、手写排序、手写查找,代码比 STL 慢且易错,面试官一问"为什么不用
std::sort"就答不上。 vector遍历时erase导致迭代器失效,程序偶发崩溃,GDB 打出栈在_M_erase里。- 分不清
map与unordered_map的复杂度差异,在热点路径用std::map做查找,性能比 hash_map 慢十倍。 - 写泛型函数时只会用
typename T,不会用 C++20 concepts 约束模板参数,报错信息一屏长看不懂。
判断自己卡住的标志:(1) 让你说出 vector、deque、list、map、unordered_map 的底层结构与复杂度,你只能说"vector 是数组";(2) 给一段 for (auto it = v.begin(); it != v.end(); ++it) if (...) v.erase(it); 代码,你找不到 bug;(3) 用 std::find、std::sort 时不会传 lambda 自定义比较。出现任一现象,先把本阶段六个模块过一遍再进 阶段 4 并发与多线程。
二、阶段目标与投入
| 能力目标(可验证的行为) | 验证方式 |
|---|---|
| 能说出常用容器的底层结构、复杂度与适用场景 | 给场景选容器并说明理由 |
| 能正确使用迭代器,知道哪些操作会使迭代器失效 | 给一段代码,指出失效点 |
能熟练使用 std::sort、find、for_each、transform 等算法 |
用算法替代手写循环 |
| 能写 lambda 作为算法参数,理解捕获与闭包 | 用 lambda 做排序与过滤 |
| 能用 C++20 ranges 写管道式数据处理 | 用 ranges 替代嵌套循环 |
| 能写一个泛型函数模板,并用 concepts 约束参数 | 编译通过,报错友好 |
建议学时:
- 全职(每天 4–6 小时):3–4 周,约 60–70 小时。其中容器 16 小时、迭代器 8 小时、算法 16 小时、lambda 与函数对象 8 小时、ranges 8 小时、concepts 与泛型设计 8 小时、练习 10 小时。
- 在职(每天 2 小时、周末补 4 小时):6–8 周,约 70 小时。
学时分配:容器 25%、迭代器 10%、算法 25%、lambda 10%、ranges 10%、concepts 10%、练习 10%。
三、先修自检
| 先修项 | 合格标准 | 不合格时怎么办 |
|---|---|---|
| 阶段 1 语法 | 懂模板、auto、lambda、引用 | 回到 阶段 1 |
| 阶段 2 内存 | 懂对象生命周期、智能指针 | 回到 阶段 2 |
| 数据结构基础 | 知道数组、链表、树、哈希表的概念 | 补一遍本科数据结构 |
| 复杂度分析 | 能区分 O(1)、O(log n)、O(n)、O(n log n) | 补算法复杂度基础 |
四、知识地图
| 模块 | 知识点 | 掌握程度 | 对应题库章节 |
|---|---|---|---|
| 序列容器 | vector、deque、list、array、string |
能讲清原理 | 04.9.2 STL 容器与迭代器失效 |
| 关联容器 | map、set、multimap、unordered_map、unordered_set |
能讲清原理 | 04.9.2 STL 容器与迭代器失效 |
| 迭代器 | 输入/输出/前向/双向/随机访问;迭代器失效规则 | 能讲清原理 | 04.9.2 STL 容器与迭代器失效 |
| 算法 | sort、find、copy、transform、accumulate、for_each |
会用 | 04.9.2 STL 容器与迭代器失效 |
| lambda 与函数对象 | 捕获、闭包、std::function、std::bind |
会用 | 04.9.2 STL 容器与迭代器失效 |
| ranges(C++20) | 视图、管道、延迟求值、适配器 | 会用 | 04.9.2 STL 容器与迭代器失效 |
| concepts | requires、标准 concepts、自定义 concept |
会用 | 04.9.2 STL 容器与迭代器失效 |
五、分模块精讲
5.1 常用容器与底层结构
为什么需要它:选错容器,性能差十倍。vector 是连续内存、list 是链表、map 是红黑树、unordered_map 是哈希表——各自适用场景完全不同。
核心机制:
vector<T>:动态数组,连续内存;随机访问 O(1);尾部插入 O(1) 摊还;中间插入 O(n);扩容时移动所有元素。deque<T>:分段连续;头尾插入 O(1);随机访问 O(1) 但比 vector 慢。list<T>:双向链表;任意位置插入 O(1);不支持随机访问;额外指针开销大。map<K,V>:红黑树;查找 O(log n);按键有序;适合需要有序遍历。unordered_map<K,V>:哈希表;平均 O(1);最坏 O(n)(哈希冲突);无序;适合纯查找。- 选型经验:默认
vector;需要键值查找用unordered_map;需要有序遍历用map;不要用list除非有明确的中间插入/删除需求。
最小可运行示例:
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>
int main() {
std::vector<std::string> names = {"ann", "bob", "carol"};
names.push_back("dave"); // 尾部 O(1)
std::unordered_map<std::string, int> ages;
ages["ann"] = 30;
ages["bob"] = 25;
for (const auto& [name, age] : ages) { // C++17 结构化绑定
std::cout << name << " is " << age << "\n";
}
// vector 预分配,避免扩容
std::vector<int> nums;
nums.reserve(1000);
for (int i = 0; i < 1000; ++i) nums.push_back(i);
return 0;
}
常见坑:
| 现象 | 原因 | 修法 |
|---|---|---|
| vector push 慢 | 反复扩容拷贝 | reserve() 预分配 |
| map 查找慢 | 红黑树 O(log n),热点路径 | 改 unordered_map |
| unordered_map 最坏 O(n) | 哈希冲突或恶意输入 | 自定义哈希或用 std::map |
5.2 迭代器与失效规则
为什么需要它:STL 算法与容器通过迭代器交互。不知道哪些操作会使迭代器失效,遍历中删除元素就会崩。
核心机制:
- 迭代器类别:输入迭代器(
++读)、输出迭代器(++写)、前向迭代器、双向迭代器(--)、随机访问迭代器(+n)。 vector:插入/删除尾部之外会使所有迭代器失效;erase返回下一个有效迭代器。deque:头尾插入使迭代器失效;中间插入使所有迭代器失效。list/map/set:只有被删元素的迭代器失效,其他不受影响。- 正确写法:
it = v.erase(it);,而不是v.erase(it); ++it;。
最小可运行示例:
#include <iostream>
#include <vector>
int main() {
std::vector<int> v = {1, 2, 3, 4, 5, 6};
// 正确:erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end(); ) {
if (*it % 2 == 0) {
it = v.erase(it); // erase 后 it 指向下一个
} else {
++it;
}
}
for (int n : v) std::cout << n << " "; // 1 3 5
std::cout << "\n";
return 0;
}
常见坑:
| 现象 | 原因 | 修法 |
|---|---|---|
| 遍历中 erase 后崩溃 | 迭代器失效 | 用 it = v.erase(it) 模式 |
| vector insert 后迭代器乱 | 插入导致扩容 | 重新获取迭代器 |
5.3 常用算法与 lambda
为什么需要它:手写循环容易越界、漏边界;STL 算法经过高度优化,可读性更好。
核心机制:
- 不修改序列算法:
find、count、for_each、all_of、any_of、none_of。 - 修改序列算法:
copy、transform、replace、remove、fill。 - 排序与划分:
sort、stable_sort、nth_element、partition。 - 二分查找:
lower_bound、upper_bound、binary_search(要求已排序)。 - lambda 作为谓词:
[](int a, int b) { return a > b; }做降序排序。
最小可运行示例:
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
int main() {
std::vector<int> v = {5, 2, 8, 1, 9, 3};
std::sort(v.begin(), v.end(), [](int a, int b) { return a > b; }); // 降序
for (int n : v) std::cout << n << " ";
std::cout << "\n";
auto it = std::find_if(v.begin(), v.end(), [](int n) { return n > 5; });
if (it != v.end()) std::cout << "first >5: " << *it << "\n";
int sum = std::accumulate(v.begin(), v.end(), 0);
std::cout << "sum: " << sum << "\n";
std::vector<int> squared;
std::transform(v.begin(), v.end(), std::back_inserter(squared),
[](int n) { return n * n; });
return 0;
}
常见坑:
| 现象 | 原因 | 修法 |
|---|---|---|
| sort 后 binary_search 找不到 | 排序顺序与查找假设不一致 | 统一用 std::less |
| transform 目标容器越界 | 目标容器大小不够 | 用 back_inserter |
5.4 ranges 管道(C++20)
为什么需要它:嵌套循环与临时容器可读性差,ranges 用管道把"过滤、变换、取值"串成一条链。
核心机制:
- 视图(view):不持有数据,只引用原容器;惰性求值。
- 管道:
container | views::filter(...) | views::transform(...) | views::take(...)。 - 与传统算法对比:传统算法需要嵌套调用
transform(..., filter(...), ...);ranges 从左到右读。 - 不产生中间容器,性能与手写循环相当。
最小可运行示例:
#include <iostream>
#include <ranges>
#include <vector>
int main() {
std::vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
auto result = nums
| std::views::filter([](int n) { return n % 2 == 0; })
| std::views::transform([](int n) { return n * n; })
| std::views::take(3);
for (int v : result) std::cout << v << " "; // 4 16 36
std::cout << "\n";
return 0;
}
常见坑:
| 现象 | 原因 | 修法 |
|---|---|---|
| ranges 编译报错嵌套深 | 视图类型复杂 | 用 auto 接收,不要手写类型 |
| 视图引用了临时容器 | 临时对象析构后视图悬垂 | 确保原容器存活 |
5.5 concepts 与泛型设计
为什么需要它:无约束的模板报错信息一屏长。concepts 让编译器只接受满足条件的类型,报错从"no matching function"变成"requires integral
核心机制:
- 标准 concepts:
std::integral、std::floating_point、std::same_as、std::derived_from、std::convertible_to、std::ranges::range。 requires表达式:requires(T a, T b) { a + b; }检查表达式合法。- 三种写法:
template<typename T> requires std::integral<T>、template<std::integral T>、T add(T a, T b) requires std::integral<T>。 - 自定义 concept:
template<typename T> concept Addable = requires(T a, T b) { a + b; };。
最小可运行示例:
#include <concepts>
#include <iostream>
#include <string>
template<std::integral T>
T add(T a, T b) { return a + b; }
template<typename T>
concept Addable = requires(T a, T b) { a + b; };
template<Addable T>
T add_generic(T a, T b) { return a + b; }
int main() {
std::cout << add(1, 2) << "\n"; // 3
std::cout << add_generic(std::string("a"),
std::string("b")) << "\n"; // ab
// add(1.5, 2.5); // 编译失败:double 不满足 integral
return 0;
}
常见坑:
| 现象 | 原因 | 修法 |
|---|---|---|
| concept 约束太严 | 把可转换类型也排除了 | 用 std::convertible_to 代替 same_as |
| 自定义 concept 报错 | requires 表达式写得不对 | 先单独测 requires 表达式 |
5.6 自定义类型与容器适配
为什么需要它:把自定义类型放进容器排序、查找,需要定义比较运算符或提供自定义谓词。
核心机制:
operator<:std::sort默认用<;std::map默认按键<。- 自定义谓词:
std::sort(v.begin(), v.end(), MyCompare{})。 std::pair:默认按 first 再 second 排序。std::tuple:字典序比较。
最小可运行示例:
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
struct Person {
std::string name;
int age;
};
int main() {
std::vector<Person> people = {{"ann", 30}, {"bob", 25}, {"carol", 35}};
// 按年龄升序
std::sort(people.begin(), people.end(),
[](const Person& a, const Person& b) { return a.age < b.age; });
for (const auto& p : people) {
std::cout << p.name << "(" << p.age << ") ";
}
std::cout << "\n";
return 0;
}
六、分层练习
6.1 复现型
| 练习 | 要求 | 验收标准 | 预计耗时 |
|---|---|---|---|
| 容器选型 | 给 5 个场景选容器并说明理由 | 选择正确,复杂度理由清晰 | 2 小时 |
| 迭代器失效 | 给一段遍历中 erase 的代码,指出 bug | 能定位失效点并修复 | 1 小时 |
| 算法替代循环 | 把一段手写循环改成 std::sort + lambda | 行为一致,代码更短 | 1 小时 |
| ranges 管道 | 用 ranges 实现过滤+变换+取前 N | 输出正确 | 1 小时 |
| concepts 约束 | 写一个 add 模板,要求整数类型 |
double 调用编译失败 | 1 小时 |
6.2 改造型
| 练习 | 要求 | 验收标准 | 预计耗时 |
|---|---|---|---|
| vector 性能优化 | 给一个频繁 push 导致扩容的代码,加 reserve | 扩容次数从 O(n) 降到 1 | 1 小时 |
| map 换 unordered_map | 热点路径用 map,改 unordered_map 对比性能 | 查找耗时下降 | 2 小时 |
| 修复迭代器崩溃 | 故意写一个 erase 导致崩溃的代码,用 ASan 定位修复 | ASan 0 报错 | 1 小时 |
| 自定义排序 | 给 Person 结构体按年龄排序、按姓名排序 | 两种排序都正确 | 1 小时 |
6.3 设计型
| 练习 | 要求 | 验收标准 | 预计耗时 |
|---|---|---|---|
| 设计一个 LRU 缓存 | 用 list + unordered_map 实现 |
O(1) get/put | 4 小时 |
| 整理容器选型表 | 列出 10 个常用容器的复杂度与适用场景 | 表格可作为面试速查 | 2 小时 |
| 泛型算法库 | 写一组泛型函数(max、filter、map),用 concepts 约束 | 支持 int、string、自定义类型 | 4 小时 |
七、排障表
| 现象 | 可能原因 | 排查步骤 | 解决办法 |
|---|---|---|---|
| 遍历中 erase 后崩溃 | 迭代器失效 | ASan 跑复现 | 用 it = v.erase(it) 模式 |
| vector push 慢 | 反复扩容 | 看 capacity 变化 | reserve() 预分配 |
| map 查找比 unordered_map 慢 | 红黑树 O(log n) | 对比耗时 | 热点路径用 unordered_map |
| sort 后 binary_search 找不到 | 排序顺序不一致 | 检查比较函数 | 统一用 std::less |
| ranges 编译报错 | 视图类型复杂 | 从最后一行往上读 | 用 auto 接收 |
| concept 模板报错 | 类型不满足约束 | 看 requires 表达式 | 检查类型,放宽约束 |
| transform 越界 | 目标容器大小不够 | 看目标容器 | 用 back_inserter |
| list 随机访问慢 | 链表不支持 O(1) 访问 | 看算法 | 换 vector |
八、出口条件
全部勾选后进入 阶段 4 并发与多线程。
- [ ] 能说出常用容器的底层结构、复杂度与适用场景
- [ ] 能正确使用迭代器,知道哪些操作会使迭代器失效
- [ ] 能熟练使用 STL 算法与 lambda,替代手写循环
- [ ] 能用 ranges 写管道式数据处理
- [ ] 能用 concepts 约束模板参数,写出类型安全的泛型函数
- [ ] 能为自定义类型定义排序与查找逻辑
- [ ] 能根据场景选对容器并说明复杂度理由
自测题:
vector、deque、list的底层结构与复杂度差异?- 要点:vector 连续数组 O(1) 随机访问;deque 分段连续;list 双向链表 O(1) 插入但无随机访问。
map与unordered_map的区别?什么时候用哪个?- 要点:map 红黑树 O(log n) 有序;unordered_map 哈希表 O(1) 无序;需要有序遍历用 map,纯查找用 unordered_map。
- 迭代器在哪些操作后会失效?怎么正确地遍历中删除?
- 要点:vector 插入删除使所有迭代器失效;用
it = v.erase(it)模式。
- 要点:vector 插入删除使所有迭代器失效;用
- ranges 相比传统 STL 算法的优势?
- 要点:管道式组合、延迟求值、不产生中间容器。
- concepts 解决什么问题?
- 要点:约束模板参数,让报错从"no matching function"变成"requires xxx",提升可读性。
- 为什么
list在现代 C++ 里很少用?- 要点:缓存不友好、额外指针开销大、随机访问 O(n);大多数场景 vector 更快。