C++算法
C++ STL list 双向链表实现与迭代器详解
深入讲解 C++ STL 中 list 容器的原理与应用。内容包括 list 的内存模型、常用接口操作（插入、删除、排序、拼接等），以及基于双向链表的模拟实现。重点剖析迭代器的封装、运算符重载机制，以及 const 与非 const 迭代器的区别与转换方式，帮助读者掌握底层实现细节。
深入讲解 C++ STL 中 list 容器的原理与应用。内容包括 list 的内存模型、常用接口操作（插入、删除、排序、拼接等），以及基于双向链表的模拟实现。重点剖析迭代器的封装、运算符重载机制，以及 const 与非 const 迭代器的区别与转换方式，帮助读者掌握底层实现细节。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 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
List 是 C++ 标准模板库（STL）中的一种容器，内存存储不连续，通过指针连接前一个节点和后一个节点。相比 vector，它在频繁插入删除操作中有 O(1) 的时间复杂度优势，但牺牲了随机访问性能。
本文重点在于理解 list 的结构以及迭代器的实现。
list<类型> 定义数据类型，例如：
// List 实例化
std::list<int> v;
std::list<int> v{1, 2, 3, 4, 5};
注意：list 初始化时不能像 vector 那样直接传入列表，需使用构造函数或 push_back。
使用 push_back 接口：
std::list<int> v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
支持迭代器的容器支持 auto 关键字。stack、queue、priority_queue 不支持迭代器。 可以通过迭代器访问元素：
auto it = v.begin();
while (it != v.end()) {
std::cout << *it << " ";
it++;
}
std::cout << std::endl;
// range-based for loop
for (auto e : v) {
std::cout << e << " ";
}
由于 list 内存不连续，不能使用 + 进行偏移，只能使用 ++（基于运算符重载指向下一个节点）。
使用 insert 接口：
v.insert(v.begin(), 5);
注意： list 内存不连续，不能直接使用 + 计算地址。insert 之后对于 list 的迭代器通常不会失效（除非插入位置导致内存重新分配，但 list 节点独立，一般不影响其他迭代器）。
使用 erase 接口：
v.erase(v.begin());
注意： 使用 erase 后，如果不接收返回值，原迭代器会失效。
List 的 sort 属于稳定排序（n log n）：
v.sort();
v.sort(std::greater<int>());
splice 支持整体拼接、单个元素拼接、范围拼接。 整体拼接： V2 拼接到 V1 末尾
v1.splice(v1.end(), v2);
单个元素拼接： 将 V2 中 it2 指向的元素拼接到 V1 的 it1 前面
v1.splice(it1, v2, it2);
前提：元素已有序。
v2.unique();
v2.reverse();
注意： reverse 翻转的是闭区间到开区间的元素。
List 属于不连续存储，通过指针连接。需要节点结构：包含 prev、next、val。
template<class T>
struct list_node {
public:
list_node(const T& date = T()) : next(nullptr), prev(nullptr), val(date) {}
list_node<T>* next;
list_node<T>* prev;
T val;
};
头节点设计：
template<class T>
class list {
typedef list_node<T> Node;
public:
list() : Head(nullptr) {
Head = new Node;
Head->next = Head;
Head->prev = Head;
}
private:
Node* Head;
};
void push_back(const T& date) {
Node* tmp = new Node(date);
Node* pc = Head->prev;
pc->next = tmp;
tmp->prev = pc;
tmp->next = Head;
Head->prev = tmp;
}
void pop_back() {
assert(Head->next != Head); // 至少有一个数据节点
Node* cur = Head->prev;
Node* pc = cur->prev;
pc->next = Head;
Head->prev = pc;
delete cur;
cur = nullptr;
}
iterator push_front(iterator it, const T& val) {
Node* pc = Head->next;
Node* cur = new Node(val);
Head->next = cur;
cur->prev = Head;
cur->next = pc;
pc->prev = cur;
return it._node = cur;
}
iterator pop_front(iterator it) {
assert(Head->next != Head);
Node* cur = Head->next;
Node* pc = cur->next;
Head->next = pc;
pc->prev = Head;
delete cur;
cur = nullptr;
return it._node = pc;
}
list(const list<T>& V) {
Head = new Node;
Head->next = Head;
Head->prev = Head;
typename list<T>::const_iterator it = V.begin();
while (it != V.end()) {
push_back(*it);
it++;
}
}
begin/end 实现：
iterator begin() { return Head->next; }
iterator end() { return Head; }
const_iterator begin() const { return Head->next; }
const_iterator end() const { return Head; }
采用交换法：
void swap(const list<T>& Vt) {
list<T> Vs(Vt);
std::swap(Vs.Head, Head);
}
list<T>& operator=(const list<T>& V) {
swap(V);
return *this;
}
迭代器封装为类，重载运算符。
template<class T>
struct __list_iterator {
typedef __list_iterator<T> iterator;
typedef list_node<T> Node;
Node* _node;
__list_iterator(Node* node) : _node(node) {}
T& operator*() { return _node->val; }
iterator& operator++(int) {
iterator tmp(*this);
_node = _node->next;
return tmp;
}
bool operator!=(const iterator& it) {
return _node != it._node;
}
};
方法 1：返回值加 const 修饰。 方法 2：通过类模板参数区分。
typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;
通过控制类模板第二个参数返回引用类型，达到'可修改'和'不可修改'的效果。
迭代器 const 与非 const 的转化通过构造函数完成。节点类型转化为迭代器类型，非 const 迭代器转化为 const 类型，均涉及构造函数重载及参数区分。