额额额，浅学了list，老规矩，模拟实现一下list，能让我们更好的理解list。若有兴趣，不妨垂阅！
目录
1.模拟实现list
1.1.list节点
1.2.list正向迭代器
1.3.list模拟实现
2. test
3.小知识
3.1.小知识1
3.2.小知识2
3.3. 小知识3
4.模拟实现list完整代码
同样的，我不可能把list所有接口都模拟实现出来，我也没有这个能力。So，模拟实现一些简单常用的接口。
本工程包括2个文件：
mylist.h：用于模拟实现list。
test.cpp：用于测试模拟实现的list接口是否达到预期。
1.模拟实现list
以下代码均放到mylist.h文件中。
1.1.list节点
由于list底层是带头（哨兵位）双向循环链表。所以模拟实现的list节点需要能找到前驱节点和后继节点，这点是毋庸置疑的。那么，我们将list节点设计如下：
namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};
}_val用于存储数据，_prev用于指向前驱节点，_next用于指向后继指针。
1.2.list正向迭代器
好的，由于list反向迭代器较为复杂，所以我只模拟实现正向迭代器。正向迭代器分为：普通正向迭代器、const正向迭代器。一个一个来模拟实现：
1.普通正向迭代器
我们知道迭代器是模拟指针的行为，但是却不是所有的迭代器都能直接用原生指针实现。例如：
string的正向迭代器，由于其底层是字符顺序表，可以直接用原生指针来实现迭代器；
但是如list底层是链表，正向迭代器就不能直接用原生指针实现，好比如，list<int>::iterator it; ++it;，如果该list的正向迭代器是原生指针实现的，++操作能让it指向下一个节点吗？显然不能，因为链表的物理空间不是连续的。
那么我们怎么办？
别忘了操作符重载这里利器，我们可以用类封装一下原生指针来实现普通正向迭代器：
namespace HD
{//list 普通正向迭代器template <typename T>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T> self;pNode _pNode;listIterator<T>(pNode pNode = nullptr):_pNode(pNode){}T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}T* operator->(){return &_pNode->_val;}};
}其实仔细看，这个类只有一个成员变量，就是list节点的指针_pNode。把这个指针用类封装一下，提供各种运算符重载作为该类的成员函数，就成了。本质上，这个类不还是list节点指针吗？但是这个list节点指针的行为却不是原生指针的行为能达到的。。。。。好好体会！！！！
2.const正向迭代器
普通正向迭代器和const正向迭代器基本一样。我们想想，const正向迭代器区别于普通正向迭代器，无非就是const正向迭代器指向的节点存储的数据不能更改吗？
SO：
namespace HD
{//list const正向迭代器template <typename T>struct listConstIterator{typedef listNode<T>* pNode;typedef listConstIterator<T> self;pNode _pNode;listConstIterator<T>(pNode pNode = nullptr):_pNode(pNode){}const T& operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}const T* operator->(){return &_pNode->_val;}};
}仔细看，实现起来跟普通正向迭代器的区别就在于operator*和operator->这2个函数的返回值不同罢了。至于operator->这个函数到底干啥的，一会儿说的。
3.普通正向迭代器和const正向迭代器合二为一
看到普通正向迭代器和const正向迭代器这两个类模板基本一样，那么我们完全可以写一个类模板来代替以上2个类模板：
namespace HD
{//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};
}通俗易懂讲，当Ref、Ptr是T&、T*的时候，不就是普通正向迭代器吗？
当Ref、Ptr是const T&、const T*的时候，不就是const正向迭代器吗？
1.3.list模拟实现
namespace HD
{//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x) {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}有点长啊。。 2个成员变量：_pHead是哨兵位的指针，_size是节点个数（不包括哨兵位）。insert和erase采用声明和定义分离，其他成员函数声明和定义不分离。
2. test
在test.cpp中测试一下list正向迭代器中的operator*和operator->这2个接口：
1.operator*
对于list的普通正向迭代器：
#include"mylist.h"
namespace HD
{void test(){list<size_t> l(3, 10);list<size_t>::iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}没什么问题吧：
对于list的const正向迭代器：
#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){(*it)++;cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}运行错误了：
问题就出现在*it的类型是const size_t&，不能修改，这就区别于普通正向迭代器了。
如果这样：
#include"mylist.h"
namespace HD
{void test(){const list<size_t> l(3, 10);list<size_t>::const_iterator it = l.begin();while (it != l.end()){cout << *it << ' ';it++;}cout << endl;}
}
int main()
{HD::test();return 0;
}没什么问题，可以实现遍历list容器的功能：
2.operator->
对于操作符->，我们的使用场景一般是在于结构体指针访问其指向变量的成员，像这样子：
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){auto E = new example;cout << E->_a << ' ' << E->_b << endl;}
}
int main()
{HD::test();return 0;
}
我们希望迭代器也能这样子，所以重载了->操作符。
对于list的普通正向迭代器：
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;//奇怪*2？cout << it->_a << ' ' << it->_b << " ";//奇怪？it++;}}
}
int main()
{HD::test();return 0;
}先看一下运行结果：
运行成功了，但是细细分析，感觉怪怪的。看到operator->的定义：
Ptr operator->(){return &_pNode->_val;}返回list节点_val的地址。那么这里的_val的类型是example，返回一个自定义类型指针example*。那么it->_a翻译过来就是example*_a，这是个啥玩意？关键还运行成功了。
其实编译器对这里作了特殊处理，本来应该是2个->才合乎语法，为了可读性，省略了后1个->。其实这里编译器省略了后1个->，在编译器看来，代码是这样子的：
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){list<example> l(3);auto it = l.begin();while (it != l.end()){//在编译器看来，等价于it->_a++;it->_b++;it.operator->()->_a++; it.operator->()->_b++;//在编译器看来，等价于cout<<it->_a<<' '<<it->_b<<" ";cout << it.operator->()->_a << ' ' << it.operator->()->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}也是可以运行成功的：
仔细体会一下，迭代器是不是在模拟指针的行为？
对于list的const正向迭代器：
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){it->_a++; it->_b++;cout << it->_a << ' ' << it->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}
运行不成功：
问题就在于it->返回值类型为const example* ，这不就区别于普通正向迭代器了吗？
虽然不能通过list的const正向迭代器来修改list容器的值，但是用来遍历list容器是没问题的：
#include"mylist.h"
namespace HD
{struct example{int _a = 1;int _b = 2;};void test(){const list<example> l(3);auto it = l.begin();while (it != l.end()){cout << it->_a << ' ' << it->_b << " ";it++;}}
}
int main()
{HD::test();return 0;
}
3.小知识
3.1.小知识1
讨论1个问题：const迭代器为什么是单独搞了一个类型const_iterator，而不是直接用const修饰普通迭代器？
const iterator：迭代器本身不能修改，若是直接用const修饰普通迭代器当作const迭代器，那么const迭代器就不能用来遍历容器了。
const_iterator：希望指向的内容不能修改，实际上const迭代器也是这样子实现的，例如如上模拟实现。这样子的话const迭代器本身是能修改的，可以可以用来遍历容器。
3.2.小知识2
list迭代器失效问题：
list容器迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入 时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
例如说，erase、pop_back、pop_front等操作都会导致迭代器失效，例如在test.cpp中：
#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){//erase()函数执行后，it所指向的节点已被删除，//因此it无效，在下一次使用it时，必须先给其赋值l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}
改正写法：
#include"mylist.h"
namespace HD
{void test(){list<int> l(3, 10);auto it = l.begin();while (it != l.end()){it = l.erase(it);//或者l.erase(it++);}}
}
int main()
{HD::test();return 0;
}
同样的，VS2022对std::list的erase进行了强制的检查，若erase后，没有更新迭代器就访问会报错，在test.cpp中：
#include"mylist.h"
namespace HD
{void test(){std::list<int> l(3, 10);auto it = l.begin();while (it != l.end()){l.erase(it);it++;}}
}
int main()
{HD::test();return 0;
}
所以使用std::list容器时，若是erase等删除操作后想要访问迭代器，请更新！
在list插入，如insert、push_back、push_front等操作，不会使得迭代器失效，所以VS2022对于std::list的insert等操作后也没有对其迭代器是否更新过进行检查。
3.3. 小知识3
按需实例化：
当模板没有实例化，就算模板内有错误，也不一定会报错，对于模板内明显的错误一般会检查出来，例如缺少一个分号这些明显错误；但是一下细节的错误就不一定能检查出来。如：
在test.cpp中，写了一个函数模板用于打印模拟实现的list对象；
#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){（*it）++;//错误cout << *it << ' ';}cout << endl;}
}
int main()
{return 0;
}如上代码，有细节错误：list的类型是const list<T>&，显然其值不能修改，但是*it++却想要修改。但是这个模板没有实例化，所以运行不报错：
如果让这个模板实例化一下，肯定会报错：
#include"mylist.h"
namespace HD
{template<class T>void printList(const list<T>& list){auto it = list.begin();while (it != list.end()){(*it)++;cout << *it << ' ';}cout << endl;}void test(){list<int> l(3, 5);printList(l);}
}
int main()
{HD::test();return 0;
}且看：error C3892: “it”: 不能给常量赋值 ，并且：
4.模拟实现list完整代码
在mylist.h文件下：
#pragma once
#include<iostream>
#include<assert.h>
#include<list>
using namespace std;
namespace HD
{//list节点template<typename T>struct listNode{typedef listNode node;//类里面可以将listNode<T>用listNode替代T _val;node* _prev;node* _next;};//list正向迭代器template <typename T,typename Ref,typename Ptr>struct listIterator{typedef listNode<T>* pNode;typedef listIterator<T,Ref,Ptr> self;pNode _pNode;listIterator<T,Ref,Ptr>(pNode pNode=nullptr):_pNode(pNode){}Ref operator*(){return (*_pNode)._val;}self operator++(int)//后置++{self it(_pNode);_pNode = _pNode->_next;return it;}self& operator++()//前置++{_pNode = _pNode->_next;return *this;}self operator--(int)//后置--{self it(_pNode);_pNode = _pNode->_prev;return it;}self& operator--()//前置--{_pNode = _pNode->_prev;return *this;}bool operator!=(const self& it){return _pNode != it._pNode;}bool operator==(const self& it){return _pNode == it._pNode;}Ptr operator->(){return &_pNode->_val;}};list const正向迭代器//template <typename T>//struct listConstIterator//{// typedef listNode<T>* pNode;// typedef listConstIterator<T> self;// pNode _pNode;// listConstIterator<T>(pNode pNode = nullptr)// :_pNode(pNode)// {// }// const T& operator*()// {// return (*_pNode)._val;// }// self operator++(int)//后置++// {// self it(_pNode);// _pNode = _pNode->_next;// return it;// }// self& operator++()//前置++// {// _pNode = _pNode->_next;// return *this;// }// self operator--(int)//后置--// {// self it(_pNode);// _pNode = _pNode->_prev;// return it;// }// self& operator--()//前置--// {// _pNode = _pNode->_prev;// return *this;// }// bool operator!=(const self& it)// {// return _pNode != it._pNode;// }// bool operator==(const self& it)// {// return _pNode == it._pNode;// }// const T* operator->()// {// return &_pNode->_val;// }//};//list 普通正向迭代器//template <typename T>//struct listIterator//{// typedef listNode<T>* pNode;// typedef listIterator<T> self;// pNode _pNode;// listIterator<T>(pNode pNode = nullptr)// :_pNode(pNode)// {// }// T& operator*()// {// return (*_pNode)._val;// }// self operator++(int)//后置++// {// self it(_pNode);// _pNode = _pNode->_next;// return it;// }// self& operator++()//前置++// {// _pNode = _pNode->_next;// return *this;// }// self operator--(int)//后置--// {// self it(_pNode);// _pNode = _pNode->_prev;// return it;// }// self& operator--()//前置--// {// _pNode = _pNode->_prev;// return *this;// }// bool operator!=(const self& it)// {// return _pNode != it._pNode;// }// bool operator==(const self& it)// {// return _pNode == it._pNode;// }// T* operator->()// {// return &_pNode->_val;// }//};//listtemplate<typename T>class list{private:typedef listNode<T> node;typedef listNode<T>* pNode;typedef T value_type;typedef size_t size_type;private:pNode _pHead;size_t _size;public:typedef listIterator<T,T&,T*> iterator;typedef listIterator<T,const T&,const T*> const_iterator;public:void emptyInit(){_pHead = new node;_pHead->_prev = _pHead;_pHead->_next = _pHead;_size = 0;}list(){emptyInit();}list(size_type n, const value_type& val=value_type()){emptyInit();while (n--){push_back(val);}}list(const list& x){emptyInit();pNode cur = x._pHead->_next;while (cur != x._pHead){push_back(cur->_val);cur = cur->_next;}}void swap(list& x){std::swap(x._pHead, _pHead);std::swap(x._size, _size);}list& operator=(list x) {swap(x);return *this;}void push_back(const value_type& val){/*pNode end = _pHead->_prev;pNode newNode = new node;newNode->_val = val;end->_next = newNode;newNode->_prev = end;_pHead->_prev = newNode;newNode->_next = _pHead;_size++;*/insert(_pHead, val);}void push_front(const value_type& val){insert(_pHead->_next, val);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}size_type size()const{return _size;}bool empty()const{return _size == 0;}iterator begin(){/*iterator it(_pHead->_next);return it;*//*return iterator(_pHead->_next);//匿名对象*/return _pHead->_next;}iterator end(){/*iterator it(_pHead);return it;*//*return iterator(_pHead);//匿名对象*/return _pHead;}const_iterator begin()const{return _pHead->_next;}const_iterator end()const{return _pHead;}void clear(){while (size() != 0){pop_back();}}~list(){clear();delete _pHead;_pHead = nullptr;_size = 0;}iterator insert(iterator position, const value_type& val);iterator erase(iterator position);};template <typename T>typename list<T>::iterator list<T>::insert(list<T>::iterator position, const list<T>::value_type& val){pNode cur = position._pNode;pNode prev = position._pNode->_prev;pNode newNode = new node;newNode->_val = val;newNode->_next = cur;cur->_prev = newNode;newNode->_prev = prev;prev->_next = newNode;_size++;return position--;}template<typename T>typename list<T>::iterator list<T> ::erase(list<T>::iterator position){assert(position != end());//不能erase哨兵位节点pNode prev = position._pNode->_prev;pNode next = position._pNode->_next;delete position._pNode;prev->_next = next;next->_prev = prev;_size--;return next;}
}感谢阅读！
