一、部分代码展示
#pragma once
#include<cassert>
namespace bit
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _data;ListNode(const T& val = T()):_prev(nullptr), _next(nullptr), _data(val){}};// 迭代器// 添加Ref Ptr是为了const迭代器能复用配普通迭代器代码template<class T, class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node):_node(node){}// 迭代器不能写析构，因为资源不是迭代器的，迭代器只是用来遍历的// *it 返回值（类）的引用//T& operator*()Ref operator*(){return _node->_data;}// it-> 返回值（类）的指针//T* operator->()Ptr operator->(){return &_node->_data;}// ++itSelf& 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;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};// const迭代器//template<class T>//struct ListConstIterator//{// typedef ListNode<T> Node;// typedef ListConstIterator<T> Self;// Node* _node;// ListConstIterator(Node* node)// :_node(node)// {}// // *it// const T& operator*()// {// return _node->_data;// }// // it->// const T* operator->()// {// return &_node->_data;// }// // ++it// 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;// }// bool operator!=(const Self& it)// {// return _node != it._node;// }// bool operator==(const Self& it)// {// return _node == it._node;// }//};// 链表template<class T>class list{typedef ListNode<T> Node;typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;public:void emptyinit(){_size = 0;_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){emptyinit();}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}list(const list<T>& l){emptyinit();for (auto& e : l){push_back(e);}}void swap(list<T>& l){std::swap(_head, l._head);std::swap(_size, l._size);}list<T>& operator=(list<T> l){swap(l);return *this;}~list(){clear();delete _head;_head = nullptr;}iterator begin(){return iterator(_head->_next);}iterator end(){// 匿名构造return iterator(_head);}// const iterator代表迭代器不能被修改，无法++ -- T* const p1// 后面加const代表迭代器指向的内容不能修改 const T* p2 const_iterator begin() const{return iterator(_head->_next);}const_iterator end() const{// 匿名构造return iterator(_head);}void insert(iterator pos, const T& val){Node* newnode = new Node(val);Node* cur = pos._node;Node* prev = cur->_prev;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;prev->_next = newnode;_size++;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->_prev;Node* next = cur->_next;prev->_next = next;next->_prev = prev;delete cur;_size--;return iterator(next);}void push_front(const T& val){insert(begin(), val);}void push_back(const T& val){insert(end(), val);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}size_t size() const{return _size;}bool empty(){return _size == 0;}private:Node* _head;size_t _size;};
}二、细节
1、成员变量
实现的是带头双向循环的链表，所以节点的定义是有前后指针和数据的。链表里面包含了头节点。
2、迭代器
链表的迭代器是非常重要的，因为与 string 和 vector 不同的是链表的存储空间是不连续的，所以迭代器不再是指针，而是一个节点。需要单独写一个迭代器的类。
我们对于迭代器的成员函数其实很熟悉，无非是重载 ++ -- * == !=
所以重点是如何实现普通迭代器和 const 迭代器。
const 迭代器是指向的内容不能改变，即成员函数的返回值是 const，那就一定要写两个类吗？
其实不用，类模板就可以定义两个不同的返回值
template<class T, class Ref, class Ptr>Ref 是引用，即返回迭代器指向数据的引用。
Ptr 是指针，即返回迭代器指向数据的指针。
这样 const 迭代器就可以复用普通迭代器的代码。
而且迭代器的类不能写析构，迭代器只是用来遍历的，不是用来操作数据的
三、list 迭代器失效问题
1、插入
插入不会迭代器失效，因为地址依然存在，没有对迭代器和迭代器的内容改变。
2、删除
删除依然会失效，因为迭代器指向的数据和空间都没了，解决办法就是返回一个新的迭代器，是删除节点的下一个节点的迭代器。
