在 STL 容器中，list 是一个非常经典、同时又极具“工程味道”的容器。 与 vector 不同，它不依赖连续内存，而是通过节点 + 指针构成的双向链表来组织数据，这也使得它在插入、删除等操作上具备天然优势。

本文将围绕一份手写 STL 风格的 list 实现，从整体设计 → 关键数据结构 → 迭代器 → 接口实现 → 边界与安全性，完整拆解一个工业级 list 容器的实现逻辑。

---

一、整体设计思路：为什么 STL 的 list 要这样设计？

在正式看代码之前，先明确 STL list 的几个核心设计目标：

1. 任意位置 O(1) 插入 / 删除

2. 插入、删除不使迭代器失效

3. 支持前向 / 后向遍历

4. 接口行为与 STL 一致（begin / end / erase / insert）

5. 异常安全 & 内存安全

要满足这些目标，最自然的数据结构选择就是：

带头结点的双向循环链表

---

二、节点结构：ListNode 的设计哲学

template<class T>
class ListNode
{
public:
    T _data;
    ListNode<T>* _prev;
    ListNode<T>* _next;
};

1️⃣ 为什么是双向链表？

• 单向链表：

  • 删除一个节点，需要知道前驱 → 不方便

• 双向链表：

  • 每个节点都知道自己的前后 → 插入 / 删除 O(1)

STL 的 list 明确要求支持：

• --it

• pop_back

• 反向遍历

👉 单向链表无法自然支持这些操作。

---

2️⃣ 为什么一定要有 头结点（哨兵节点）？

你的代码采用的是：

_head->_next = _head;
_head->_prev = _head;

这是一个循环双向链表 + 哨兵节点的结构。

这样做的好处非常关键：

• 统一边界条件

  • 空链表：head->next == head

  • 非空链表：真实节点永远夹在中间

• 插入 / 删除时：

  • 不需要区分“头插 / 尾插 / 中间插”

• end() 可以直接返回 _head

这是 STL list 的核心工程技巧之一。

---

三、迭代器设计：ListIterator 不是指针的简单封装

template<class T>
struct ListIterator
{
    Node* _node;
};

1️⃣ 为什么 STL 要“自己写迭代器”？

STL 的核心思想之一是：

算法与容器解耦

算法（如 for_each、find）不关心你底层是数组还是链表，只关心：

• ++it

• *it

• it != end()

因此，list 必须提供一个行为类似指针的对象 —— 这就是迭代器。

---

2️⃣ 解引用与箭头运算符

T& operator* () const { return _node->_data; }
T* operator->() const { return &_node->_data; }

这使得：

*it        // 访问数据
it->field  // 访问成员

在使用体验上与指针完全一致。

---

3️⃣ 前置 / 后置 ++ -- 的区别

Self& operator++();   // ++it
Self operator++(int); // it++

• 前置：效率更高（推荐）

• 后置：返回旧值，符合 C++ 语义

STL 要求两者都支持，你的实现是标准做法。

---

4️⃣ const_iterator 的意义

typedef ListIterator<const T> const_iterator;

这意味着：

• const list<int> 只能读取元素

• 防止误修改容器内容

这是 STL 非常重要的一点： 👉 const 容器 ≠ 容器里元素是 const

---

四、list 的核心成员变量

Node* _head;
size_t _size;

1️⃣ 为什么要自己维护 size？

链表理论上可以通过遍历统计长度，但：

• 每次 size() 都遍历 → O(n)

• STL 要求 size() 是 O(1)

所以必须额外维护 _size。

---

五、构造 / 析构 / 拷贝：RAII 思想的体现

1️⃣ 默认构造函数

list()
{
    _head = new Node();
    _head->_next = _head->_prev = _head;
}

构造即建立一个合法的空容器状态。

---

2️⃣ 拷贝构造函数

list(const list& x) : list()
{
    for (const auto& val : x)
        push_back(val);
}

这里非常值得注意：

• 不直接拷贝节点指针

• 而是逐元素插入

原因：

• 两个 list 必须完全独立

• 否则析构会 double free

---

3️⃣ 析构函数与 clear()

~list()
{
    clear();
    delete _head;
}

这是标准 RAII：

• 谁 new，谁 delete

• 析构时必须释放所有节点

---

六、insert：list 的灵魂操作

iterator insert(iterator pos, const T& val)

插入本质只有四步：

1. 找到 pos 指向的节点 cur

2. 找到它的前驱 prev

3. 新节点接入链表

4. 更新前后指针

prev <-> newnode <-> cur

这是 O(1) 的，完全不依赖链表长度。

---

多个元素插入（n 个）

void insert(iterator pos, size_t n, const T& val)

关键点：

• 不能在循环中直接用 n 更新 _size

• 因为 n 会被减到 0

• 必须用单独的计数变量

这正是工程代码中非常容易出 bug 的地方。

---

七、erase：为什么 STL 的 erase 要返回迭代器？

iterator erase(iterator pos)

删除后返回 下一个有效位置：

it = erase(it);

这样你就可以安全地在遍历中删除：

for (auto it = l.begin(); it != l.end(); )
{
    if (*it == x)
        it = l.erase(it);
    else
        ++it;
}

如果 erase 不返回值，这种写法会非常别扭。

---

八、区间 erase 的实现思想

erase(first, last)

STL 约定：

• 删除 [first, last)

• 返回 last

你的实现：

• 先断链

• 再统一 delete 节点

• 最后一次性返回

这是最优写法，避免了反复调整指针。

---

九、front / back / pop 系列的安全性设计

assert(!empty());

这是调试期防御性编程：

• 避免非法访问

• 在 Debug 阶段尽早暴露错误

STL 的 list 在 Release 下是 UB，你的实现更“教学友好”。

---

十、这份 list 已经具备什么 STL 水平？

✅ 支持双向迭代

✅ O(1) 插入 / 删除

✅ 迭代器稳定

✅ RAII 内存管理

✅ const 正确性

✅ 行为与 STL list 一致

---

十一、还能继续扩展什么？

如果你想继续进阶，可以加：

• splice

• merge

• sort

• reverse

• allocator 支持

• iterator traits

---

十二、整体代码实现

#pragma once
#include <iostream>
#include <assert.h>

namespace List
{
    template<class T>
    class ListNode
    {
    public:
        T _data;
        ListNode<T>* _prev;
        ListNode<T>* _next;

        ListNode(const T& data = T())
            :_data(data), _prev(nullptr), _next(nullptr)
        {
        }
    };

    template<class T>
    struct ListIterator
    {
        typedef ListNode<T> Node;
        typedef ListIterator<T> Self;

        Node* _node;

        ListIterator(Node* node) : _node(node) {}
        ListIterator() : _node(nullptr) {}

        T& operator* () const { return _node->_data; }
        T* operator->() const { return &_node->_data; }

        Self& operator++()
        {
            _node = _node->_next;
            return *this;
        }
        Self operator++(int)
        {
            Self tmp = *this;
            ++(*this);
            return tmp;
        }

        Self& operator--()
        {
            _node = _node->_prev;
            return *this;
        }
        Self operator--(int)
        {
            Self tmp = *this;
            --(*this);
            return tmp;
        }

        bool operator==(const Self& s) const { return s._node == _node; }
        bool operator!=(const Self& s) const { return s._node != _node; }
    };

    template<class T>
    class list
    {
    public:
        typedef ListNode<T> Node;
        typedef ListIterator<T> iterator;
        typedef ListIterator<const T> const_iterator;

        // 构造 / 析构
        list() :_head(new Node()), _size(0)
        {
            _head->_next = _head->_prev = _head;
        }

        list(const list& x) : list() // 委托构造
        {
            for (const auto& val : x) push_back(val);
        }

        list& operator=(const list& x)
        {
            if (this != &x)
            {
                list tmp(x);
                swap(tmp);
            }
            return *this;
        }

        ~list()
        {
            clear();
            delete _head;
            _head = nullptr;
        }

        void clear()
        {
            Node* cur = _head->_next;
            while (cur != _head)
            {
                Node* next = cur->_next;
                delete cur;
                cur = next;
            }
            _head->_next = _head->_prev = _head;
            _size = 0;
        }

        void swap(list& x)
        {
            std::swap(_head, x._head);
            std::swap(_size, x._size);
        }

        bool empty() const { return _size == 0; }
        size_t size() const { return _size; }

        // 迭代器
        iterator begin() { return _head->_next; }
        iterator end() { return _head; }
        const_iterator begin() const { return _head->_next; }
        const_iterator end() const { return _head; }

        // 反向迭代器
        iterator rbegin() { return _head->_prev; }
        iterator rend() { return _head; }

        // 插入
        iterator insert(iterator pos, const T& val)
        {
            Node* cur = pos._node;
            Node* prev = cur->_prev;
            Node* newnode = new Node(val);

            newnode->_prev = prev;
            newnode->_next = cur;
            prev->_next = newnode;
            cur->_prev = newnode;

            ++_size;
            return iterator(newnode);
        }

        void insert(iterator pos, size_t n, const T& val)
        {
            size_t count = 0;
            Node* cur = pos._node->_prev;
            Node* next = cur->_next;
            while (n--)
            {
                Node* newnode = new Node(val);
                cur->_next = newnode;
                newnode->_prev = cur;
                cur = newnode;
                ++count;
            }
            cur->_next = next;
            next->_prev = cur;
            _size += count;
        }

        // push / pop
        void push_back(const T& val) { insert(end(), val); }
        void push_front(const T& val) { insert(begin(), val); }

        void pop_back() { if (!empty()) erase(--end()); }
        void pop_front() { if (!empty()) erase(begin()); }

        // front / back
        T& front() { assert(!empty()); return _head->_next->_data; }
        T& back() { assert(!empty()); return _head->_prev->_data; }
        const T& front() const { assert(!empty()); return _head->_next->_data; }
        const T& back() const { assert(!empty()); return _head->_prev->_data; }

        // 删除
        iterator erase(iterator pos)
        {
            assert(pos._node != _head);
            Node* cur = pos._node;
            Node* next = cur->_next;
            Node* prev = cur->_prev;

            prev->_next = next;
            next->_prev = prev;

            delete cur;
            --_size;

            return iterator(next);
        }

        iterator erase(iterator first, iterator last)
        {
            if (first == last) return last;

            Node* first_node = first._node;
            Node* last_node = last._node->_prev;

            Node* before_first = first_node->_prev;
            Node* after_last = last_node->_next;

            before_first->_next = after_last;
            after_last->_prev = before_first;

            Node* cur = first_node;
            while (cur != after_last)
            {
                Node* next_node = cur->_next;
                delete cur;
                cur = next_node;
                --_size;
            }

            return iterator(after_last);
        }

    private:
        Node* _head;
        size_t _size = 0;
    };
}