手写 std::list

手写 std::list

使用循环双向哨兵链表实现稳定迭代器、常数时间插入删除和 splice。

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

---

一、学习目标

• 用循环哨兵消除边界分支
• 维护 prev/next 对称关系
• 理解节点型容器的迭代器稳定性

---

二、前置条件

完成 forward_list 篇，理解双向链表与双向迭代器。

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

---

三、问题与设计选择

根哨兵的 next 指向首节点、prev 指向尾节点；空表时二者都指向自身。节点构造完成后执行四次指针更新。

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

---

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

对任意节点 x，x->next->prev == x 且 x->prev->next == x；绕一圈恰好访问 size 个数据节点。

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

---

五、核心实现

static void link_before(node_base* pos, node_base* fresh) noexcept {
    fresh->prev = pos->prev;
    fresh->next = pos;
    pos->prev->next = fresh;
    pos->prev = fresh;
}

static void unlink(node_base* victim) noexcept {
    victim->prev->next = victim->next;
    victim->next->prev = victim->prev;
}

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

---

六、完整教学实现

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

namespace oc::handmade {

template<class T>
class list {
    struct node_base {
        node_base* prev{this};
        node_base* next{this};
    };
    struct node : node_base {
        T value;
        template<class... Args>
        explicit node(Args&&... args) : value(std::forward<Args>(args)...) {}
    };
    node_base root_{};
    std::size_t size_{};

    static void link_before(node_base* position, node_base* fresh) noexcept {
        fresh->prev = position->prev;
        fresh->next = position;
        position->prev->next = fresh;
        position->prev = fresh;
    }
    static void unlink(node_base* victim) noexcept {
        victim->prev->next = victim->next;
        victim->next->prev = victim->prev;
    }

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

    list() = default;
    list(const list& other) {
        for (const T& item : other) push_back(item);
    }
    list(list&& other) noexcept {
        take_from(other);
    }
    list& operator=(const list& other) {
        if (this == &other) return *this;
        list copy(other);
        clear();
        take_from(copy);
        return *this;
    }
    list& operator=(list&& other) noexcept {
        if (this == &other) return *this;
        clear();
        take_from(other);
        return *this;
    }
    ~list() { clear(); }

    void swap(list& other) noexcept {
        if (this == &other) return;
        list temporary(std::move(other));
        other.take_from(*this);
        take_from(temporary);
    }

    iterator begin() const noexcept { return iterator(root_.next); }
    iterator end() const noexcept { return iterator(const_cast<node_base*>(&root_)); }
    bool empty() const noexcept { return size_ == 0; }
    std::size_t size() const noexcept { return size_; }
    T& front() { return *begin(); }
    T& back() { auto it = end(); --it; return *it; }

    template<class... Args>
    iterator emplace(iterator position, Args&&... args) {
        std::unique_ptr<node> fresh(new node(std::forward<Args>(args)...));
        node* raw = fresh.get();
        link_before(position.current_, raw);
        fresh.release();
        ++size_;
        return iterator(raw);
    }
    void push_back(const T& value) { emplace(end(), value); }
    void push_back(T&& value) { emplace(end(), std::move(value)); }
    void push_front(const T& value) { emplace(begin(), value); }
    void push_front(T&& value) { emplace(begin(), std::move(value)); }
    iterator erase(iterator position) noexcept {
        node_base* next = position.current_->next;
        unlink(position.current_);
        delete static_cast<node*>(position.current_);
        --size_;
        return iterator(next);
    }
    void pop_front() noexcept { erase(begin()); }
    void pop_back() noexcept { auto it = end(); erase(--it); }
    void clear() noexcept { while (!empty()) pop_back(); }

private:
    void take_from(list& other) noexcept {
        if (other.empty()) return;
        root_.next = other.root_.next;
        root_.prev = other.root_.prev;
        root_.next->prev = &root_;
        root_.prev->next = &root_;
        size_ = std::exchange(other.size_, 0);
        other.root_.next = other.root_.prev = &other.root_;
    }
};

}  // namespace oc::handmade

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

---

七、使用示例与输出

预期输出或状态：

空表 push_back(2)、push_front(1)、push_back(3) 后遍历为 1 2 3，反向为 3 2 1。

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

---

八、复杂度与失效规则

操作	复杂度	说明
push_front/back	O(1)	链接节点
insert/erase	O(1)	位置已知
splice	O(1)	整表或已知范围
find	O(n)	顺序扫描

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

---

九、异常安全与资源管理

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

---

十、常见错误

1. 只更新两个方向中的一个

只更新两个方向中的一个会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

2. 移动后忘记让哨兵重新指向新对象

移动后忘记让哨兵重新指向新对象会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

3. splice 自己的重叠区间

splice 自己的重叠区间会破坏本篇建立的契约。调试时先检查核心不变量，再缩小到触发该状态的最短操作序列。

---

十一、面试追问

1. list 的迭代器为什么通常比 vector 稳定？
2. 节点额外保存两个指针对缓存局部性有何影响？
3. splice 为什么不复制元素？

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

---

十二、练习与自测

1. 实现单节点 splice
2. 实现稳定 merge
3. 统计节点遍历与 vector 遍历的时间差

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

---

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

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

---

上一篇：手写 std::forward_list ｜ 下一篇：手写 std::deque