1.list的使用

1.1构造

1.2迭代器遍历

（1）迭代器是算法和容器链接起来的桥梁

容器就是链表，顺序表等数据结构，他们有各自的特点，所以底层结构是不同的。在不用迭代器的前提下，如果我们的算法要作用在容器上面，不可避免的需要获取底层结构，这不仅会增加耦合度，而且也不利于算法库的实现。所以我们创建一个迭代器，将底层结构的访问方式封装成迭代器，直接利用迭代器去访问容器。

有两个好处，

其一，我们不用根据各种各样的容器去一直创造新的算法兼容，保证了算法库的可维护性

其二，我们的访问更加简单了，都用迭代器访问，不需要对各种容器的底层有很多了解

1.3首尾元素访问

1.4插入数据

第一行表示在it迭代器的位置插入一个2

第二行表示在it位置插入三个1

第三行创建了有两个元素值为10的链表，然后第四行把test从头到尾的节点值都插入到了it位置

1.5删除数据

还有一个删除函数：remove

他会删除所有指定值的元素

这里我们删除10这个值之前second里面有两个10

我们进行remove（10）后，list里面的10都被删除了。

1.6交换链表

1.7清除所有有效数据

1.8排序

list自带的排序效率很低

甚至我们先把数据拷贝给vector，用vector排完序之后再给回list，此时我们list自己排序花的时间比拷贝到vector排完序再拷贝回来还要慢。

1.9splice（剪贴）

splice的作用是把list中某一段迭代器区间的内容移动到pos迭代器的位置的前面，就像剪切一样

一共有三种用法

第一种：把整个list剪切到pos迭代器位置

这里我们看到一开始second是有四个节点，经过整个second的剪切， second变成空链表，而first则具有了second的四个节点

第二种：把list的it位置节点剪切到pos迭代器位置

这里我们看到，成功的把second的第一个节点剪切到了first上

第三种：把list中一段迭代器区间的内容剪切到pos迭代器位置

这里我们把second的后面三个节点都剪切到了first中

2.list的模拟实现

2.1节点

2.1.1结构

由于我们实现的是双向带头循环链表，所以我们节点中需要存有前一个和下一个节点的地址，以及最基本的节点的值。

注意：因为我们实现的是模板的链表节点，所以才要写成list_node<T>.

疑问：我们不是不希望暴露底层结构吗？为什么这里用struct？

首先，我们后面的list需要频繁使用到节点内的指针等

其次，因为每个编译器内部实现的时候命名没有统一，所以我们就算想访问也是很难的

2.1.2构造函数

这里我们使用匿名对象来给到缺省值，对于自定义类型和内置类型都可以有效

内置类型：

自定义类型：

自定义类型会调用对应的构造函数

2.2迭代器

2.2.1结构

这里的迭代器底层是指向链表节点的指针，但是迭代器的类型实际上是一个自定义类型

让自定义类型充当迭代器的原因：对于链式结构，内置类型指针无法实现++移动到下一个元素的迭代器位置，所以我们需要把它封装成自定义类型，通过运算符重载实现++移动到下一个元素迭代器位置。

简单来说，原生指针指向地址的功能没问题，但是移动到下一个元素的内置元素运算符逻辑无法满足链式结构的遍历，所以需要我们把迭代器类型设置为自定义类型，通过自定义类型的运算符重载实现链式遍历。

2.2.2构造函数

因为结构中只有一个指向链表节点的指针，所以这里我们只要用node初始化即可

2.2.3运算符重载

（1）解引用

1.非const迭代器版本

解引用就是为了访问节点的值，所以我们直接返回m_date

2.const迭代器版本

const T& operator*()
{
  return node->m_date;
}

这里返回的是const就保证了指向的内容不可改变,注意我们不可以在函数后面加const，如果那样加就表示迭代器本身不可改变了

（2）++与--

++是为了我们可以访问到下一个节点的位置，而下一个节点的位置我们可以通过

node->next访问，把node更新一下就行

（3）！=

判断迭代器指向的位置是否相等只要判断他们的node就行

（4）==

（5）->

当我们的数据类型是自定义类型的时候，我们有两种方法访问该自定义类型内的值

第一种：解引用然后用.访问

第二种：->再用->访问（场景比较固定）

比如说我们的list中存的是A类型对象，那么我们要访问到a1就需要先访问节点中的m_date（A类型数据），然后再访问a1或a2.

（1）非const版本

我们返回的是A类型的指针，然后再->访问a1或者a2。

为了保证可读性，我们不会用两个->去表示，而是直接缩略成一个->

（2）const版本

2.2.4const与非const迭代器合并

我们首先要添加两个模板参数，Ref和Ptr。

Ref表示引用（&），Ptr表示指针（*）

因为const和非const只有两个方法存在区别，所以我们把这两个方法的返回值设置为模板参数

然后我们在list中typedef即可

2.3链表

2.3.1结构

因为我们是双向链表，所以只需要知道头结点地址即可

2.3.2构造函数与析构函数

构造函数

我们的目标是构建一个节点，且该节点自成循环

拷贝构造

为了方便调用构造函数空初始化的功能，我们单独写一个empty_init方法，并调用他来为l2初始化

我们先给l2创建一个头结点初始化，然后复用push_back插入数据即可

析构函数

我们首先要写一个方法用来删除链表的所有有效节点，然后再释放list的哨兵节点

2.3.3尾插

第一步：根据传的值创建节点

第二步：调整节点指向

2.3.4 begin与end

因为头结点是不存储有效数据的，所以begin是head的下一个节点

而end是最后一个有效节点的下一个节点，所以是m_head

这个就是const版本的begin和end

2.3.5insert

第一步：记录前一个节点和下一个节点，并创建出cur节点

第二步：修改指向关系

注意：这里不存在扩容，所以也就没有迭代器失效的问题，我们的it仍然是有效的

2.3.6erase 

注意：

（1）it迭代器会失效，因为这个位置节点被删除了，空间也释放了

（2）为了方便后续的使用，我们需要返回删除后顶替上原本节点的迭代器

2.3.7赋值重载

因为传参的时候就调用了一次拷贝构造，所以l1就是被拷贝链表的深拷贝，把l1和*this交换后，调用赋值符号的对象就相当于完成了深拷贝。且由于l1是临时变量，所以他会调用析构函数释放掉，而调用赋值的对象则不会。

2.3.8改进结构

因为我们对容器的操作经常涉及size的获取，所以我们要写一个size方法。

但是对于链表这个结构，要获取size还要我们遍历一次链表，效率太低下了。于是我们可以在list的结构中加上m_size，并在构造函数和insert，erase这种设计节点数变化的方法中更新size的值。