C++中list的使用与实现
一、list的使用
1.1创建
创建的方式与vector很想，也支持
initializer_list
类型的数组快捷创建
1.2迭代器只支持++与--，不再支持+和-
因为+和-涉及到数据的随机访问，链表的随机访问效率很低，因此不再支持
1.3排序
不再支持库里的sort排序，但是重载了一个无参成员函数sort()，默认排升序，可以通过传仿函数来排降序（仿函数本质是类模板，greater<int>就是有符号整形排降序的参数）
（注）
但是
我们最好不要随意使用sort()，他的效率实在太低（底层实际是归并排序），就算经过：把list的值拷贝给vector，在vector中调用库函数里的sort，排序完成之后再拷贝回list 这样一个过程，它的效率还是比直接调用sort()高
1.4unique去重
前提是排序完成，可以把相邻的，值相等的重复节点删去只留一个
1.5assign更新
可以把原来链表中的数据全部清除，把新的数据拷贝上去
1.6splice转接
它的作用更像一种剪切，原声明为
void splice (iterator position, list& x);
可以把x转接到pos位置之前，而x中数据清空
二、list的模拟实现
2.1本质
list的本质是一个带头双向循环链表
2.2尾插
按照双向链表的思路实现尾插，此时不需要区分原来list是否为空两种情况，因为实现过程都一样
2.2补：按需实例化
这是编译器一种保证效率的做法，即在运行程序过程中，当一个函数不被调用的时候，即使其中有一些错误也不会报错，因为函数因为不使用没有被实例化
2.3存节点用的类模板⭐
为了储存各种类型的数据以及前后指针，我们需要设计一个类模板
template<class T>
class ListNode
{
//......
ListNode<T>* _pPre;
ListNode<T>* _pNext;
T _val;
}来存储节点，因为在list中我没还需要频繁调用节点类的成员函数，所以我们不可以把他们设置为private，
结合来看，我们完全可以不写class，而用struct代替，这也是源码库中的做法。
2.4遍历
list中，我们的遍历不可以再用下标访问+[]了，因为不支持随机访问，
因此，我们只支持使用迭代器
2.5迭代器对应的类模板⭐
2.5.1出现原因
按照之前在vector中的做法，我们把ListNode<T>* 进行重命名为iterator，可是这时候问题来了：
链表节点之间的空间不再连续，iterator++的值与我们希望的完全不一样了，该怎么办呢？
为此，我们希望有一个方法可以即存储节点，又可以按照我们想要的方式进行++与--等操作，这时我们不妨将他们封装为一个类ListIterator。
此时我们只要在类中存储节点，重载++ -- *等符号即可
2.5.1补：
需求说明：
++是想要返回下一个节点，但是Node*进行++返回的是物理上的下一个节点
!=是想要看节点的地址是否相同，不重载只会去看迭代器类实例化的对象所在地址是否相同
*是想要得到节点中的值，Node*进行*只会返回节点对象
2.5.2封装：不同容器，相同的iterator
在写完迭代器类以后，回到list中我们有两种选择：
//①
ListIterator<int> it=it1.begin();
//②
list<int>::iterator it=it1.begin();很显然，
其一、我们在实现其他容器的时候知道对应的类模板不难，但是知道对应的迭代器类模板并不简单。
其二、因为迭代器类模板的特殊性，在实现的过程中我们常在容器得类里使用迭代器的成员变量，源码中把迭代器类设置为了struct，即成员共有，为了保护迭代器的成员变量不被篡改，封装为统一的iterator势在必行。
综上，在任何支持迭代器的容器中，我们全部在容器类中把迭代器类重命名为iterator，时刻体现着封装的思想。
2.5.3迭代器类模板中的成员变量
关于迭代器类模板中存储的成员变量类型，我们可以结合string的值访问方式来迁移理解：
string中我们存数组名_str，通过解引用可以直接访问到值
迭代器中我们存结点指针Node*，通过解引用可以访问节点，节点可以直接访问到值
2.5.4析构
因为存储成员变量属于节点类，所以无需显式实现，因为程序结束节点早已释放完毕
2.5.5拷贝构造，赋值重载
他们两个都不需要显式实现，也不能显示实现：
试想我们把一个迭代器赋值给另一个迭代器的场景，不就是为了让另一个迭代器也可以直接修改原来位置的值吗？一旦深拷贝了，其中的指针成员变量自然就不是指向原来位置了
2.5.6链表中数值的*后修改
为了保证*后可以修改数值，如*it=10;
我们把operator*的返回值设置为T&，以此达到目的
2.5.7一个特殊的重载符号->
它的返回值是T*
它的存在是为了让迭代器可以直接访问数据T
例：
假设数据T的类型是一个自定义类型，我们要修改其中的成员变量_r
我们有两个选择：
//①
(*it)->_r;
//②
it->_r;很明显第二种更加方便，其实第二种的本质是
it.operator->()->_r;但是为了程序的可读性，我们删去了一个->
2.5.7补：++begin()可以运行的原因
begin()返回的是临时对象，临时对象可以去调用非静态的成员函数：operator++
这里的临时对象具有常性（const），但是这里的const与我们直接定义
const int i=10;
中的const不一样，他们都不可以直接引用，但是自行定义的限制比临时对象返回的更大
如：
//这是不可以的
list<A> iterator& it=lt1.begin();
//这是可以的(特殊情况)
list<A> iterator it=++lt1.begin();
2.5.8const迭代器
const迭代器本意是自身可以修改，但是指向的内容不能修改，类似
const T* p;要实现它，我们需要单独再写一个类const_ListIterator,其中*和->的重载函数需要把返回值改为const修饰的类型，其他函数都不变，再在list类中重新命名其为const_iterator来与其他容器统一即可
2.5.8补：常规思维不可行的原因
起初处理这一问题我们想到的当然不会是重写一个类，而是直接加上const
typedef ListIterator<const T> const_iterator;但是把这种想法带入到实现中会发现，这样只会改变Node的类型，但不会改变list中的T，匹配下来会发生错乱
2.5.9const迭代器的简化方法
再实现一个类，大多函数还都是一样的实在有些冗余，那有没有方法更简便一些呢？
有的，因为只有*和->的返回值有改变，那我们完全可以把这种改变体现在模板参数当中，
即
template <class T,class Ref,class Ptr>而在list中重命名的时候直接
typedef ListIterator<T, T&, T*> iterator;
typedef ListIterator<T, const T&, const T&> const_iterator;就可以解决这一问题
2.6 list中的拷贝构造和赋值重载
在list不能只进行浅拷贝，否则会出现：
创建l1，
l2(l1)
在l1中插入一个数据
此时会导致l2中也插入一个数据，但这并不是我们想要的，因此我们需要通过循环尾插来进行深拷贝。
2.7clear清除数据与list的析构
clear目的是清楚当前所有数据，但是容器结构不变，也就是仍然保留头节点
而析构就是在clear完毕以后delete掉头节点，彻底释放空间
2.7补：范围for使用的习惯
在使用范围for的时候，如果不确定具体类型，为了避免效率的浪费，我们推荐
for(const auto& arr)
{//...}2.8赋值重载实现技巧
在书写赋值重载的时候，我们可以通过传值传参来获取一个list类型的拷贝，然后直接进行头节点互换，此时结束代码书写还有一个隐藏的作用：出作用域时该拷贝生命周期结束，自动进行销毁（析构）。
2.9关于std中的迭代器
我们的迭代器只存了一个节点指针，但是如果我们对std中的迭代器进行sizeof的话（64位），会意外的发现结果是12
其实之所以多出来4个字节的大小，是因为其中还有一个用作标记的成员变量，前文我们已经知道了在insert和erase以后会出现迭代器失效的问题，此标记就是为了区分迭代器是否失效
2.10模板构造函数：迭代器构造(数组首尾指针的兼容)
以往我们使用迭代器构造都会想当然的以为只能传begin和end的返回值过去，但实际上当我们传数组首位指针的时候，STL会自动构建一个迭代器，从头指针一直到尾指针的位置开始遍历数组元素，每遍历一个数组元素会把它尾插入list