手写容器前置：契约、迭代器与对象生命周期

在写第一行容器代码前，掌握原始存储、allocator_traits、迭代器类别、异常保证和移动语义的共同契约。

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

一、学习目标

区分分配存储与构造对象
使用 allocator_traits 管理对象生命周期
为容器写出可验证的异常安全承诺

二、前置条件

掌握类模板、RAII、placement new、移动构造和基本异常处理。

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

三、问题与设计选择

拥有内存的容器只通过 allocator_traits 分配、构造、销毁和释放。迭代器表达遍历能力而不是所有权；容器析构必须只销毁已构造对象。

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

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

[data, data + size) 中对象已经构造；[data + size, data + capacity) 只是满足对齐的原始存储。任何回滚路径都必须恢复这个边界。

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

五、核心实现

template<class T, class Alloc>
class raw_buffer {
    using traits = std::allocator_traits<Alloc>;
    Alloc alloc_;
    T* data_{};
    std::size_t built_{};
    std::size_t allocated_{};
public:
    explicit raw_buffer(std::size_t n)
        : data_(traits::allocate(alloc_, n)), allocated_(n) {}
    template<class... Args>
    void construct_next(Args&&... args) {
        traits::construct(alloc_, data_ + built_,
                          std::forward<Args>(args)...);
        ++built_;
    }
    ~raw_buffer() {
        while (built_) traits::destroy(alloc_, data_ + --built_);
        if (data_) traits::deallocate(alloc_, data_, allocated_);
    }
};

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

七、使用示例与输出

预期输出或状态：

该辅助类型没有输出；在异常注入测试中，已构造对象计数最终回到 0。

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

八、复杂度与失效规则

操作	复杂度	说明
allocate	通常 O(1)	只获得原始存储
construct	O(1)	对象生命周期开始
destroy	O(1)	对象生命周期结束
reallocate	O(n)	移动或复制并提交

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

九、异常安全与资源管理

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

十、常见错误

1. 把分配出的字节当成已经存在的 T 对象

把分配出的字节当成已经存在的 T 对象会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 移动后仍假设源对象保持原容量

移动后仍假设源对象保持原容量会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 返回受锁保护对象的裸引用

返回受锁保护对象的裸引用会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

十一、面试追问

reserve 为什么不改变 size？
何时应该优先复制而不是移动以提供强保证？
随机访问迭代器比双向迭代器多承诺了什么？

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

十二、练习与自测

实现带回滚的 uninitialized_copy
写一个第 N 次复制时抛异常的测试类型
用 C++20 concept 检查随机访问迭代器

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

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

上一篇：手写系列完整学习路线｜下一篇：手写 std::array