探索解析C++ STL中的 list：双向链表的高效实现与迭代器
前引：链表作为一种基础数据结构，其非连续内存存储特性使其在频繁的插入和删除操作中具有O(1)的时间复杂度优势，这与数组类型容器形成了鲜明对比。然而，这种优势的背后也伴随着随机访问性能的牺牲和额外的内存开销。本文将从底层实现原理出发，深入探讨`std::list`的内存模型、迭代器特性、以及与其他STL容器的性能对比。我们将通过详细的代码示例和性能分析，帮助读者全面理解何时选择`std::list`，如何高效使用其接口，以及在实际项目中如何权衡其优缺点。无论您是希望深化对STL理解的C++进阶开发者，还是正在学习数据结构与算法的学生，本文都将为您提供系统性的技术洞察和实践指导。让我们一同探索这一经典数据结构在现代C++中的精妙实现
【注意：本文的重点一是知道list的结构，二是迭代器的实现】
目录
List介绍
List也是C++标准模板库（STL）中的一种容器，它的内存存储特点与string、vector不同，它的存储不是连续的，List将元素存储在不连续的内存中，通过指针连接前一个节点和后一个节点。综合来说：就是另一种vector：只是内存存储变成了不连续，下面我来介绍它的各种常用接口！
List实例化
list<类型> 就是它的数据类型，后面跟上变量名即可，例如：
//list实例化 list<int> V;//list实例化 list<int> V{ 1,2,3,4,5 };如果想在实例化的时候放上元素，不能和vector、string那样，例如：
尾插元素
使用和之前的两个容器string与vector一样，例如：
//list实例化 list<int> V; //尾插元素 V.push_back(1); V.push_back(2); V.push_back(3);访问元素
在C++中支持迭代器的容器那就支持auto，而不支持迭代器的容器很少：
stack queue priority_queue
所以我们可以通过迭代器去访问元素，例如：
问：为何不是连续的空间，可以使用“++”?
首先“++”是在迭代器里面用了运算符重载（因此只支持在迭代器里面使用），例如：
//迭代器读\写 auto it = V.begin(); while (it != V.end()) { cout << *it << " "; it++; } cout << endl; //auto的底层就是迭代器 for (auto e : V) { cout << e << " "; } cout << endl;
指定位置前插入
这个就是 insert 接口，我们直接看：
//指定位置前插入 V.insert(V.begin(), 5);
注意：list 的内存是不连续的，不能直接使用“+”，例如：
注意：insert 之后对于List的迭代器是不会失效的，例如：
指定位置删除
//指定位置删除 V.erase(V.begin());
注意：使用erase之后，如果不接收返回值，那么迭代器就会失效，例如：
排序（升序）
List的排序属于稳定排序（n logn），例如：
v.sort();
排序（降序）
V.sort(greater<int>());
拼接
拼接支持：整体拼接、单个元素拼接、范围拼接，具体的我们实战的时候再去了解
拼接我们在合成多个链表时可以使用，比如：先拼接多个链表再用排序，这样就实现了整体有序
整体拼接：
//拼接V2在V1的末尾 V1.splice(V1.end(), V2);
单个元素拼接：
例如：将 V2中 it2 指向的元素拼接到 V1的 it1 前面
去重
去重的前提是元素已经有序
V2.unique();
反转
V2.reverse();
注意：
pos找到的是5的位置，而reverse翻转的是“闭区间，开区间”的元素，也就是0~4
例如：
注意
对于连续存储的 string、Vector我们可以通过 ++ 来移动获得下一个元素\地址
虽然对于 list 属于非连续的存储，我们还是可以使用 ++ ，这是因为支持了运算符重载，++ 的本质是 ->next，比如我们获取 pos 位置的下一个地址应该用 ++ 而不是 +1
模拟实现
list的结构
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; };为何使用struct？因为这是节点，后面有头节点访问这个节点，私有的不能被访问到
除了节点结构外，我们还需要一个指针去指向这个节点，这个节点我们就为头节点：
//头节点 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; }效果展示：
尾删
尾删注意：如果只有一个头结点的情况下，是不能删除的
我们只需要找到尾cur，然后再标记尾的前一个节点pc，再连接pc和头节点即可，最后释放
//尾删 void push_front() { //如果只有一个节点 assert(Head->next != Head); //找尾 Node* cur = Head->prev; //标记 Node* pc = cur->prev; //重新连接 pc->next = Head; Head->prev = pc; //释放 delete cur; cur = nullptr; }效果展示：
头插
头插需要找到头结点的下一个节点，然后连接即可，例如：
注意：我们这里使用的是迭代器，因此在最后需要更新迭代器
//头插 iterator pop_back(iterator it, const T& date) { //先标记头节点的下一个节点 Node* pc = Head->next; //新节点 Node* cur = new Node(date); //连接 Head->next = cur; cur->prev = Head; cur->next = pc; pc->prev = cur; return it = it._node->prev; }
头删
头删还是先标记头节点的下一个节点cur，和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; }效果展示：
拷贝构造
（1）根据当前存在的链表拷贝构造出新链表，注意深浅拷贝：
如果是内置类型：那么使用字节拷贝
如果是自定义类型：那么使用浅拷贝（编译器默认的拷贝构造）
（2）调用拷贝构造函数时候，不会去再之前调用构造函数，这点很重要，关乎头结点
//拷贝构造 list(const list<T>& V) { //开辟头节点 Head = new Node; Head->next = Head; Head->prev = Head; list<T>::const_iterator it = V.begin(); while (it != V.end()) { //插入 push_back(*it); it++; } }这里由于 V 的类型是 const 类型，需要支持 const 的迭代器
//begin() iterator begin()const { return Head->next; } //end() iterator end()const { return Head; }效果展示：
赋值运算符重载
这里需要注意：空间的问题
我们还是采用新方法：拷贝构造出一个临时空间，再采用交换指针的方法
//交换 void swap(const list<int>& Vt) { //拷贝构造临时对象 list<int> Vs(Vt); //交换 std::swap(Vs.Head, Head); } //赋值运算符重载 list<T>& operator=(const list<int>& V) { swap(V); return *this; }效果展示：
迭代器
迭代器的效果：如果是解引用，那么需拿到元素；如果是++，那么需要跳到下一个节点
因此：迭代器的指针不能是固定的，否则解引用拿到的就是节点而非数据（运算符重载）
我们先观察库里面迭代器的特点：
list<int>::iterator it = V.begin(); while (it != V.end()) { std::cout << *it << " "; it++; }迭代器结构
这里 ++ 与 * 为了表示出不同的效果，我们使用的是运算符重载；对于非连续的空间的迭代 器实现，最好的方法是单独封装为一个类（大家记住即可），下面是迭代器的实现类结构
//迭代器 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; } };注意：iterator 被重定义了，使用 iterator 其实就是调用 类模板
begin()、end()
第一行会先执行 V.begin()，它的调用解析如下：
过程解析：
先是调用 V.begin（），拿到节点，然后发生隐式转换，调用 iterator 类模板构造，参数是节 点，完成转换，返回值再交给 it ，同理 V.end（）也是一样
这里的返回值是隐式类型转化，无法使用 &
关系比较 !=
过程解析：
V.end() 作为参数先在类模板被初始化，然后直接调用运算符重载函数，返回 bool 值
运算符重载 *
过程解析：
it 的类型是 iterator 类型，它的改变就是下面的 ++ 操作
运算符重载 ++
为方便识别前置后置++：有 int 参数就是后置，无参数就是前置
无法修改的迭代器
对于无法修改的迭代器的效果：只可以访问，不能修改访问元素
方法（1）
const 的修饰效果：
所以我们可以直接在返回值这里加上 const 修饰，这是最直接的方法：
方法（2）
我们发现 const T 跟 T 只是类型不同，其它都是相同的，那么我们可以通过类模板的参数去修改它
而 节点 的类型模板参数是 T ，所以我们得保证它跟迭代器的第一个参数是吻合的，比如：
不然节点的类型参数和迭代器的对不上，那就报错了
所以我们const类的迭代器和非const的迭代器，可以如下定义：
typedef list_iterator<T, T&> iterator; typedef list_iterator<T, const T&> const_iterator; 原因：我们的类模板重定义了，由于两个不同的类参数： <T T&> <T const T&>
会形成两个不同的类：iterator<T T&> iterator<T constT&>
所以我们只需要控制类模板的第二个参数去返回就可以达到“修改”和“不可修改”的效果了
const与非const迭代器转化图：
这里最右边的第二个构造函数的参数我们现在只需要看就行了，这比较超前，我们后面再说！
总结：
对于迭代器const与非const的转化，以及其它类型的转化，我们都是调用构造函数来完成的，比如
一个节点类型 转化为 迭代器类型 一个迭代器 非const类型 转化为 const类型
这期间可能涉及到构造函数的重载，都是区分构造函数的参数来实现
