C++ list 模拟实现：带头双向链表增删查改详解
与 vector、string 的差异
在深入实现之前，先明确 list 与其他容器的区别。相比 vector 和 string，list 有以下显著特点：
- 不支持随机访问：没有重载
[]运算符。底层结构非连续内存，访问效率低，因此主要依赖迭代器。 - 无 reserve 接口：扩容机制不同，list 每次插入一个节点，无需预分配连续空间。
- 特有接口丰富：
reverse()：逆置操作。merge()：归并两个有序链表。unique()：去重（需有序）。remove()/remove_if()：按值或条件删除元素。splice()：接合链表，移动数据而非复制。sort()：内部排序（基于归并排序）。注意，STL 算法库中的 sort 通常依赖迭代器相减，而 list 迭代器不支持该操作，故 list 实现了自己的 sort 接口。
- 迭代器封装：vector 使用原生指针作为迭代器，但 list 节点不连续，必须对迭代器进行包装并重载运算符才能满足核心功能（解引用、自增）。
底层结构与节点构造
list 的底层是带头双向循环链表。验证这一点只需查看 SGI 源码中的成员变量和构造函数，会发现仅有一个指向哨兵位节点的指针。
节点设计
节点包含三个部分：数据域、前驱指针 (prev)、后继指针 (next)。为了简化访问权限控制，这里使用 struct 而非 class，默认成员公有，避免频繁使用友元。
struct Node {
T data;
Node* prev;
Node* next;
Node(const T& val = T()) : data(val), prev(nullptr), next(nullptr) {}
};
哨兵位节点
构造函数中会初始化一个哨兵位节点，其 next 指向自己，prev 也指向自己，形成一个空的双向循环链表。这样处理头尾边界时会更加统一，无需特殊判断。
迭代器封装实现
这是 list 实现的难点。由于不能直接使用原生指针，我们需要自定义迭代器类/结构体。
迭代器分类与性质
迭代器需要支持解引用 (*) 和自增 (++)。对于 const 迭代器和非 const 迭代器，解引用返回值的类型不同（左值引用 vs const 引用）。
实现策略
采用模板参数区分返回值类型，既保证效率又减少代码冗余。使用 struct 包装迭代器，利用其默认公有特性，方便外部访问底层指针。
template <typename T>
{
iterator_category = std::bidirectional_iterator_tag;
value_type = T;
difference_type = ;
pointer = T*;
reference = T&;
Node* _node;
(Node* node) : _node(node) {}
reference *() { _node->data; }
reference *() { _node->data; }
pointer ->() { &(_node->data); }
pointer ->() { &(_node->data); }
ListIterator& ++() {
_node = _node->next;
*;
}
ListIterator ++() {
;
_node = _node->next;
tmp;
}
ListIterator& --() {
_node = _node->prev;
*;
}
ListIterator --() {
;
_node = _node->prev;
tmp;
}
==( ListIterator& other) {
_node == other._node;
}
!=( ListIterator& other) {
_node != other._node;
}
};
