C++ STL list 底层剖析：从内存布局到反向迭代器的设计哲学
这篇不讲 push_back 怎么用。如果你还在记接口，先去翻文档。这里只聊 list 的底层——内存怎么排、迭代器怎么封、反向迭代器为什么是那个鬼样子，以及 list 在现代硬件上到底还行不行。
一、内存布局：为什么 list 不是你想的那样
标准只说 list 是双向链表，实现可以五花八门。但 glibc 的 libstdc++ 和 MSVC 的 STL 都选了同一种结构：带头结点的双向循环链表。这不是偶然。
1.1 节点长什么样
template <class T>
struct _List_node {
_List_node* _M_next;
_List_node* _M_prev;
T _M_data;
};
两个指针 + 一个 T。没有额外字段，紧凑到极致。_M_data 放在最后有个好处：空 list 的哨兵头结点可以只分配 _M_next 和 _M_prev，不构造 T——如果 T 的构造函数有副作用，这一点能省不少事。
1.2 哨兵头结点：一个让代码变优雅的设计
空 list 时头结点的 _M_next 和 _M_prev 都指向自己：
head
|
v
+——–+
| prev |—+
| next |—+
+——–+
^
|
+—-+
为什么非要这个哨兵？
没有哨兵，在 push_front 和 push_back 时你得分别处理"空链表"和"非空链表"两种情况。代码大概长这样：
// 没有哨兵的丑陋版本
void push_front(const T& val) {
Node* n = new Node(val);
if (_head == nullptr) {
_head = n;
_tail = n;
} else {
n->_next = _head;
_head->_prev = n;
_head = n;
}
}
有哨兵之后，push_front 和 push_back 走同一条路径——不管链表空不空，新节点永远插在"哨兵和第一个节点之间"或"哨兵和最后一个节点之间"。代码统一了，分支少了，bug 也就少了。
这是 Dijkstra 说的 “sentinel value eliminates boundary conditions” 的经典应用。
1.3 循环结构的隐藏好处
头尾相连意味着：
- end() 可以直接返回头结点的迭代器，不需要额外存储尾指针
- rbegin() 可以直接用 end() 构造，物理上就是同一个位置
- 遍历时不需要判空——空链表 begin() == end() 天然成立
二、迭代器：不止是个"封装了指针的类"
PPT 里说"暂时把迭代器理解成指针"，但如果你要手写，得知道 STL 迭代器体系对它有严格的要求。
2.1 迭代器必须暴露的五种类型
STL 算法通过 iterator_traits 来查询迭代器的属性。一个合格的 list 迭代器至少要定义这些：
template <class T>
struct ListIterator {
typedef bidirectional_iterator_tag iterator_category; // 迭代器分类
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef ptrdiff_t difference_type;
// …
};
iterator_category 是最关键的。list 的迭代器是 bidirectional_iterator_tag，意味着它支持 ++ 和 –，但不支持 + n 或 – n。这直接决定了很多算法能不能用在 list 上。
比如 std::sort 的底层是 introsort，需要随机访问（random_access_iterator_tag），所以 std::sort(l.begin(), l.end()) 编译不过。list 自己提供了一个 l.sort()，内部用归并排序，只要求双向迭代器。
2.2 operator-> 的实现细节
迭代器重载 -> 时有个反直觉的点：
T* operator->() { return &(_node->_M_data); }
operator-> 的返回值不是直接当成指针用，而是编译器会递归调用。也就是说 it->foo() 实际等价于 (it.operator->())->foo()。这个语法糖是 C++ 内置的，但写迭代器时必须配合它。
2.3 为什么 list 迭代器不能是指针
vector 的迭代器在很多实现里就是原生指针（T*），因为 vector 的内存是连续的，it + 1 就是下一个元素。
list 的节点散落在堆上，节点之间没有地址连续性，++it 必须走 _node->_M_next。所以 list 的迭代器必须是类，重载 ++ 和 –。
这也意味着：list 的 std::distance 是 O(N)。因为 distance 对 bidirectional iterator 只能一步一步走。对 vector 的 random access iterator，distance 直接做指针减法，O(1)。
三、反向迭代器：适配器模式的教科书案例
反向迭代器不是"重新发明一个反向链表"，而是适配器（Adapter）模式的经典应用。它内部持有一个正向迭代器，把所有操作转调过去。
3.1 为什么 operator* 要先 –
这是最容易让人困惑的地方。看代码：
Ref operator*() {
Iterator tmp(_it);
—tmp;
return *tmp;
}
直接解引用 _it 不行吗？不行。因为 rbegin() 的构造方式是：
reverse_iterator rbegin() { return reverse_iterator(end()); }
end() 指向哨兵头结点。如果直接对 end() 解引用，拿到的是哨兵头结点的 _M_data——未定义行为。
所以 reverse_iterator::operator* 必须先把内部迭代器回退一步，落到真正的最后一个元素上，再解引用。
3.2 off-by-one 的数学解释
正向区间：[begin, end) —— begin 指向第一个元素，end 指向最后一个元素的下一个位置
反向区间：[rbegin, rend) —— rbegin 指向最后一个元素，rend 指向第一个元素的前一个位置
但 rbegin 的物理位置在 end（最后一个元素的下一个），rend 的物理位置在 begin（第一个元素）。
也就是说：
正向： [1] [2] [3] [4] [5] end
^ ^
begin end
反向： rend [5] [4] [3] [2] [1] rbegin
^ ^
rend rbegin
注意 rbegin 物理上在 end 的位置。为了让它逻辑上指向最后一个元素，解引用时必须 –。
这个设计的代价是：base() 成员函数（返回底层正向迭代器）和解引用的位置差一个。*(rit) 和 *(rit.base()) 永远指向不同的元素。写代码时如果混用正向和反向迭代器，这个坑一定要记住。
3.3 为什么 operator== 写错了
PPT 里的代码有个 bug：
bool operator==(const Self& l) const { return _it != l._it; } // 错了！
应该是 == 而不是 !=。这是一个很隐蔽的笔误，编译能过但逻辑是反的。如果你手写反向迭代器，这个 bug 会让 == 和 != 的行为互换，调试起来非常痛苦。
四、插入与删除：指针修改的完整流程
4.1 insert 的每一步
在位置 pos 前插入新节点：
iterator insert(iterator pos, const T& val) {
Node* new_node = new Node(val);
Node* cur = pos._node;
Node* prev = cur->_M_prev;
// 1) 新节点的 next 指向当前节点
new_node->_M_next = cur;
// 2) 新节点的 prev 指向当前节点的前驱
new_node->_M_prev = prev;
// 3) 前驱节点的 next 指向新节点
prev->_M_next = new_node;
// 4) 当前节点的 prev 指向新节点
cur->_M_prev = new_node;
++_size;
return iterator(new_node);
}
四步指针修改，没有元素搬移，没有扩容。时间复杂度 O(1)。
但注意：如果 pos 是通过遍历找到的，找到的过程是 O(N)。所以"list 插入是 O(1)"有个隐含前提——你已经持有指向该位置的迭代器。
4.2 erase 的每一步
iterator erase(iterator pos) {
Node* cur = pos._node;
Node* prev = cur->_M_prev;
Node* next = cur->_M_next;
// 1) 前驱的 next 跳过当前节点
prev->_M_next = next;
// 2) 后继的 prev 跳过当前节点
next->_M_prev = prev;
delete cur;
—_size;
return iterator(next);
}
也是四步指针修改。返回 next 的迭代器，这就是为什么 it = l.erase(it) 能正确工作。
4.3 为什么插入不会导致迭代器失效
从上面的代码可以看到，insert 只修改了插入位置相邻的两个节点的指针。其他节点的 _M_next 和 _M_prev 完全没变，内存地址也没变。所以所有已存在的迭代器仍然有效。
这和 vector 形成鲜明对比：vector insert 可能导致扩容，所有元素被搬到新地址，所有迭代器全部作废。
4.4 为什么删除只让当前迭代器失效
erase 里只有被删节点的内存被 delete 了。其他节点的指针被重新连接，但节点本身还在原地。所以只有指向被删节点的那个迭代器变成了悬空指针，其他迭代器仍然指向有效的节点。
五、list vs vector：不只是复杂度差异
5.1 缓存局部性（Cache Locality）
vector 的元素在内存中连续排列。CPU 读取一个元素时，会把附近的一大块内存预取到缓存行（通常是 64 字节）。遍历 vector 时，几乎每次访问都命中缓存。
list 的节点散落在堆上，彼此之间没有地址关联。遍历 list 时，每次 ++it 都跳到一个完全随机的地址，缓存命中率极低。实际测试中，vector 的遍历速度通常比 list 快 5-10 倍，哪怕 list 的理论复杂度也是 O(N)。
5.2 内存开销
一个 list<int> 的节点在 64 位系统上至少占 24 字节（两个 8 字节指针 + 4 字节 int + 4 字节对齐填充）。存储 100 万个 int，vector 占 4MB，list 占 24MB 以上。
更糟的是，每个节点独立 new/delete，堆分配器会在节点之间插入元数据（大小、标志位等），进一步浪费内存。小节点还容易造成内存碎片——大量 24 字节的块散落在堆中，后续申请大块内存时可能找不到连续空间。
5.3 什么时候 list 真的赢了
list 的优势场景其实很少：
- 需要稳定的迭代器/指针/引用：如果你在遍历容器的同时，需要保存指向某些元素的指针长期有效，list 是更好的选择。vector 一旦扩容，所有指针都废了。
- 大量中间插入删除且元素很大：如果元素类型是重型对象（比如包含大数组的结构体），vector 的搬移开销可能超过 list 的缓存劣势。这时 list 更合适。
- 需要 splice：list 提供 splice 操作，可以在 O(1) 时间内把一段链表整体移动到另一个位置，不需要拷贝元素。这是 list 独有的能力。
除此之外，默认选 vector。 Herb Sutter 在《Exceptional C++》里也表达过类似观点：现代硬件上，list 的性能优势被缓存不友好完全抵消了。
六、现代 C++ 中的 list
C++11 引入了 forward_list——单向链表，比 list 更轻量。每个节点少一个 prev 指针，内存开销更小。代价是只能单向遍历，没有 push_back() 和反向迭代器。
如果你的需求只需要头插/头删，或者只需要单向遍历，forward_list 是比 list 更好的选择。
另外，C++17 的 pmr::polymorphic_allocator 和 C++20 的 std::vector 配合 std::deque 风格的分块存储，在很多场景下进一步挤压了 list 的生存空间。
但这不意味着 list 不重要。它的价值在于教学和设计思想：
- 哨兵头结点的边界消除技巧
- 迭代器封装让算法和容器解耦
- 反向迭代器的适配器模式
- 插入删除时的强异常保证（strong exception guarantee）
这些思想在其他数据结构和设计模式里反复出现。搞懂 list 的底层，对你理解 STL 的整体架构大有裨益。
七、动手验证
如果你看完觉得懂了，建议写个简化版 list 验证一下。需要实现的最低限度：
template <class T>
class list {
struct Node { T data; Node* prev; Node* next; };
Node* _head; // 哨兵
size_t _size;
public:
class iterator; // 正向迭代器
class reverse_iterator; // 反向迭代器
list();
~list();
void push_back(const T& val);
void push_front(const T& val);
iterator insert(iterator pos, const T& val);
iterator erase(iterator pos);
iterator begin();
iterator end();
reverse_iterator rbegin();
reverse_iterator rend();
size_t size() const;
bool empty() const;
};
跑这几个测试用例：
全部通过，list 就算真学透了。
