STL库中list的迭代器实现痛点分析

前文

本篇文章准备换个模式，之前都是先详解模拟实现，但是模拟实现的基本逻辑大多数老铁都是明白的，所以我们这次主要讲解STL库中list的独特性，也就是模拟实现中的重难点
文末有模拟实现的源码

一，list实现的特殊类

list实现和前面vector，string最大的区别莫过于单独封装了迭代器。
我们通常使用的迭代器分为两种：1.原生指针作为迭代器。如vector，string。2.自定义类型对原生指针进行封装，模拟指针的行为。如list。

vector：

list:

在list中，我们对原生指针进行封装，模拟指针的行为，因此我们需要在该类中实现*(),->,前置++,后置++，前置--，后置--，!=,==等函数重载

这时候可能有的老铁对，迭代器模板中三个模板参数感到惊讶，下面我们就来讲解一下。

二，迭代器模板中的多个模板参数

如图，迭代器模板参数中定义了三个模板参数，这是为什么呢？要注意这里是list中模板非常非常巧妙的一种用法。
第一个T就不用多说了，和vector中的模板参数意义一样。我们重点说第二和第三个.

2.1 Ref模板参数

Ref模板参数的产生主要是因为*()操作符重载

在实际的应用中，我们的list可能会被const修饰，导致里面的值只能读取不能修改，而如果用第一个模板参数我们则无法实现 const修饰返回值，因此我们专门写了第二个模板参数Ref来应对这种情况。

如上图所示，右边const修饰的list其中的值无法改变，我们会直接调用const_iterator迭代器进行模板实例化，这样Ref的值就为const T&,至此，我们就借助了第二个模板参数实现了正常迭代器和const修饰的迭代器的区分.

2.2 Ptr模板参数

Ptr模板参数是专门给->操作符重载准备的.

没有Ptr的话应该是这样

我们多一个模板参数的原因和Ref的原因一样，都是为了应对list被const修饰无法改变的情况

但是list迭代器中->操作符重载有一个重要的特性。如下所示

图中第313行和314行代码不一样但执行效果却一样，为什么呢？
根据语法，313行想访问_a1，应该这样写it->->_a1，但it->_a1却也可以，为什么呢？
这是因为在这里我们为了增强可读性，省略了一个->。

三，源码

#pragma once
#include <iostream>
#include <assert.h>
using namespace std;
namespace mjw
{template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;list_node(const T& val=T()):_prev(nullptr),_next(nullptr),_data(val){}};template<class T,class Ref,class Ptr>struct _list_iterator{typedef list_node<T> node;typedef _list_iterator<T, Ref,Ptr> iterator;node* _node;_list_iterator(node* n):_node(n){}//*()重载Ref operator*(){return _node->_data;}//->重载T* operator->(){return &_node->_data;}//前置++iterator& operator++(){_node = _node->_next;return *this;}//后置++iterator operator++(int){iterator tmp(*this);_node = _node->_next;return tmp;}//前置--iterator& operator--(){_node = _node->_prev;return *this;}//后置--iterator operator--(int){iterator tmp(*this);_node = _node->_prev;return tmp;}//!=重载bool operator!=(const iterator ls){return _node != ls._node;}//==重载bool operator==(const iterator ls){return _node == ls._node;}};template<class T>class list{public:typedef list_node<T> node;typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&,const T*> const_iterator;void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}//构造list(){empty_init();}//区间构造//先初始化，然后一个一个尾插template<class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);++first;}}void swap(list<T>& tmp){std::swap(_head, tmp._head);}//拷贝构造list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(),lt.end());swap(tmp);}//赋值list<T>& operator=(list<T> lt){swap(lt);return *this;}//析构~list(){delete _head;_head = _head->_next = _head->_prev = nullptr;}//clearvoid clear(){iterator cur = begin();while (cur != end()){erase(cur++);}}//begin()iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}//end()iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}//尾插void push_back(const T& val){/*node* newnode = new node(val);node* next = _head;node* prev = _head->_prev;newnode->_next = next;newnode->_prev = prev;prev->_next = newnode;next->_prev = newnode;*/insert(end(), val);}//尾删void pop_back(){erase(--end());}//头插void push_front(const T& val){insert(begin(), val);}//头删void pop_front(){erase(begin());}void insert(iterator pos, const T& val){node* newnode = new node(val);node* next = pos._node;node* prev = next->_prev;newnode->_next = next;newnode->_prev = prev;prev->_next = newnode;next->_prev = newnode;}//为了防止迭代器失效，返回要删除的迭代器的下一个数据iterator erase(iterator pos){assert(pos._node != _head);node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;pos._node = nullptr;return iterator(next);}private:node* _head;};}