众所周知，C++给我们底层搬砖人提供了很多便捷的数据结构，让我们能偶尔偷懒，list就是其中之一，现在让我们来了解一下它吧
一，原理
1）底层大致结构
list底层是由带头双向链表构成的，带头即带哨兵位，双向就是可以从前往后遍历也可从后往前遍历。那这个时候就有人好奇哨兵位指向前一个结点的指针指向哪里？最后一个结点的next指针指向哪里？答案是哨兵位的prv指针指向最后一个结点，最后一个结点的next则指向哨兵位。
2）迭代器
大家有没有发现一个问题，底层是链表，链表的地址是随机的，那迭代器的++不是有问题吗？这是当然的，所有我们需要单独处理迭代器，无法像vector一样的直接++就可拿到下一个元素的地址，那我们应该怎么解决呢？答案是将迭代器单独写一个类，对++，--，等函数进行重载，封装之后就可利用链表里面的指针拿到下一个或者上一个元素的地址，同时begin（）和end()返回的就应该是这个迭代器类。
3）模板
因为要适配各种元素，所有这里必须使用模板。而模板的加入必然会让底层的难度和结构更加复杂，同时我们要考虑迭代器类也要加模板以此来适配各种类。
二，模拟源码
1）链表结点
我们要分析链表里面的结构，我们要从需求出发，里面需要什么，首先两个链表指针分别指前和指后，还有应该模板元素用于存储使用者的值，构造函数用于调用初始化，而析构函数建议交给list类。
template<class T> struct ListNode { ListNode(const T& val = T()): _pPre(nullptr), _pNext(nullptr), _val(val) {} ListNode<T>* _pPre;//指向前一个结点 ListNode<T>* _pNext;//指向后一个结点 T _val; //真正存储的有效值 };
2）list类部分
首先我们要考虑，list的私有成员是什么？那肯定是结点啊，从前面的描述可知，list底层结构是带头双向链表，因此私有成员应该是哨兵位指针，由于我们会使用Node* 很多次，因此我们命名为PNode，增加可读性。这里面唯一值得我们注意的就是end（）和begin()函数，因为链表底层是不连续的地址，因此我们要将迭代器及其操作封装，begin和end就应该返回被包装的类。还有麻烦的一点就是有些函数需要提供const版本，防止调用的时候找不到匹配的函数。其余的可以按照数据结构链表的基础来写，如果有不懂的可以看我以往的数据结构初阶博客。
//list类 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; public: /// // List的构造 list() { CreateHead(); } list(int n, const T& value = T()) { CreateHead(); for (int i = 0; i < n; ++i) push_back(value); } template <class Iterator> list(Iterator first, Iterator last) { CreateHead(); while (first != last) { push_back(*first); ++first; } } list(const list<T>& l) { CreateHead(); // 用l中的元素构造临时的temp,然后与当前对象交换 list<T> temp(l.cbegin(), l.cend()); this->swap(temp); } list<T>& operator=(const list<T> l) { this->swap(l); return *this; } ~list() { clear(); delete _pHead; _pHead = nullptr; } /// // List 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); } /// // List Capacity size_t size()const { size_t size = 0; ListNode *p = _pHead->_pNext; while(p != _pHead) { size++; p = p->_pNext; } return size; } bool empty()const { return size() == 0; } // List Access T& front() { assert(!empty()); return _pHead->_pNext->_val; } const T& front()const { assert(!empty()); return _pHead->_pNext->_val; } T& back() { assert(!empty()); return _pHead->_pPre->_val; } const T& back()const { assert(!empty()); return _pHead->_pPre->_val; } // List Modify void push_back(const T& val) { insert(end(), val); } void pop_back() { erase(--end()); } void push_front(const T& val) { insert(begin(), val); } void pop_front() { erase(begin()); } // 在pos位置前插入值为val的节点 iterator insert(iterator pos, const T& val) { PNode pNewNode = new Node(val); PNode pCur = pos._pNode; // 先将新节点插入 pNewNode->_pPre = pCur->_pPre; pNewNode->_pNext = pCur; pNewNode->_pPre->_pNext = pNewNode; pCur->_pPre = pNewNode; return iterator(pNewNode); } // 删除pos位置的节点，返回该节点的下一个位置 iterator erase(iterator pos) { // 找到待删除的节点 PNode pDel = pos._pNode; PNode pRet = pDel->_pNext; // 将该节点从链表中拆下来并删除 pDel->_pPre->_pNext = pDel->_pNext; pDel->_pNext->_pPre = pDel->_pPre; delete pDel; return iterator(pRet); } void clear() { iterator p = begin(); while(p != end()) { p = erase(p); } _pHead->_pPrev = _pHead; _pHead->_pNext = _pHead; } void swap(List<T>& l) { pNode tmp = _pHead; _pHead = l._pHead; l._pHead = tmp; } private: void CreateHead() { _pHead = new Node; _pHead->_pPre = _pHead; _pHead->_pNext = _pHead; } PNode _pHead; }; }
3）迭代器类
当然，我们首先考虑的还是私有成员，私有成员应该是链表结点，结点不一定是哨兵位，可能是任何一个结点，因为迭代器可以指向任何一个元素，然后就要对迭代器的操作符重写，手动进行地址的加减或者解引用，其中值得人注意的是->操作符重写，很多人可能好奇为什么返回的是结点地址，因为其实a->其实是等价于&a->->，我们返回这个地址便于我们拿到私有成员进行操作。最难理解的一个点是为什么要提供一个ListIterator<T, Ref, Ptr> 的构造函数，因为ListIterator类的模板定义中，有三个模板参数：T, Ref, 和 Ptr。这三个参数是为了提供更大的灵活性和控制。
//List的迭代器类 template<class T, class Ref, class Ptr> class ListIterator { typedef ListNode<T>* PNode; typedef ListIterator<T, Ref, Ptr> Self; public: ListIterator(PNode pNode = nullptr):_pNode(pNode) {} ListIterator(const Self& l): _pNode(l._pNode) {} T& operator*() { return _pNode->_val; } T* operator->() { return &*this; } Self& operator++() { _pNode = _pNode->_pNext; return *this; } Self operator++(int) { Self temp(*this); _pNode = _pNode->_pNext; return temp; } Self& operator--() { _pNode = _pNode->_pPre; return *this; } Self& operator--(int) { Self temp(*this); _pNode = _pNode->_pPre; return temp; } bool operator!=(const Self& l) { return _pNode != l._pNode; } bool operator==(const Self& l) { return !(*this!=l); } private: PNode _pNode; };
