list的模拟实现

一.list的简单介绍

list是一个带头双向循环的链表，通过头结点分隔开首末尾。它和vector的使用方法类似，可以进行头插尾插，++/--等操作，区别在于list的结点在内存上不是连续的。list属于双向迭代器即可以++/--，不能想vector一样可以进行随机访问。

二.list模拟实现的三个类

1.结点类

根据list的特点带头双向循环，我们可以得知，他需要一个前置结点prev，以及后置结点next，保证能向前向后找到结点。 每个结点存有数据data，我们可以用模板T来进行复用。

template <class T>struct list_node{list_node(const T& x = T())//模板有x时情况:_next(nullptr),_prev(nullptr),_data(x){}list_node<T>* _next;list_node<T>* _prev;T _data;};

 2.迭代器类

我们知道迭代器分为普通迭代器和const迭代器，在实现string类和vector类时我们并没有单独对迭代器这一类进行实现，这是因为vector和string类在底层空间上是连续的，可以直接进行++/--，解引用操作。但list在底层中是由指针来连接的，所以直接++/--解引用无法实现我们想要的效果。所以我们要单独提出迭代器对++/--解引用进行重载运算符操作。

template<class T, class Ref, class Ptr>
struct list_iterator
{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}T& operator*(){return _node->_data;}T& operator++()//前置{_node = _node->_next;return *this;}T& operator++(int)//后置,后置++区分前置要加入括号{Self tmp(*this);_node = _node->_next;return tmp;}T& operator--()//前置{_node = _node->_prev;return *this;}T& operator--(int)//前置{Self tmp(*this);_node = _node->_prev;return tmp;}T* operator->(){return &_node->_data;}bool operator!=(const T& it){return _node != it._node;}bool operator==(const T& it){return _node == _it._node;}
};

如上我们对迭代器进行了初步的实现，里面的实现内容较为简单就不一一展开叙述。这时候又有了另一个问题，如果迭代器是const类型的该怎么办呢？还是像上面这样，重新封装一个const_iterator类吗？

这样操作固然是没有问题的，但是还不够简略。

我们可以仔细想想，普通迭代器与const迭代器的区别不就是多了一个const吗？所以我们可以考虑用模板来套用实现。

	template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Self& operator++()//前置{_node = _node->_next;return *this;}Self operator++(int)//后置,后置++区分前置要加入括号{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--()//前置{_node = _node->_prev;return *this;}Self operator--(int)//前置{Self tmp(*this);_node = _node->_prev;return tmp;}Ptr operator->(){ return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == _it._node;}};

我们将原先的T&  用模板Ref来替代，T*  用模板Ptr来代替。这样就对代码进行了缩减。所以用ref和ptr模板我们就不需要关心是不是const类型迭代器，只要传就是什么，我们就无需关心。 

3.链表类

template <class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return list_iterator(_head->_next);}iterator end(){return list_iterator(_head);}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}list(){empty_init();}list(initializer_list<T> it){for (auto& e : it){push_back(e);}}list(const list<T>& it){empty_init();for (auto& e : it){push_back(e);}}~list(){clear();}void swap(list<T>& it){std::swap(_head, it._head);}list<T>& operator=(list<T> it){swap(it);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;newnode->_prev = tail;tail->_next = newnode;newnode->_next = _head;_head->_prev = newnode;}void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){insert(end(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* nextNode = cur->_next;Node* prevNode = cur->_prev;prevNode->_next = nextNode;nextNode->_prev = prevNode;delete cur;return iterator(nextNode);}private:Node* _head;};
}

上述只需要注意一点，就是erase的用法。erase在官方库中是有返回值的，在使用时，例如析构时需要用变量来接收erase的返回值，否则容易导致迭代器失效。

链表部分的实现不难，基本都是先前vector类实现的功能相差无几，构造函数，拷贝函数，析构函数，迭代器的运用，以及增删等操作。

 三.总结

本篇文章最关键的内容就是对于模板的复用，在面对代码相似度较高，实现功能类似的情况下，我们需要优先考虑模板的复用。

下面放上完整代码：

#pragma once
#include <iostream>
using namespace std;namespace wu
{template <class T>struct list_node{list_node(const T& x = T())//模板有x时情况:_next(nullptr),_prev(nullptr),_data(x){}list_node<T>* _next;list_node<T>* _prev;T _data;};template<class T,class Ref,class Ptr>//提供模板参数，为const类型提供模板参数,ref代替引用，ptr代替*，复用struct list_iterator{typedef list_node<T> Node;typedef list_iterator<T, Ref, Ptr> Self;Node* _node;list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_data;}Self& operator++()//前置{_node = _node->_next;return *this;}Self operator++(int)//后置,后置++区分前置要加入括号{Self tmp(*this);_node = _node->_next;return tmp;}Self& operator--()//前置{_node = _node->_prev;return *this;}Self operator--(int)//前置{Self tmp(*this);_node = _node->_prev;return tmp;}Ptr operator->(){ return &_node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == _it._node;}};template <class T>class list{typedef list_node<T> Node;public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return list_iterator(_head->_next);}iterator end(){return list_iterator(_head);}void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;}list(){empty_init();}list(initializer_list<T> it){for (auto& e : it){push_back(e);}}list(const list<T>& it){empty_init();for (auto& e : it){push_back(e);}}~list(){clear();}void swap(list<T>& it){std::swap(_head, it._head);}list<T>& operator=(list<T> it){swap(it);return *this;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prev;newnode->_prev = tail;tail->_next = newnode;newnode->_next = _head;_head->_prev = newnode;}void push_front(const T& x){insert(begin(), x);}void push_back(const T& x){insert(end(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_prev = prev;cur->_prev = newnode;newnode->_next = cur;}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* nextNode = cur->_next;Node* prevNode = cur->_prev;prevNode->_next = nextNode;nextNode->_prev = prevNode;delete cur;return iterator(nextNode);}private:Node* _head;};
}