实现思路
List是一个类模板，实际上是一个双向循环链表。在上一篇list基本使用的博客中，可以发现list支持了像vector一样的"下标访问"，也就是通过迭代器区间去访问链表的每个节点数据。本人在初学阶段也是比较好奇——list的迭代器（正向与反向）是如何实现的；本篇博客将以自己所掌握的知识，详细的介绍list是如何实现的。
list实现结构：
1.节点设计
2.正向迭代器设计
3.反向迭代器设计
4.list各个接口完善（增删查改）
一、list的节点设计
list本身和list的结点是两个不同的结构，需要分开设计。以下是list的节点结构：
/*ListNode.h*/ namespace mlg { template<class T> struct ListNode { ListNode<T>* _prev; //节点的前指针 ListNode<T>* _next; //节点的后指针 T _data; //节点的数据 ListNode(const T& data= T())//初始化列表进行初始化 :_prev(nullptr) ,_next(nullptr) ,_data(data) {} }; }
首先，我们在自己的命名空间内模拟实现list（为了防止与库冲突），上面的代码就是list节点的结构。在这里是用并没有使用class，因为struct默认访问权限是public，又因为节点是需要经常访问的，所以使用struct更好。
我们将这个类加上 template<class T> 后，就能够实现节点存储不同类型的数据，这也是C++模板的好处。
二、list的初步框架
当我们设计好了list的结点以后，我们就需要对list的基本框架进行设计，list要能够去控制这些节点，它的成员变量就必须是这个节点类；以下是list的结构设计：
/*List.h*/ namespace mlg //命名空间保持一致 { template<class T> //list是一个类模板，设计时需要这个 class list { typedef ListNode<T> Node; //将其类型重命名方便书写，在后续的类型中会有比较多的typedef public： /* 成员函数包含了默认成员函数、迭代器和增删查改 */ private: Node* _head; //带头结点的双向循环链表 }; }
在以上两个基本的框架搭建完毕以后，接下来重点主要是正向与反向迭代器
三、list的正向迭代器设计
1.实现原理
list的确是支持了迭代器，但是list不在能够像vector一样以普通的指针作为迭代器，因为其节点不保证在存储空间中连续。list的迭代器必须有能力指向list的节点，并有能力进行递增、递减、取值、成员存储等操作。如何具备这样的能力呢？那就是递增时指向下一个结点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员；
2. 正向迭代器的结构
/*iterator.h*/ namespace mlg { template<class T,class Ref,class Ptr> struct __list_iterator { typedef ListNode<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; //迭代器构造函数 __list_iterator(Node* x) :_node(x) {} //重载*号 —— 实现解引用操作 Ref operator*() { return _node->_data; } //重载->操作符 —— 实现指针访问元素 Ptr operator->() { return &_node->_data; } //++it 重载前置++ —— 让链表能够像数组一样去++操作，访问元素 self& operator++() { _node = _node->_next;//前置++返回的是++之后的值，直接让当前位置的结点指向下一个节点 return *this; } //it++ 重载后置++ —— （这里需要加上int作为一个站位符，与前置++区分） self operator++(int) { self tmp(*this); _node = _node->_next;//后置++返回的是++之前的值，需要保存当前节点，再指向下一个节点 return tmp; } //--it 重载前置-- —— 让链表能够像数组一样去--操作，访问元素 self& operator--() { _node = _node->_prev;//前置--返回的是--之后的值，直接让当前位置的结点指向前一个节点 return *this; } //it-- 重载后置-- ——（这里需要加上int作为一个站位符，与前置--区分） self operator--(int) { self tmp(*this); _node = _node->_prev;//后置--返回的是--之前的值，需要保存当前节点，再指向下一个节点 return tmp; } //重载== bool operator==(const self& it)const { return _node == it._node; } //重载!= bool operator!=(const self& it)const { return _node != it._node; } }; }
在上述代码中，有三个地方没有做解释：
1. template<class T,class Ref,class Ptr>
2. typedef __list_iterator<T, Ref, Ref> self;
它是迭代器类模板，里面包含了三个参数：T、Ref、Ptr；这三个参数表明传给iterator类的类型是不确定的，需要根据实际的情况，将这三个参数匹配到相应的地方。
如：
1. ++/--操作：返回的是一个对象，只要用到了对象，一般都是写成__list_iterator<T, Ref, Ref>，因为类名太长，就有了第2点的typedef __list_iterator<T, Ref, Ref> self;
2. operator* 操作：返回的是对象的数据的值，并且*号是具有读写操作的，我们应该返回的是这个数据类型的引用（T&）；
3. operator->操作：返回的是对象的数据的地址，我们应该返回的是这个数据类型的地址（T*）；
--------------------------------------------------------------------------------------------------------------------------
3. typedef ListNode<T> Node;
Node* _node;
iterator类中的成员变量也是节点，我们刚刚已经解释了list迭代器的原理，它是通过重载++ / --,其内部实现上是节点中的_prev指针（找当前节点的前一个位置，相当于--操作）和_next指针（找当前节点的下一个位置，相当于++操作）的操作来实现的；
所以，list正向迭代器的实现，本质上是用节点的两个指针的操作来代替了传统的++/--操作。再简单点说，其实就是函数调用（包括*/->）
四、list反向迭代器的设计
1.实现原理
我们刚刚对list正向迭代器做了介绍以后，你是否会想，反向迭代器也是同样的原理呢？确实可以这样理解，但是中间还有一个过程，我们先通下面的图解了解一下双链表（list）中和数组（vector）中正向迭代器与反向迭代器的区别。
vector迭代器的位置不需要多说，对于list的迭代器：begin( )是数据的起始位置，end( )是数据的结束位置，也就是头结点；反向迭代器不就是与之相反嘛。
那如何才能通过反向迭代器控制链表的++/--等一系列操作呢？
方法一：我们可以重新写一个，也通过节点的指针去控制（比较麻烦：如果我想用正向迭代器区获取某个节点的位置传个反向迭代器，就需要给反向迭代器增设正向迭代器的接口）
方法二：反向迭代器通过正向迭代器去间接控制list节点，达到想要的效果（在SLT原码中是这样子实现的，其目的是能适应其他容器，其称之为迭代器适配器）
2.反向迭代器的结构
/*reverse_iterator.h*/ namespace mlg { template<class Iterator,class Ref,class Ptr> class __list_reverse_iterator { typedef __list_reverse_iterator<Iterator, Ref, Ptr> self; public: //反向迭代器构造函数（通过正向迭代器去构出造反向迭代器） __list_reverse_iterator(Iterator it) :_it(it) {} //重载* Ref operator*() { Iterator prev = _it; //获取正向迭代器end()的位置 return *--prev; //返回的是当前位置执行前置--操作后的解引用 } //重载-> Ptr operator->() { return &operator*(); //调用上面一个重载函数 } //++it self& operator++() { --_it; //反向迭代器的前置++就是调用正向迭代器的前置-- return *this; // } //it++ self operator++(int) { self tmp(*this); //后置++返回的是++之前的，所有先记录当前正向迭代器的位置 _it--; //反向迭代器的后置++就是调用正向迭代器的后置-- return tmp; } //--it self& operator--() { ++_it; //反向迭代器的前置--就是调用正向迭代器的前置++ return *this; } //it-- self operator--(int) { self tmp(*this); //后置--返回的是--之前的，所有先记录当前正向迭代器的位置 _it++; //反向迭代器的后置--就是调用正向迭代器的后置++ return tmp; } //重载!= bool operator!=(const self& rit)const { return _it != rit._it; } //重载== bool operator==(const self& rit)const { return _it == rit._it; } private: Iterator _it;//成员变量是一个正向迭代器 }; }
1.反向迭代器的 ++ / -- 操作解析
//++it self& operator++() { --_it; //调用正向迭代器的前置-- return *this; } //it++ self operator++(int) { self tmp(*this); _it--; //调用正向迭代器的后置-- return tmp; }
通过上图可以发现：
1.反向迭代器++（前置/后置）：调用正向迭代器的--
2.反向迭代器--（前置/后置）：调用正向迭代器的++
2.反向迭代器的 * / -> 操作解析
//重载* Ref operator*() { Iterator prev = _it; //获取正向迭代器end()的位置 return *--prev; //返回的是当前位置执行前置--操作后的解引用 } //重载-> Ptr operator->() { return &operator*(); //调用上面一个重载函数 }
对于->的重载，只要去复用就可以了。
