系列文章
http://t.csdnimg.cn/u80hL
定义
list作为一个容器，它有容器的模板参数和空间配置器；
功能
常数时间在任意位置插入元素
优点
插入非常高效
缺点
链表的遍历不支持下标访问（效率极低），链表只能使用迭代器来实现遍历（C++尽可能少用内部类）
在使用层面，对于链表类可以使用范围for来遍历，但底层是迭代器在起作用（特殊情况下，迭代器的底层就是范围for,具体使用那个取决于编译器的选择）
在实践上，list可以支持[ ]查询，但效率太低因此标准库里没有支持。
函数
经过一段时间的学习我们可以发现各个函数的实现有着功能上的继承关系，及一个函数是另一个函数实现的前提，灵活继承函数的功能我们可以使用较低的代码量就实现较多的功能，接下来我们实现list类将会按照继承的顺序给出函数，因此函数顺序会略显混乱；
成员函数
链表只有front、back允许访问头和尾，没有访问中间节点的运算符重载
insert: 在pos位置插入value（头部和中间插入效率很高）
步骤：
- insert函数我们通过参数生成一个新的链表节点；
- 再将这个节点接入原链表；
- size++；
- 最后返回指向插入的节点的迭代器。
list迭代器在insert之后不会有扩容操作，因此它的迭代器不会失效，即list不会有迭代器失效问题
iterator insert(iterator pos, const T& val) //用含参构造建立一个新节点，这个节点带有val值，它的前后节点与原链表有机结合
{
//我们生成一个以val为参数的节点
PNode newnode = new Node(val); //该节点本身有未定义的前_pPre(nullptr),后 ，我们现在要在下面找到它要被接在哪里
// 利用pos迭代器找到我们要找的节点，通过这个节点得到该插入的位置的_pPre，_pNext
PNode cur = pos._node; // 这里我们不用对pos位置的节点数据本身做任何操作，我们要更改它的链表性信息，以它为媒介获取我们要插入的pos位置的前面和后面的节点的链表关系
PNode pre = cur->_pPre;
//接下来我们把新节点接上去
//拼接方法很简单，把头尾位置重置一下即可
pre->_pNext = newnode;
cur->_pPre = newnode; //
newnode->_pPre = pre;
newnode->_pNext = cur;
++_size;
return iterator(newnode);
}
push_back()\bush_front():都使用insert（）完成功能。
erase:删除指定位置的节点，返回被删除的节点的下一个位置
删除pos位置的单个节点（删除效率高）
步骤：
- 首先记忆将要被删节点和它的前后节点；
- 删除被删节点的数据（不用管表示前后节点的变量，那是未实例化的变量，不占用空间）；
- 将记忆的前后节点相连；
- size–;
- 返回指向被删节点的下一个节点的迭代器。
erase之后迭代器会失效，因为节点被删除.
// 删除pos位置的节点，返回该节点的下一个位置
iterator erase(iterator pos)
{
//定位并记忆该节点的各个信息
PNode _val = pos._node;
PNode pPrev = _val->_pPre;
PNode pNext = _val->_pNext;
//根据以上信息去修改pos位置的节点
delete _val; //核心目标：删除pos位置的节点数据，在此完成
//接下来更新节点的链接关系
pPrev->_pNext = pNext;
pNext->_pPre = pPrev;
--_size; //大小更新
return iterator(pNext); //返回下一节点的位置
}
pop_front()\pop_back()都使用erase（）完成功能，
swap：交换两个链表的内容
这里取巧了，我们不交换链表内容，我们直接交换链表的头节点地址；
void swap(list<T>& l) //交换头节点与大小
{
std::swap(_pHead, l._pHead);
std::swap(_size, l._size);
}
clear：清除链表数据
凭借指向链表起点的迭代器，将链表数的所有节点清楚掉，只留下头节点；
void clear() //清理数据,要深度清理,需要erase（）
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
}
sort：排序
list的sort（）函数底层是自身独有的，不同于算法库的sort，它的迭代器是双向迭代器，无法与其他的容器模板兼容；sort()函数排序默认为升序;
list_name.sort(); //sort函数使用方法
想要改变为降序，则：
greater<data_type> gt;
list_name.sort(gt);
或者一步到位：
list_name.sort(greater<data_type> ()); //匿名对象
排序效率
list/vector（release）:数据量大时list的排序效率远远大于vector（指数级强大），数据量小则相反。
其他函数
merge：归并，两个链表归并到一起，小的接到大的后面，要求被归并的链表必须有序
assign:拷贝
list2_name.assign(list1_name.begin(),list1_name.end());//将list1拷贝至list2
unique：去重
list_name.unique();
remove:删除,删去一个值为data的节点
list_name.remove(data);
splice:转移，以极高的自由度将一个链表的一部分转移到另一个链表的任意位置（翻译为粘贴，粘接）
例如：
list1:1,2,3,4
list2:10,20,30
eg1.转移全部
iterator1=++list_name1.begin();
list1_name.splice(literator1,list2_name); //将list2转移至list1的尾部
list2_name此时为空。
result:
list1:1,10,20,30,2,3,4
list2(empty)
eg2.转移一个值
list1_name.splice(iterator，list2_name,++list2_name.begin());
result:
list1:1,20,2,3,4
list2:10,30
eg3.转移一个区间
list1_name.splice(iterator，list2_name,list2_name.begin(),list2_name.end());
result:
list1:1,20,30,2,3,4
list2:10
流插入
对于一些自定义类型我们不编写它自己的流插入，我们使用公共的流插入配合解引用即可，防止写死;
重载—>
由于C++全新的命名格式，导致—>在使用过程中不优化就会非常怪异：
- 正式写法：iterator.operator—>()—>data_name;
- 简化写法：iterator—>—>data_name;
第一个箭头返回对象地址，第二个返回元素地址。
由于正式写法太丑，C++的众多编译器都为其做了特殊处理，只需一个箭头即可调用元素：iterator—>data_name;
empty_init( ): 初始化节点
void empty_init() //节点初始化
{
_pHead = new Node;
_pHead->_pPre = _pHead; //空节点头节点的前后节点都指向自己
_pHead->_pNext = _pHead;
_size = 0;
}
默认构造
无参构造:list（）
list() //空链表的构造函数，其作用大多是声明链表的存在和调用列表函数
{
empty_init(); //初始化空节点
}
n个value初始化构造
list(int n, const T& value = T()) //新建一个链表，初始化后里面有n个value值节点
{
empty_init();
for (int i = 0; i < n; i++)
{
push_back(value);
}
}
拷贝构造：list（const list& lt）
逐个节点拷贝（深拷贝）——使用push_back()遍历一遍
如果我们不写拷贝构造，默认给出的构造会浅拷贝，然后一个节点释放两次报错，拷贝要用const迭代器。
//含参的构造
list(const list<T>& l) //以一个链表为参考，拷贝其内容到一个新链表
{
empty_init();
for (auto e : l)
{
push_back(e);
}
}
赋值运算符重载：operator=
list<T>& operator=( list<T> l) //将一个链表的值赋给另一个链表
{
//这里传值l时就已经生成了一个可供调换头节点的链表了
swap(l);
return *this;
}
析构：~list（）
~list() //出现问题，编译错误，delete对val实行几次后val的地址就变成乱序，开始报错
{
//cout << endl << "~list()" << endl;
clear();
delete _pHead;
_pHead = nullptr;
}
逐个节点释放
知识点
list核心接口：双向迭代器Bidirectional
确认一个容器的节点是不是带头双向循环的方法：看初始化——决定初始结构，结构会显示方向个头的数量；（使用速览定义）
迭代器的底层
迭代器的底层是范围for，编译器会默认使用迭代器处理问题；
不同的迭代器代表且只代表某种访问规律，其本身没有内存实体；
迭代器模拟指针的行为。
debug/release的差异
debug：优化没有全开，递归和循环要很大资源
release：递归和循环影响较小
迭代器的分类
功能上分类
- const:正向和反向;
- 非const:正向和反向;
迭代器iterator性质上分类（与容器的底层实现有关系）
- 单向（++）：单链表/哈希表
- 双向（++/–）：双向链表/红黑树（map/set）
- 随机（++/–/+/-）:vector/string/deque
迭代器应用点
迭代器提现了封装理念的优越性，封装屏蔽了底层差异和实现的细节，提供了统一的访问修改遍历方式,vector、list、string我们不去关注其中的底层细节，他们的使用方法统一，而底层的实现细节天差地别.
vector使用随机迭代器，它可以使用底层为双向迭代器的函数（类似于权限缩小，随机即可以视为一种特殊的双向，也可以视为一种特殊的单向）
迭代器的底层是范围for
对于list而言，const有两种形式：
- 非const形式——iterator，T*，可读可写，权限齐全；
- const形式——const_iterator，const T* ，只读，权限只能不变与缩小；
这两种迭代器是以两种类的形式实现的，它们彼此之间没有任何联系，只是概念上相对不同；
迭代器修改数据都是解引用行为。
在日常使用中，如果在使用迭代器之前编写了const iterator组织迭代器本身修改，会锁死迭代器，使其失效。
const 顺序与修饰
- const T*——const修饰指向内容；
- T* const——const修饰了指针本身；
![[数据结构与算法]-(第0期)-什么是二叉树？](https://img-blog.csdnimg.cn/direct/3e3064cbc87e4a3a9902f844d133c883.jpeg#pic_center)
