C++：list（带头双向链表)增删查改模拟实现
Hello大家好！ 很高兴与大家见面！ 给生活添点快乐，开始今天的编程之路。
我的博客:<但愿.
我的专栏:C语言、题目精讲、算法与数据结构、C++
欢迎点赞，关注
目录
前言：(这里相对于string、vector，相对复杂，讲解较多）
1与string、vector相比：
1.1没有重载运算符[]接口：
1.2没有reserve(扩容)接口：
1.3list增加的接口：
1.4迭代器的不同：
一、list底层带头双向链表验证，节点构造
1.1节点的构造：
1.2list底层数据结构(带头双向链表)
二 迭代器总结
2.1迭代器的分类（支持的操作/性质)
2.2迭代器的实现：
三 迭代器封装实现(是一个重点，涉及到多个模板参数的使用，和由于迭代器的封装普通迭代器和const迭代器怎么实现）
3.1前置说明
3.2迭代器的实现
四 list及取接口的实现
4.1基本框架
4.2迭代器和const迭代器(底层上面实现了就不多讲）
4.3构造函数、析构函数、拷贝构造函数、赋值重载、交换、清除
4.3.1构造
4.3.2 清除
4.3.3析构
4.3.4拷贝构造
4.3.5交换函数(对于内置类型调用std库中的交换函数即可)
4.3.6赋值重载(要进行深拷贝)
4.4任意位置插入、任意位置删除、尾插、尾删、头插、头删、节点个数
4.4.1任意位置插入数据
4.4.2任意位置删除数据
4.4.3尾插、尾删、头插、头删（直接复用任意位置插入、任意位置删除）
4.4.4节点个数
五 list完善
5.1迭代器重载(->)
5.2打印数据
六 所有代码
前言：(这里相对于string、vector，相对复杂，讲解较多）
1与string、vector相比：
1.1没有重载运算符[]接口：
前面两个重载两运算符[]是因为它们的底层结构式数组或者是数组类似的结构，访问较快，而list如果重载效率就不行，所以list使用迭代器。
1.2没有reserve(扩容)接口：
因为前面两个扩容插入数据可能一次插入多个，而list每次只能插入一个数据。
1.3list增加的接口：
1.3.1reserve() 接口：用于逆置。
1.3.2merge()接口：归并（要是两个有序带头双向链表）。
1.3.3unique()接口：去重（要是个有序带头双向链表,不然达不到去重效果)。
1.3.4remove()接口：删除这个与rease接口不同，erase接口是删除迭代器指向的位置，而remove()是删除与给定值相同的数据。
1.3.5remove_if()接口：顾名思义效果与remove()接口相同，只是这个是配合仿函数使用满足对应条件就删除。
1.3.6splie()接口：接合，实现两个list对象的接合,注意是将一个list中的数据移动到另一个list中,一个数据增加，一个减少数据。对于参数只有一个list对象，是调整这个对象的数据之间的左右关系。如果有两个list对象就是将一个list中的数据移动到另一个list中。
1.3.7sqrt()接口：排序(底层使用归并排序),所以效率不高，这个并不常用。
（1）为啥算法库中有不像vector一样直接使用算法库中的，而是直接实现一个接口。因为算法库中的sqrt使用了迭代器相减，而list的迭代器不支持迭代器相减的操作。
（2）效率问题：与vector调用算法库中的sqrt进行比较，【注意要在relices版本下进行比较，因为deBug版本下增加了调试的各种信息等原因，并不正确）,从比较来看数据少还好，数据一多就不行，甚至使用vector调用算法库中的sqrt进行排序，再将数据复制到list中时间都比list使用自己的sqrt快，所以数据少可用，数据大尽量不用。
1.4迭代器的不同：
迭代器的核心功能是（*）解引用可以得到指向位置的数据，++可以向前挪动，vector,string都是用原声指针作为迭代器，因为它们的底层结构是数组使用原声指针作为迭代器就可以满足得到迭代器的核心功能，而list如果将原声指针作为迭代器，由于list底层的每个结点不像前面两一样是数组直接是连续的(有联系），此时就满足不了迭代器的核心功能，所以list要对迭代器进行包装，进行运算符重载来满足迭代器的核心功能。是否能使用原声指针作为迭代器，还是要自己包装迭代器实现，是要看是否能满足迭代器的核心功能。
一、list底层带头双向链表验证，节点构造
1.1节点的构造：
节点和数据结构中双向链表的节点一样，有三个变量：节点数据，下一个节点(next)，上一个节点(prev）
小问题：
注意起名尽量和库中名字一样，后续如果在其他类中使用时在typedef。
2这里使用struct进行包装而未使用class进行包装，原因在于C++将struct升级成和类功能相似，只是其中的成员访问权限全部时公有。如果使用class进行包装，要访问取私用成员时要使用友元，过于繁琐。后续如果在一个类中调整其访问权限可以使用typedef在使用访问限定符修饰即可(typedef受访问限定符的限定)
1.2list底层数据结构(带头双向链表)
这里我们通过SGI库中list的成员变量和构造函数来验证，取底层数据结构是带头双向链表。
结合库中list的成员变量和构造函数以及节点的构造，我们不难发现list的实现中只有node一个成员变量。构造函数构造出一个头尾相连的节点(所谓的哨兵位）。同时也验证了list底层时应该带头(哨兵位)双向链表.
二 迭代器总结
本博客采用SGI版本，C++：list增删查改的模拟实现使用的是带头双向链表，非常简单，只是这里对于迭代器的实现不像原来一样使用原声指针，实现较难。对于模板的使用更加丰富,对于初学者确实较难。
2.1迭代器的分类（支持的操作/性质)
2.2迭代器的实现：
对于使用原声指针作为迭代器的直接定义就行，而对于不能将原声指针作为迭代器的就要对迭代器进行包装，这里可以使用class类、还有C++将struct结构体升级为与类相识的只是struct中的是公有。由于使用连要访问其中的成员要么将其设为公有、提供gte函数、将其声明为友元函数，这些情况都不好。这里可以利用struct的特性都是公用，所以我们一般用struct来包装迭代器，那用人问都是公有别人可以访问不会出问题吗？这里对于迭代器的底层实现都不知道，不同平台的实现方式也不同，别人不可能直接访问。
三 迭代器封装实现(是一个重点，涉及到多个模板参数的使用，和由于迭代器的封装普通迭代器和const迭代器怎么实现）
3.1前置说明：说明写的怎么实现list的迭代器，使用struct进行包装在对其使用的运算符进行重载。
3.2迭代器的实现
这里普通迭代器和const迭代器基本一样，只是对于(*)解引用操作得到和（->）操作得到的返回值不同怎么解决呢？方法一：对两种迭代器分别进行封装(不好代码冗余，可读性很差）。方法而：使用多个模板参数，对于不同返回值分别使用一个模板参数【两种从效率上没有差别，只是代码可读性不同】
注意迭代器的实现不用写析构函数，如果使用析构函数不就会打乱节点之间的指向关系，迭代器只是借助这个节点指针进行访问修改，而不是销毁，销毁是由list管。
四 list及取接口的实现
4.1基本框架
list模拟我们和库一样，给一个头节点，还可以加一个统计节点个数的变量_size（方便我们后续得到节点个数，其实可以不定义这个变量，可以通过遍历计算节点个数，为了方便这里还是定义这个变量)。由于接口都是通过迭代器进行访问，所以我们对两个迭代器进行重命名，一方面为了统一接口（string、vector等接口都一样),另一方面屏蔽底层的变量和成员函数的属性。
4.2迭代器和const迭代器(底层上面实现了就不多讲）
4.3构造函数、析构函数、拷贝构造函数、赋值重载、交换、清除
4.3.1构造
思路：由于无参构造就是创建一个只有哨兵位节点的双向链表，后续会用到，所以这里用一个函数(empty_init）来实现。
4.3.2 清除
思路：由于清除函数只是清除数据，所以对于哨兵位不处理。
4.3.3析构
思路：由于上面已经实现clear清除函数，这里我们可以复用清除函数，再对哨兵位节点处理。
4.3.4拷贝构造
思路：拷贝构造首先要初始化一个哨兵位节点（调用empty_init函数），在将需要拷贝的数据尾插即可（尾插后面会实现）
4.3.5交换函数(对于内置类型调用std库中的交换函数即可)
4.3.6赋值重载(要进行深拷贝)
思路：赋值重载的实现方式有很多种。其中比较简单的是我们直接传参(不引用传参)因为编译器优化了，然后将待赋值的变量和传值传参生成的临时变量进行互换。
4.4任意位置插入、任意位置删除、尾插、尾删、头插、头删、节点个数
4.4.1任意位置插入数据
思路：首先依据要插入的数据new出一个新节点newnode,然后将pos节点和pos的后一个节点和新节点newnode相连，最后++_size即可。
4.4.2任意位置删除数据
思路：一定要注意哨兵位节点是不能删除的，将待删除节点的前后节点用一个变量储存（由于这里已经用变量进行储存，所以连接顺序就没有向后要求），然后将pos出节点删除，在将pos处前后节点连接起来，最后--size即可。
小问题：由于最后我们要把pos位置销毁，此时就会引起迭代器失效，所以这里返回新的pos。
4.4.3尾插、尾删、头插、头删（直接复用任意位置插入、任意位置删除）
4.4.4节点个数
五 list完善
5.1迭代器重载(->)
我们可下面代码
struct AA { AA(int a1 = 0, int a2 = 0) :_a1(a1) ,_a2(a2) {} int _a1; int _a2; }; void test_list3() { list<AA> lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); list<AA>::iterator it = lt.begin(); while (it != lt.end()) { cout<<*it<<" "; ++it; } cout << endl; } 分析由于list没有重载<<，所以使用<<只能识别自定义类型，而这里存储的是自定义类型之间访问会编译报错。
那我们重载下<<运算符不就行了吗？很不幸的是C++库在list中不支持<<，很大原因也在于编译器不知到我们如何取数据
所以对于自定义类型我们可以先解引用在去访问成员，也可以在迭代器中重载operator->()函数。但需要注意的是编译器优化了隐藏了一个->，具体原生行为如下：
struct AA { AA(int a1 = 0, int a2 = 0) :_a1(a1) ,_a2(a2) {} int _a1; int _a2; }; void test_list3() { list<AA> lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); list<AA>::iterator it = lt.begin(); while (it != lt.end()) { //cout << (*it)._a1<<" "<<(*it)._a2 << endl; cout << it->_a1 << " " << it->_a2 << endl; //上面编译器访问成员变量的真正行为如下： //cout << it.operator->()->_a1 << " " << it.operator->()->_a1 << endl; ++it; } cout << endl; } 5.2打印数据
//大多数情况模板中使用class还是typename定义是一样的，但当有未实例化模板时，必须使用typename //template<typename T> void print_list(const list<T>& lt) { // list<T>未实例化的类模板，编译器不能去他里面去找 // 编译器就无法list<T>::const_iterator是内嵌类型，还是静态成员变量 // 前面加一个typename就是告诉编译器，这里是一个类型，等list<T>实例化 // 再去类里面去取 typename list<T>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; } 优化：上面打印数据是针对list，下面是针对容器的（使用泛型即模板)
// 模板(泛型编程)本质，本来应该由我们干的活交给编译器 template<typename Container> void print_container(const Container& con) { typename Container::const_iterator it = con.begin(); while (it != con.end()) { cout << *it << " "; ++it; } cout << endl; } 六 所有代码
本篇文章就到此结束，欢迎大家订阅我的专栏，欢迎大家指正，希望有所能帮到读者更好理解C++相关知识 ，觉得有帮助的还请三联支持一下~后续会不断更新C/C++相关知识，我们下期再见。
