list的特性
STL中的list是指带头双向循环列表，list每个元素的存储相互独立，因为其节点存储位置独立不连续，其插入和删除不需要挪动其他元素效率比起vector更高。但也因为存储空间不连续的问题，不能做到和vector一样的随机访问。
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;};//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.getpNode();}//T& operator*();Ref operator*(){return _pNode->_val;}//T* operator->();Ptr operator->(){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;}bool operator!=(const Self& l){return _pNode != l.getpNode();}bool operator==(const Self& l){return _pNode == l.getpNode();}PNode getpNode()const{return _pNode;}private:PNode _pNode;};//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()){_size += n;CreateHead();PNode cur = _pHead;while (n--){PNode newnode = new Node(value);cur->_pNext = newnode;newnode->_pPre = cur;newnode->_pNext = _pHead;_pHead->_pPre = newnode;cur = cur->_pNext;}}template <class Iterator>list(Iterator first, Iterator last){Iterator cur = first;while (cur != last){push_back(cur.getpNode()->_val);cur++;}}list(const list<T>& l){CreateHead();for (auto& a : l){push_back(a);}}list<T>& operator=(const list<T> l){list<T> tmp(l);swap(tmp);}~list(){clear();delete _pHead;_pHead = nullptr;}///// List Iteratoriterator begin(){return _pHead->_pNext;}iterator end(){return _pHead;}const_iterator begin()const{return _pHead->_pNext;}const_iterator end()const{return _pHead;}///// List Capacitysize_t size()const{return _size;}bool empty()const{return _size == 0;}// List AccessT& front(){return _pHead->_pNext->_val;}const T& front()const{return _pHead->_pNext->_val;}T& back(){return _pHead->_pPre->_val;}const T& back()const{return _pHead->_pPre->_val;}// List Modifyvoid 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 newnode = new Node(val);PNode cur = pos.getpNode();PNode prev = cur->_pPre;newnode->_pNext = cur;cur->_pPre = newnode;prev->_pNext = newnode;newnode->_pPre = prev;_size++;return iterator(newnode);}// 删除pos位置的节点，返回该节点的下一个位置iterator erase(iterator pos){PNode cur = pos.getpNode();PNode prev = cur->_pPre;PNode next = cur->_pNext;prev->_pNext = next;next->_pPre = prev;delete cur;_size--;return iterator(next);}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void swap(list<T>& l){std::swap(_pHead, l.getpHead());std::swap(_size, l.size());}PNode getpHead()const{return _pHead;}private:void CreateHead(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPre = _pHead;_size = 0;}PNode _pHead;size_t _size;};迭代器失效问题
与vector不同，list插入时迭代器不会失效，因为节点相互独立的原因，所以list的插入不会改变其节点存储位置，如此一来迭代器的指向也不会有影响。
不过删除时仍会出现迭代器失效，迭代器指向的节点被删除时该迭代器失效（指向的节点失效，迭代器自然也就失效了），其余不受影响。
list与vector的区别
| vector | list | |
| 插入与删除 | 插入与删除都可能需要挪动部分元素，时间复杂度为O(n)，插入还往往伴随着扩容，又因为其需要连续的存储空间还可能出现开辟新空间，拷贝数据，释放旧空间的操作，整体效率低下。 | 插入与删除的时间复杂度均为O(1)，存储空间的独立使其不需要扩容，需要新节点时才进行申请，并且不需要挪动数据。 |
| 随机访问 | 存储空间连续，支持随机访问,查找的时间复杂度为O(1) | 不支持随机访问，查找的时间复杂度为O(n) |
| 迭代器 | 使用原生指针 | 使用被封装的原生指针 |
| 空间利用率 | 因其内存连续，不易造成内存碎片，空间利用率高，但缓存利用率高 | 因其节点是动态开辟而来，且相互独立。容易造成内存碎片，空间利用率低，但缓存利用率低 |
总结：如果需要高效存储、需要随机访问且不关心插入删除效率则使用vector。反之需要大量插入删除查找，不关心随机访问则使用list。
