Appearance
手写实现专题
手写题考察的是接口与不变量、生命周期、复杂度与失效规则、异常安全，而非算法技巧。 本专题覆盖五类高频手写题，每题给出「精简版（先交）与完整版」两档（各带实现范围说明、技术选型与自测小问答）， 另附必需的配套实现；结构统一为「题面与澄清 → 接口与约束 → 精简版 → 完整版 → 配套 → 边界与测试 → 高频问答 → 常见错误」。代码均为可编译实现。
一、题目索引
| 题目 | 考察点 | 难度 | 关联讲解页 |
|---|---|---|---|
| 手写智能指针 | 精简版：堆上独立控制块；完整版：类型擦除 + 同块分配 + weak_ptr::lock | ⭐⭐⭐⭐⭐ | 智能指针 |
| 手写容器 | 精简版：有序数组增删查；完整版：全接口；配套动态数组扩容 | ⭐⭐⭐⭐ | vector、vector 扩容 |
| 手写 optional | 精简版 / 完整版均为 union 原地（区别在访问接口）；配套指针版；含 ctor/dtor 时序题 | ⭐⭐⭐⭐ | 内存布局、RAII |
| 手写 flat hashmap | 精简版：增删查 + 墓碑；完整版：全接口 + 迭代器 | ⭐⭐⭐⭐ | unordered_map |
| 手写并发件 | 精简版：有界阻塞队列；完整版：SPSC 无锁环；配套：发布不可变快照 | ⭐⭐⭐⭐ | 并发编程 |
工程题（orderbook、带
get/put/get_at的 snapshot store、LRU cache）不在本站，见本地练习仓livecoding/tasks/（含评分器与 mutation 验证；flat_map的手写评分器为其中的t04_flat_map）。
二、通用答题步骤
| 阶段 | 时长 | 内容 |
|---|---|---|
| 复述需求 | 2 min | 复述要实现的对象与边界，澄清至少 3 个语义问题 |
| 写接口与约束 | 5 min | 按下方七要素先落纸，再写第一行循环 |
| 主路径 | 15 min | 写可编译可运行的最小实现，边写边讲 |
| 覆盖边界 | 10 min | 空 / 单元素 / 满 / 重复 / 越界 / 删除后重插，并说明测试思路 |
| 收尾 | 5 min | 报复杂度、已知限制、规模放大后的替代结构 |
接口与约束的七个要素
- 接口：函数签名、返回值、错误通道（异常 /
optional/ 布尔 / 错误码） - 不变量：一句能写成
assert的话（例：底层数组按 key 严格递增） - 复杂度：逐操作；区分均摊与最坏
- 迭代器与引用失效规则
- 所有权与拷贝/移动语义（含是否
noexcept） - 异常安全级别：基本保证 / 强保证 / 不抛，及达成手段
- 前置条件：违反即 UB（可
assert，不在热路径抛异常）
前七项回答「要满足什么」，技术选型回答「为什么这样实现」，两者分开写： 先给约束，再逐条给出设计与理由（见各题「技术选型」小节）。
三、跨题速查
迭代器与引用失效
| 容器 | 插入 | 删除 |
|---|---|---|
vector / flat_map | 扩容 → 全部失效；否则插入点及其后失效 | 删除点及其后失效 |
deque | 两端插入：迭代器失效，引用/指针有效；中间插入全部失效 | 中间删除全部失效；两端删除只失效被删的 |
list / map / set | 都不失效 | 只失效被删元素 |
unordered_map | rehash → 迭代器全部失效，引用/指针有效 | 只失效被删元素 |
| flat hashmap | rehash → 全部失效（元素搬家） | 只失效被删元素 |
异常安全三档
| 级别 | 含义 | 常用手段 |
|---|---|---|
| 基本保证 | 不泄漏，不变量仍成立 | 先分配/构造，成功后再改状态 |
| 强保证 | 失败则状态原样 | copy-and-swap；先造新缓冲，成功再替换 |
| 不抛保证 | noexcept，失败即 terminate | 只做不会失败的操作；移动构造与析构标 noexcept |
内存序档位
| 场景 | 内存序 | 原因 |
|---|---|---|
| 仅自增计数，无跨变量顺序 | relaxed | 只需原子性 |
| 发布数据（写数据 → 写标志） | release | 保证此前所有写在标志可见前完成 |
| 消费数据（读标志 → 读数据） | acquire | 与 release 配对 |
| 无法判断 / 追求易推理 | seq_cst | 默认，代价最高 |
分配纪律
reserve是唯一能让容器提前停止分配的调用，也是唯一会让迭代器提前全部失效的调用；- 稳态零分配依赖对象池 / freelist / 侵入式链表 / 预分配；
- 结论以分配计数（练习仓的
omtest::alloc_calls()）或perf stat前后对比为准。
四、自测清单
- [ ] 写代码前先写接口与约束七要素，而不是先写循环
- [ ] 能说出各容器迭代器失效规则，并给出失效原因
- [ ] 能解释扩容时为何不能无条件
std::move（noexcept与回滚） - [ ] 能徒手写出
union+ placement new 的原地存储及四步流程 - [ ] 能写出
weak_ptr::lock的 CAS 循环并说明「先读后加」的竞态 - [ ] 能解释 flat hashmap 墓碑的必要性，以及删除对引用失效的影响
- [ ] 能说明 SPSC 环为何不需要 CAS、为何需要
alignas(64) - [ ] 每题都能给出规模放大后的第二版结构
五、与其他小类的关系
- 智能指针：
../smart-pointers/讲原理与用法；手写智能指针 给完整实现，原handwrite.md已迁入本专题。 - STL：
../stl/讲容器结构与选型；本专题给 容器、flat hashmap 的手写版。 - 内存与布局：
../memory/的sizeof/对齐/padding 是 optional 追问链的下半场。 - 并发：
../../system/concurrency/讲原语与内存模型；并发件 将其落成代码。 - 设计思想：
../design/的异常安全与零开销是各题的评分维度。
六、子文档
| 文件 | 内容 |
|---|---|
smart-pointer.md | 配套 unique_ptr；shared_ptr 两档（精简版：堆上独立控制块 / 完整版：类型擦除 + 同块分配 + weak_ptr::lock）；演进路径 |
container.md | FlatMap 两档（精简版增删查 / 完整版全接口 + 迭代器）与配套动态数组扩容 |
optional.md | optional 两档（union 原地：最小接口 / 完整接口）+ 配套指针版，含 ctor/dtor 时序题 |
flat-hashmap.md | flat hashmap 两档（精简版增删查 / 完整版全接口 + 迭代器）：开放寻址 + 墓碑 + rehash |
concurrency.md | 两档（有界阻塞队列 / SPSC 无锁环）+ 配套单写多读快照发布 |