前言
list是C++STL的容器之一，相比string和vector，list在插入和删除数据时的效率更高。因为list的存储模型是一个个节点，新增数据并不需要将旧空间销毁，重新开辟新空间。但是list访问数据的速度较差，因为需要从某个节点开始不断迭代
一、关于list
1.list的大小
用不同的类型分别对库中的list进行实例化，并计算其大小，我们会发现，大小都是12。并且list的存储空间是动态申请，是否插入数据不会影响list的大小，因为sizeof只会计算所占栈空间的大小。如下图
2.list的存储结构
容器list的底层是带头双向循环链表。list的存储空间并不是连续的，而是依靠指针联系在一起的一个个节点。如下图
通过查看stl库中list节点的定义，我们可以清楚的看到其结构。如下图
每个节点中有三个变量。
指针prev用来指向前一个节点，指针next指向后一个节点，data则用来存储数据
3.list的成员变量
list本身只有一个成员变量，是指向头节点的指针。
因为不管链表有多少个数据，创建了多少个节点，都可以通过头节点迭代到其他任何节点。但是因为list存储空间的不连续，所以不能通过指针来进行迭代，而是需要我们自己实现迭代器类。
但是为了方便计算节点个数，可以新增一个成员变量用来记录节点个数。
4.list的成员函数
4.1Member functions部分函数
关于构造函数会存在调用歧义的问题，下文会进行说明。
4.2Iterators部分函数
迭代器是链表的重点，因为需要我们自己实现，下文会进行详解。
4.3Capacity部分函数
4.4Modifiers部分函数
重点是erase函数存在的迭代器失效问题，下文会进行解释。
二、list的模拟实现
1.节点的实现
节点是自定义类型，除了三个成员变量，还应该有以一个构造函数用来对节点中的两个指针和存储的数据进行初始化。
对于任何新创建的节点，两个指针都置为空，因为链接关系的建立在创建节点之后，因为节点存储的数据类型不确定是内置类型还是自定义类型，因此缺省参数给的默认值写法是匿名对象的写法，这样写可以保证即使T是自定义类型，也能进行初始化。如下图
2.成员变量的实现
list的底层是带头双向循环链表，list的成员变量只有一个指向头节点的指针，通过头节点指针，就可以迭代到其他任何节点。
为了方便获取list的节点个数，为list添加一个size_t _size=0;的成员变量。如下图
3.list迭代器的实现
3.1vector中的迭代器
在vector中，普通迭代器和const迭代器就是对普通指针和const指针的重定义。其中模板参数T表示指针所指向内容的类型。如下图
vector的迭代器本质上就是指针，这是因为vector的存储空间是连续的，指针的++，--可以让vector找到下一个数据的位置。
但是对于list来说，它的存储模型是一个个不连续的节点，指针的++，--不能让list找到下一个或者前一个节点的位置。
3.2list的迭代器类
普通的指针不能用做list的迭代器。list的迭代器需要我们自己封装实现，并且在用法上和vector的迭代器用法完全相同。也就是说要实现一个迭代器类，该类就等同于适用于list的指针。
又因为普通对象和const对象的存在，所以需要实现普通迭代器类和const迭代器类。但实际上可以只实现一个迭代器类，通过模板参数来控制想要实例化出普通迭代器还是const迭代器。
3.3普通迭代器类
如下图
3.4const迭代器
如下图
3.5list迭代器类的正确打开方式
普通迭代器和const迭代器之间的区别其实并不大，只不过是const迭代器指向的内容不可以被修改，而普通迭代器指向的内容可以被修改。而这正和operator*,operator->的返回值相关联。
const迭代器的operator*函数和operator->函数的返回值有const修饰，所以指向的内容才不可以被修改，而普通迭代器这两个函数的返回值没有const修饰，所以可以通过迭代器修改指向的内容。
也就是说，只要控制了迭代器类中返回值的类型，就控制了迭代器类实例化出的到底是普通迭代器还是const迭代器。这样我们就只需要写一个迭代器类。没必要像上文一样，写两个迭代器类，并且两个类的实现大同小异，实在太过繁琐。
通过模板参数来迭代器类的返回值。如下图
迭代器类Iterator的模板参数的解释：
T:控制迭代器指向内容的数据类型
Ptr:控制迭代器函数operator*的返回值
Ref：控制迭代器函数operator->的返回值
list中的普通迭代器和const迭代器。如下图
在list中，普通迭代器和const迭代器的参数是确定的。也就是说，迭代器类会分别根据list中普通迭代器和const迭代器所给的模板参数去实例化。
普通迭代器在迭代器类中的实例化
迭代器类接收的三个模板分别是T,T*,T&
所以Self的类型就是普通迭代器的类型 Iterator<T,T*,T&>,所以Self作为++，--的返回值，没问题。
Ptr的类型是T*，作为普通迭代器operator*的返回类型，可以被修改，没问题。
Ref的类型是T&，作为普通迭代器operator->的返回类型，可以被修改，也没问题。
const迭代器在迭代器类中的实例化
迭代器类接收的三个模板分别是T,const T*,const T&
所以Self的类型就是const迭代器的类型 Iterator<T,const T*,const T&>,所以Self作为++，--的返回值，没问题。
Ptr的类型是const T*，作为普通迭代器operator*的返回类型，不允许被修改，没问题。
Ref的类型是const T&，作为普通迭代器operator->的返回类型，不允许被修改，也没问题。
4.成员函数的实现
4.1Member functions部分函数实现
前情提要：对于带头双向循环链表，每个节点的prev指针指向前一个节点，next指向指向后一个节点。只有头节点时也不例外 ，即使它指向的都是自己。
所以即使是空的list（只有头节点），也要在构造函数中进行初始化，让头节点的前后指针都指向自己。
如下图
构造函数 一
初始化列表当中的初始化，只能让头指针_head指向的头节点中的_prev和_next置为空，所以需要Init函数来指向自身。如下图
构造函数 二
作用：将list初始化为有n个val的链表
链接关系：只要让每个节点的_prev指针指向前一个节点，_next指针指向后一个节点即可。如下图
构造函数 三
作用：将list初始化为迭代器所指向链表相同的内容
构造函数 四
当有如下list3的初始化时，虽然我们的本意是调用构造函数二，但是在编译器看来构造函数三更加符合int,int类型。所以就会调用构造函数三导致发生错误。如下图
解决方法：新增一个构造函数，只要将构造函数二的第一个参数的size_t类型改为int即可。如下图
析构函数：
list的析构函数需要将每个节点各自的空间释放掉。
注意事项：
在释放当前节点之前，需要保存下一个节点的位置，最后释放头节点，并将头指针置空。
拷贝构造函数
作用：用一个list对象来初始化另一个list对象
注意事项：每个节点的拷贝都需要动态申请空间，然后才是节点关系的链接
如下图
赋值运算符重载
赋值运算符重载函数的参数没有用引用，所以会调用拷贝构造，而后交换拷贝构造而来的x，拷贝对象除了作用域后就会销毁。
4.2Iterators部分函数的实现
需要注意的是begin返回的是头节点的下一个节点，而end返回的就是头节点。这是因为头节点的下一个节点才是真正存储数据的第一个节点，而头节点才是最后一个存储数据节点的下一个节点。
4.3Capacity部分函数的实现
直接利用成员变量_size进行判断即可。如下图
4.4Modifiers部分函数实现
尾插
创建新节点后，建立链接关系，最后更新链表数据个数。如下图
尾删
尾删前需要保存前一个节点的位置，删除节点一定要释放空间，建立链接关系后，更新节点个数即可。如下图
任意位置插入
在position位置前插入。需要保存当前节点已经当前节点的前一个节点的位置。建立链接关系后更新节点个数。如下图
任意位置删除
注意事项：头节点不能被删除。删除当前节点前需要先保存前后节点的位置，然后建立链接关系，最后跟新节点个数。如下图
5.删除中的迭代器失效问题
删除迭代器it指向的数据后，it指向的节点已经被销毁，此时对it++，会引发报错。如下图
正确的写法是每次删除后重新赋值。如下图
6.反向迭代器的实现
反向迭代器是利用正向迭代器来实现的，正向迭代器就是我们自己实现的迭代器类。
模板参数接收的是我们自定义的迭代器类。成员变量也是迭代器类的对象。
反向迭代器的++就是正向迭代器的--，--就是++。
typename的作用是明确告诉编译器，Ref是Iterator类中的类型。如下图
