list的结构，比我们之前说的string和vector都要复杂的多，那么现在我们就来详细了解一下list的结构组成并且尝试实现它
1.list的结构
首先来看一下list的框架结构，list在底层上是一个带头双向循环链表，所以对于整体框架的设计就已经很明确了。这里我们使用一个命名空间将我们实现的list包起来
namespace zht { template<class T> class list//这是一个list类，其中的成员变量只有一个头节点。 { typedef __list_node<T> node; public: typedef __list_iterator<T> iterator;//普通迭代器 //typedef __list_const_iterator<T> const_iterator;//const迭代器 private: node* _head; }; }
这里简单搭了个list的框架，但是现在的list还不足以跑起来，下面我们实现一些接口让这个类能够跑起来。
❓为什么list节点的类不是用class修饰而是用struct？
✅struct和class修饰的区别就是成员的默认属性是公有还是私有，在这里我们需要能够在命名空间内都能访问到__list_node中的成员变量，所以推荐使用struct(使用class然后将成员变量和成员函数使用public修饰也可以)。
push_back接口和默认构造的简易实现
这里为了能够尽快的让我们的list跑起来，我们先简易的实现两个必须的接口。push_back接口，后面可以直接复用insert即可
list() { _head = new node;//创建头节点 //头节点首尾相连 _head->_next = _head; _head->_prev = _head; } void push_back(const T& val = T()) { node* newnode = new node(val);//创建一个新节点 //将节点连接到list上 node* tail = _head->_prev; //head <=> tail <=> newnode <=> tail->_next = newnode; newnode->_prev = tail; newnode->_next = _head; _head->_prev = newnode; }
2.迭代器的简单设置
迭代器按照功能分类
- 单项迭代器：例如单链表，只支持++，不支持–
- 双向迭代器：例如list，支持++和–
- 随即迭代器：例如vector，支持++和–，也支持+ 和 -。
迭代器的行为有以下几种:
- 能够通过*解引用拿到容器内的指定元素
- 能够++或–改变迭代器的指向
那么，针对迭代器的行为，我们发现，对于string和vector，原生指针就能够很好的支持迭代器行为，所以在SGI版本的STL库中，就是用原生指针实现的迭代器，但是，对于list的结构来说，原生指针已经不能满足迭代器的行为了。所以我们封装了一个迭代器的类来使用，这就是我们之前说的迭代器有指针，但是不全是指针实现的。
对应到上文中迭代器功能，我们需要实现的是双向迭代器，那么，针对迭代器行为，我们尝试写出一个迭代器类
template<class T> struct __list_iterator { typedef __list_node<T> node;//重命名节点类 node* _pnode;//迭代器的成员变量就是结点指针 __list_iterator(node* p)//迭代器的构造函数 :_pnode(p) {} T& operator*()//重载*，作用是返回指向的节点的元素值 { return _pnode->_data; } __list_iterator<T>& operator++()//重载++，作用是将迭代器自增1 { _pnode = _pnode->_next; return *this; } bool operator!=(const __list_iterator<T>& it) { return _pnode != it._pnode; } }; //list模板类中 iterator begin() { return _head->_next; } iterator end() { return _head; }
到现在，已经能够让这个搭起来的简易的list跑起来啦，这样我们对后续实现的list就可以调试查看是否实现功能。
void Test1() { list<int> lt; lt.push_back(1); lt.push_back(2); lt.push_back(3); lt.push_back(4); lt.push_back(5); list<int>::iterator it = lt.begin(); while (it != lt.end()) { cout << *it << " "; ++it; } cout << endl; }
3. 迭代器类详细实现
在上面，我们简易的实现了一个迭代器的基本功能，但是还非常简陋，他甚至不能支持const迭代器。
首先我们现在的目标就是这么实现const迭代器。
const迭代器与普通迭代器的区别就是const迭代器对通过迭代器拿到的数据有限制
❓问题：
const list<T> iterator it是不是const迭代器，为什么？✔不是，const修饰的是it，而不是it指向的对象，所以，使用上述的const修饰方式不能满足迭代器的行为，是不合理的。
所以，这种偷懒的方式实现const迭代器是不行的。
那么，正常情况下，我们能想到的方法是什么？
当然是再实现一个const_iterator类
template<class T> struct __list_const_iterator { typedef list_node<T> node; node* _pnode; __list_const_iterator(node* p) :_pnode(p) {} const T& operator*() { return _pnode->_data; } __list_const_iterator<T>& operator++() { _pnode = _pnode->_next; return *this; } bool operator!=(const __list_const_iterator<T>& it) { return _pnode != it._pnode; } };
可以发现，这种方式的实现除了返回的类型与普通迭代器不同之外，其余的所有内容完全相同，这样看起来就很冗余。这种冗余对于大佬们来说当然是不能忍受的，所以我们去看看在标准库中是怎么解决这个问题的。
哦~，原来大佬用到了模板，哇趣，这么妙的用法，这就是我跟大佬的区别吗。同样的语法基础，大佬能想到的使用方式，我们想不到。
这就是我们学习STL，深究它的源码的原因，我们并不是为了造一个更好的轮子，而是为了学习大佬们的编程思想，看他们对一些问题的解决，在我们之后遇到类似问题的时候，能够想到类似的解法
所以对于迭代器类的实现，我们就可以写出以下代码
template<class T, class Ref> struct __list_iterator { typedef __list_node<T> node;//重命名节点类 typedef __list_iterator<T, Ref> Self; node* _pnode;//迭代器的成员变量就是结点指针 __list_iterator(node* p)//迭代器的构造函数 :_pnode(p) {} Ref operator*()//重载*，作用是返回指向的节点的元素值 { return _pnode->_data; } Self& operator++()//重载++，作用是将迭代器自增1 { _pnode = _pnode->_next; return *this; } Self operator++(int) { Self tmp(*this); _pnode = _pnode->_next; return tmp; } Self& operator--() { _pnode = _pnode->_prev; return *this; } Self operator--(int) { Self tmp(*this); _pnode = _pnode->_prev; return tmp; } bool operator!=(const Self& it) { return _pnode != it._pnode; } bool operator==(const Self& it) { return _pnode == it._pnode; } };
至此，我们算是实现了支持一般迭代器行为的list迭代器了。但是我们看下面一段代码
void Test2() { typedef pair<int, int> Pos; list<Pos> lt; Pos pos(3, 3); lt.push_back(pos); lt.push_back(pos); lt.push_back(pos); lt.push_back(Pos(2, 4)); list<Pos>::iterator it = lt.begin(); while (it != lt.end()) { cout << (*it).first << ':' << (*it).second << endl; ++it; } cout << endl; }
这里对于迭代器的使用，感觉有点生硬了，按理来说，迭代器的行为是和指针类似的，参照类内成员的使用，我们是不是可以重载一个->运算符？答案是肯定的，并且，在库里也是实现了的。这也就是我们之前看到库里面的迭代器类为什么有三个模板参数的原因
在迭代器类中支持->运算符的使用
指针运算符的本质是通过指针访问到结构体内部的成员变量的地址，所以我们的实现->的方法也就显而易见了
Ptr operator->() { return &(operator*()); //return &(_pnode->_data);//当然也可以采用这种方式，本质上是一样的 }那么我们对上面示例代码的迭代器使用的语句就可以简化一下，这里为了方便理解，我们首先使用显示调用运算符重载的方式看一下这个函数调用到底是啥样的
//写法一 //写法二 //写法三 it.operator->()->first ==> it->->first ==> it->first其实，写法二
it->->first是一个错误的语法，按照底层的实现来说，是正确的，但是为了方便使用者，所以做了优化，优化掉一个->符号，所以在实现的时候就认定写法二是错误的，否则将会影响编译器识别。如下图，可以看到编译器将写法二识别成语法错误。
至此，我们的迭代器类就已经实现了，在list类中的迭代器的一些接口在这里就不赘述了，和string，vector是一样的，如果有需要可以去看一下博主的【C++】string类的模拟实现和【C++】vector的简化模拟实现。
最后，附上迭代器类的完整源码：
//list的迭代器类 template<class T, class Ref, class Ptr> struct __list_iterator { typedef __list_node<T> node;//重命名节点类 typedef __list_iterator<T, Ref, Ptr> Self; node* _pnode;//迭代器的成员变量就是结点指针 __list_iterator(node* p)//迭代器的构造函数 :_pnode(p) {} Ptr operator->() { return &operator*(); } Ref operator*()//重载*，作用是返回指向的节点的元素值 { return _pnode->_data; } Self& operator++()//重载++，作用是将迭代器自增1 { _pnode = _pnode->_next; return *this; } Self operator++(int) { Self tmp(*this); _pnode = _pnode->_next; return tmp; } Self& operator--() { _pnode = _pnode->_prev; return *this; } Self operator--(int) { Self tmp(*this); _pnode = _pnode->_prev; return tmp; } bool operator!=(const Self& it) { return _pnode != it._pnode; } bool operator==(const Self& it) { return _pnode == it._pnode; } };
