前言
std::list是 C++ 标准库的双向链表容器。它的接口看起来和std::vector相似，但内部结构完全不同：元素分散在独立结点里，每个结点保存前驱和后继指针，插入删除不搬移其他元素，代价是不能随机访问。很多教程只列接口，不讲实现，读者遇到“迭代器为什么只能双向移动”“为什么erase返回下一个迭代器”“为什么空链表的end()还能减一”时，就缺少一个具体的模型。
本文从头实现一个简化版的List，重点讲三件事：带哨兵结点的循环双向链表、迭代器如何把结点指针包装成begin()/end()语义、插入删除时指针如何更新。实现以 C++17 为准，只依赖标准库的头文件和类型标签，不涉及分配器、异常安全细节和const_iterator。它不是std::list的替代品，而是理解标准库设计的教学模型。
先说明一个常见误解：std::list的end()不是空指针，而是一个真实的哨兵结点。正因如此，--end()才能得到最后一个元素，++到尾结点后也能自然回到end()。如果自己用nullptr表示结尾，这些操作都要特判，迭代器很难写一致。
一、结点、哨兵与所有权
链表由结点组成。每个结点需要：
value：元素；prev：前一个结点；next：后一个结点。
为了支持end()，我们再引入一个哨兵结点（sentinel）。哨兵不存元素，它的next指向第一个元素，prev指向最后一个元素；空链表时，哨兵的next和prev都指向自己。整条链因此是一个环：
sentinel <-> first <-> ... <-> last <-> sentinel这样做的好处是插入删除不需要特判头尾。在end()前插入，就是“在哨兵前插入”，等价于追加到尾部；删除第一个元素，就是删除sentinel.next。所有位置的操作都变成同一套“改四个指针”的流程。
哨兵如果直接定义成Node，会要求T可默认构造，因为哨兵里也有一个T value成员。标准库的常见做法是把“链接指针”和“值”分开：定义一个只含prev/next的基类，真正的结点继承它并加上value。本文采用这个结构：
struct NodeBase
{
NodeBase* prev;
NodeBase* next;
};
struct Node : NodeBase
{
T value;
};哨兵是NodeBase，迭代器持有NodeBase*，解引用时再static_cast<Node*>。只要保证不对哨兵解引用，这个向下转型就是安全的。
二、迭代器：把结点指针包装成双向迭代器
迭代器的本质是一个指针的包装。它需要提供：
operator*返回元素引用；operator->返回元素指针；- 前置/后置
++、--； ==、!=；- 标准迭代器所需的类型别名，例如
iterator_category、value_type、difference_type。
begin()返回iterator(sentinel_.next)，end()返回iterator(&sentinel_)。对最后一个元素执行++，p_变成sentinel_.next的下一结点，也就是哨兵，于是恰好等于end()；对end()执行--，p_变成哨兵的prev，也就是最后一个元素。这套对称性是指针链表很难做到的。
迭代器不拥有结点，只是“位置”。插入和删除会让某些迭代器失效：erase使被删元素的迭代器失效，其他迭代器不受影响；insert不使任何已有迭代器失效。这一点和std::vector的“扩容全失效”不同。
三、插入与删除
在位置 pos 前插入，需要拿到 pos 的前驱：
- 新建结点，
prev指向前驱，next指向 pos； - 前驱的
next指向新结点； - pos 的
prev指向新结点； - 返回指向新结点的迭代器。
顺序可以调整，但必须先保证新结点的两个指针已经就绪，再让旧结点指向它；否则链上会出现指向未初始化结点的瞬间（单线程下不可见，但异常安全和大对象构造时要考虑）。
删除 pos：
- 保存
next，用于返回； pos->prev->next = pos->next；pos->next->prev = pos->prev；delete结点；- 返回
iterator(next)。
因为有哨兵，pos 是第一个或最后一个元素时也不需要特判。唯一要避免的是删除end()（哨兵本身），那是未定义行为；本文的实现遇到end()直接返回，属于防御性处理，标准库并不保证。
四、完整实现
// 适用于 C++17
#include <cstddef>
#include <iterator>
#include <iostream>
template <typename T>
class List
{
private:
struct NodeBase
{
NodeBase* prev;
NodeBase* next;
};
struct Node : NodeBase
{
T value;
Node(const T& v, NodeBase* p, NodeBase* n)
: NodeBase{p, n}, value(v)
{
}
};
public:
class iterator
{
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;
explicit iterator(NodeBase* p) : p_(p) {}
T& operator*() const
{
return static_cast<Node*>(p_)->value;
}
T* operator->() const
{
return &static_cast<Node*>(p_)->value;
}
iterator& operator++()
{
p_ = p_->next;
return *this;
}
iterator operator++(int)
{
iterator old(*this);
++(*this);
return old;
}
iterator& operator--()
{
p_ = p_->prev;
return *this;
}
iterator operator--(int)
{
iterator old(*this);
--(*this);
return old;
}
bool operator==(const iterator& other) const { return p_ == other.p_; }
bool operator!=(const iterator& other) const { return p_ != other.p_; }
private:
friend class List;
NodeBase* p_ = nullptr;
};
List() noexcept
{
sentinel_.prev = &sentinel_;
sentinel_.next = &sentinel_;
}
~List()
{
clear();
}
List(const List&) = delete;
List& operator=(const List&) = delete;
iterator begin() noexcept { return iterator(sentinel_.next); }
iterator end() noexcept { return iterator(&sentinel_); }
bool empty() const noexcept { return sentinel_.next == &sentinel_; }
std::size_t size() const noexcept { return size_; }
void push_back(const T& value)
{
insert(end(), value);
}
void push_front(const T& value)
{
insert(begin(), value);
}
iterator insert(iterator pos, const T& value)
{
NodeBase* current = pos.p_;
NodeBase* before = current->prev;
Node* node = new Node(value, before, current);
before->next = node;
current->prev = node;
++size_;
return iterator(node);
}
iterator erase(iterator pos)
{
NodeBase* current = pos.p_;
if (current == &sentinel_)
return end();
NodeBase* next = current->next;
current->prev->next = current->next;
current->next->prev = current->prev;
delete static_cast<Node*>(current);
--size_;
return iterator(next);
}
void clear()
{
NodeBase* p = sentinel_.next;
while (p != &sentinel_)
{
NodeBase* next = p->next;
delete static_cast<Node*>(p);
p = next;
}
sentinel_.prev = &sentinel_;
sentinel_.next = &sentinel_;
size_ = 0;
}
private:
NodeBase sentinel_;
std::size_t size_ = 0;
};
int main()
{
List<int> values;
values.push_back(1);
values.push_back(2);
values.push_front(0);
for (int v : values)
std::cout << v << ' ';
std::cout << '\n';
auto it = values.begin();
++it;
values.erase(it); // 删除 1
for (int v : values)
std::cout << v << ' ';
std::cout << '\n';
return 0;
}这段代码有几个值得核对的细节。
哨兵的初始化：构造函数把sentinel_.prev和sentinel_.next都指向自己，形成空环。empty()判断sentinel_.next == &sentinel_；如果忘记初始化，begin()会返回野指针，遍历直接崩溃。
迭代器的向下转型：static_cast<Node*>(p_)只在p_确实指向Node时有效。end()的p_指向NodeBase哨兵，不能解引用；标准库同样规定对end()解引用是未定义行为。insert和erase返回的迭代器都指向真实结点或end()，不会把哨兵当元素。
插入的四条赋值：before->next = node; current->prev = node;与Node构造函数里的prev/next初始化配合，保证新结点两侧都连通。size_在链接完成后自增。如果new抛异常，链表尚未修改，仍保持一致。
删除的返回值：erase返回next，调用方可以继续遍历而不必重新begin()。这是std::list的接口约定，也是“边遍历边删除”能写成it = list.erase(it)的原因。删除后current已释放，不能再访问它的任何成员。
析构与 clear：先保存next再delete，因为delete之后p->next不可读。清空后把哨兵重新指向自己，size_归零，对象可以继续使用。
拷贝被删除：List拥有所有结点，默认拷贝会复制哨兵指针和size_，两个对象析构同一批结点。需要拷贝时应实现深拷贝：遍历源链表，对每个元素调用push_back；需要移动时，把源对象的哨兵重新指向自己，并接管其结点。
五、和 std::list 的差距
| 特性 | 本文实现 | std::list |
|---|
| 双向迭代器 | 支持 | 支持 |
| 哨兵 | 支持 | 支持 |
const_iterator | 未实现 | 支持 |
| 拷贝/移动 | 删除拷贝，未实现移动 | 完整支持 |
| 分配器 | 未使用 | 支持自定义分配器 |
emplace/insert重载 | 仅const T& | 完整转发与就地构造 |
| 异常安全 | 基本保证 | 标准库实现保证 |
splice/merge/sort | 未实现 | 支持 |
这些差距不是“实现得不够好”，而是教学模型有意裁剪。真正要补的第一项是const_iterator：它需要一套只读的迭代器类型，并让begin()/end()在 const 对象上返回它。第二项是移动语义：移动构造可以把源对象的结点整体接过来，只需重新指向哨兵，复杂度 O(1)。第三项是emplace_back：把参数完美转发到结点构造，避免先构造临时对象再拷贝。
常见坑点
- ❌ 构造函数忘记把哨兵的
prev/next指向自己，空链表遍历进入野指针。
✅ 构造时立即形成自环；empty()用sentinel_.next == &sentinel_判断。
- ❌ 对
end()解引用，或对空链表的begin()解引用。
✅end()只是位置标记，不解引用；空链表遍历前先判断begin() != end()。
- ❌ 析构或
clear时先delete p再读p->next。
✅ 先保存NodeBase* next = p->next;，再删除，最后移动p。
- ❌ 插入时先改旧结点的指针，再构造新结点，异常时链表断裂。
✅ 先完成新结点的构造和初始化，再修改旧结点的链接；或保证构造不抛异常后再链接。
- ❌
erase返回void或返回错误的迭代器，导致边遍历边删除无法写。
✅ 返回被删元素的后继迭代器；调用方用it = list.erase(it)继续。
- ❌ 删除结点时只改
prev->next，忘记next->prev。
✅ 双向链表的两侧都要更新；有哨兵时头尾也不需要特判。
- ❌ 让
List可拷贝但使用默认拷贝，两个对象共享结点。
✅ 删除拷贝，或实现深拷贝；析构重复释放同一结点是未定义行为。
- ❌ 认为
insert会让所有迭代器失效。
✅list的插入不使已有迭代器失效；只有被删除元素的迭代器失效，其他位置不受影响。
总结
| 组件 | 作用 | 关键实现 |
|---|
NodeBase | 只含前后指针 | 让哨兵不必构造T |
Node | 指针 + 元素 | 继承NodeBase |
| 哨兵 | 表示end()，连接首尾 | 空表时自环 |
iterator | 包装结点指针 | ++/--沿环移动 |
insert | 在 pos 前插入 | 改前驱 next 与 pos prev |
erase | 删除 pos | 两侧互连，返回后继 |
clear | 释放全部结点 | 先存 next 再 delete |
实现list的关键不是记住多少个指针，而是理解哨兵如何把“头、尾、空表”三种特殊情况统一成一种情况。一旦整条链是一个环，插入删除就只剩“在某个位置前接入/摘除一个结点”这一个动作，迭代器的begin/end/--end也都自然成立。理解这一点，再去看std::list的接口，就不会觉得那些看似奇怪的约定是随意设计的。
