————————————————————
list与vector相比，插入、删除等操作实现的成本非常低，如果在C语言阶段熟悉理解过链表，那么现在实现起来list就显得比较简单，可以说操作层面上比vector更简洁，因为list没有扩容这个繁琐而耗时的操作，就不需要实现reserve函数了，

唯一的难点在于实现链表遍历，当然这里说得不是像C语言下通过原生节点跳转遍历，而是采用迭代器遍历。

STL中所有的容器都采用迭代器++ or --的方式进行访问，对于string和vector来说，迭代器是非常好理解的，得益于string和vector的物理存储空间连续，迭代器可以视作原生指针。

But，对于链表而言，每一个节点的位置都是随机存储的，如果还是使用原生节点去访问，那么势必为出现野指针导致访问权限冲突的问题。故而需要借助类和模板进行封装模拟原生指针的效果。

故而可以 得出：STL中的迭代器可以分为两类
1、原生指针
2、模拟指针效果的对象

因此文章主要谈论list迭代器的模拟实现，具体代码请参考gitee仓库👇

https://gitee.com/chxchenhaixiao/test_c/blob/master/List/List/list.h

首先需要定义节点的结构，数值+前驱指针+后继指针的结构体

template<typename T>
struct list_node{T _data;list_node<T>* _next;		//带上<T>才是一个类型噢list_node<T>* _prev;list_node(const T& val= T()):_next(nullptr),_prev(nullptr){_data=val;}
}

其次需要实现list的主题框架，我们所实现的是双向带哨兵位循环链表

template<typename T>
class list{
private:typedef list_node<T> node;	//内部typedef，方便起见node* _head;		//_head是哨兵位节点
public:list(){_head = new node;_head->_prev=_head->_next=_head;}void push_back(const T& val = x){node* new_node = new node(x);new_node->_prev = _head->_prev;_head->_prev->_next=new_node;new_node->_next = _head;_head->_prev=new_node;}//此处非最优版本，只是为了后续方便测试
}

现在我声明了一个list< int > 类型的 lst 对象，并对它进行尾插操作，使得lst存有整型数据1，2，3，4

现在需要遍历链表，就要去定义迭代器iterator

so，我们开始遍写迭代器

template<typename T>
struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T> self;node* _node;_list_iterator(node* val):_node(val){}T& operator * (){return _node->_data;}self& operator ++(){_node=_node->_next;return *this;}self& operator --(){_node=_node->_prev;return *this;}bool operator !=(const self& val)const{return _node!=val._node;}

其实这就是对原生指针的一个封装

接着，我们自然而然会想到，既然已经实现了迭代器，那么我们遍历的时候肯定要通过迭代器类型去访问，则就需要在list类中补充返回迭代器类型的成员函数begin和end

template<typename T>
class list{
private:typedef list_node<T> node;	//内部typedef，方便起见node* _head;		//_head是哨兵位节点public:typedef _list_iterator<T> iterator;	//typedef _list_iterator<T,T&> iterator;	//typedef _list_iterator<T,const T&> cosnt_iterator;list(){_head = new node;_head->_prev=_head->_next=_head;}iterator begin(){return iterator(_head->_next);}	//哨兵位下一个节点才是第一个数据iterator end(){return iterator(_head);}void push_back(const T& val = x);
}

这样就可以实现一个普通list对象的遍历了，
目前还欠缺的是const list对象的遍历实现，因此还需要补充const迭代器，const迭代器的写法可以说是照抄普通迭代器的写法了，但是为了代码变得更为简洁，可以在定义迭代器类型的时候多设置一个模板参数，变成
template<typename T,typename Ref> //Ref指引用

而list中的typedef语句可以更新为
typedef _list_iterator<T,T&> iterator;
typedef _list_iterator<T,const T&> cosnt_iterator;

list类中增设成员函数

	const_iterator begin(){return const_iterator(_head->_next);}const_iteraotr end(){return const_iterator(_head);}

到这里为止，迭代器基本上已经是大致功能健全了，list的大部分操作借助我们定义的迭代器可以说说非常容易了，这里就不做过多展开。

最后，为了方便读者更好理解，文末献上模板实例化的过程：