OliverChiu
管理
浏览知识库目录

C++

手写系列完整学习路线

从对象生命周期和迭代器契约出发，逐步手写常用容器、三种智能指针、内存池、线程池与现代缓存策略的完整 C++20 学习路线。

发布于 2026年7月23日

手写系列完整学习路线

从对象生命周期和迭代器契约出发，逐步手写常用容器、三种智能指针、内存池、线程池与现代缓存策略的完整 C++20 学习路线。

本系列代码使用 C++20 和 oc::handmade 命名空间，目标是解释实现机制、复杂度和工程边界，不是替代标准库。普通容器与缓存核心不内置互斥锁；这不代表 lock-free。

一、学习目标

  • 理解整套实现的依赖关系与学习顺序
  • 明确教学实现与生产标准库的边界
  • 建立编译、测试、Sanitizer 和基准验证习惯

二、前置条件

熟悉 C++ 基本语法、模板、RAII、移动语义，并能使用命令行编译一个多文件项目。

Linux/macOS：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build -j
ctest --test-dir build --output-on-failure

Windows PowerShell：

cmake -S . -B build -DCMAKE_BUILD_TYPE=Debug
cmake --build build --config Debug
ctest --test-dir build -C Debug --output-on-failure

三、问题与设计选择

全系列使用同一个 oc::handmade 命名空间和 CMake 工程。先解决对象生命周期，再实现顺序容器、树和哈希容器；接着手写 unique_ptr、shared_ptr 与 weak_ptr，随后把内存与并发能力组合成线程池，最后比较七种缓存策略。

这里刻意保留一条边界：教学实现覆盖构造、复制移动、核心修改、查找和迭代契约，但不复刻标准库全部重载、ABI、constexpr、异构查找或节点句柄。

四、内存布局与核心不变量

任何新增抽象都必须回答四个问题：谁拥有内存、对象何时构造和销毁、哪些操作使迭代器失效、失败时对象处于什么状态。

每个修改操作都按“准备资源 → 构造新状态 → 提交连接或指针 → 清理旧状态”的顺序设计。提交点之前发生异常，应保持原对象可继续使用；无法提供强保证时，会在接口说明中明确基本保证。

五、核心实现

#include <oc/handmade.hpp>
#include <iostream>

int main() {
    oc::handmade::vector<int> values;
    values.push_back(3);
    values.push_back(1);
    values.push_back(2);
    for (int value : values) std::cout << value << ' ';
}

上面先聚焦最容易写错的核心步骤；若本篇对应一个独立组件，下一节给出统一工程中的完整教学实现。代码没有放入 std 命名空间，避免未定义行为和名称冲突。

六、手写系列文章目录

下表按照知识库中的实际阅读顺序列出本系列全部 34 篇文章。新增主题会同步维护在这里，序号同时对应左侧目录顺序。

序号 模块 文章 核心内容
0 路线 手写系列完整学习路线 从对象生命周期和迭代器契约出发，逐步手写常用容器、三种智能指针、内存池、线程池与现代缓存策略的完整 C++20 学习路线
1 基础契约 手写容器前置：契约、迭代器与对象生命周期 在写第一行容器代码前，掌握原始存储、allocator_traits、迭代器类别、异常保证和移动语义的共同契约
2 顺序容器与适配器 手写 std::array 用最小实现理解固定容量连续容器、零长度特化、聚合语义以及随机访问迭代器
3 顺序容器与适配器 手写 std::vector 从原始存储、几何扩容和异常回滚出发，实现支持复制移动、迭代器与主要修改操作的动态数组
4 顺序容器与适配器 手写 std::string 实现限定 char 的动态字符串与小字符串优化，理解结尾零字节、容量标记和移动语义的细节
5 顺序容器与适配器 手写 std::forward_list 通过单向节点、哨兵头和 after 系列操作，实现低额外开销的单链表
6 顺序容器与适配器 手写 std::list 使用循环双向哨兵链表实现稳定迭代器、常数时间插入删除和 splice
7 顺序容器与适配器 手写 std::deque 实现由固定大小块和块索引表组成的双端队列，分析随机访问与两端增长
8 顺序容器与适配器 手写 std::stack 用容器适配器限制接口，实现后进先出语义并理解组合优于重复实现
9 顺序容器与适配器 手写 std::queue 基于双端容器实现先进先出适配器，并讨论 front/back、关闭语义与后续阻塞队列的关系
10 顺序容器与适配器 手写 std::priority_queue 使用动态数组和二叉堆实现优先队列，推导 sift_up、sift_down 与建堆复杂度
11 关联容器 手写红黑树内核 使用左倾红黑树实现旋转、变色、插入与删除，为 set/map 系列建立共享有序索引
12 关联容器 手写 std::set 在红黑树内核之上实现唯一键集合、只读迭代器、查找边界与插入结果
13 关联容器 手写 std::multiset 扩展有序树以保存重复键，理解等价区间、计数与 erase 的不同语义
14 关联容器 手写 std::map 把键值对接入红黑树，实现唯一键映射、operator[]、at 和安全的迭代引用
15 关联容器 手写 std::multimap 在有序映射中保存一键多值，处理等价区间、稳定遍历和单条记录删除
16 关联容器 手写哈希表内核 使用独立链地址、负载因子和 rehash 实现通用哈希索引，为 unordered 容器提供共享内核
17 关联容器 手写 std::unordered_set 基于独立链地址哈希内核实现唯一键集合、桶接口与负载因子管理
18 关联容器 手写 std::unordered_map 在哈希内核上实现键值映射、try_emplace、operator[] 和可控 rehash
19 智能指针 手写 std::unique_ptr 独占所有权、deleter 与数组特化
20 智能指针 手写 std::shared_ptr 控制块、强引用计数与 make_shared
21 智能指针 手写 std::weak_ptr 弱引用、lock 与循环引用
22 内存管理 手写内存池 实现满足对齐要求的固定块自由链表、页级扩容和 pmr::memory_resource 适配器
23 内存管理 手写对象池 在内存池之上管理 T 的构造与析构，提供异常安全 acquire/release 和 RAII 归还句柄
24 并发 手写有界阻塞队列 使用 mutex、condition_variable_any 和 stop_token 实现有容量、可关闭的阻塞队列
25 并发 手写线程池 组合 jthread、有界阻塞队列、packaged_task 与 future，实现可回收异常和优雅关闭的线程池
26 缓存 手写 FIFO 缓存 用哈希索引和插入顺序队列实现 FIFO 淘汰，建立所有缓存策略的统一接口和测试方法
27 缓存 手写 LRU 缓存 通过双向链表和哈希表实现 O(1) 的最近最少使用缓存，并处理更新、容量和引用安全
28 缓存 手写 LFU 缓存 使用频率桶和桶内 LRU 实现平均 O(1) LFU，并解决相同频率时的确定性淘汰
29 缓存 手写 TTL 缓存 组合可注入单调时钟、最小堆惰性删除和 LRU 容量控制，实现可确定测试的过期缓存
30 缓存 手写 2Q 缓存 使用 A1in、A1out 和 Am 三个队列抵抗一次性扫描，理解幽灵记录的价值
31 缓存 手写 ARC 缓存 实现 T1/T2/B1/B2 四队列与自适应参数 p，让缓存在线平衡近期性和频率
32 缓存 手写 Window TinyLFU 缓存 组合窗口 LRU、分段 LRU、Doorkeeper 与 Count-Min Sketch，实现基于频率估计的缓存准入
33 测试与复盘 综合测试、性能基准与面试复盘 把所有实现纳入差分测试、随机状态机、异常注入、Sanitizer 和可复现基准，并形成面试复盘清单

七、使用示例与输出

预期输出或状态：

3 1 2

示例必须在文章对应的测试目标中实际编译。涉及顺序的输出只依赖接口明确承诺的顺序；无序容器不会把某次桶顺序写成稳定结果。

八、复杂度与失效规则

操作 复杂度 说明
阶段一 契约、array、vector、string 连续存储与生命周期
阶段二 链表、deque、适配器 节点与分段存储
阶段三 红黑树、哈希表 有序与无序查找
阶段四 unique_ptr、shared_ptr、weak_ptr 所有权与控制块
阶段五 内存池、线程池 资源与并发
阶段六 FIFO 到 TinyLFU 淘汰与准入策略

复杂度中的 O(1) 若标记为“平均”或“摊还”，不能在面试中省略限定词。任何重新分配、节点删除、rehash 或缓存淘汰都必须单独说明迭代器、引用与指针是否失效。

九、异常安全与资源管理

  • 获取资源后立即交给 RAII 对象或明确记录已构造数量。
  • 用户类型构造、复制、移动、比较器和哈希器都可能抛异常。
  • 只有在所有后续步骤不会失败时才修改不可回滚的链接。
  • 析构、释放和关闭路径不得抛异常。
  • 并发包装通过回调在锁内访问，避免返回保护对象的裸引用。

十、常见错误

1. 一开始就追求完整复刻标准库，导致看不到关键不变量

一开始就追求完整复刻标准库，导致看不到关键不变量会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 只看代码不写失败路径和边界测试

只看代码不写失败路径和边界测试会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 把“没有内置互斥锁”误称为 lock-free

把“没有内置互斥锁”误称为 lock-free会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

  1. 为什么标准容器通常不能简单地用 new T[n] 实现？
  2. 异常安全的基本保证和强保证有何区别？
  3. 基准更快是否能证明实现更好？

回答时先说数据结构不变量，再给复杂度，最后说明异常、迭代器或并发边界，通常比背诵结论更有说服力。

十二、练习与自测

  1. 画出各文章之间的依赖图
  2. 为自己的编译器准备 Debug、ASan 和 TSan 三套构建目录
  3. 列出你最想追问的五个容器实现问题

自测标准：能够不看代码画出内存或节点关系，解释一次成功操作和一次失败回滚，并写出至少一个会击穿错误实现的测试。

十三、官方资料与延伸阅读

上一篇：无（本篇为系列路线页） ｜ 下一篇：手写容器前置：契约、迭代器与对象生命周期