list模拟实现

list原理讲解

在C++中SGI版本的STL中的list容器是用带头双向循环链表来实现的；
那么什么是带头双向循环链表？
如下图：

该链表有一个head头节点，该节点不存储任何有效数据！仅用于链接第一个有效节点和最后一个有效节点；head的前一个节点就是该链表的最后一个有效节点，head的后一个节点，就是该链表的第一个有效节点！
只要我们能够找到head节点，我们就能找到整条带头双向循环链表！
使用该结构存储数据的话，插入和删除数据都非常的快，时间复杂度为O(1)
相比于前面的vector来说vector的插入和删除数据效率都比较低！当我们需要进行大量的插入和删除数据的时候我们可以考虑使用list数据结构！

节点结构

该节点，有数据域和指针域，其中数据域专门用来存储数据，指针域细分的话，又有两个指针域：前指针域（用于存储前一个节点的指针）、后指针域（用于存储后一个节点的指针）；
因此我们可以这样设置节点数据结构：

//节点template <class T>struct list_node{T _date;list_node<T>* _prev;list_node<T>* _next;list_node(const T& val = T())//这里可以考虑使用缺省参数；//由于模板的出现，这就要求了对于内置类型必须提供构造函数，不然的话对于这种情况const T& val = T()我们无法处理，因为我们不知道T的具体类型是什么，无法准确的给缺省值！同时const引用可以延长匿名对象的生命周期，直到引用所在作用域销毁:_date(val), _prev(nullptr), _next(nullptr) {}};

我们可以用一个模板来写一个节点数据结构，因为节点的数据域可以存储任何类型的数据，同时我们可以为该节点提供一个构造函数，方便后续向节点插入数据的需求！
同时这里我们用了struct来创建节点类，不用class，是因为struct创建的类的默认权限是public更为方便我们后续的操作，class创建的类的默认权限是private的，当我们将类内部的成员全部放开时，我们可以利用struct来创建类！当然也可以用class，只不过这时候我们需要加上public访问限定符！

list类设计

list类也应该成一个模板类，因为list可以插入任何类型的元素！

template <class T>
{
public:
private:
//list的成员我们可以设计为一个list_node<T>*的指针
//该指针用于存储带头双向循环链表的head节点；
//只要我们找到了head节点，我们就能找到整条链表！
//list_node<T> * _head;//当然这里我们可以考虑typedef一下list_node<T>，毕竟这个类型太长了，写起来比较麻烦，当然我们也可以不typedef，直接使用原生类型
typedef list_node<T> node;
node*_head;
}

既然list类成员已经设计出来了，那么我们现在就创建一个带头双向循环链表来玩一玩；
首先要有一个带头双向循环链表，我们就得现有一个head节点，方便我们list对于整条链表的管理；
因此我们的构造函数可以写成：

list()
{
_head=new node;//创建一个头节点
_head->_prev=_head->_next=_head;//让其头节点的_next指针和_prev指针都指向自己，因为现在一个元素也没有，_head的下一个节点就是自己，_head的前一个节点也是自己
}

push_back

在上面，我们已经实现出list的一个简单无参构造函数,我们现在就有了_head节点，我们现在就只需要插入元素了，对于插入元素来说很简单：

要实现尾插，就需要找到最后一个一个节点，那么最后一个节点在哪里？
_head->_prev不就是最后一个节点嘛，最后在将new_node节点的_next域链接向_head节点，_head的_prev域链接向new_node节点就可以了；

void push_back(const T&val)
{node*new_node=new node(val);node*tail=_head->_prev;//尾节点tail->_next=new_node;new_node->_prev=tail;new_node->_next=_head;_head->_prev=new_node;
}

Iterators:

现在我们已经可以向list里面插入元素了，但是我们想打印一下list元素，以此来检查一下我们push_back的正确性！
为此我们就要遍历整个链表,遍历的话我们就需要迭代器，可是现在有个问题，我们应该拿什么作为迭代器呢？
原生的节点指针(list_node<T>*)吗?

如果是这样的话,那么迭代器该如何往后迭代呢?要知道迭代器只允许使用++、–等迭代方式，是不允许->这样的迭代方式的，但是我们使用++、–等方式对我们的迭代器进行迭代的话，我们能保证it++就是下一个节点的指针吗？这显然是无法保证的，因为节点与节点之间都是不连续的，it++自然也就无法保证++过后就一定是下一个节点的指针！但凡list的结构是类似于vector、string的连续空间我们都可以使用原生指针来充当迭代器！但对于list不行，因此list中使用原生指针作为迭代器的想法被直接pass掉！
那么有没有什么既可以指向对应节点，同时又能使用++、–来进行迭代的东西呢？

当然有，我们可以对原生指针进行封装！封装成一个类，让这个类充当迭代器，然后在这个类内部重载++、–等运算符，以此来实现迭代器的迭代；

事不宜迟，咱们现在就来干一个:

template <class T//元素类型>
struct _list_iterator
{			//用于初始化迭代器_list_iterator(list_node<T>* node=nullptr):_node(node){}//由于_list_iterator<T> 这个迭代器类型使用起来比较麻烦，有需要大量的使用，我们这里解直接typedef一下；typedef _list_iterator<T> self;//self就表示迭代器的类型，本质还是_list_iterator<T>//开始重载++、--、*、!=等运算符self&operator++()//前置++{assert(_node);//防止_node为nullptr，避免出现这种情况：_list_iterator it;//此时it会调用无参构造，_node会被初始化成nullptr，这时候如果再使用++it就会对nullptr解引用，会崩溃_node=_node->_next;return *this;}self operator++(int)//后置++{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构++(*this);return tmp;}T& operator*()//对迭代器解引用，返回数据域的值{assert(_node);return _node->_date;}bool operator!=(const self&it)//两个迭代器之间进行比较{//这也是迭代器继续迭代比较运算符//对于list这类迭代器，就不在适合使用>、<等运算符进行比较了，因为节点不是连续的return _node!=it._node;}self&operator--()//前置--{assert(_node);_node=_node->_prev;return *this;}self operator++(int)//后置--{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构--(*this);return tmp;}//成员变量list_node<T> *_node;//用于存储当前迭代器所迭代的位置	
}

实现了迭代器，我们就可以在list类内部使用了，不过我们需要先将我们实现的迭代器的名字在list类内部typedef一下，因为STL的所有容器的迭代器都是iterator，这算是一种默认的规范！
在list内部加上:

typedef _list_iterator<T> iterator;

begin与end

有了迭代器在list内部的begin与end函数就可以写了

iterator begin()
{
return iterator(_head->_next);
}
iteratro end()
{
return iterator(_head);
}

const对象的迭代器

我们上面实现的迭代器，还是有缺陷的，比如上面的begin与end我们只是实现了普通list对象，对于const对象也无法调用begin、end，换而言之const不能使用迭代器进行迭代，只有普通list对象可以；
那么有读者就说，const对象调不了，begin、end是因为begin、end的this指针权限过大，我们在重载一个const对象的begin、end不就好了：

iterator begin()const
{
return iterator(_head->_next);
}
iteratro end()const
{
return iterator(_head);
}

嗯，这样的话const对象确实能够进行迭代了，可是新问题又来了，(*迭代器)的时候，也能改变迭代器所指节点的值！因为operator*（）的返回值是T&，嗯？？？这似乎与我们的预期相违背了，const对象的值怎么能通过迭代去修改呢？我们必须解决这个问题；
我们可以不可在普通迭代器前面加个const来充当const对象的迭代器呢？
比如：

typedef _list_iteratro iterator;
//iterator不是普通对象的迭代器嘛
//那么const对象的迭代器可不可以是:
typedef const _list_iteratro const_iterator;
//const _list_iteratro 来充当const对象的迭代器？
//答：不可以！！！如果我们这样做了的话，我们迭代器本身就无法完成迭代了！
//迭代器本身都无法完成迭代，那还叫个屁的迭代器！
//这就好比，int a=10;与const int b=10；
//a可以实现++、--，但是b就不可以！

怎么解决呢？
1、重新为const对象协议一个迭代器，其中operator*（）的返回值设置为const T &;
2、按照方法1确实可以解决问题，可是太麻烦了，你看嘛我们const迭代器与普通对象的迭代器都需要实现++、–等迭代操作，但是这两个迭代器的唯一区别就是operator*()的返回值，const迭代器是const T& ,而普通迭代器是T& 二者之间就差一个const，要是我们能用一个“变量”来控制operator*的返回值就好了！
那么能不能实现呢？
当然可以，我们可以在_list_iterator模板参数列表，再添加一个参数Ref，以此来控制operator*（）的返回值，但我们给_list_iterator类模板传入不同的参数时，_list_iterator类模板就会给我们实例化出不同的具体类型！
因此我们的迭代器可以优化成：

template <class T,class Ref>
struct _list_iterator
{			//用于初始化迭代器_list_iterator(list_node<T>* node=nullptr):_node(node){}//由于_list_iterator<T> 这个迭代器类型使用起来比较麻烦，有需要大量的使用，我们这里解直接typedef一下；typedef _list_iterator<T,Ref> self;//self就表示迭代器的类型，本质还是_list_iterator<T,Ref>//开始重载++、--、*、!=等运算符self&operator++()//前置++{assert(_node);//防止_node为nullptr，避免出现这种情况：_list_iterator it;//此时it会调用无参构造，_node会被初始化成nullptr，这时候如果再使用++it就会对nullptr解引用，会崩溃_node=_node->_next;return *this;}self operator++(int)//后置++{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构++(*this);return tmp;}Ref operator*()//对迭代器解引用，返回数据域的值,根据Ref的不同，来决定operator\*()的返回值类型{assert(_node);return _node->_date;}bool operator!=(const self&it)//两个迭代器之间进行比较{//这也是迭代器继续迭代比较运算符//对于list这类迭代器，就不在适合使用>、<等运算符进行比较了，因为节点不是连续的return _node!=it._node;}self&operator--()//前置--{assert(_node);_node=_node->_prev;return *this;}self operator++(int)//后置--{assert(_node);self tmp(*this);//这里可以使用默认拷贝构造,因为在迭代器类中不会对节点进行析构--(*this);return tmp;}//成员变量list_node<T> *_node;//用于存储当前迭代器所迭代的位置	
}

这样的话，再list内部我们就需要重新实例化一下普通对象与const对象的迭代器了:

typedef _list_iterator<T,T&> iterator;//普通list对象的迭代器
typedef _list_iterator<T,const T&> const_iterator;//const对象的迭代器
//由于传递的模板参数不同，_list_iterator<class T,class Ref>会实例化出两份不同类型的迭代器！

重载->运算符

对于list迭代器来说，我们可以说是模拟原生指针的行为，比如(*迭代器)返回的就是节点数据域的值！
那么如果现在有一个结构体:

struct AA
{
int _a;
int _b;AA(int a=0;int b=0):_a(a),_b(b){}
}
int main()
{list<int> l1;l1.push_back(AA(1,2));list<int> :: iterator it=l1.begin();//正常写法://std::cout<<(*it)._a<<" "<<(*it)._b<<std::endl;//可是现在我们嫌弃上面那种方法比较麻烦，我们可不可以直接使用下面这种方法来实现呢？std::cout<<it->_a<<" "<<it->_b<<std::endl;//答案是可以的，因此在迭代器内部,我们需要重载->运算符；
}

迭代器内部重载->运算符

T*operator->()
{
return &_node->date;
}

我们只有实现了上诉部分的运算符重载，我们才能直接使用:

 std::cout<<it->_a<<" "<<it->_b<<std::endl;

语句；
可是我们仔细观察一下operator->的返回值就会发现很奇怪的地方，operator->的返回值是T*,那么正确访问_a成员的方式，不应该是:it->->_a 不应该是两个箭头吗？为什么这里只需要一个->就可以！这里的话就与重载->的特殊性有关了，建议观看大佬的这篇文章:C++箭头(->)重载函数这位大佬讲的很明白！
现在又有个问题，如果const对象的迭代使用operator->()函数的或是不是也会改变节点数据域的值？
因为operator->的返回值是T*，没有const限制！为此为了限制这一“漏洞”，我们可以效仿operator*()返回值的作法，在增加一个模板参数，那么_list_iterator就会被优化成：

template<class T,class Ref,class Ptr>
struct _list_iterator{_list_iterator(list_node<T>* node = nullptr):_node(node) {}typedef _list_iterator<T, Ref, Ptr > self;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp = *this;--*this;return tmp;}self operator++(int){self tmp = *this;++* this;return tmp;}bool operator!=(const self& it){return _node != it._node;}Ref operator*(){return _node->_date;}Ptr operator->(){return &_node->_date;}//成员list_node<T>* _node;};

在list内部，普通迭代器与const迭代器的原生类型就是：

typedef _list_iterator<T,  T&,  T*> iterator; //这是个普通对象的正向迭代器
typedef _list_iterator<T, const T&, const T*> const_iterator;//const对象的正向迭代器

反向迭代器

我们发现上面实现的迭代器，++操作就是向后迭代、–等操作就是向前迭代，妥妥的正向迭代器，可是反向迭代器嘞？
反向迭代器，也可以按照上面的方法来实现，只不过反向迭代器内部可以封装一个正向迭代器，正向迭代器的++就是反向迭代器的–；正向迭代器的–就是反向迭代器的++；

     //反向迭代器template<class Forward_iterators, class Ref, class Ptr>//Forward_iterators是个正向迭代器，那么到底是普通对象的正向迭代器还是const对象的正向迭代器，我们是未知的，全靠程序员利用该模板实例化的时候，给该模板参数传递的类型；Ref、Ptr与上面在正向迭代器中的意义一样struct _list_reverse_iterator{_list_reverse_iterator(const Forward_iterators& it= Forward_iterators()):_it(it) {}typedef _list_reverse_iterator<Forward_iterators, Ref, Ptr> Reself;//反向迭代器类型名字太长了，换个简短点的Reself& operator++()//前置{//正向迭代器的----_it;return *this;}Reself operator++(int)//后置{Reself tmp(_it);--_it;return tmp;}Reself& operator--()//前置{//正向迭代器的--++_it;return *this;}Reself operator--(int)//后置{Reself tmp(_it);++_it;return tmp;}Ref operator*(){return *_it;}Ptr operator->(){return _it.operator->();}bool operator!=(const Reself&rit){return _it != rit._it;}bool operator==(const Reself& rit){return _it==rit;}//成员是一个正向迭代器;Forward_iterators _it;};

因此在list内部的我们需要实例化一下普通对象的反向迭代器、和const对象的反向迭代器:

typedef _list_reverse_iterator<iterator, T&, T*> reverse_iterator;//普通对象反向迭代器
typedef _list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//const对象反向迭代器
//给_list_reverse_iterator<Forward_iterators ,Ref,Ptr>传递的模板参数不同，就能实例化出不同类型的反向迭代器；

迭代器所有代码

        iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator rend()const{return const_reverse_iterator(_head);}

迭代器总结

迭代器主要有两种形式：
1、迭代器要么就是原生指针；
2、迭代器要么就是自定义类型对原生指针的封装，模拟指针的行为；

constructor:

list这个容器，难点就在于迭代器，现在我们把迭代器给啃了，后面就好办了；
注意：在每次初始化list的时候都需要创建头节点，为此我们可以把创建头节点的操作封装在一个函数里面；
创建头节点：

void empty_init(){_head = new node;_head->_next = _head->_prev = _head;}

同时我们可以把该函数放在private作用域下，不对外开放！
无参构造:

list()
{empty_init();
}

有参构造(利用n个val来初始化)：

 list(int n, const T& val = T()){empty_init();for (int i = 0; i < n; i++){push_back(val);}}

区间构造(可以用任何容器的元素来进行构造，只要可以发生类型转换):

template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);first++;}}

拷贝构造：

list(const list<T>& l){//现代写法的拷贝构造empty_init();list<T> tmp(l.begin(),l.end());//先让tmp去调用区间构造创建一个带头双向双向循环链表//然后交换tmp对象中_head与*this对象中_head的值；//相当于让*this中的_head指向了tmp创建的带头双向循环链表//tmp中的_head指向*this创建的带头双向循环链表(只不过只有头而已！)；swap(tmp);}

clear

功能:清除所有节点，但是不清除头节点，让整个链表的size变为0；

	void clear(){iterator it = begin();while (it != end()){it=erase(it);}_head->_next = _head->_prev = _head;}

~list

析构函数与clear的功能类似，但是析构函数需要释放头节点：

~list(){clear();delete _head;_head = nullptr;}

front与back

获取头节点元素与尾节点元素

T& front(){assert(empty() == false);return _head->_next->_date;}const T& front()const{assert(empty() == false);return _head->_next->_date;}T& back(){assert(empty() == false);return _head->_prev->_date;}const T& back()const{assert(empty() == false);return _head->_prev->_date;}

insert与erase

	//insert过后的pos失效，返回新插入节点的迭代器iterator insert(iterator pos, const T& val){node* prev = pos._node->_prev;node* new_node = new node(val);prev->_next = new_node;new_node->_prev = prev;new_node->_next = pos._node;pos._node->_prev = new_node;return iterator(new_node);}//erase过后pos迭代器失效！返回原pos迭代器的下一个迭代器iterator erase(iterator pos){//不能删除_headassert(empty()==false);node* prev = pos._node->_prev;node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;pos = iterator(next);return pos;}

size与empty与swap

        size_t size()const{size_t count = 0;const_iterator cit = begin();while (cit++ != end())count++;return count;}bool empty()const{return (begin() == end());}void swap(list<T>&l1){std::swap(_head,l1._head);}

pop_back()

        void pop_back(){assert(empty()==false);erase(--end());}

总代码:

节点类

   namespace MySpace{//节点template <class T>struct list_node{T _date;list_node<T>* _prev;list_node<T>* _next;list_node(const T& val = T()):_date(val), _prev(nullptr), _next(nullptr) {}};}

正向迭代器类

namespace MySpace
{
//利用一个类来封装list_node<T>*//让这个类作为list<T>的迭代器,然后重载这个类的++、--、*就可以实现迭代器的通用迭代办法template<class T, class Ref, class Ptr>struct _list_iterator//正向迭代器，底层封装了list_node<T>*{_list_iterator(list_node<T>* node = nullptr):_node(node) {}typedef _list_iterator<T, Ref, Ptr > self;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp = *this;--* this;return tmp;}self operator++(int){self tmp = *this;++* this;return tmp;}bool operator!=(const self& it){return _node != it._node;}bool operator==(const self& it){return !(*this!=it);}Ref operator*(){return _node->_date;}Ptr operator->(){return &_node->_date;}//成员list_node<T>* _node;};
}

反向迭代器类

namespace MySpace
{
//反向迭代器template<class Forward_iterators, class Ref, class Ptr>struct _list_reverse_iterator{_list_reverse_iterator(const Forward_iterators& it= Forward_iterators()):_it(it) {}typedef _list_reverse_iterator<Forward_iterators, Ref, Ptr> Reself;//反向迭代器类型名字太长了，换个简短点的Reself& operator++()//前置{//正向迭代器的----_it;return *this;}Reself operator++(int)//后置{Reself tmp(_it);--_it;return tmp;}Reself& operator--()//前置{//正向迭代器的--++_it;return *this;}Reself operator--(int)//后置{Reself tmp(_it);++_it;return tmp;}Ref operator*(){return *_it;}Ptr operator->(){return _it.operator->();}bool operator!=(const Reself&rit){return _it != rit._it;}bool operator==(const Reself& rit){return _it==rit;}//成员是一个正向迭代器;Forward_iterators _it;};
}

list类

namespace MySpace
{
//带头双向循环链表template<class T>class list{public:typedef _list_iterator<T,  T&,  T*> iterator; //这是个普通对象的正向迭代器typedef _list_iterator<T, const T&, const T*> const_iterator;//const对象的正向迭代器typedef _list_reverse_iterator<iterator, T&, T*> reverse_iterator;//普通对象反向迭代器typedef _list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator;//const对象反向迭代器typedef list_node<T> node;//节点list(){empty_init();}list(int n, const T& val = T()){empty_init();for (int i = 0; i < n; i++){push_back(val);}}list(const list<T>& l){empty_init();list<T> tmp(l.begin(),l.end());swap(tmp);}template <class InputIterator>list(InputIterator first, InputIterator last){empty_init();while (first != last){push_back(*first);first++;}}~list(){clear();delete _head;_head = nullptr;}list<T>& operator=(list<T> l){if (this != &l){swap(l);}return *this;}void push_back(const T& val){node* tail = _head->_prev;node* new_node = new node(val);new_node->_prev = tail;tail->_next = new_node;new_node->_next = _head;_head->_prev = new_node;}void pop_back(){assert(empty()==false);erase(--end());}iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(_head->_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator rbegin()const{return const_reverse_iterator(_head->_prev);}const_reverse_iterator rend()const{return const_reverse_iterator(_head);}T& front(){assert(empty() == false);return _head->_next->_date;}const T& front()const{assert(empty() == false);return _head->_next->_date;}T& back(){assert(empty() == false);return _head->_prev->_date;}const T& back()const{assert(empty() == false);return _head->_prev->_date;}iterator insert(iterator pos, const T& val){node* prev = pos._node->_prev;node* new_node = new node(val);prev->_next = new_node;new_node->_prev = prev;new_node->_next = pos._node;pos._node->_prev = new_node;return iterator(new_node);}iterator erase(iterator pos){//不能删除_headassert(empty()==false);node* prev = pos._node->_prev;node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;pos = iterator(next);return pos;}size_t size()const{size_t count = 0;const_iterator cit = begin();while (cit++ != end())count++;return count;}bool empty()const{return (begin() == end());}void swap(list<T>&l1){std::swap(_head,l1._head);}void clear(){iterator it = begin();while (it != end()){it=erase(it);}_head->_next = _head->_prev = _head;}private:list_node<T>* _head;void empty_init(){_head = new node;_head->_next = _head->_prev = _head;}};
}