前言：(这里相对于string、vector，相对复杂，讲解较多）

1与string、vector相比：

1.1没有重载运算符[]接口： 前面两个重载两运算符[]是因为它们的底层结构式数组或者是数组类似的结构，访问较快，而list如果重载效率就不行，所以list使用迭代器。 1.2没有reserve(扩容)接口： 因为前面两个扩容插入数据可能一次插入多个，而list每次只能插入一个数据。 1.3list增加的接口： 1.3.1reserve() 接口：用于逆置。 1.3.2merge()接口：归并（要是两个有序带头双向链表）。 1.3.3unique()接口：去重（要是个有序带头双向链表,不然达不到去重效果)。 1.3.4remove()接口：删除这个与rease接口不同，erase接口是删除迭代器指向的位置，而remove()是删除与给定值相同的数据。 1.3.5remove_if()接口：顾名思义效果与remove()接口相同，只是这个是配合仿函数使用满足对应条件就删除。 1.3.6splie()接口：接合，实现两个list对象的接合,注意是将一个list中的数据移动到另一个list中,一个数据增加，一个减少数据。对于参数只有一个list对象，是调整这个对象的数据之间的左右关系。如果有两个list对象就是将一个list中的数据移动到另一个list中。 1.3.7sqrt()接口：排序(底层使用归并排序),所以效率不高，这个并不常用。 （1）为啥算法库中有不像vector一样直接使用算法库中的，而是直接实现一个接口。因为算法库中的sqrt使用了迭代器相减，而list的迭代器不支持迭代器相减的操作。 （2）效率问题：与vector调用算法库中的sqrt进行比较，【注意要在relices版本下进行比较，因为deBug版本下增加了调试的各种信息等原因，并不正确）,从比较来看数据少还好，数据一多就不行，甚至使用vector调用算法库中的sqrt进行排序，再将数据复制到list中时间都比list使用自己的sqrt快，所以数据少可用，数据大尽量不用。 1.4迭代器的不同： 迭代器的核心功能是（*）解引用可以得到指向位置的数据，++可以向前挪动，vector,string都是用原声指针作为迭代器，因为它们的底层结构是数组使用原声指针作为迭代器就可以满足得到迭代器的核心功能，而list如果将原声指针作为迭代器，由于list底层的每个结点不像前面两一样是数组直接是连续的(有联系），此时就满足不了迭代器的核心功能，所以list要对迭代器进行包装，进行运算符重载来满足迭代器的核心功能。是否能使用原声指针作为迭代器，还是要自己包装迭代器实现，是要看是否能满足迭代器的核心功能。

一、list底层带头双向链表验证，节点构造

1.1节点的构造：

节点和数据结构中双向链表的节点一样，有三个变量：节点数据，下一个节点(next)，上一个节点(prev）

小问题：

注意起名尽量和库中名字一样，后续如果在其他类中使用时在typedef。 2这里使用struct进行包装而未使用class进行包装，原因在于C++将struct升级成和类功能相似，只是其中的成员访问权限全部时公有。如果使用class进行包装，要访问取私用成员时要使用友元，过于繁琐。后续如果在一个类中调整其访问权限可以使用typedef在使用访问限定符修饰即可(typedef受访问限定符的限定)

1.2list底层数据结构(带头双向链表)

这里我们通过SGI库中list的成员变量和构造函数来验证，取底层数据结构是带头双向链表。

结合库中list的成员变量和构造函数以及节点的构造，我们不难发现list的实现中只有node一个成员变量。构造函数构造出一个头尾相连的节点(所谓的哨兵位）。同时也验证了list底层时应该带头(哨兵位)双向链表.

二 迭代器总结

本博客采用SGI版本，C++：list增删查改的模拟实现使用的是带头双向链表，非常简单，只是这里对于迭代器的实现不像原来一样使用原声指针，实现较难。对于模板的使用更加丰富,对于初学者确实较难。

2.1迭代器的分类（支持的操作/性质)

2.2迭代器的实现：

对于使用原声指针作为迭代器的直接定义就行，而对于不能将原声指针作为迭代器的就要对迭代器进行包装，这里可以使用class类、还有C++将struct结构体升级为与类相识的只是struct中的是公有。由于使用连要访问其中的成员要么将其设为公有、提供gte函数、将其声明为友元函数，这些情况都不好。这里可以利用struct的特性都是公用，所以我们一般用struct来包装迭代器，那用人问都是公有别人可以访问不会出问题吗？这里对于迭代器的底层实现都不知道，不同平台的实现方式也不同，别人不可能直接访问。

三 迭代器封装实现(是一个重点，涉及到多个模板参数的使用，和由于迭代器的封装普通迭代器和const迭代器怎么实现）

3.1前置说明：说明写的怎么实现list的迭代器，使用struct进行包装在对其使用的运算符进行重载。

3.2迭代器的实现

这里普通迭代器和const迭代器基本一样，只是对于(*)解引用操作得到和（->）操作得到的返回值不同怎么解决呢？方法一：对两种迭代器分别进行封装(不好代码冗余，可读性很差）。方法而：使用多个模板参数，对于不同返回值分别使用一个模板参数【两种从效率上没有差别，只是代码可读性不同】

注意迭代器的实现不用写析构函数，如果使用析构函数不就会打乱节点之间的指向关系，迭代器只是借助这个节点指针进行访问修改，而不是销毁，销毁是由list管。

四 list及取接口的实现

4.1基本框架

list模拟我们和库一样，给一个头节点，还可以加一个统计节点个数的变量_size（方便我们后续得到节点个数，其实可以不定义这个变量，可以通过遍历计算节点个数，为了方便这里还是定义这个变量)。由于接口都是通过迭代器进行访问，所以我们对两个迭代器进行重命名，一方面为了统一接口（string、vector等接口都一样),另一方面屏蔽底层的变量和成员函数的属性。