透过源码看本质：list 的模拟实现与核心原理
一、STL源码
定义节点
迭代器
list定义
成员函数
初始化
从内存池中获取空间
创建节点
定位new 初始化
销毁节点
二、模拟实现 list 容器
1. list成员变量
//定义节点template<classT>structlist_node{ list_node<T>* _prev;//指向前驱节点 list_node<T>* _next;//指向后继结点 T val;//存储值//默认构造函数list_node(const T& x =T()):_prev(nullptr),_next(nullptr),val(x){}};//容器listtemplate<classT>classlist{typedef list_node<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator;private: Node* _head; size_t _size;//list_node _head;};2. 构造函数
//初始化voidempty_init(){//带头节点 _head =new Node; _head->_prev = _head; _head->_next = _head; _size =0;}//默认构造函数list(){empty_init();}list是一个带头的双向循环链表，因此，构造时创建一个带头的节点。
3. insert
voidinsert(const iterator& pos,const T& x)//void insert(iterator pos, const T& x){ Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode =newNode(x); newnode->_prev = prev; prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode;++_size;}list容器与数据结构之带头双向循环链表这篇文章的原理是一样的，只不过进行了封装而已。看不懂细节的，可以移步这篇文章。list容器，重点讲解迭代器部分。
4. push_back
voidpush_back(const T& x){ Node* newnode =newNode(x); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;++_size;}其实，push_back就是尾插，可以复用 insert 函数。这样去实现。
voidpush_back(const T& x){insert(end(), x);}这样是不是简单多了，end返回的就是list容器中的末尾后的一个位置（即头结点），而插入节点是在该位置之前插入的。
5. 拷贝构造
//lt2(lt1)list(list<T>& lt){empty_init();for(constauto& e : lt){push_back(e);}}拷贝构造也需要先初始化 list 对象，在调用 push_back 逐个插入元素。
6. 初始化列表构造
list(initializer_list<T> lt){empty_init();for(constauto& e : lt){push_back(e);}}逐个访问初始化列表中的元素，进行插入。
7. operator=
voidswap(list<T>& lt){ std::swap(_head, lt._head); std::swap(_size, lt._size);}//lt3=lt2//拷贝构造+交换 list<T>&operator=(list<T> lt){swap(lt);return*this;}通过拷贝构造出一个局部对象，在进行资源的交换就完成赋值重载了。
8. erase
iterator erase(iterator pos){assert(pos !=end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev;delete cur;--_size;//隐式类型转换returniterator(next);}请看数据结构之带头双向循环链表这篇文章。
9. pop_back,push_front,pop_front
voidpop_back(){erase(--end());}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}直接复用insert,erase函数即可。
10. clear
voidclear(){ iterator it =begin();while(it !=end()){ it =erase(it);}}清空 list 中的所有元素，从 list 中的 begin 位置的节点开始删除。
11. 析构函数
~list(){clear();delete _head; _head =nullptr; _size =0;}清空 list 容器中的所有节点，再删除头结点，更新_size。
12. size
size_t size()const{return _size;}13. 迭代器
iterator begin(){//_head->_next是一个指向list_node节点的指针//iterator是一个list_iterator的类//隐式类型转换，借助构造函数//返回的是iterator的临时对象//return _head->_next;returniterator(_head->_next);} iterator end(){//隐式类型转换//return _head;returniterator(_head);} const_iterator begin()const{returnconst_iterator(_head->_next);} const_iterator end()const{//隐式类型转换//return _head;returnconst_iterator(_head);}以前使用库里面的迭代器，都是直接获取迭代器，该迭代器指向某个元素的这块空间，通过解引用就可以访问到该元素。那么，在 list 这里，可以直接用原生指针Node*（list_node<T>*）作为迭代器吗？答案是不可以的。
因为如果用原生指针Node*(内置类型)作为迭代器，那么解引用能访问到元素，但是使用迭代器的方式就会与平时不一样，需要手动访问数据，而且原生指针是一个内置类型，要如何通过++操作访问下一个节点呢？基于以上原因，因此，不能用原生指针作为迭代器。
那要如何处理呢？
我们可以对原生指针进行封装，使之成为一个自定义类型，这样不就可以通过解引用操作，调用运算符重载函数了，访问到数据了吗！其次，自定义类型在++操作的时候，也可以通过运算符重载指向下一个Node节点。
具体实现如下。
template<classT,classRef,classPtr>structlist_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){//浅拷贝，默认拷贝构造函数就可以用 list_iterator<T>tmp(*this); _node = _node->_next;//局部变量，不能用引用返回return tmp;} Self&operator--(){ _node = _node->_prev;return*this;} Self operator--(int){ list_iterator<T>tmp(*this); _node = _node->_prev;return tmp;}booloperator!=(const Self& it){return _node != it._node;}booloperator==(const Self& it){return _node == it._node;}};可以看到，这里不仅有模板参数T，还多了两个模板参数Ref 和 Ptr。实现迭代器的时候，不仅实现了普通迭代器，还实现了 const 版本的迭代器，如果不增加这两个模板参数，我们就还需要写一个类来封装Node*指针，而且，这两个类的代码基本是一样的，在返回值，参数类型上会有所区别，代码会非常的冗余。所以，添加两个模板参数就可以很好的解决这个问题了。
三、完整代码实现
. list.h
#pragmaonce#include<iostream>#include<assert.h>usingnamespace std;namespace LC {template<classT>structlist_node{ list_node<T>* _prev; list_node<T>* _next; T val;//默认构造函数list_node(const T& x =T()):_prev(nullptr),_next(nullptr),val(x){}};template<classT,classRef,classPtr>structlist_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){//浅拷贝，默认拷贝构造函数就可以用 list_iterator<T>tmp(*this); _node = _node->_next;//局部变量，不能用引用返回return tmp;} Self&operator--(){ _node = _node->_prev;return*this;} Self operator--(int){ list_iterator<T>tmp(*this); _node = _node->_prev;return tmp;}booloperator!=(const Self& it){return _node != it._node;}booloperator==(const Self& it){return _node == it._node;}};template<classT>classlist{typedef list_node<T> Node;public:typedef list_iterator<T, T&, T*> iterator;typedef list_iterator<T,const T&,const T*> const_iterator; iterator begin(){//_head->_next是一个指向list_node节点的指针//iterator是一个list_iterator的类//隐式类型转换，借助构造函数//返回的是iterator的临时对象//return _head->_next;returniterator(_head->_next);} iterator end(){//隐式类型转换//return _head;returniterator(_head);} const_iterator begin()const{returnconst_iterator(_head->_next);} const_iterator end()const{//隐式类型转换//return _head;returnconst_iterator(_head);}voidempty_init(){ _head =new Node; _head->_prev = _head; _head->_next = _head; _size =0;}//默认构造函数list(){empty_init();}//lt2(lt1)list(list<T>& lt){empty_init();for(constauto& e : lt){push_back(e);}}list(initializer_list<T> lt){empty_init();for(constauto& e : lt){push_back(e);}}voidswap(list<T>& lt){ std::swap(_head, lt._head); std::swap(_size, lt._size);}//lt3=lt2//拷贝构造+交换 list<T>&operator=(list<T> lt){swap(lt);return*this;} size_t size()const{return _size;}voidpush_back(const T& x){ Node* newnode =newNode(x); Node* tail = _head->_prev; tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode;++_size;//insert(end(), x);}//在pos位置之前插入voidinsert(const iterator& pos,const T& x)//void insert(iterator pos, const T& x){ Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode =newNode(x); newnode->_prev = prev; prev->_next = newnode; newnode->_next = cur; cur->_prev = newnode;++_size;} iterator erase(iterator pos){assert(pos !=end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev;delete cur;--_size;//隐式类型转换returniterator(next);}voidpop_back(){erase(--end());}voidpush_front(const T& x){insert(begin(), x);}voidpop_front(){erase(begin());}voidclear(){ iterator it =begin();while(it !=end()){ it =erase(it);}}~list(){clear();delete _head; _head =nullptr; _size =0;}private: Node* _head; size_t _size;//list_node _head;};}. test.cc
#define_CRT_SECURE_NO_WARNINGS#include"list.h"structA{int _a1;int _a2;A(int a1 =1,int a2 =2):_a1(a1),_a2(a2){}};voidtestlist1(){ LC::list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); LC::list<int>::iterator it = l1.begin();//l1.end()返回的是临时变量，形参必须是const&while(it != l1.end()){ cout <<*it <<" ";++it;} cout << endl; l1.insert(l1.begin(),5); l1.insert(l1.end(),6); it = l1.begin();while(it != l1.end()){ cout <<*it <<" ";++it;} cout << endl; l1.erase(l1.begin()); it = l1.begin();while(it != l1.end()){ cout <<*it <<" ";++it;} cout << endl;}voidtestlist2(){ LC::list<int> l1; l1.push_back(1); l1.push_back(2); l1.push_back(3); l1.push_back(4); LC::list<int>l2(l1); LC::list<int>::iterator it = l2.begin();while(it != l2.end()){ cout <<*it <<" ";++it;} cout << endl; cout << l2.size()<< endl; LC::list<int> l3; l3.push_back(10); l3.push_back(20); l3.push_back(30); l3.push_back(40); l3.push_back(50); l2 = l3; LC::list<int>::iterator it1 = l2.begin();while(it1 != l2.end()){ cout <<*it1 <<" ";++it1;} cout << endl; cout << l2.size()<< endl;//LC::list<double> l4 = { 100,200,300,400 }; LC::list<double> l4 ={1.1,2.2,3.3,4.4}; LC::list<double>::iterator it2 = l4.begin();while(it2 != l4.end()){ cout <<*it2 <<" ";++it2;} cout << endl; cout << l4.size()<< endl; LC::list<A> l5; l5.push_back({1,1}); l5.push_back({2,2}); l5.push_back({3,3}); l5.push_back({4,4}); LC::list<A>::iterator it3 = l5.begin();while(it3 != l5.end()){ cout << it3->_a1 <<" "<< it3->_a2 << endl;++it3;} cout << endl; cout << l5.size()<< endl;}intmain(){testlist2();return0;}今天的文章分享到此结束，感谢观看。
