list库实现

list库实现的要点：

构建list类时，需要同时构建struct Node来存储节点信息，list类中只存储哨兵位节点信息，迭代器类需要template<T,Ptr,Ref>来构建const和非const迭代器，迭代器中也是存储节点信息。反向迭代器也是同样道理，但是可以用迭代器来构建反向迭代器。具体代码如下 

#include<iostream>
#include<assert.h>
#include<algorithm>
using namespace std;template<class T>
struct __list_node
{__list_node(const T& val = T()):_data(val),_prev(nullptr),_next(nullptr){}__list_node* _prev;__list_node* _next;T _data;
};//构建每个节点//构建迭代器struct
template<class T, class Ptr, class Ref>
struct __list_iterator
{typedef __list_node<T> Node;typedef __list_iterator<T, Ptr, Ref> Self;Node* _node;//成员变量还是节点，只是在成员函数做手脚__list_iterator(Node* val ):_node(val){}Self& operator++(){_node = _node->_next;return *this;}Self operator++(int)//后置{Self tmp = *this;++(*this);return tmp;}Self& operator--(){_node = _node->_prev;return *this;}Self operator--(int){Self tmp = *this;--(*this);return tmp;}Ptr operator->(){return &(_node->_data);}Ref operator*(){return _node->_data;}bool operator!= ( const Self& val ){return !(_node == val._node);}};
template<class T,class Ptr,class Ref>
struct __list_reverse_iterator
{typedef __list_iterator<T, T*, T&> iterator;typedef __list_reverse_iterator<T, T*, T&> Self;iterator _it;__list_reverse_iterator(iterator it):_it(it){}Self operator++(){_it = _it._node->_prev;return *this;}T& operator*(){return _it._node->_data;}bool operator!=(const Self& rit){return !(_it._node == rit._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;typedef __list_reverse_iterator<T, T*, T&> reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(--end());}reverse_iterator rend(){return reverse_iterator(end());}iterator begin(){return iterator(_phead->_next);}const_iterator begin()const{return const_iterator(_phead->_next);}iterator end(){return iterator(_phead);}const_iterator end()const{return const_iterator(_phead);}list()//开头空间，初始化{_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;}~list(){clear();delete _phead;_phead = nullptr;}//拷贝构造(先创建一个哨兵位，然后再pushback)list(const list<T>& l){_phead = new Node;_phead->_next = _phead;_phead->_prev = _phead;for (auto& x : l){push_back(x);}}list<T>& operator=(const list<T>& l){list<T> tmp(l);swap(_phead, tmp._phead);return *this;}//尾插入void push_back(const T& val){//Node* tail = _phead->_prev;//Node* newnode = new Node(val);更变链接//tail->_next = newnode;//newnode->_prev = tail;//newnode->_next = _phead;//_phead->_prev = newnode;insert(end(), val);}//头插void push_front(const T& val){insert(begin(), val);}//头删除void pop_front(){erase(begin());}//尾删除void pop_back(){erase(--end());}//清空节点(除了哨兵位，都清除)void clear(){iterator it = begin();while (it != end()){it = erase(it);}}//随机插入void insert(iterator pos, const T& val){Node* pcur = pos._node;Node* prev = pcur->_prev;Node* newnode = new Node(val);//构建联系newnode->_prev = prev;newnode->_next = pcur;prev->_next = newnode;pcur->_prev = newnode;}//删除指定位置(不能将哨兵位删掉！！iterator erase(iterator pos){assert(pos != end());Node* pcur = pos._node;Node* prev = pcur->_prev;Node* next = pcur->_next;delete pcur;pcur = nullptr;prev->_next = next;next->_prev = prev;return iterator(next);}private:Node* _phead;
};