本文我们模拟实现STL中的list，为了模拟实现list，实际上我们需要实现三个类，分别为：_list_node , _list_iterator , list。
我们先看一下这三个类的基本组成，主要是看看每个类中包含的变量有什么：
namespace CYF
{//模拟实现list当中的结点类template<class T>struct _list_node{//成员变量T _val; //数据_list_node<T>* _prev; //prev指针_list_node<T>* _next; //next指针};//模拟实现list迭代器//T表示结点内数据类型，Ref表示引用类型，Ptr表示指针类型template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型//成员变量node* _pnode; //一个指向结点的指针};//模拟实现listtemplate<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;private:node* _head; //指向链表头结点的指针};
}节点类的模拟实现
我们在上篇文章中讲过list的底层就是一个带头双向循环链表。所以我们就要先实现一个节点类，这个结点中要存储的信息有数据，前一个结点的地址和后一个结点的地址，也就是list_node中的三个成员变量。
而节点类实现的目的就是根据构造函数构造出来一个一个结点即可，构造出来的结点数据域存储传过来的数据，而两个指针都置为空即可：
//模拟实现list当中的结点类template<class T>struct _list_node{//成员函数_list_node(const T& val = T())//构造函数:_val(val),_next(nullptr),_prev(nullptr){}//成员变量T _val; //数据_list_node<T>* _prev; //prev指针_list_node<T>* _next; //next指针};迭代器类的模拟实现
list迭代器类存在的意义
我们之前模拟实现过string和vector，他们俩都没说要实现一个迭代器类，为什么现在实现list的时候要实现一个迭代器类呢？
因为string和vector对象的数据都存储在一块连续的内存空间，我们可以通过指针进行++，--以及解引用等操作，就可以对相应的数据进行一系列操作，因此string和vector当中的指针就是原生指针。
但是对于list来说，其各个结点在内存中的位置是随机的，不是连续的，也就导致我们不能通过结点指针的++，--以及解引用对结点的数据进行操作。
而我们之前也说过，迭代器的意义就是让使用者可以不用关心容器的底层实现，可以用统一的方式对容器内的数据进行访问。
那么既然list的结点指针不能直接用于定义迭代器，那么我们可以对这个结点指针进行封装，对结点的各个运算符进行重载。例如，我们将++操作operator为p=p->_next;类似的，即可使用++，--，解引用等和vector这种容器一样的操作方法操作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;实际上定义这三个模板参数就是为了区分普通迭代器和const迭代器。
迭代器类的模板参数中的Ref和Ptr分别表示的就是数据的引用和指向数据的指针。
我们使用普通迭代器时，就会实例化出一个普通迭代器对象，使用const迭代器时，就会实例化出一个const迭代器对象，有关操作的参数和返回值都会加上const。
而我们还在迭代器类中typedef出来个self：
typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型
而这个self就是当前迭代器对象的类型。
实现各类函数及运算符重载
构造函数
迭代器类中就一个成员变量——结点指针，我们只初始化一个结点指针就行：
_list_iterator(node* pnode):_pnode(pnode){}operator++(前置 && 后置)
++的作用就是让结点指针指向下一个结点，前置++就返回++后的结点，后置++就还返回原先的结点，代码如下：
self operator++()//前置{_pnode = _pnode->_next;return *this;}self operator++(int)//后置{self tmp(*this);_pnode = _pnode->_next;return tmp;}//返回值类型self就是迭代器类型operator--(前置 && 后置)
--的作用就是让结点指针指向前一个结点，前置--就返回--后的结点，后置--就还返回原先的结点，代码如下：
self operator--()//前置{_pnode = _pnode->_prev;return *this;}self operator--(int)//后置{self tmp(*this);_pnode = _pnode->_prev;return tmp;}operator==
我们看两个list对象是否是同一个只需要看他们的头指针是否为同一个即可：
bool operator==(const self& s) const{return _pnode == s._pnode;}operator!=
我们看两个list对象是否不是同一个只需要看他们的头指针是否不为同一个即可：
bool operator!=(const self& s) const{return _pnode != s._pnode;}operator* (就是对*的重载)
我们使用迭代器的时候，就像使用指针一样使用，所以我们在使用*的时候是为了得到这个位置的数据，那么我们直接返回结点的数据即可：
//返回当前结点指针所指向的数据，这里的返回值是引用，因为可能会修改Ref operator*(){return _pnode->_val;}operator->
某些情况下，我们会用到->运算符：
当list对象中存储的不是内置类型，而是自定义类型时，例如日期类，当我们拿到一个位置的迭代器时，我们可能会使用->运算符访问日期类的某个成员：
list<Date> lt;
Date d(2024,6,5);
lt.push_back(d);
list<Date>::iterator it = d.begin();
cout<<it._day<<endl;提示：我们使用it->_day这种访问方式的时候，需要将Date类的成员变量设置为共有。
我们实现的时候返回结点中存储数据的地址即可：
//当list内存储的是自定义类型时候就需要使用->,我们直接返回结点中存储数据的地址即可Ptr operator->(){return &_pnode->_val;//对于类似于Date这样的类这里本来是有两个->的，//为了增强程序的可读性，省略了一个-> }我们这里要注意一点：拿Date类举例，我们想得到一个Date对象的一个成员变量_day。我们应该是有两个箭头，即：先it->去调用Date的operator->返回Date*的指针，然后再用返回的Date*的指针->去访问Date的成员变量_day。
但是这里为了增加程序的可读性，我们省略了一个箭头。
list的模拟实现
构造函数
构造时，我们直接申请一个头节点，并让该头节点_prev,_next指针都指向自己即可：
//默认成员函数list(){_head = new node;_head->_next = _head;_head->_prev = _head;}拷贝构造函数
我们先申请一个头节点，头节点的_prev,_next都指向自己，然后遍历要拷贝的list对象，将所有元素push_back。
list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& e : lt){push_back(e);}}赋值运算符重载函数
法一（传统写法）：
用clear()将容器清空，然后通过遍历将被赋值的list对象中的元素push_back。
list<T>& operator=(const list<T>& lt){if (this != <){clear();const_iterator it = lt.begin();//while (it != lt.end())//{// push_back(it._pnode->_val);// it++;//}for(const auto& e : lt)//用范围for比较简洁{push_back(e);}}return *this;}法二（现代写法）：
与之前的string和vector现代写法相似，故意不使用引用传参接收参数，通过编译器自动调用list的拷贝构造函数构造出一个局部的list对象，然后使用swap函数交换两个list对象即可：
list<T>& operator=(list<T> lt){swap(lt);return *this;}析构函数
先调用clear函数清空容器内数据，然后将头节点释放，置空：
~list(){clear();delete _head;_head = nullptr;}begin() && end()
begin()函数返回第一个有效数据的迭代器，end()函数返回最后一个有效数据下一个的迭代器。
我们仔细想想，list是一个带头双向循环的链表，第一个有效数据就是_head->_next的迭代器，而最后一个有效数据下一个的迭代器就是_head的迭代器，因为最后一个结点的_next就是_head。
iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{return iterator(_head);}front() && back()
这两个函数分别用于获取第一个有效数据和最后一个有效数据。因此，我们直接返回第一个和最后一个有效数据的引用即可：
//访问容器相关函数T& front(){return _head->_next->_val;//或者这样写：return *begin();//返回第一个有效数据的引用}T& back(){return _head->_prev->_val;//或者这样写：return *(--end());//返回最后一个有效数据的引用}const T& front() const{return _head->_next->_val;}const T& back() const{return _head->_prev->_val;}insert
我们先创建一个新结点，然后建立新结点与前后结点的关系即可：
void insert(iterator pos, const T& x){assert(pos._pnode);//检测pos的合法性node* cur = pos->_pnode;//迭代器pos处的指针node* prev = cur->_prev;//迭代器前一个位置的结点指针node* newnode = new node(x);//创建的新结点指针//构建新结点newnode和prev和cur结点的关系newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;prev->_next = newnode;}erase
我们需要先通过迭代器找到要删除的结点，然后记录要删除的结点的前后结点，然后释放这个该删除的结点，之后建立前后结点的双向关系：
iterator erase(iterator pos){assert(pos._pnode);//检查pos的合法性assert(pos != end());//删除的不能是头结点node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;return iterator(next);}push_back
法一、我们可以创建并赋值新结点，然后记录_head->_next，最后录入新结点和_head->_next，_head的双向关系
法二、我们可以复用insert()函数
void push_back(const T& x)//法一{node* last = _head->_prev;node* newnode = new node;newnode->_val = x;last->_next = newnode;newnode->_prev = last;newnode->_next = _head;_head->_prev = newnode;}void push_back(const T& x)//法二{isnert(end(), x);}pop_back && push_front && pop_front
我们都直接复用insert()和erase()函数：
void pop_back(){//注意end()是最后一个结点的下一个位置，我们这里要删除的是最后一个结点//所以我们这里要--erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}size
由于链表的每个元素在内存中的位置是随机的，所以我们只能通过遍历的方式统计有效数据的个数：
size_t size() const{size_t sz = 0;const_iterator it = begin();while (it != end()){sz++;it++;}return sz;}resize
resize函数我们需要分两种情况来讨论：
1.若当前容器的size小于所给n，则尾插结点，直到size等于n。
2.若当前容器的size大于所给n，只保留前n个有效数据。
我们这里要注意：当我们实现resize函数的时候，不能通过size函数获取当前list对象中的有效数据个数，因为当我们调用size函数后就遍历一遍容器了，若size>n，那么还要遍历容器，找到第n个有效结点并释放后面的结点。
所以我们要设置一个变量len，用于记录当前所遍历的数据个数，然后开始遍历数组，在遍历过程中：
1.当len大于或等于n时遍历结束，此时说明该结点后的结点都应该被释放，将之后的结点释放即可
2.当容器遍历完时遍历结束，说明此时容器容器中的有效数据小于n个，则需要尾插结点，直到容器中的有效数据个数为n。
void resize(size_t n, const T& val = T()){iterator i = begin();//获取第一个有效数据的迭代器size_t len = 0;//记录当前所遍历的数据个数while (i != end() && len < n)//遍历{i++;len++;}if (len == n)//说明list中数据个数大于等于n，删除多出的数据{while (i != end()){//erase(i);//i++;//↑上面两行写的是错误的，迭代器失效，不要犯错误i = erase(i);//每次删除后要接收下一个数据的迭代器}}else//说明list中数据个数小于n，要尾插若干个数据为val的结点，直到容器中结点为n个{while (len != n){push_back(val);len++;}}}clear
通过遍历的方式逐个删除结点，只保留头节点即可：
void clear(){iterator it = begin();while (it != end())//去除其他结点，只保留头节点{it = erase(it);}}empty
判断容器是否为空，我们直接判断begin()和end()返回的迭代器是否为同一个位置即可：
bool empty() const{return begin() == end();}swap
list容器中实际上就存了一个_head指针，我们将两个容器中的头指针交换位置即可：
void swap(list<T>& lt){std::swap(_head, lt._head);}完整代码
最后贴上全部代码：
#pragma once
#include<iostream>
#include<cassert>namespace CYF
{//模拟实现list当中的结点类template<class T>struct _list_node{//成员函数_list_node(const T& val = T())//构造函数:_val(val),_next(nullptr),_prev(nullptr){}//成员变量T _val; //数据域_list_node<T>* _next; //后继指针_list_node<T>* _prev; //前驱指针};//模拟实现list迭代器//T表示结点内数据类型，Ref表示引用类型，Ptr表示指针类型template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> node;typedef _list_iterator<T, Ref, Ptr> self;//self就是当前迭代器对象的类型//构造函数_list_iterator(node* pnode):_pnode(pnode){}//各种运算符重载函数self operator++(){_pnode = _pnode->_next;return *this;}self operator--(){_pnode = _pnode->_prev;return *this;}self operator++(int){self tmp(*this);_pnode = _pnode->_next;return tmp;}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内存储的是自定义类型时候就需要使用->,我们直接返回结点中存储数据的地址即可Ptr operator->(){return &_pnode->_val;//这里本来是有两个->的，为了增强程序的可读性，省略了一个-> }//成员变量node* _pnode; //一个指向结点的指针};//模拟实现listtemplate<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(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){_head = new node;_head->_next = _head;_head->_prev = _head;for (const auto& e : lt){push_back(e);}}list<T>& operator=(const list<T>& lt)//operator=传统写法{if (this != <){clear();const_iterator it = lt.begin();while (it != lt.end()){push_back(it._pnode->_val);it++;}}return *this;}list<T>& operator=(list<T> lt)//operator=现代写法{swap(lt);return *this;}~list(){clear();delete _head;_head = nullptr;}//迭代器相关函数iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{return iterator(_head);}//访问容器相关函数T& front(){return _head->_next->_val;//或者这样写：return *begin();//返回第一个有效数据的引用}T& back(){return _head->_prev->_val;//或者这样写：return *(--end());//返回最后一个有效数据的引用}const T& front() const{return _head->_next->_val;}const T& back() const{return _head->_prev->_val;}//插入、删除函数void insert(iterator pos, const T& x){assert(pos._pnode);//检测pos的合法性node* cur = pos->_pnode;//迭代器pos处的指针node* prev = cur->_prev;//迭代器前一个位置的结点指针node* newnode = new node(x);//创建的新结点指针//构建新结点和prev和cur结点的关系newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;prev->_next = newnode;}iterator erase(iterator pos){assert(pos._pnode);//检查pos的合法性assert(pos != end());//删除的不能是头结点node* cur = pos._pnode;node* prev = cur->_prev;node* next = cur->_next;delete cur;prev->_next = next;next->_prev = prev;return iterator(next);}//void push_back(const T& x)//{// node* last = _head->_prev;// node* newnode = new node;// newnode->_val = x;// last->_next = newnode;// newnode->_prev = last;// newnode->_next = _head;// _head->_prev = newnode;//}void push_back(const T& x){isnert(end(), x);}void pop_back(){//注意end()是最后一个结点的下一个位置，我们这里要删除的是最后一个结点//所以我们这里要--erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}//其他函数size_t size() const{size_t sz = 0;const_iterator it = begin();while (it != end()){sz++;it++;}return sz;}void resize(size_t n, const T& val = T()){iterator i = begin();//获取第一个有效数据的迭代器size_t len = 0;//记录当前所遍历的数据个数while (i != end() && len < n)//遍历{i++;len++;}if (len == n)//说明list中数据个数大于等于n，删除多出的数据{while (i != end()){//erase(i);//i++;//↑上面两行写的是错误的，迭代器失效，不要犯错误i = erase(i);//每次删除后要接收下一个数据的迭代器}}else//说明list中数据个数小于n，要尾插若干个数据为val的结点，直到容器中结点为n个{while (len != n){push_back(val);len++;}}}void clear(){iterator it = begin();while (it != end())//去除其他结点，只保留头节点{it = erase(it);}}bool empty() const{return begin() == end();}void swap(list<T>& lt){std::swap(_head, lt._head);}private:node* _head; //指向链表头结点的指针};
}