一、list源码分析
1.分析构造函数
list的分析与vector的分析思路是一样的，我们一开始最先看到的就是这个结点的结构体，在这里我们可以注意到这是一个双向链表。有一个前驱指针，一个后继指针。然后在有一个存储数据的空间
其次我们还会注意到，它的迭代器是一个自定义类型，而非原生指针。这与vector是不同的，至于迭代器为什么要这么设计，我们暂时还看不懂，那么我们就往下继续看，先把大结构给研究出来
那么我们继续找成员变量，在这里我们就找到了成员变量，但是这个类型我们很明显看不懂，于是我们速览定义去查看
可以看到这个实际上还是一个指针。但是这个指针我们还是看不懂，于是我们继续去速览定义，于是就找到了这里
这里我们可以注意到这个结点的类型其实就是一个类模板，这个模板正好就是我们一开始就看到的用结构体定义的一个结点。于是我们就清楚了，这个成员变量实际就是一个指针，这个指针指向一个结点。这样一想象，就有点类似于我们在c语言使用链表时候的头节点了。
那么接下来，我们应该分析一下构造函数是什么样子的。
不难注意到，就在成员变量的下方，正好就是一个无参的构造函数。也就是默认构造函数
但是在这里它又封装了一层函数，于是乎我们继续深入查看
如下所示，我们看到了具体的函数内容，从名字上来看，get_node 不出意外就是开空间的。也就是得到一个结点，然后返回这个结点指针。这样一来，我们的成员变量就获取的实际的一个结点，然后让它的next和prev都指向自己，这样一来这个结点形成一个自循环。现在就能看出来这是一个带头双向循环链表了
那么这个得到结点的函数内部究竟是什么，我们还可以继续深入查看一下
如上图所示，这里的allocated设计到空间配置器。这里我们就先不做了解了。后序在详细介绍
我们不妨顺着这个思路往下继续理解，下面刚好有一个put_node，这个函数其实就是释放结点的。
在后面还有这样一个函数，这个函数是creat_node不难理解，这个就是获取一个结点，先给这个结点开空间，然后调用构造函数。等一系列操作。
既然这里涉及到一个构造，那么我们继续深入，看看这个构造里面是什么东西？这里其实我们还是有点懵的，这里其实就涉及到了C++11的内容了，我们就先不管它了，我们只需要这道能new出来空间就行了
2.分析尾插等
好了，构造函数分析完了，那么我们继续分析一下push_back系列的插入函数
我们不难注意到，这里的push_front和push_back都是复用了insert接口，那么我们就直接去分析一下insert接口吧
我们可以分析出来，它调用的是这个函数
在这里我们也是不难理解的，先创造一个结点，然后进行连接。现在我们也基本读懂了这个大体的框架了
这里还需要注意的是：由于一开始的结点里面的指针都是空指针，导致后面需要经历很多的强制类型转化。其实这里大可不必，我们如果一开始就定义好指针的类型自然是最好的。
二、手把手教你写一个list
1.结点声明
如下所示，是我们的结点的定义，对于这里的定义，我们可能刚看到的时候会比较陌生感，又有一丝熟悉感，这是正常的。多写写就熟悉了。我们现在来深入了解一下这个结点是如何进行声明的，我们这里和c语言的链表采用同样的方法，使用一个结构体，但是这里的结构体已经非比结构体了。因为C++对结构体进行了升级，这里应该是一个类，使用struct的话会是类成员变量默认为公有的成员变量，方便类外的变量可以随时访问。
其次，C++中对结点进行定义的时候可以只写类名，这与class是一样的。注意不要忘记带上模板参数T，因为我们写的结点也只是一个模板。因为类名不是类型，他实例化以后可以有各种各样的结点类型。
template<class T> struct list_node { list_node<T>* _next; list_node<T>* _prev; T _val; };
2.list类的成员变量
由于我们的结点是一个模板，对于它而言，它的类型就比较繁琐，我们可以在list类里面使用typedef进行一次重命名。然后再私有里面再定义一个指针，这个指针就是一个结点指针。
template<class T> class list { typedef list_node<T> Node; public: private: Node* _head; };
3.list类的默认构造函数
如下所示，我们定义好了成员变量以后，我们就写一个默认构造函数，当我们对这个链表类进行实例化的时候，自动调用这个默认构造函数，这个默认构造函数会为成员变量的头节点指针分配实际的空间，在new Node空间的时候，会调用它Node（即list_node<T>）类的默认构造函数函数。从而成功的开辟好这块空间。
list() { _head = new Node; _head->_next = _head; _head->_prev = _head; }
4.list类的尾插
如下所示，我们的尾插逻辑也是比较简单的，先利用我们传过来的val去开辟一个新的结点，注意这里开辟新结点的时候使用new的话可以直接带一个括号去调用它的构造函数
void push_back(const T& val) { Node* newnode = new Node(val); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; }
5.结点的默认构造函数
有了上面的分析之后，我们现在缺的就是一个结点的默认构造函数，我们直接给一个缺省值，使用T()就是一个匿名对象来初始化，对于内置类型也是同样适用的。然后我们使用初始化列表即可。
list_node(const T& val = T()) :_next(nullptr) ,_prev(nullptr) ,_val(val) {}
6.list类的迭代器
首先我们思考一下，可否像vector一样直接在类里面typedef 一个迭代器？
答案是显然不可以的，这样大错特错。vector可以这样使用的原因是数组天生就是一个迭代器。解引用后就能找到对应的值。
而对于list，首先它就是不连续的，指针加1后，地址早已不知道跑到哪个结点去了。其次这里仅仅只是结点的指针，解引用后，找到的仅仅只是结点，我们还需要进一步解引用才能找到对应的真正的值。
总之直接typedef的话，会使得迭代器的++和解引用操作均失效了，这时候我们只能使用运算符重载了。才能解决这个问题。既然要运算符重载，这里我们最好再次封装一个类出来。因为如果不封装一个类出来的话，我们无法完成此处的运算符重载。
如下所示，是我们实现的iterator的类
template<class T> struct __list_iterator { typedef list_node<T> Node; Node* _node; __list_iterator(Node* node) :_node(node) {} T& operator*() { return _node->_val; } __list_iterator<T>& operator++() { _node = _node->_next; return *this; } bool operator!=(const __list_iterator<T>& it) { return _node != it._node; } };
这个类我们使用了一个结构体去封装，在这个结构体中，我们只有一个成员变量，这个成员变量是结点类的指针，用于指向某一个结点， 在我们一开始定义出迭代器的时候，我们需要先写一个构造函数，用于迭代器的初始化。即需要传一个参数node来控制。
与之对应的，我们在list中就需要写出对应的begin和end函数，来返回迭代器。
typedef __list_iterator<T> iterator; iterator begin() { //return _head->_next //单参数的构造函数支持隐式类型转换 return iterator(_head->_next); } iterator end() { return iterator(_head); }
在这里的迭代器中，首先返回值肯定是iterator，根据我们前面iterator函数的构造函数，我们可以利用匿名对象去构造一个迭代器对象。这里我们正好传一个参数，这个参数根据我们函数的特性去传递，在list类中，它的成员变量就是一个结点类指针，我们可以直接传递该节点的下一个指针，用这个指针刚好就能构造出这个迭代器类型。
现在我们已经获得了这个迭代器，这个迭代器本质就是一个类，而不是指针。由于结点是无法直接正常解引用的，那么我们就需要去在迭代器类中去重载一个*运算符，让他看上去就像一个指针一样，试想一下，我们解引用出来的结果应该是什么呢？其实就是该迭代器类型里面这个唯一的公有成员变量_node所指向的结点中的_val，这个_val就是我们所需要返回的值。这个值的类型是T，由于解引用后我们还可以去修改这个结点里面的值，所以我们还需要传引用返回
除此之外，我们还需要一个++运算符重载，在这个运算符重载中，我们也很明确，我们需要返回的类型就是迭代器类型。那么我们是如何进行++的呢？，因为我们的成员变量就是指向一个结点的指针，所以我们直接让这个结点的指针去往后移动一次即可。由于是前置++，所以我们先移动，在返回*this，因为*this就是我们的该迭代器。这里我们注意，我们可以传引用返回，也可以传值返回。因为无非就是多了一个类。如果传引用返回，另外一个类改变的时候，这个it所指向的内容也将改变。如果传值返回就不会了。
为了方便我们测试，我们还需要再写一个！=的运算符重载，这个运算符重载我们在上面也给出来了，就是简单的进行比较即可。
我们使用如下代码进行测试（这里的测试代码与list在同一个命名空间，所以不需要域作用限定符）
void test1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; }
总而言之，list的迭代器确实比较抽象一些，这里存在三个类之间的各种纠缠。所以导致比较抽象，但是认真分析之后，还是比较容易读懂的。
那么我们再来思考一下，这里是否需要拷贝构造呢？事实上，这里我们可以不需要写拷贝构造函数，因为库里面会默认生成一个浅拷贝，而我们这里也就需要一个浅拷贝。不需要深拷贝。所以我们不需要写。
那么我们在思考一下，我们这里有很多个迭代器，迭代器里面的指针指向同一块空间，那么这里是否会产生崩溃呢？其实是不会的，因为我们就没写析构函数。那么为什么不写析构呢？其实这是因为这个结点就不是我这个迭代器去生成的，迭代器只是拿走了这个结点的地址罢了。要析构也轮不到迭代器去析构，应该让list去析构。迭代器只是借助这个结点去访问容器。迭代器只是为了访问，而不是去管理容器。
我们这里先将迭代器的基本操作写的稍微完善一些
template<class T> struct __list_iterator { typedef list_node<T> Node; Node* _node; __list_iterator(Node* node) :_node(node) {} T& operator*() { return _node->_val; } __list_iterator<T>& operator++() { _node = _node->_next; return *this; } __list_iterator<T> operator++(int) { __list_iterator<T> tmp(*this); _node = _node->_next; return tmp; } bool operator!=(const __list_iterator<T>& it) { return _node != it._node; } bool operator==(const __list_iterator<T>& it) { return _node == it._node; } };
7.设计const迭代器
我们先来看看下面这种设计方法是否可行？
先说结论：不行，为什么不行呢？这是因为const迭代器要求的是迭代器指向的内容不可以被修改，迭代器本身可以被修改。而这里呢？我们的对迭代器类型加上了const，我们的迭代器本身就是一个类，对一个类加上一个const，这是让这个类对象无法被修改啊。里面的成员变量都不可以被修改，而我们迭代器对象里面的指针指向的才是结点指针。我们这样一来，这个迭代器里面的指针无法移动了。也就意味着不满足我们的迭代器本身可以被修改的性质了。它就无法调用前置++，后置++了。
那么我们到底该如何控制指向的数据不可被修改呢？
答案就是在这里加上const
这样一来返回的就是const引用，自然就无法进行修改内容了。
这样一来，我们就有了一种实现const迭代器的想法了。我们可以拷贝一份原来的迭代器，然后改变一下类名和解引用这个成员函数的返回值即可
template<class T> struct __list_const_iterator { typedef list_node<T> Node; Node* _node; __list_const_iterator(Node* node) :_node(node) {} const T& operator*() { return _node->_val; } __list_const_iterator<T>& operator++() { _node = _node->_next; return *this; } __list_const_iterator<T> operator++(int) { __list_const_iterator<T> tmp(*this); _node = _node->_next; return tmp; } bool operator!=(const __list_const_iterator<T>& it) { return _node != it._node; } bool operator==(const __list_const_iterator<T>& it) { return _node == it._node; } };
即如上代码所示，但是这样设计太过于冗余了。不过这个也是可以正常运行的，我们先补两个接口
const_iterator begin() const { //return _head->_next //单参数的构造函数支持隐式类型转换 return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); }
如上所示代码中，要特别注意的是我们访问这两个接口时候使用的是list类，并且是const的对象，那么一定要加上const，否则就是权限放大了。
我们来测试一下const迭代器，我们只需要在上面的测试用例中补上一个Print接口即可
void Print(const list<int> lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { cout << (*it) << " "; ++it; } cout << endl; }
显然是可以的，不过还是刚才那个问题，这个迭代器太冗余了。因为仅仅就是一个返回值不一样而已，那么我们能否去改善呢？其实是可以的。我们可以通过一个类型去控制这个返回值，而要控制这个类型，就需要增加一个模板参数即可
我们可以这样做
在迭代器类中添加一个Ref参数
然后让*的运算符重载返回这个模板参数。
最后我们在list类中定义const_iterator的时候这样定义。
如此一来，很巧妙的解决了代码冗余的问题。虽然说从实际上来说并无太大变化。本质还是两个迭代器类。但是使我们的代码更加精简了
不过这样一来虽然list精简了，但是按照我们之前的迭代器代码，后面的大部分迭代器类型都需要大幅度改动，于是我们不妨使用typedef一下。以防后序再次修改。
如下代码所示：
template<class T, class Ref> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref> self; Node* _node; __list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } bool operator!=(const self & it) { return _node != it._node; } bool operator==(const self & it) { return _node == it._node; } };
当然现在还没完，还有时候，我们可能会写出这样的代码
struct A { A(int a = 0, int b = 0) :_a(a) ,_b(b) {} int _a; int _b; }; void test2() { list<A> lt; lt.push_back(A(1, 1)); lt.push_back(A(2, 2)); lt.push_back(A(3, 3)); lt.push_back(A(4, 4)); lt.push_back(A(5, 5)); list<A>::iterator it = lt.begin(); while (it != lt.end()) { cout << it->_a << " "; it++; } cout << endl; }
在这里我们显然发现是无法正常运行的。由于迭代器是类似于指针的操作，我们有时候就需要->操作符去解引用。所以我们就需要写一个->的运算符重载。
T* operator->() { return &_node->_val; }
如上所示，是写在迭代器里面的operator运算符重载。
利用这个运算符重载我们就可以跑上面的代码了
然而当我们细心的话，我们会发现这个运算符重载是比较怪异的。哪里怪异呢？
首先我们这个运算符重载返回的是什么呢？是A*，也就是说它还需要一次->解引用才能找到真正的值。那么我们这里为什么可行呢？
严格来说，it->->_a，才是符合语法的。
因为运算符重载要求可读性，那么编译器特殊处理，省略了一个->
上面这个运算符重载仅仅只是针对于普通对象的，如果是const对象的话，那么我们只能使用跟*运算符重载一样的处理方法，多传一个参数，才可以解决这个问题。也就是我们需要三个模板参数才可以。
最终我们的迭代器代码如下所示
template<class T, class Ref, class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; __list_iterator(Node* node) :_node(node) {} Ref operator*() { return _node->_val; } Ptr operator->() { return &_node->_val; } self& operator++() { _node = _node->_next; return *this; } self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; } self& operator--() { _node = _node->_prev; return *this; } self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; } bool operator!=(const self & it) const { return _node != it._node; } bool operator==(const self & it) const { return _node == it._node; } };
