C++之list模拟实现

一.介绍list

同vector一样都是容器，list底层：双向循环链表，由前驱指针、后继指针和数据组成，与vector不同于不是连续内存，vector是连续数组。

优点：任意位置插入，删除元素时间复杂度为O（1），erase删除时，仅仅被删除的节点迭代器失效，其余迭代器依旧有效

缺点：不支持下标访问，遍历效率低

二.list实现

1.list构造函数

2.list iterator

此处begin和end为正向迭代器（反向还莫有学），可进行++操作，迭代器向后移。

swap交换：先给自己一个头指针，再把需要交换的头指针给 给创建好的头指针，再把临时对象tmp的新头指针给原来的，完成交换。

为什么会有list类和list iterator类：

list容器管整块链表数据，迭代器iterator专门管单个节点的访问、遍历，分工完全不一样，必须拆成两个类；

后者掌管：

1. 重载 * 解引用： *it 取出节点里存储的数据T

2. 重载 ++ 前置/后置自增： it++ 跳到下一个节点 _pNode = _pNode->_pNext

3. 重载 -- 自减：往前遍历上一个节点

4. 重载 == != ：判断两个迭代器是否指向同一个节点

为什么要重载++，--：相较于vector，它空间是连续的，

1. vector迭代器本质就是封装的原生T*指针
vector内存连续，原生指针天然支持 ++ 、 -- 、 +n 、 [] 随机偏移：指针自增直接跳到下一个相邻元素。
所以不用手动重载 operator++ 、 operator-- ，直接复用原生指针自带的运算规则即可。

2. list不能用裸指针做迭代器，必须手动重载所有运算符
list节点零散分布在堆上，前后节点内存地址并不挨着。
单纯对节点Node*做 ++ ，只会走到这块内存后面随机地址，找不到下一个链表节点。
只能手动写重载

一、为啥三个模板参数
1. T ：链表存的数据类型

2. Ref （引用）、 Ptr （指针）：用来一套代码做出两种迭代器

- 普通迭代器： Ref=T&、Ptr=T* ，能读写数据

- const迭代器： Ref=const T&、Ptr=const T* ，只能读不能改
不用写两份重复代码，省事。

3. Self ：给自己这个迭代器类起短别名，少写长名字。

二、各个函数为啥对应不同类型
1. Ref operator*() ：解引用取值，用Ref控制能不能修改元素

2. Ptr operator->() ：箭头访问成员，用Ptr控制读写权限

3. 拷贝构造、++运算符用 Self ：指代迭代器本身类型，书写简单，方便链式运

总代码：