手写 std::array

手写 std::array

用最小实现理解固定容量连续容器、零长度特化、聚合语义以及随机访问迭代器。

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

---

一、学习目标

• 实现固定容量连续存储
• 正确处理 N=0
• 理解 array 不负责动态分配的代价与优势

---

二、前置条件

完成容器契约篇，熟悉类模板、数组和范围 for。

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

---

三、问题与设计选择

array<T,N> 直接内嵌元素，大小属于类型。提供 begin/end/data/front/back/operator[]/at/fill/swap，零长度时 data()==nullptr。

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

---

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

当 N>0 时始终恰有 N 个 T 子对象，容器与元素生命周期一致；没有独立的 size/capacity 状态。

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

---

五、核心实现

template<class T, std::size_t N>
struct array {
    T elems[N == 0 ? 1 : N];
    constexpr T* begin() noexcept { return N ? elems : nullptr; }
    constexpr T* end() noexcept { return N ? elems + N : nullptr; }
    constexpr std::size_t size() const noexcept { return N; }
    constexpr T& operator[](std::size_t i) noexcept { return elems[i]; }
    constexpr T& at(std::size_t i) {
        if (i >= N) throw std::out_of_range("array::at");
        return elems[i];
    }
};

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

---

六、完整教学实现

下面是统一工程中经过 GCC、Clang、GoogleTest 和 Sanitizer 验证的完整组件。它依赖前序文章已经实现的公共类型以及头文件中的标准库 #include。

namespace oc::handmade {

template<class T, std::size_t N>
class array {
    T elements_[N == 0 ? 1 : N]{};

public:
    using value_type = T;
    using size_type = std::size_t;
    using iterator = T*;
    using const_iterator = const T*;

    constexpr iterator begin() noexcept { return data(); }
    constexpr const_iterator begin() const noexcept { return data(); }
    constexpr iterator end() noexcept { return N == 0 ? data() : data() + N; }
    constexpr const_iterator end() const noexcept { return N == 0 ? data() : data() + N; }
    constexpr T* data() noexcept { return N == 0 ? nullptr : elements_; }
    constexpr const T* data() const noexcept { return N == 0 ? nullptr : elements_; }
    static constexpr size_type size() noexcept { return N; }
    static constexpr bool empty() noexcept { return N == 0; }
    constexpr T& operator[](size_type index) noexcept { return elements_[index]; }
    constexpr const T& operator[](size_type index) const noexcept { return elements_[index]; }
    constexpr T& at(size_type index) {
        if (index >= N) throw std::out_of_range("oc::handmade::array::at");
        return elements_[index];
    }
    constexpr const T& at(size_type index) const {
        if (index >= N) throw std::out_of_range("oc::handmade::array::at");
        return elements_[index];
    }
    constexpr T& front() noexcept { return elements_[0]; }
    constexpr const T& front() const noexcept { return elements_[0]; }
    constexpr T& back() noexcept { return elements_[N - 1]; }
    constexpr const T& back() const noexcept { return elements_[N - 1]; }
    constexpr void fill(const T& value) { std::fill_n(begin(), N, value); }
};

}  // namespace oc::handmade

生产级标准库还要处理完整 allocator 传播、全部重载、ABI、调试迭代器和平台特化；这里保留的是能够独立推导核心数据结构的教学边界。

---

七、使用示例与输出

预期输出或状态：

array<int, 3>{1, 2, 3} 的 size 为 3，连续地址差均为 sizeof(int)。

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

---

八、复杂度与失效规则

操作	复杂度	说明
operator[]/front/back	O(1)	不检查边界
at	O(1)	越界抛出
fill	O(N)	逐元素赋值
swap	O(N)	逐元素交换

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

---

九、异常安全与资源管理

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

---

十、常见错误

1. 用 T elems[0] 依赖非标准扩展

用 T elems[0] 依赖非标准扩展会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 误以为复制 array 只复制一个指针

误以为复制 array 只复制一个指针会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 对空 array 调用 front/back

对空 array 调用 front/back会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 为什么 N 是类型的一部分？
2. array 和 C 数组在函数传参时有何差异？
3. 零长度 array 的 begin()==end() 如何成立？

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

---

十二、练习与自测

1. 补充 const_iterator
2. 实现 to_array 辅助函数
3. 用 static_assert 验证迭代器 concept

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

---

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

• C++20 工作草案 N4861
• C++ Core Guidelines

---

上一篇：手写容器前置：契约、迭代器与对象生命周期 ｜ 下一篇：手写 std::vector