list的模拟实现和学习

1. list的介绍及使用

说白了就是带头循环双向循环链表

stl 的两大组件就是容器和算法 ，他们两个之间是通过迭代器进行联系的

这三种算法函数

迭代器的种类 性质（容器底层结构决定）

单项：++             forward_list /哈希(unordered_xxx)

双向：++ / --        list/map/set

随机：++/--/+/-     vector  /string/deque

vector用算法里面的sort 排序效率很高，list不支持库里面的算法sort 但是list里面实现了sort函数，用的是归并排序，效率较低，list.sort唯一的优点就是方便数据量大的时候就不适用了

2. list的深度剖析及模拟实现

merge() 两链表直接归并（先排序）

unique()去重复的数据 ，也是先排序

remove（）== find + erase

splic 就是粘接，转移

这里list的迭代器用类封装了，要着重讲一下

带头双向循环，所以节点就用类（struct）封装起来，在list里面new 一个list_node 节点

struct里面构造函数可以  就去构造（new一个自定义类型就是调用拷贝构造）

这里就是用类去封装迭代器 （因为list 节点不连续）迭代器如果直接用Node*来表示，++后就不知道去了什么位置了，所以用类去封装的时候运用运算符重载，就可以经行让类里面_node 指向下一个节点

这样对于++  *   ==  这些运算符就可以按照我们的意思去进行设计

注意：iterator本质就是为了指向要访问的节点，所以类里面还是有Node* 指向节点 本质就是借用类更好的进行对节点指针的操作

对于一些地方加const修饰，比如！=  这是因为传值的时候 传的是lt.end() 这里临时变量具有常性

当然还有const 修饰的迭代器 

如何设计一个const修饰的迭代器呢？ 

目的是为了让iterator指向的内容是不能修改的，而iterator本身可以修改指向的节点

如：const T* ptr1   和  T* const ptr2

我们要的是第一种

因为iterator 和const_iterator 的区别就是一个返回值（*重载的返回值)不同，其实我们可以加一个模板参数，来控制这个返回值就可以了，不用再写一个const_iterator了

若为const迭代器 返回的是const T* 所以再加一个模板参数

这就是list 简单的主体部分

3. list与vector的对比

vector与list都是STL中非常重要的序列式容器，由于两个容器的底层结构不同，导致其特性以及应用场景不 同，其主要不同如下：

这个迭代器失效问题同样是用传iterator来处理迭代器失效

完整实现