本次所需实现的三个类及其成员函数接口总览
//链表的节点
struct list_node
{list_node* _next;list_node* _prev;T _val;
};
//链表的迭代器类
template<class T,class Ref,class ptr>
struct list_iterator
{typedef list_iterator<T,Ref,ptr> self;typedef list_node<T> Node;Node* _node;
}
//链表
template<class T>
class list
{typedef list_node<T> Node;
public://显示实例化typedef list_iterator<T, T&, T*> iterator;typedef const list_iterator<T, const T&, const T*> const_iterator;
private：
Node*_head;
结点类的模拟实现
我们经常说list在底层实现时就是一个链表，更准确来说，list实际上是一个带头双向循环链表。
因此，我们若要实现list，则首先需要实现一个结点类。而一个结点需要存储的信息有：数据、前一个结点的地址、后一个结点的地址，于是该结点类的成员变量也就出来了（数据、前驱指针、后继指针）。
节点类的实现：
template <class T>
struct list_node
{list_node* _next;list_node* _prev;T _val;list_node(const T& val=T()):_next(nullptr),_prev(nullptr),_val(val){}
};
迭代器类的实现
之前我们在实现string,vector的时候我们迭代器都没有都是他们的原生指针，在这边为什么要封装成一个类呢？首先string,vector他们本质上是一个数组，在空间上是连续的，我们指针++一个以后就到了下一个元素的位置。因此我们可以使用原生指针来实现。
链表的迭代器实现，首先我们得知道我们遍历链表的时候通常是cur->next;cur++是不能实现的，因为链表在空间上不是连续的。我们需要使用运算符重载来给它封装起来，使他在上层看起来使用是一样的
struct list_iterator
{typedef list_iterator<T,Ref,ptr> self;typedef list_node<T> Node;Node* _node;list_iterator(Node*node):_node(node){}bool operator!=(self it){return _node != it._node;}bool operator==(self it){return _node == it._node;}Ref operator*(){return _node->_val;}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->_val;}};
list的模拟实现
默认成员函数
构造函数
list是一个带头双向循环链表，在构造一个list对象时，直接申请一个头结点，并让其前驱指针和后继指针都指向自己即可。
class list
{typedef list_node<T> Node;
public://显示实例化typedef list_iterator<T, T&, T*> iterator;typedef const list_iterator<T, const T&, const T*> const_iterator;list(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}void clear(){list<T>::iterator it = begin();while (it != end()){it = erase(it);}}size_t size(){list<T>::iterator it = begin();size_t count = 0;while (it != end()){count++;++it;}return count;}//现代写法list<T>&operator=(list<T>lt){swap(lt);return *this;}void push_back(const T& val){Node* newnode = new Node(val);Node* tail = _head->_prev;tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;}iterator insert( iterator pos,const T& val){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(val);prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;return newnode;}void push_front(const T val){insert(begin(), val);}void swap(list<T>& lt){std::swap(_head, lt._head);}iterator erase( iterator pos){assert(pos != end());Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;cur = nullptr;return next;}void pop_front(){erase(begin());}void pop_back(){erase(--end());}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}private:Node* _head;
};