注意事项
list是需要模版来实现的容器，所以申明与定义必须处于同一文件下，否则会出现：
“error: undefined reference to `...`”错误
原因：模版函数调用需要实例化，而实例化需要看到定义，但如果定义放在其它文件（比如.cpp），在其它文件中，这个函数仍然是未实例化的模版，既然没有实例化，就没有机器码，没有机器码就会链接失败。
list的节点类
（注意：我们这里实现的是双向循环链表。）
list的节点类我们使用struct来封装，而非class，好处在于struct默认public。
list的节点类中包含前驱指针，后驱指针这些后面会频繁访问的成员，由于class默认是private，而struct的特点就能省去很多麻烦，这也是二者唯一的区别。
构造函数我们需要写两个版本，一个数据构造和无参构造，原因在于list是有头节点的，而头结点通常不存储数据。
为了不与标准库冲突，建议使用自己的命名域封装一下，具体代码如下：
//list的节点类 template<class T> struct ListNode { //数据节点构造 ListNode(const T& x) :_pPre(nullptr) ,_pNext(nullptr) ,_val(x) { } //头节点构造 ListNode() :_pPre(nullptr) , _pNext(nullptr) { } ListNode<T>* _pPre; //前驱指针 ListNode<T>* _pNext; //后驱指针 T _val; };list的迭代器类
list的迭代器实现起来与vector有很大不同，我们先把申明贴过来，再一一说明。
template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; PNode _pNode;//指向节点的指针 ListIterator(PNode pNode = nullptr);//构造 ListIterator(const Self& l);//拷贝构造 Ref operator*();//取值 Ptr operator->();//访问成员 Self& operator++();//前置++ Self operator++(int);//后置++ Self& operator--();//前置-- Self operator--(int);//后置-- bool operator==(const Self& l);//等于 bool operator!=(const Self& l);//不等于 };Ref与Ptr
首先，先说明参数中，Ref和Ptr的含义。
简单来说，如果T是int，那么Ref就是int&，Ptr就是int*，它们分别代表一种返回类型，即引用类型和指针类型。
那为何不直接使用T&和T*？
原因在于，T&和T*无法传递const属性，Ref和Ptr可以。比如，如果你想使用一个只读的迭代器：
const list<int> cv = {1,2,3}; auto it = cv.begin(); // 是 const_iterator，只读 *it = 5;但T*这种写法无法传递const属性，到最后begin仍然被修改为5，但Ref就不会发生这种错误。
有人可能会觉得，我另外写一个const T& operator*()和const T* operator->()的版本，重载*和->不就行了？
但问题是这两个版本的重载签名完全相同，你不能塞到同一个struct里，如果你执意这么写，最后你就要写两份迭代器struct，而二者大多功能完全相同，没必要这样。
operator*和operator->
在具体实现中，重载*和->的函数必须是const修饰的成员函数。
原因在于我们需要适应一个场景：迭代器对象本身是const类型，需要const类型的operator来接收。
const cIt = l.begin() //const类型的迭代器 *cIt;//需要const类型的operator*具体来说：
我们说的const_iterator 和 const iteraator不是同一个东西。
前者的迭代器类型是非const，对operator没要求，它只是指向的list的元素不可修改，这个情况通过Ref和Ptr已经解决，而后一个是迭代器本身就是const，本身就不可修改，所以需要const类型operator才能适应。
operator!=和operator==
重载等于和不等于时，也有需要注意的地方。
具体而言这两个需要除了也是const成员，还有一个要求就是，它们需要再套一个模版。
原因在于，C++标准库中，这两个允许不同类型的迭代器进行比较，为了适应这个场景，我们必须单独给这两个函数的第二个操作数套一个模版。
具体代码
其它的功能基本上没什么坑，大家自己看看代码就行。
template<class T, class Ref, class Ptr> struct ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; PNode _pNode;//指向节点的指针 ListIterator(PNode pNode = nullptr) : _pNode(pNode) {}//构造 ListIterator(const Self& l) : _pNode(l._pNode) {}//拷贝构造 Ref operator*() const { return _pNode->_val; }//取值 Ptr operator->() const { return &_pNode->_val; }//访问成员 Self& operator++() { _pNode = _pNode->_pNext; return *this; }//前置++ Self operator++(int) { Self tmp = *this; _pNode = _pNode->_pNext; return tmp; }//后置++ Self& operator--() { _pNode = _pNode->_pPre; return *this; }//前置-- Self operator--(int) { Self tmp = *this; _pNode = _pNode->_pPre; return tmp; }//后置-- template <class Ref2, class Ptr2> bool operator==(const ListIterator<T, Ref2, Ptr2>& l) const { return _pNode == l._pNode; }//等于 template <class Ref2, class Ptr2> bool operator!=(const ListIterator<T, Ref2, Ptr2>& l) const { return _pNode != l._pNode; }//不等于 };list类
基本框架
首先需要写好两种迭代器的两个版本。
_pHead指向哨兵节点，_size是节点个数。
template<class T> class list { typedef ListNode<T> Node; typedef Node* PNode; public: typedef ListIterator<T, T&, T*> iterator; typedef ListIterator<T, const T&, const T*> const_iterator; iterator begin() { return iterator(_pHead->_pNext); } iterator end() { return iterator(_pHead); } const_iterator begin() const { return const_iterator( _pHead->_pNext); } const_iterator end() const { return const_iterator(_pHead); } private: PNode _pHead; size_t _size; }注意迭代器同样遵循“左闭右开”的原则，所以end（）是返回哨兵节点。
构造，拷贝构造，析构，赋值重载
双向循环链表的默认构造需要产生一个自环的哨兵节点，析构则是要先实现clear()清空list，最后delete哨兵节点。注意clear清空list后要让剩下的哨兵节点自环。
赋值重载和拷贝构造一般都是先实现了push_back后再回来复用实现会比较好，但是赋值拷贝最好的写法是使用copy-and-swap办法。
我们先实现一个成员swap，交换两个list的_pHead和_size，再将operator=的参数改为传值拷贝，把参数list和this交换，最后返回this即可。
void swap(list& l) { std::swap(_pHead, l._pHead); std::swap(_size, l._size); }//构造 list() :_pHead(new Node) ,_size(0) { _pHead->_pNext = _pHead->_pPre = _pHead; } list(const list& l) :_pHead(new Node) ,_size(0) { _pHead->_pNext = _pHead->_pPre = _pHead; for (auto& x : l) { push_back(x); } } void clear() { PNode cur = _pHead->_pNext; while (cur != _pHead) { PNode next = cur->_pNext; delete cur; cur = next; } _pHead->_pNext = _pHead->_pPre = _pHead; _size = 0; } //析构 ~list() { clear(); delete _pHead; } //赋值拷贝 list& operator=(list l) { swap(l); return *this; }增删查改
这里主要包括insert，push_back, push_front, erase，pop_back, pop_front。
我们可以先实现insert和erase，其它的只需复用即可。
insert需要传入插入位置的迭代器和需插入的数据，然后返回插入后该节点的迭代器，逻辑就是普通的双向链表插入。
iterator insert(iterator pos,const T& x) { PNode n = new Node(x); n->_pNext = pos._pNode; n->_pPre = pos._pNode->_pPre; pos._pNode->_pPre->_pNext = n; pos._pNode->_pPre = n; _size++; return iterator(n); }void push_back(const T& x) { insert(end(), x); } void push_front(const T& x) { insert(begin(), x); }然后是erase。
iterator erase(iterator pos) { PNode prev = pos._pNode->_pPre, next = pos._pNode->_pNext; prev->_pNext = next; next->_pPre = prev; delete pos._pNode; _size--; return iterator(next); } iterator pop_back() { return erase(--end()); } iterator pop_front() { return erase(begin()); }还有各种访问器，例如size()返回有效节点个数，front()和back()分别返回第一个与最后一个节点的引用, 以及判空empty()。
这些的逻辑都比较简单。不过需要注意的是，front和back需要实现const的版本。
size_t size() const { return _size; } bool empty() const { return _size == 0; } T& front() { return begin()._pNode->_val; } const T& front() const { return begin()._pNode->_val; } T& back() { return (--end())._pNode->_val; } const T& back() const { return (--end())._pNode->_val; }list与vector的比较
从使用场景的角度来看，list适用于需要频繁插入删除的场景，而vector适用于需要高效存储，支持随机访问的场景。
