list和vector都是容器，只不过他们的存储结构不同，vector实际底层结构是顺序表，支持随机访问。list的底层结构带头双向链表，不支持随机访问。
但list的底层实现不同，因为他是链表的缘故，所它的节点和迭代器必须在外在创建类来嵌套
vector的insert和erase函数都有迭代器失效的问题，而list的只有erase函数有迭代器失效的问题
_list_node
首先是一个用来创建节点的类
一个节点有他的前后指针，和他存储的值
此类还有进行初始话的操作
其次是创建迭代器的类
记住 vector的迭代器本质上可以认为是一个指针，而list的迭代器不同，它是以链表内的节点区分的。跟vector的区别很大
1.创建一个迭代器，必然要知道一个节点
2.因为迭代器分为const和非const的版本 但如果再创建一个数据大部分相同的，但只是加几个const的类，这对复用性非常差，所以我们根据源码来修改
主要思路，就是通过模版类型，和外面的名字不同，传过来的类型就不同。
比如 我用的是非const 那么Ref和Ptr就会传来非const的版本
如果我们用的是const 那么Ref和Ptr就会传来const的版本
3.要用的节点放到函数来赋给能让我们使用的节点
self本质就是为了方便，整个名太长，直接重命名为短的名。
这里记住解释
解引用的 本质将本体传过来，然后返回他里面存储的值，他的值时他的类型，并且需要修改，就是T& 而是不需要传另外的值的，所以是不需要参数的
->符合，本质是传出去它存储的值的地址。 也就是解引用传出来的值，在加上指针。而指针是用指针传出去，而它是模版类型 也就是T*
前置++符号重载，记住这里的++，–他们都是用来对迭代器的向前，后移动，而不是改变他们的值，所以他们的返回值 也是迭代器， 也就是self
后置++符合重载，本质就是返回不先++，而是返回它自己的值后，再++，但函数是不允许return后再进行操作的，所以可以创建一个临时的迭代器，用来存储现在的迭代器，然后返回临时的迭代器。（后置++不用引用的原因，是因为返回的是临时的迭代器，返回后，函数结束，这个临时迭代器的生命周期也结束了，如果你传的是引用，再对这个已经释放的临时迭代器进行操作时，会造成非法访问地址，所以后置++不用引用返回）而本体迭代器直接进行++即可
前置后置++ 都是用next向后移动到下一个节点
前置–和后置–的操作和前置++和后置–的解释是一样的，只不过一个向前一个向后的区别而已。
符号重载：只要这个符合它是对自己本身操作的，那么这个函数是不需要进行传参的！
！=符合重载，是本身与其他迭代器比较，所以传参的类型也是迭代器类型
传参的本质，是要看它传过来的到底是迭代器还是值还是他的节点！
操作很简单，就是对它的节点进行比较即可。
==符合重载也是一样，只不过操作内容相反而已
list本体
你要使用上面的两个类（节点，迭代器） 那么必须对他们重命名 即可使用 （本质上也可以不重命名，只不过名字很长，写起来会很麻烦）
begin和end的两个版本 const和非const版本。
记住，这是有哨兵位的，所以begin返回的是哨兵的下一个，而end是最后一个节点的下一个，也就是head
cbegin和cend是自创，非官方库内，这两个是直接使用const的版本，如果是const_begin它必须用函数传参，让它的节点为const才能使用const （不然编译器会默认稳非const版本）而我的是可以直接使用const版本的
list的无参构造函数
只需要把当前节点初始化即可（根据穿进来的节点初始化，不是头结点！！）
list的有参构造，用迭代器范围构造
用迭代器的构造，都是要用模版类型
empyt_into
用来初始化节点
swap
交换函数
拷贝构造
传统写法
初始化后，用范围for一个一个的节点拷贝到当前节点内
拷贝构造
现代写法
初始化
创建一个对象，也就是新的链表，去复用构造函数，构造出一个新的链表，然后让当前链表与临时对象交换头节点即可
=符号重载
现代写法
不用引用，直接交换他们的数据，并不改变外面的数据 就可以直接得到外面的数据，返回时，时返回这个节点 就是*this
list& operator=(list lv)
{
swap(lv);
return *this;
}
insert
在某个位置插入某个值
因为这是节点，不存在下标，所以是传迭代器
但这个insert是不存在迭代器失效的问题的
首先创建一个新节点，用来存储要传进来的数据
然后我们用一个新节点记录来存储这个迭代器的位置。
然后用这个节点找到它的前一个节点
接下来就是链接
这个函数为什么不会存在迭代器失效？
因为这个函数是用指针链接，其次他们是没有直接改变pos，pos只是给他们提供位置，内部数据时不会对pos改动的，所以pos不会失效，其次list的结构问题，要插入节点，是创建这个节点的新空间，也就是新地址，不想vector的扩容，是整个顺序表都搬到另一个新空间，所以pos是不存在失效的。本质就是pos并未改动
void insert(iterator pos, const T& val)
{
node* newcapacity = new node(val);
node* cur = pos._node;
node* prve = cur->prve;
//prve newcapacity pos
prve->next = newcapacity;
newcapacity->prve = prve;
newcapacity->next = cur;
cur->prve = newcapacity;
}
erase
它要删除某个位置，list的结构是链表，所以传的也是迭代器，不存在下标。
但pos不能删除end （end就是head哨兵位）
用一个节点接收这个迭代器的位置,然后利用这个号节点找到它的前后，链接
最后删除这个节点 这时候，这节点是被删除的，也就是pos指向的节点，被删除了，那么pos就指向的个随机值，那你下次++时，指向随机值的迭代器的它++，你能确定它++到哪吗？？所以这个迭代器就是失效了，而刚才我们已经有两个节点存储了刚才节点的前后的节点，那么我们的迭代器就更新为删除节点的下一个节点的位置即可，也就是erase删除后，自动++了。
就是返回的是迭代器，因为要对外面的迭代器更新，所以返回值是迭代器类型，但我们存储的是节点啊，所以这个节点要传到迭代器内初始化为迭代器类型，才能返回。
iterator erase(iterator pos)//返回的是迭代器 用于更新迭代器
{
assert(pos != end());
node* poos = pos._node;
node* prve = poos->prve;
node* cur = poos->next;
prve->next = cur;
cur->prve = prve;
delete poos;
return iterator(cur);
}
push_back
实际就是插入到最后的位置，就可以直接复用insert。最后的位置就是head的上一个位置就是最后的位置
void pop_back()
{
erase(head->prve);
}
push_front
在最开始的位置插入，迭代器就是begin的位置 复用insert即可
void push_front(const T& val)
{
insert(begin(), val);
}
pop_back
在最后的位置删除，复用erase即可
void pop_back()
{
erase(head->prve);
}
pop_front
在最前的位置删除，复用erase即可
void pop_front()
{
erase(begin());
}
clear
复用erase全部删除
因为erase删除后，会自动++ 所以不用再外部++
但没删除时，是需要我们手动++
~list
先复用clear删除全部数据
再删除他的头结点的数据并置空
测试代码
Original: https://www.cnblogs.com/LonelyMoNan/p/16650858.html
Author: lemon-Breeze
Title: list底层实现
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/606832/
转载文章受原作者版权保护。转载请注明原作者出处！