前言：学习C++的STL，我们不仅仅要求自己能够熟练地使用各种接口，我们还必须要求自己了解一下其底层的实现方法，这样可以帮助我们写出比较高效的代码程序！
⭐在本篇文章中，list的迭代器是重点，它不像string和vector的迭代器一样可以使用原生指针，至于为啥，您可以继续往下看看！
首先是关于list的基本概念：
⭐1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
⭐2. list的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
⭐3. list与forward_list非常相似：最主要的不同在于forward_list是单链表，只能朝前迭代，已让其更简单高效。
⭐4. 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
⭐5. 与其他序列式容器相比，list和forward_list最大的缺陷是不支持任意位置的随机访问,比如：要访问list的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
模拟实现list
首先创建节点和list类，以及使用命名空间来防止冲突。
namespacemy_list{ //节点template<classT>structListNode { ListNode*_next; ListNode*_prev; T_data; //new node创建节点的时候，要默认构造初始化ListNode(constT&x) :_next(nullptr) , _prev(nullptr) , _data(x) {} }; //创建list类template<classT>classlist { typedefListNode<T>Node; public: private: Node*_head; size_t_size; }; }
构造函数
1.无参构造
因为list的一个带头双向循环链表，因此，构造的时候，第一个节点不带值，做头节点，其指针指向自己。在new node初始化的时候，因为T是泛型，如果T是string类等等，需要调用T的默认构造去初始化，T初始化后再传入节点的构造函数，进行节点的初始化。
list() { _head=newNode(T()); _head->_next=_head; _head->_prev=_head; _size=0; }
因为后续的接口实现，多处用到list的空初始化，因此，可以按照实现一个函数，专门用来空初始化list对象。
voidempty_initialize() { _head=newNode(T()); _head->_next=_head; _head->_prev=_head; _size=0; } list() { empty_initialize(); }
2.迭代器区间构造
//迭代器区间构造template<classInputIterator>list(InputIteratorfirst, InputIteratorlast) { //创建哨兵位头节点empty_initialize(); while (first!=last) { push_back(*first); ++first; } }
3.拷贝构造
传统写法：
先初始化lt2，然后lt1有多少节点，lt2也尾插多少，数据也得一样。这里需要注意两点：
第一点：for循环中，最好使用引用，因为T是泛型，如果T是string类，是vector类，那么在赋值给e的时候，就会不断地进行拷贝。
第二点：auto前加const，是基于实现了const迭代器的情况，如果没有实现，就不能加const。
//lt2(lt1)list(constlist<T><) { //先初始化,搞一个哨兵位的头节点empty_initialize(); for (constauto&e : lt) { push_back(e); } }
现代版本的写法：
现代写法的思路就是找打工人，然后跟打工人交换。因为默认无论如何，即使是空的链表，也会有一个哨兵位的头节点。如果没有这个哨兵位的头节点，在交换之后，tmp会导致野指针问题，在析构的时候会报错！
voidswap(list<T><) { std::swap(_head, lt._head); std::swap(_size, lt._size); }
list(constlist<T><) { //得有一个哨兵位empty_initialize(); list<T>tmp(lt.begin(), lt.end()); swap(tmp); }
4.赋值
传统写法：
list<T>&operator=(constlist<T><) { //防止自己给自己赋值if (this!=<) { //先清掉原有的节点clear(); for (auto&e : lt) { push_back(e); } } return*this; }
现代写法：
赋值不同于拷贝，因为this本来就有自己的哨兵位，因此不需要调用empty_initialize();函数。传参并不是引用传参，原有有两个：第一个是最重要的，如果用了引用，就会修改传进来的参数的值。第二个是：lt是局部变量，出来作用域后会析构带走。而传统写法不会对传进来的参数的值进行修改，选择引用是比较好的，可以省掉一次拷贝构造。
//lt1 = lt2;list<T>&operator=(constlist<T>lt) { swap(lt); return*this; }
5.析构函数
先将除头节点外的节点全部删掉，最后再单独释放头节点。clear()的实现在后面~
~list() { clear(); delete_head; _head=nullptr; }
新增节点：
1.push_back(const T& x);
尾插很简单，就是修改一下指针而已。
voidpush_back(constT&x) { Node*newnode=newNode(x); Nodetail=_head->_prev; tail._next=newnode; newnode->_prev=tail; newnode->_next=_head; _head->_prev=newnode; ++_size; }
2.insert(iterator pos,const T&x);
iteratorinsert(iteratorpos, constT&x) { Node*newnode=newNode(x); Node*cur=pos._pnode; Node*prev=cur->_prev; prev->_next=newnode; newnode->_prev=prev; newnode->_next=cur; cur->_prev=newnode; ++_size; returniterator(newnode); }
3.push_front(const T& x);
复用insert就好，push_back()其实也可以服用insert。代码里面的begin()和end()是基于迭代器而实现的接口，迭代器的实现，在文章下面点。
voidpush_front(constT&x) { insert(begin(), x); }
voidpush_back(constT&x) { //Node* newnode = new Node(x);//Node tail = _head->_prev;//tail._next = newnode;//newnode->_prev = tail;//newnode->_next = _head;//_head->_prev = newnode;insert(end(), x); }
删除节点：
1.erase(iterator pos);
前面说过，此处可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
解决的方法，便是更新pos，返回pos的下一个位置的即可。
iteratorerase(iteratorpos) { assert(pos!=end()); Node*prev=pos._pnode->_prev; Node*next=pos._pnode->_next; prev->_next=next; next->_prev=prev; --_size; deletepos._pnode; returniterator(next); }
2.头删跟尾删。
服用erase();即可。尾删的时候，因为end()是最后一个数据的下一个位置，因此需要end()减减一下，则需要在迭代器的类域里面实现operator--()的接口。
//头删voidpop_front() { erase(begin()); } //尾删voidpop_back() { erase(--end()); }
3、清空节点
使用迭代器进行删除，erase函数会返回删除的节点的下一个节点！这里需要注意的是，while循环的条件it!=end()，不能改写为it<end()。因为，链表节点的地址不是连续的，不能这样判断。
voidclear() { iteratorit=begin(); while (it!=end()) { it=erase(it);//erase会返回下一个节点 } }
list迭代器：
迭代器，它是内嵌类型的，即是在某个类里面的。并且它是行为是像指针一样的！在上层中，每种迭代器的使用方法几乎一样，但是其底层实现的方法压根不一样！
如果我们像实现string类和vector类（官方库中不是使用原生指针）一样，直接使用原生指针，是不可以写出我们需要的迭代器的！
![8]3RV{FY~T1$EDT4PJEV8B1.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_b99c2df6f7534eb0b60a9d6f2986ec2b.png?x-oss-process=image/resize,w_1400/format,webp "8]3RV{FY~T1$EDT4PJEV8B1.png")
而指针重要的两个行为如下：
1.解引用
2.支持++或--
vector或string类的迭代器是可以使用原生指针，因为它们是一段连续的物理空间，不管是解引用还是++/--，都能够保证获取到指定位置的数据或到达指定的位置（因为指针的++，加的是一个对象的大小，T是多大，就+多大，指针就往前走多少步）。
但是对于链表，它的节点的地址是不连续的！此时原生指针（Node*）不能满足迭代器的行为！此时，类的封装的重要性就体现出来了！类的封装+运算符重载闪亮登场！
此时的迭代器，不再是内置类型，而是一个自定义类型，我们一步步往下讲。
初步写法：
我们初步的写法，便是先将++，解引用和判断相等的功能实现。所谓的解引用，就是返回当前节点的值，而++，链表的++，本质就是到下一个节点，那便是next！
注意这里没有写出拷贝构造，意味着当我们使用赋值的时候，是浅拷贝，这也是我们所需要的，因为需要迭代器的对象跟调用迭代器的对象指向同一个节点！这也是不写析构函数的原因，否则会对同一块空间进行两次析构！
template<classT>struct__list_iterator { typedefListNode<T>node; node*_pnode; __list_iterator(node*p) :_pnode(p) {} //解引用T&operator*() { return_pnode->_data; } //++__list_iterator<T>&operator++() { _pnode=_pnode->_next; return*this; } //--__list_iterator<T>&operator--() { _pnode=_pnode->_prev; return*this; } //！=boolpoerator!=(const__list_iterator<T>&it) { return_pnode!=it._pnode; } };
此时，就可以在list类里面写出迭代器的两个函数：begin和end。需要注意的是，begin的位置，是头节点的下一个位置，因为这是带头链表。end的位置，是最后一个节点的下一个位置，那就是头节点了。
![6SPY]X~LT%)AOOJRZN(M9[D.png](https://ucc.alicdn.com/pic/developer-ecology/ipajprmaanvwy_b188af60a75f403db6ba5b49756cccc0.png?x-oss-process=image/resize,w_1400/format,webp "6SPY]X~LT%)AOOJRZN(M9[D.png")
typedef__list_iterator<T>iterator; iteratorbegin() { returniterator(_head->_next);//使用匿名对象 } iteratorend() { //iterator it(_head);//return it;returniterator(_head); }
const 迭代器
const迭代器，只读不写。那么，const迭代器该如何去实现呢？对于const迭代器的写法，会有以下误写！
第一种错写：直接在使用的迭代器前加个const，如下：
这个是我们自己写的，基于普通迭代器，然后使用的时候，加const
这样写是不行的！因为const迭代器中的const是用于保护指向的对象不被修改，迭代器本身可以被修改。因此，上面这种情况，会让迭代器本身，即it不能被修改，如果不能被修改，那么还怎么去访问数据？即迭代器it不能++往后走了！
第二种错写：在普通迭代器的类里面，加上成员函数的const版本：
这种错误，是建立在第一种错误之上的！如果我们这样子实现const迭代器后，在使用两种迭代器的时候，const迭代器的使用依然是这样子使用：
const list<int>::iterator it = lt.begin();
我承认，此时，const迭代器对象去解引用的时候，确实是会调用const版本的operator*()，而普通迭代器对象解引用的时候，也是去调用普通版本的operator*()。但是，重点是const版本迭代器不能++，即不能往后走！又回到了第一种错误身上！我们的const迭代器，是只读不写，如果不能让const迭代器++往后走，如何去读？难道实现一个const版本的operator++()吗？那么请operator++()这个函数接口，可以去实现const吗？显然是不行的！
正确的写法：
我们可以单独实现一个const版本的迭代器的类，只需要把operator*()变成const版本，然后其它的不变即可，接着begin()和end()也实现一个const版本即可！这样的话就能明确我们写的迭代器是const版本还是普通版本，然后去调用相应的接口函数。
但是捏，这种想法有个很明显的不好——代码冗余！解决办法就是传多个模板参数！
然后在list类里面，分别重命名两种迭代器，这种做法的本质就是复用代码，实际上是两种类！比如T的类型是int，当使用const_iterator,那么T和Ref就会推演成int和const int&，如果是普通迭代器，那么就会推演成int和int&。
template<classT,classRef>struct__list_iterator { typedefListNode<T>node; typedef__list_iterator<T, Ref>Self; node*_pnode; __list_iterator(node*p) :_pnode(p) {} Refoperator*() { return_pnode->_data; } T*operator->() { return&_pnode->_data; } //++it 前置++Self&operator++() { _pnode=_pnode->_next; return*this; } //it++ 后置++Selfoperator++(int) { Selftmp(*this); _pnode=_pnode->_next; returntmp; } booloperator!=(constSelf&it) const { return_pnode!=it._pnode; } booloperator==(constSelf&it) const { return_pnode==it._pnode; } //--it 前置--Self&operator--() { _pnode=_pnode->_prev; return*this; } //--it 后置--Selfoperator--() { Selftmp(*this); _pnode=_pnode->_prev; returntmp; } };
那么，此时begin()和end()当然也要重载一份const版本的出来！
const_iteratorbegin() const { returnconst_iterator(_head->_next); } const_iteratorend() const { returnconst_iterator(_head); }
上面代码完善了以下所需的接口。其中的operator->()需要额外说明一下：
调用这个函数，返回的是数据的地址，比如数据是一个日期的数据，那就是返回Date*，但当我们去调用这个函数并且取其数据的时候，按道理来说，因为会有两个箭头：
第一个箭头，表示的是这个数据的的指针，第二个箭头是原生指针，表示的是解引用后的这个数据本身。
it->->year,it->->month,it->->day
但实际上我们在写的时候却不是这样，我们只需要写一个箭头即可，因为编译器为了可读性，做了特殊的处理，省略掉了一个箭头。
如果一个const迭代器对象使用operator->()并且试图对数据进行修改，我们发现确实被修改了，原因是T* operator->()是普通迭代器的版本，因此，我们需要再额外加一个模板参数，去分成const版本和普通版本！
此时，就完成了我们模拟实现list中，迭代器的最终版
template<classT,classRef,classPtr>struct__list_iterator { typedefListNode<T>node; typedef__list_iterator<T, Ref,Ptr>Self; node*_pnode; __list_iterator(node*p) :_pnode(p) {} Refoperator*() { return_pnode->_data; } Ptroperator->() { return&_pnode->_data; } //++it 前置++Self&operator++() { _pnode=_pnode->_next; return*this; } //it++ 后置++Selfoperator++(int) { Selftmp(*this); _pnode=_pnode->_next; returntmp; } booloperator!=(constSelf&it) const { return_pnode!=it._pnode; } booloperator==(constSelf&it) const { return_pnode==it._pnode; } //--it 前置--Self&operator--() { _pnode=_pnode->_prev; return*this; } //--it 后置--Selfoperator--() { Selftmp(*this); _pnode=_pnode->_prev; returntmp; } };
总结反思
list和vector的对比：
list和vector，说白了，就是链表跟顺序表这两兄弟的对比，这对活宝很幽默，对方的缺点是自身的优点，对方的优点是自身的缺点，有时候我们会突然区分不清他们的优缺点，因此来总结一下下！
vector的优点：
①下标的随机访问
②尾插尾删比list的效率高
③CPU高速缓冲命中率高。
这三点都是结构的优点！
vector的缺点：
①随机插入或删除数据效率低O(N)
②扩容有消耗，还存在一部分的空间浪费，因此扩两倍或1.5倍是比较合适的，扩容多了会浪费，少了还得再次扩容。
list的优点：
①按需申请释放，无需扩容
②任意位置插入删除，时间复杂度是O(1)
list的缺点：
①不支持下标随机访问
②CPU高速缓冲命中率低
使用情况：
如果大量数据需要在中间（反正不是头和尾）插入删除的时候，就用list，如果是大量在头和尾插入或删除就用vector。
迭代器失效总结
vector的迭代器失效是在insert和erase，即插入和删除数据都有可能导致迭代器失效，因为位置发生了变化。
list的迭代器失效是在erase，即删除节点的时候会导致迭代器失效，因为迭代器指向的节点被删除了。
解决的方法是更新迭代器，即返回迭代器的位置。
而对于string类。string的迭代器也会失效，跟vector类似，但是一般不会去关注string迭代器失效问题。因为vector和list的insert和erase接口，参数给的是迭代器，而string常用的给的是下标，迭代器支持的用得很少。
| vector | list | |
| 底 层 结 构 | 动态顺序表，一段连续空间 | 带头结点的双向循环链表 |
| 随 机 访 问 | 支持随机访问，访问某个元素效率O(1) | 不支持随机访问，访问某 效率O(N) |
| 插 入 和 删 除 | 任意位置插入和删除效率低，需要搬移元素，时间复杂 度为O(N)，插入时有可能需要增容，增容：开辟新空 间，拷贝元素，释放旧空间，导致效率更低 |
任意位置插入和删除效率 需要搬移元素，时间复杂 O(1) |
| 空 间 利 用 率 | 底层为连续空间，不容易造成内存碎片，空间利用率 高，缓存利用率高 |
底层节点动态开辟，小节 造成内存碎片，空间利用 缓存利用率低 |
| 迭 代 器 | 原生态指针 | 对原生态指针(节点指针)进 |
| 迭 代 器 失 效 | 在插入元素时，要给所有的迭代器重新赋值，因为插入 元素有可能会导致重新扩容，致使原来迭代器失效，删 除时，当前迭代器需要重新赋值否则会失效 |
插入元素不会导致迭代器 删除元素时，只会导致当 器失效，其他迭代器不受 |
| 使 用 场 景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不 机访问 |
