C++ STL list 基于双向链表实现。节点结构、迭代器设计（含指针与引用适配）、默认成员函数（构造/拷贝/赋值/析构）及核心接口（增删查改）。重点分析迭代器失效机制，对比 std::sort 与 list::sort 效率差异，并提供 vector 辅助排序的优化方案。
list 是 STL 中支持在任意位置高效（常数时间）插入、删除的双向迭代序列式容器，底层基于带头双向链表实现。每个元素存于独立节点，通过指针连接前后元素。它和 forward_list 类似但后者是单链表、仅支持前向迭代；和 array、vector、deque 相比，list 的插入删除效率更优，但缺点是不支持随机访问（访问第 n 个元素需线性遍历），且每个节点的指针会占用额外空间。
namespace impl {
template<class T>
struct list_node {
// 构造函数：初始化节点值，前后指针默认置空
list_node(const T& val = T()) : _next(nullptr), _prev(nullptr), _val(val) {}
T _val; // 节点数据域
list_node<T>* _next; // 后继节点指针
list_node<T>* _prev; // 前驱节点指针
};
}
成员变量设为公有，是为了让后续写 list 容器 / 迭代器时，能直接操作节点的 _next/_prev/_val，省写 get/set，简化代码。
namespace impl {
template<class T>
struct _list_iterator {
typedef list_node<T> Node;
// 构造：用节点指针初始化迭代器
_list_iterator(Node* node) :_node(node) {}
Node* _node; // 指向链表节点的指针
};
}
因为链表的原生指针只能访问节点本身，而迭代器需要模拟'像普通指针一样解引用取数据、++/-- 遍历'的行为。链表节点里存的是 _val（实际数据），原生指针解引用得到的是整个节点，不是数据；且链表的'下一个元素'需要通过 _next 指针跳转，原生指针的 ++ 是地址 +1（不符合链表的节点连接逻辑），所以得封装迭代器类来重载 *、++ 等运算符。
迭代器结构体用 struct，是因为迭代器只是遍历容器的工具，没有对应的容器支撑也没法实际访问有效数据，所以不用刻意封装成私有，用 struct 让成员直接暴露，能简化后续迭代器功能的实现。
不能为迭代器编写析构函数。因为节点的内存是由容器管理的，迭代器只是'借用节点指针来访问元素'，本身并不持有节点的所有权。若在迭代器析构时释放节点，会导致容器内的节点被非法销毁，进而引发内存错误。
namespace impl {
template<class T>
class list {
typedef list_node<T> Node;
private:
Node* _head; // 指向链表头节点的指针
size_t _size; // 链表中有效元素的个数
};
}
// 初始化空链表（创建哨兵位）
void empty_init() {
_head = new Node;
_head->_prev = _head; // 头节点前驱指向自身（循环链表）
_head->_next = _head; // 头节点后继指向自身（循环链表）
_size = 0; // 链表初始长度为 0
}
// 链表构造函数
list() { empty_init(); }
// 拷贝构造函数：用已有的 list 对象 lt 初始化新对象
list(const list<T>& lt) {
empty_init(); // 先初始化空链表（创建头节点）
// 遍历 lt 的每个元素，逐个尾插到新链表中
for (auto& e : lt) {
push_back(e);
}
}
void swap(list<T>& lt) {
std::swap(_head, lt._head); // 交换头节点指针
std::swap(_size, lt._size); // 交换元素个数
}
// 赋值运算符重载
list<T>& operator=(list<T> lt) // 传值调用，自动拷贝出临时对象 lt
{
swap(lt); // 交换当前对象与临时对象的资源
return *this; // 返回当前对象，临时对象会自动销毁旧资源
}
利用拷贝构造 + 交换实现赋值运算符重载，高效且安全。
// 清空链表中所有有效元素（保留头节点）
void clear() {
iterator it = begin();
while (it != end()) {
it = erase(it);
}
_size = 0;
}
// 链表析构函数：释放所有资源
~list() {
clear(); // 先清空所有有效元素
delete _head; // 释放头节点的堆内存
_head = nullptr; // 将头节点指针置空，避免野指针
}
// 普通迭代器：元素可读写
typedef _list_iterator<T, T&, T*> iterator;
// const 迭代器：元素只读
typedef _list_iterator<T, const T&, const T*> const_iterator;
// 普通正向迭代器：指向第一个有效元素
iterator begin() {
return iterator(_head->_next);
}
// 普通正向迭代器：指向尾后位置（头节点）
iterator end() {
return iterator(_head);
}
// const 正向迭代器：指向第一个有效元素（只读）
const_iterator begin() const {
return const_iterator(_head->_next);
}
// const 正向迭代器：指向尾后位置（只读）
const_iterator end() const {
return const_iterator(_head);
}
迭代器类的单参数构造函数支持隐式类型转换，可将 Node* 自动转为 iterator/const_iterator 对象。
template<class T, class Ref, class Ptr >
struct _list_iterator {
typedef list_node<T> Node;
typedef _list_iterator<T, Ref, Ptr> self;
Node* _node; // 指向链表节点的核心指针
// 单参数构造函数
_list_iterator(Node* node) :_node(node) { }
// 解引用运算符重载：返回元素的引用
Ref operator*() {
return _node->_val;
}
// ->运算符重载：返回元素的指针
Ptr operator->() {
return &this->_node->_val;
}
// 前置++运算符重载：移动到下一个节点，返回自身引用
self& operator++() {
_node = _node->_next;
return *this;
}
// 后置++运算符重载：移动到下一个节点，返回原位置迭代器
self operator++(int) {
self tmp(*this);
_node = _node->_next;
return tmp;
}
// 前置--运算符重载：移动到前一个节点，返回自身引用
self& operator--() {
_node = _node->_prev;
return *this;
}
// 后置--运算符重载：移动到前一个节点，返回原位置迭代器
self operator--(int) {
self tmp(*this);
_node = _node->_prev;
return tmp;
}
// 判不等运算符重载
bool operator!=(const self& it) const {
return _node != it._node;
}
// 判相等运算符重载
bool operator==(const self& it) {
return _node == it._node;
}
};
这里返回的是 _node 节点存储的数据，返回类型用 T&（目的是避免传递自定义类型时产生不必要的拷贝开销）。
Ref 参数的作用？
而我们在代码里用 Ref 替代了具体的返回值类型，是为了通过这个模板参数适配 const 迭代器：当第二个模板参数传入的是 const T& 时，就代表这是一个 const 迭代器（此时解引用返回的是只读引用）。
重载这个运算符，是为了应对数据是结构体的场景。当存储的数据是结构体时，仅用 operator* 解引用后，没办法直接访问结构体的成员；而重载 -> 后，就能直接通过迭代器用 -> 访问结构体成员。
编译器对迭代器的 operator-> 做了'语法糖'优化，允许省略一次 ->，让 it->_a2 等价于 (it.operator->())->_a2，用起来更自然简洁。
ptr 模版参数的作用？
Ptr 的作用在此体现：区分普通迭代器返回的 T*（可读写结构体成员）和 const 迭代器返回的 const T*（只读），实现一套模板复用，保证 const 迭代器的安全性。
前置 ++ 和 -- 的逻辑很相似：都是直接修改当前迭代器的节点指针（_node），然后返回自身的引用。返回自身引用的好处是支持链式操作（比如 ++(++it)），而且没有临时对象的开销，效率更高。
后置 ++ 和 -- 的核心是'先返回原状态，再移动'。函数参数里的 int 是个占位符（没有实际意义，只是用来区分前置 / 后置）。这样外部使用时，it++ 拿到的是'移动前的迭代器'，而 it 本身已经完成了移动。
这两个运算符的逻辑很直接：判断两个迭代器的 _node 指针是否指向同一个节点。其中 operator!= 后面加了 const，是为了保证'调用这个函数时不会修改当前迭代器的状态'，更符合 const 正确性的规范。
lt.begin() 返回临时迭代器，it 是用它拷贝构造而来的。编译器默认生成的拷贝构造是浅拷贝，只会复制内部节点指针，让 it 和原临时迭代器指向链表中同一个节点。这刚好满足需求，深拷贝不仅多此一举，还会带来巨大开销，对迭代器来说毫无意义。因此迭代器不用写拷贝构造。
void push_back(const T& x) {
Node* tail = _head->_prev;
Node* newnode = new Node(x);
tail->_next = newnode;
newnode->_prev = tail;
newnode->_next = _head;
_head->_prev = newnode;
++_size;
}
先找到链表的尾节点 tail，再创建新节点 newnode；接着把 tail 的 next 指向新节点、新节点的 prev 指向 tail，完成新节点和原尾节点的连接；最后让新节点的 next 指向头节点、头节点的 prev 指向新节点，维持链表的循环结构。
// pos 位置之前插入
iterator insert(iterator pos, const T& x) {
Node* cur = pos._node;
Node* prev = cur->_prev;
Node* newnode = new Node(x);
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
++_size;
return newnode; // 返回新节点的迭代器
}
先从迭代器 pos 里拿到它指向的节点 cur，再找到 cur 的前驱节点 prev，同时创建新节点 newnode；把 prev 的 next 指向新节点、新节点的 next 指向 cur，再让 cur 的 prev 指向新节点、新节点的 prev 指向 prev—— 这样就把新节点'夹'在了 prev 和 cur 之间。
void push_front(const T& x) {
insert(begin(), x);
}
直接复用 insert，在 begin()（头节点迭代器）前插入元素 x，既简化代码又保证逻辑一致。
void pop_back() {
assert(_head->_next != _head); // 断言：确保链表不为空
Node* del = _head->_prev; // 找到要删除的尾节点
Node* tail = del->_prev; // 找到尾节点的前驱节点（新的尾节点）
tail->_next = _head; // 建立新尾节点和头节点的双向连接
_head->_prev = tail; // 断开原尾节点
delete del; // 释放原尾节点的内存
_size--; // 更新链表元素个数
}
// pos 位置删除
iterator erase(iterator pos) {
assert(pos != end()); // 断言：确保删除的不是尾后迭代器
Node* cur = pos._node; // 提取待删除节点 cur
Node* prev = cur->_prev; // 找到 cur 的前驱和后继节点
Node* next = cur->_next;
prev->_next = next; // 建立前驱和后继的双向连接，跳过待删除节点
next->_prev = prev;
delete cur; // 释放待删除节点内存
--_size; // 更新链表元素个数
return next; // 返回后继节点迭代器，避免迭代器失效
}
void pop_front() {
erase(begin());
}
直接复用 erase 函数，删除 begin() 对应的头节点。
insert 操作：list 节点物理离散，插入仅新增节点、不改变原有节点地址，因此原迭代器不会失效；返回新节点迭代器，可按需更新使用。
erase 操作：仅被删除节点的迭代器失效（节点内存被释放），其他迭代器仍有效；返回被删节点的后继节点迭代器，需用它更新原迭代器，避免访问失效节点。
void swap(list<T>& lt) {
std::swap(_head, lt._head); // 交换两个链表的头节点指针
std::swap(_size, lt._size); // 交换两个链表的元素个数
}
通过 std::swap 分别交换两个链表的头节点指针和元素个数，实现两个链表数据的高效交换（无需拷贝 / 移动节点，仅交换两个核心成员，时间复杂度 O(1)）。
void clear() {
iterator it = begin();
while (it != end()) {
it = erase(it);
}
_size = 0;
}
通过遍历 + 复用 erase 删除所有节点，利用 erase 返回的后继迭代器避免失效，最后重置 _size 完成清空。
单向迭代器：仅支持 ++（向后移动），对应底层是单向链表 / 哈希结构的容器（如 forward_list、unordered_map）；
双向迭代器：支持 ++/--（前后移动），对应底层是双向链表 / 树形结构的容器（如 list、map、set）；
随机迭代器：支持 ++/--/+/-（任意位置跳转），对应底层是连续存储的容器（如 vector、string、deque）。
std::sort 算法要求迭代器是随机迭代器（支持 +/- 等随机跳转操作），但 list 的迭代器是双向迭代器（仅支持 ++/--），不满足 std::sort 的要求，因此 list 无法直接使用全局的 std::sort。
list 提供了自己的 sort 成员函数，但它的效率存在局限性：因为链表是离散存储的，元素不连续，缓存利用率低，所以 list::sort 的效率比 std::sort（基于连续存储的高效排序）要差；仅在数据量较小时，list::sort 的效率尚可；数据量较大时，和 std::sort 的效率差异会非常明显。
void test_op() {
srand((unsigned)time(NULL));
const int N = 5000000;
vector<int> v;
v.reserve(N);
list<int> lt1;
for (int i = 0; i < N; ++i) {
auto e = rand();
v.push_back(e);
lt1.push_back(e);
}
// vector 用 std::sort 排序
int begin1 = clock();
sort(v.begin(), v.end());
int end1 = clock();
// 链表用 list::sort 排序
int begin2 = clock();
lt1.sort();
int end2 = clock();
printf("vector sort:%d\n", end1 - begin1);
printf("list sort:%d\n", end2 - begin2);
}
数据量越小，差异越小：当数据量仅 5 万时，vector sort 耗时 3，list sort 耗时 5，两者效率接近；
数据量越大，差异越悬殊：数据量到 500 万时，vector sort 仅需 267，list sort 却要 2772—— 耗时是前者的 10 倍以上；
核心原因：vector 是连续存储，std::sort 能利用缓存高效排序；而 list 是离散节点，list::sort 缓存利用率低，数据量放大后效率劣势会被急剧放大。
std::list 中的元素拷贝到 std::vector 中（利用 vector 的连续存储特性）；std::sort 对 vector 中的数据排序（std::sort 适配随机迭代器，效率高）；vector 数据再拷贝回 std::list。借助 vector 的连续存储 + 缓存友好，结合 std::sort 的高效实现，能大幅提升 list 数据的排序性能（尤其适合大数据量场景）。
void test_op() {
srand((unsigned)time(NULL));
const int N = 5000000;
list<int> lt1;
list<int> lt2;
for (int i = 0; i < N; ++i) {
auto e = rand();
lt1.push_back(e);
lt2.push_back(e);
}
// 方案 1：list→vector→std::sort→回写 list
int begin1 = clock();
vector<int> v;
v.reserve(N);
for (auto& e : lt1) {
v.push_back(e);
}
sort(v.begin(), v.end());
int i = 0;
for (auto& e : lt1) {
e = v[i++];
}
int end1 = clock();
// 方案 2：直接调用 list 内置 sort 成员函数
int begin2 = clock();
lt2.sort();
int end2 = clock();
printf("list→vector→std::sort 耗时：%d\n", end1 - begin1);
printf("list::sort 直接排序 耗时：%d\n", end2 - begin2);
}
从运行结果能明显看到：'list→vector→std::sort' 仅耗时 412，而'list::sort 直接排序'耗时 3299，前者效率是后者的 8 倍左右，充分体现了借助 vector+std::sort 优化 list 排序的显著优势。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online