需要实现的三个类及其成员函数接口总览
namespace cl { //模拟实现list当中的结点类 template<class T> struct _list_node { //成员函数 _list_node(const T& val = T()); //构造函数 //成员变量 T _val; //数据域 _list_node<T>* _next; //后继指针 _list_node<T>* _prev; //前驱指针 }; //模拟实现list迭代器 template<class T, class Ref, class Ptr> struct _list_iterator { typedef _list_node<T> node; typedef _list_iterator<T, Ref, Ptr> self; _list_iterator(node* pnode); //构造函数 //各种运算符重载函数 self operator++(); self operator--(); self operator++(int); self operator--(int); bool operator==(const self& s) const; bool operator!=(const self& s) const; Ref operator*(); Ptr operator->(); //成员变量 node* _pnode; //一个指向结点的指针 }; //模拟实现list template<class T> class list { public: typedef _list_node<T> node; typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; //默认成员函数 list(); list(const list<T>& lt); list<T>& operator=(const list<T>& lt); ~list(); //迭代器相关函数 iterator begin(); iterator end(); const_iterator begin() const; const_iterator end() const; //访问容器相关函数 T& front(); T& back(); const T& front() const; const T& back() const; //插入、删除函数 void insert(iterator pos, const T& x); iterator erase(iterator pos); void push_back(const T& x); void pop_back(); void push_front(const T& x); void pop_front(); //其他函数 size_t size() const; void resize(size_t n, const T& val = T()); void clear(); bool empty() const; void swap(list<T>& lt); private: node* _head; //指向链表头结点的指针 }; }
结点类的模拟实现
list在底层实现时就是一个链表,更准确的来说,list实际上就是一个带头双向循环链表.
因此,我们若要实现list,则首先需要实现一个结点类.而一个结点需要存储的信息有:数据,前一个结点的地址,后一个结点的地址,于是该结点类的成员变量也就出来了.
而对于该结点类的成员函数来说,我们只需要实现一个构造函数即可.因为该结点类只需要根据数据来构造一个结点即可,而结点的释放则由list的析构函数来完成.
构造函数
结点类的构造函数直接根据所给数据构造一个结点即可,构造出来的结点的数据域存储的就是所给数据,而前驱指针和后继指针均初始化为空指针即可.
_list_node(const T& val=T()) :_val(val) ,_prev(nullptr) ,_next(nullptr) {}
注意:若构造结点时未传入数据,则默认以list容器所存储类型的默认构造函数所构造出来的值为传入数据.
迭代器类的模拟实现
迭代器类存在的意义
之前模拟实现string和vector时都没有说要实现一个迭代器类，为什么实现list的时候就需要实现一个迭代器类了呢？
因为string和vector对象都将其数据存储在了一块连续的内存空间，我们通过指针进行自增、自减以及解引用等操作，就可以对相应位置的数据进行一系列操作，因此string和vector当中的迭代器就是原生指针。
但是对于list来说，其各个结点在内存当中的位置是随机的，并不是连续的，我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作。
而迭代器的意义就是，让使用者可以不必关心容器的底层实现，可以用简单统一的方式对容器内的数据进行访问。
既然list的结点指针的行为不满足迭代器定义，那么我们可以对这个结点指针进行封装，对结点指针的各种运算符操作进行重载，使得我们可以用和string和vector当中的迭代器一样的方式使用list当中的迭代器。例如，当你使用list当中的迭代器进行自增操作时，实际上执行了p = p->next语句，只是你不知道而已。
总结： list迭代器类，实际上就是对结点指针进行了封装，对其各种运算符进行了重载，使得结点指针的各种行为看起来和普通指针一样。（例如，对结点指针自增就能指向下一个结点）
迭代器类的模板的参数说明
这里我们所实现的迭代器类的模板参数列表当中为什么有三个模板参数？
template<class T, class Ref, class Ptr>
在list的模拟实现当中，我们typedef了两个迭代器类型，普通迭代器和const迭代器。
typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator;
这里我们就可以看出，迭代器类的模板参数列表当中的Ref和Ptr分别代表的是引用类型和指针类型。
当我们使用普通迭代器时，编译器就会实例化出一个普通迭代器对象；当我们使用const迭代器时，编译器就会实例化出一个const迭代器对象。
若该迭代器类不设计三个模板参数，那么就不能很好的区分普通迭代器和const迭代器。
构造函数
迭代器类实际上就是对结点指针进行了封装，其成员变量就只有一个，那就是结点指针，其构造函数直接根据所给结点指针构造一个迭代器对象即可。
//构造函数 _list_iterator(node* pnode) :_pnode(pnode) {}
++运算符的重载
首先是前置++，前置++原本的作用是将数据自增，然后返回自增后的数据。我们的目的是让结点指针的行为看起来更像普通指针，那么对于结点指针的前置++，我们就应该先让结点指针指向后一个结点，然后再返回“自增”后的结点指针即可。
//前置++ self operator++() { _pnode = _pnode->_next; //让结点指针指向后一个结点 return *this; //返回自增后的结点指针 }
对于后置++，我们则应该先记录当前结点指针的指向，然后让结点指针指向后一个结点，最后返回“自增”前的结点指针即可。
//后置++ self operator++(int) { self tmp(*this); //记录当前结点指针的指向 _pnode = _pnode->_next; //让结点指针指向后一个结点 return tmp; //返回自增前的结点指针 }
说明： self是当前迭代器对象的类型：
typedef _list_iterator<T, Ref, Ptr> self;
--运算符的重载
对于前置- -，我们应该先让结点指针指向前一个结点，然后再返回“自减”后的结点指针即可。
1.
//前置-- self operator--() { _pnode = _pnode->_prev; //让结点指针指向前一个结点 return *this; //返回自减后的结点指针 }
而对于后置- -，我们则应该先记录当前结点指针的指向，然后让结点指针指向前一个结点，最后返回“自减”前的结点指针即可。
//后置-- self operator--(int) { self tmp(*this); //记录当前结点指针的指向 _pnode = _pnode->_prev; //让结点指针指向前一个结点 return tmp; //返回自减前的结点指针 }
==运算符的重载
当使用==运算符比较两个迭代器时，我们实际上想知道的是这两个迭代器是否是同一个位置的迭代器，也就是说，我们判断这两个迭代器当中的结点指针的指向是否相同即可。
bool operator==(const self& s) const { return _pnode == s._pnode; //判断两个结点指针指向是否相同 }
!=运算符的重载
!=运算符刚好和==运算符的作用相反，我们判断这两个迭代器当中的结点指针的指向是否不同即可。
bool operator!=(const self& s) const { return _pnode != s._pnode; //判断两个结点指针指向是否不同 }
*运算符的重载
当我们使用解引用操作符时，是想得到该位置的数据内容。因此，我们直接返回当前结点指针所指结点的数据即可，但是这里需要使用引用返回，因为解引用后可能需要对数据进行修改。
Ref operator*() { return _pnode->_val; //返回结点指针所指结点的数据 }
->运算符的重载
某些情景下，我们使用迭代器的时候可能会用到->运算符。
想想如下场景：
当list容器当中的每个结点存储的不是内置类型，而是自定义类型，例如日期类，那么当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问Date的成员：
list<Date> lt; Date d1(2021, 8, 10); Date d2(1980, 4, 3); Date d3(1931, 6, 29); lt.push_back(d1); lt.push_back(d2); lt.push_back(d3); list<Date>::iterator pos = lt.begin(); cout << pos->_year << endl; //输出第一个日期的年份
注意： 使用pos->_year这种访问方式时，需要将日期类的成员变量设置为公有。
对于->运算符的重载，我们直接返回结点当中所存储数据的地址即可。
Ptr operator->() { return &_pnode->_val; //返回结点指针所指结点的数据的地址 }
讲到这里，可能你会觉得不对，按照这种重载方式的话，这里使用迭代器访问日期类当中的成员变量时不是应该用两个->吗？
这里本来是应该有两个->的，第一个箭头是pos ->去调用重载的operator->返回Date* 的指针，第二个箭头是Date* 的指针去访问对象当中的成员变量_year。
但是一个地方出现两个箭头，程序的可读性太差了，所以编译器做了特殊识别处理，为了增加程序的可读性，省略了一个箭头。
list的模拟实现
默认成员函数
构造函数
list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。
//构造函数 list() { _head = new node; //申请一个头结点 _head->_next = _head; //头结点的后继指针指向自己 _head->_prev = _head; //头结点的前驱指针指向自己 }
