list
list是一个带头双向循环链表。
list文档介绍：https://legacy.cplusplus.com/reference/list/list/
list因为是链表结构，所以没有 [] 去访问数据的方式，只有用迭代器，list当中迭代器是很重要的。
这里透彻尾插不会导致迭代器失效问题，不过删除会导致迭代器失效。
list还有一个特性，就是他的sort排序接口函数效率是低于算法库中排序的效率。
更多内容就配合模拟实现来看。
list的常用接口模拟实现
list基本结构
template<class T> struct list_node//结点 { list_node* _next; list_node* _prev; T _data; list_node(const T& x) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} };
下面都是模拟list类中的结构
在list中其实控制整个链表的就是头节点，这样交换内容也是非常的方便。
list成员变量：
_head
因为list是带头双向循环链表，所以最重要的是创建头节点，这里因为后面结构需要大量重复这个动作我就单独写了个函数。
void initialize()//创建头节点 { _head = new node(T()); _head->_next = _head; _head->_prev = _head; }
构造函数：（无参）
list() { initialize(); }
在pos位置之前插入：
void insert(iterator pos, const T& x)//在pos位置之前插入 { node* newnode = new node(x); node* cur = pos._pnode;//pos位置的结点 node* p = cur->_prev;//pos位置之前的结点 p->_next = newnode; newnode->_prev = p; newnode->_next = cur; cur->_prev = newnode; }
删除pos位置的结点：（返回值是迭代器类型）
iterator erase(iterator pos)//删除pos位置的结点 { assert(pos != end()); node* cur = pos._pnode; node* front = cur->_prev; node* later = cur->_next; front->_next = later; later->_prev = front; delete cur; return iterator(later); }
其实完成这两个函数就很方便各种插入删除了。
void push_back(const T& x)//尾插 { insert(end(), x); } void push_front(const T& x)//头插 { insert(begin(), x); } void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); }
清空链表：（注意不清理头结点）
void clear()//清空链表 { iterator front = begin(); while (front != end()) { front = erase(front); } }
拷贝构造：
template<class _iterator>//这里如果不是模板会导致不同类中的迭代器有冲突 list(_iterator front, _iterator later) { initialize(); while (front != later) { push_back(*front); ++front; } } list(const list<T>& it)//拷贝构造 { initialize();//必须创建头节点，不然交换会传过去一个空指针导致析构出现问题 list<T>newnode(it.begin(), it.end()); swap(newnode); }
赋值重载：（现代写法）
list<T>& operator=(list<T> p) { swap(p); return *this; }
这里传参的值不是引用，也就等于p是一个拷贝构造出来的对象，也就是说和之前赋值的对象没有任何关系，只是内容相同罢了。
所以这里直接交换就好了出了这个函数的p就会自动销毁。
交换函数：
void swap(list<T>& tmp) { std::swap(_head, tmp._head);//交换头结点就好 }
这里就体现出头结点的好处了，因为空间不是连续的，是随机的，所以控制整个链表就是头结点，所以交换了头结点就等于交换了两个list。
析构函数：
~list() { clear(); delete _head;//清理头结点 _head = nullptr; }
C++有一个特性：
我们发现参数不是完整的类型（缺一个模板参数T），也就是说在类里面类名等于类型。
begin与end：
typedef _list_iterator<T, T&> iterator;//模板函数下面实现 typedef _list_iterator<T, const T&> const_iterator; const_iterator begin()const { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); }
迭代器（非常重要）
template<class T, class cur, class prt> struct _list_iterator//用struct是因为里面的内容都需要公开使用 { typedef list_node<T> node; typedef _list_iterator<T, cur, prt> coord; node* _pnode;//迭代器指针的本质 _list_iterator(node* p) :_pnode(p) {} cur operator*()//返回值分const与非const { return _pnode->_data; } prt operator->() { return &_pnode->_data;//注意->的优先级大于& } coord& operator++()//前置++ { _pnode = _pnode->_next; return *this; } coord& operator++(int)//后置++ { coord old(*this); _pnode = _pnode->_next; return old; } coord& operator--()//前置-- { _pnode = _pnode->_prev; return *this; } coord& operator--(int)//后置-- { coord old(*this); _pnode = _pnode->_prev; return old; } bool operator!=(const coord& it) { return _pnode != it._pnode; } bool operator==(const coord& it) { return _pnode == it._pnode; } };
list因为是个链表，所以和vector，string不一样，空间不是连续的，想进行++，- -，就等于访问下一个结点或者上一个结点。
这里要注意迭代器是需要有const的：
迭代器指向的内容不能被修改，并不代表不能++，- -
所以就需要实现一份const迭代器，其实也就是解引用的不同，解引用返回的是const，和非const，其他函数一摸一样，进行函数重载是不行的，因为参数也要加const，不然无法重载，但是参数加了const其他函数就无法进行调用了，涉及到了权限放大，如果再写一个类太麻烦，这时候就可以加一个模板参数cur来决定用的时候添加什么参数。
重点是重载的->
如果list中的类型是一个自定义类型呢？
struct test { int row; int col; test(int x = 0, int y = 0) :row(x) ,col(y) {} }; void test4() { list<test>arr; arr.push_back(test(1, 2)); arr.push_back(test(3, 4)); arr.push_back(test(5, 6)); arr.push_back(test(7, 8)); list<test>::iterator cur = arr.begin(); while (cur != arr.end()) { cout << cur->row << ' ';//这里如果用解引用是不可以的，因为cout需要再次进行重载才能打印出来内容 } cout << endl; }
这时候就要用->就方便了，首先cur要是个指针才行，很明显它不是，所以返回的时候需要返回地址，并且要注意const的类型，就和解引用一样。
还有一点很奇怪：
cur->row == cur.operator->(row)
这里返回的是地址，为什么还能进行访问row呢？这是因为编译器在这里进行了特殊处理，原本面貌是这样的：
cur->->row
这样的代码看起来非常不美观，所以就进行了处理，去掉了一个->。
完整代码
#include <iostream> #include <list> #include <assert.h> #include <algorithm> using namespace std; template<class T> struct list_node//结点 { list_node* _next; list_node* _prev; T _data; list_node(const T& x) :_next(nullptr) ,_prev(nullptr) ,_data(x) {} }; template<class T, class cur, class prt> struct _list_iterator { typedef list_node<T> node; typedef _list_iterator<T, cur, prt> coord; node* _pnode;//迭代器指针的本质 _list_iterator(node* p) :_pnode(p) {} cur operator*()//返回值分const与非const { return _pnode->_data; } prt operator->() { return &_pnode->_data;//注意->的优先级大于& } coord& operator++()//前置++ { _pnode = _pnode->_next; return *this; } coord& operator++(int)//后置++ { coord old(*this); _pnode = _pnode->_next; return old; } coord& operator--()//前置-- { _pnode = _pnode->_prev; return *this; } coord& operator--(int)//后置-- { coord old(*this); _pnode = _pnode->_prev; return old; } bool operator!=(const coord& it) { return _pnode != it._pnode; } bool operator==(const coord& it) { return _pnode == it._pnode; } }; template<class T> class list { typedef list_node<T> node; public: typedef _list_iterator<T, T&, T*> iterator; typedef _list_iterator<T, const T&, const T*> const_iterator; const_iterator begin()const { return const_iterator(_head->_next); } const_iterator end()const { return const_iterator(_head); } iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } void initialize()//创建头节点 { _head = new node(T()); _head->_next = _head; _head->_prev = _head; } list() { initialize(); } template<class _iterator> list(_iterator front, _iterator later) { initialize(); while (front != later) { push_back(*front); ++front; } } list(const list<T>& it)//拷贝构造 { initialize();//必须创建头节点，不然交换会传过去一个空指针导致析构出现问题 list<T>newnode(it.begin(), it.end()); swap(newnode); } void insert(iterator pos, const T& x)//在pos位置之前插入 { node* newnode = new node(x); node* cur = pos._pnode;//pos位置的结点 node* p = cur->_prev;//pos位置之前的结点 p->_next = newnode; newnode->_prev = p; newnode->_next = cur; cur->_prev = newnode; } iterator erase(iterator pos)//删除pos位置的结点 { assert(pos != end()); node* cur = pos._pnode; node* front = cur->_prev; node* later = cur->_next; front->_next = later; later->_prev = front; delete cur; return iterator(later); } list<T>& operator=(list<T> p) { swap(p); return *this; } void push_back(const T& x)//尾插 { insert(end(), x); } void push_front(const T& x)//头插 { insert(begin(), x); } void pop_back()//尾删 { erase(--end()); } void pop_front()//头删 { erase(begin()); } void clear()//清空链表 { iterator front = begin(); while (front != end()) { front = erase(front); } } void swap(list<T>& tmp) { std::swap(_head, tmp._head); } ~list() { clear(); delete _head; _head = nullptr; } private: node* _head; };
list与vector的区别
list：
优点：
按照需要申请空间，不需要扩容。
任意位置插入删除。
缺点：
不支持下标随机访问。
cpu命中率低。（因为list是随机结构，vector是连续空间地址）
vector：
优点：
支持下标随机访问.
尾插尾删效率高。
cpu命中率高。
缺点：
前面插入删除效率低。
需要扩容。（可能导致浪费空间）
迭代器失效问题
vector插入删除都会失效，list只有删除会失效。
