一、部分代码展示

#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、删除

删除依然会失效，因为迭代器指向的数据和空间都没了，解决办法就是返回一个新的迭代器，是删除节点的下一个节点的迭代器。