综合测试、性能基准与面试复盘

综合测试、性能基准与面试复盘

把所有实现纳入差分测试、随机状态机、异常注入、Sanitizer 和可复现基准，并形成面试复盘清单。

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

---

一、学习目标

• 建立容器差分与性质测试矩阵
• 用 Sanitizer 捕获内存和数据竞争问题
• 正确解读微基准而不过度推断

---

二、前置条件

完成前面所有手写文章，能够阅读 CMake 和 GoogleTest。

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

---

三、问题与设计选择

测试按契约而不是实现细节组织：确定性边界、与标准库差分、固定种子随机状态机、异常注入、并发关闭和缓存轨迹。基准与正确性测试完全分离。

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

---

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

同一操作序列下，教学容器与参考模型的可观察状态一致；所有资源计数最终归零；并发任务恰执行一次。

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

---

五、核心实现

TEST(VectorDifferential, RandomOperationsMatchStdVector) {
    std::mt19937 random(20260723);
    oc::handmade::vector<int> actual;
    std::vector<int> expected;
    for (int step = 0; step < 10'000; ++step) {
        if (expected.empty() || random() % 2) {
            const int value = static_cast<int>(random());
            actual.push_back(value);
            expected.push_back(value);
        } else {
            actual.pop_back();
            expected.pop_back();
        }
        ASSERT_TRUE(std::ranges::equal(actual, expected));
    }
}

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

---

---

七、使用示例与输出

预期输出或状态：

GCC 与 Clang 的 Debug、ASan/UBSan、TSan 测试全部通过；固定基准报告操作吞吐和命中率，不给出跨机器绝对结论。

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

---

八、复杂度与失效规则

操作	复杂度	说明
单元测试	确定性	边界和局部契约
随机差分	固定种子	长操作序列
ASan/UBSan/TSan	独立构建	内存与竞态
Benchmark	多轮统计	不代替正确性

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

---

九、异常安全与资源管理

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

---

十、常见错误

1. 只测试 happy path

只测试 happy path会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 随机测试不记录种子

随机测试不记录种子会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 把 Debug 与 Release 基准混在一起

把 Debug 与 Release 基准混在一起会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

4. 看到零 Sanitizer 报告就声称没有 bug

看到零 Sanitizer 报告就声称没有 bug会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 怎样验证异常安全强保证？
2. 如何设计容器的参考模型？
3. 微基准最常见的失真来源是什么？

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

---

十二、练习与自测

1. 加入失败时打印随机操作轨迹
2. 为红黑树每次修改后运行不变量检查
3. 准备一页复杂度与失效规则速查表

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

---

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

• C++20 工作草案 N4861
• C++ Core Guidelines
• GoogleTest 1.17
• Google Benchmark 1.9.5
• Clang AddressSanitizer
• Clang ThreadSanitizer

---

上一篇：手写 Window TinyLFU 缓存 ｜ 下一篇：无（本篇为系列终章）