前言：(这里相对于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增删查改的模拟实现使用的是带头双向链表，非常简单，只是这里对于迭代器的实现不像原来一样使用原声指针，实现较难。对于模板的使用更加丰富,对于初学者确实较难。