罗罗编程学习记录 全栈面试题库
本页导航 展开查看

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 约束模板参数,写出类型安全的泛型函数
  • [ ] 能为自定义类型定义排序与查找逻辑
  • [ ] 能根据场景选对容器并说明复杂度理由

自测题:

  1. vector、deque、list 的底层结构与复杂度差异?
    • 要点:vector 连续数组 O(1) 随机访问;deque 分段连续;list 双向链表 O(1) 插入但无随机访问。
  2. map 与 unordered_map 的区别?什么时候用哪个?
    • 要点:map 红黑树 O(log n) 有序;unordered_map 哈希表 O(1) 无序;需要有序遍历用 map,纯查找用 unordered_map。
  3. 迭代器在哪些操作后会失效?怎么正确地遍历中删除?
    • 要点:vector 插入删除使所有迭代器失效;用 it = v.erase(it) 模式。
  4. ranges 相比传统 STL 算法的优势?
    • 要点:管道式组合、延迟求值、不产生中间容器。
  5. concepts 解决什么问题?
    • 要点:约束模板参数,让报错从"no matching function"变成"requires xxx",提升可读性。
  6. 为什么 list 在现代 C++ 里很少用?
    • 要点:缓存不友好、额外指针开销大、随机访问 O(n);大多数场景 vector 更快。