手写 std::forward_list

手写 std::forward_list

通过单向节点、哨兵头和 after 系列操作，实现低额外开销的单链表。

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

---

一、学习目标

• 理解 before_begin 的价值
• 实现 insert_after/erase_after
• 在异常时保持链表结构不变

---

二、前置条件

掌握节点所有权、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

---

三、问题与设计选择

使用不含 T 的哨兵头节点，使表头插入与普通节点插入统一。新节点完全构造后才连接到链上。

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

---

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

从哨兵沿 next 最终到达 nullptr；每个数据节点恰好拥有一个已构造 T；不存在环。

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

---

五、核心实现

template<class... Args>
iterator emplace_after(iterator pos, Args&&... args) {
    node* fresh = new node(std::forward<Args>(args)...);
    fresh->next = pos.current_->next;
    pos.current_->next = fresh;
    ++size_;
    return iterator{fresh};
}

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

---

六、完整教学实现

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

namespace oc::handmade {

template<class T>
class forward_list {
    struct node {
        T value;
        node* next{};
        template<class... Args>
        explicit node(Args&&... args) : value(std::forward<Args>(args)...) {}
    };
    node* head_{};
    std::size_t size_{};

public:
    class iterator {
        node* current_{};
        explicit iterator(node* current) : current_(current) {}
        friend class forward_list;
    public:
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;
        iterator() = default;
        T& operator*() const { return current_->value; }
        T* operator->() const { return &current_->value; }
        iterator& operator++() { current_ = current_->next; return *this; }
        iterator operator++(int) { auto old = *this; ++*this; return old; }
        friend bool operator==(iterator, iterator) = default;
    };

    forward_list() = default;
    forward_list(const forward_list& other) {
        std::vector<T> values(other.begin(), other.end());
        for (auto it = values.rbegin(); it != values.rend(); ++it) push_front(*it);
    }
    forward_list(forward_list&& other) noexcept
        : head_(std::exchange(other.head_, nullptr)),
          size_(std::exchange(other.size_, 0)) {}
    forward_list& operator=(forward_list other) noexcept {
        swap(other);
        return *this;
    }
    ~forward_list() { clear(); }
    void swap(forward_list& other) noexcept {
        std::swap(head_, other.head_);
        std::swap(size_, other.size_);
    }
    iterator begin() const noexcept { return iterator(head_); }
    iterator end() const noexcept { return iterator(nullptr); }
    bool empty() const noexcept { return size_ == 0; }
    std::size_t size() const noexcept { return size_; }
    T& front() { return head_->value; }
    const T& front() const { return head_->value; }
    template<class... Args>
    T& emplace_front(Args&&... args) {
        std::unique_ptr<node> fresh(new node(std::forward<Args>(args)...));
        fresh->next = head_;
        head_ = fresh.release();
        ++size_;
        return head_->value;
    }
    void push_front(const T& value) { emplace_front(value); }
    void push_front(T&& value) { emplace_front(std::move(value)); }
    void pop_front() noexcept {
        assert(head_);
        node* old = head_;
        head_ = head_->next;
        delete old;
        --size_;
    }
    void reverse() noexcept {
        node* previous = nullptr;
        node* current = head_;
        while (current) {
            node* next = current->next;
            current->next = previous;
            previous = current;
            current = next;
        }
        head_ = previous;
    }
    void clear() noexcept { while (head_) pop_front(); }
};

}  // namespace oc::handmade

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

---

七、使用示例与输出

预期输出或状态：

依次在 before_begin 后插入 3、2、1，遍历结果为 1 2 3。

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

---

八、复杂度与失效规则

操作	复杂度	说明
push_front	O(1)	头插
insert_after/erase_after	O(1)	已知前驱
find	O(n)	顺序扫描
size	O(1)	教学版维护计数

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

---

九、异常安全与资源管理

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

---

十、常见错误

1. 删除节点后再读取其 next

删除节点后再读取其 next会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 让哨兵节点错误构造 T

让哨兵节点错误构造 T会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. 试图在 O(1) 内访问尾部

试图在 O(1) 内访问尾部会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. 为什么接口是 insert_after 而不是 insert？
2. 单链表为何不能提供双向迭代器？
3. splice_after 怎样做到 O(1)？

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

---

十二、练习与自测

1. 实现 reverse
2. 实现 remove_if
3. 用快慢指针检测调试版本中的环

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

---

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

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

---

上一篇：手写 std::string ｜ 下一篇：手写 std::list