一、标准库中的list类
1.1 list类介绍
1.2 list的常用接口
1.2.1 常用的构造函数
1.2.2 容量操作接口
（1）size
（2）empty
（3）resize
1.2.3 访问和遍历
（1）迭代器
（2）反向迭代器
（3）back
（4）front
1.2.4 list的增删查改
（1）push_front
（2）pop_front
（3）push_back
（4）pop_back
（5）find
（6）insert
（7）erase
（8）swap
（9）assign
（10）clear
1.2.5 list的顺序修改接口
（1）sort
（2）reverse
二、模拟实现list类
一、标准库中的list类
1.1 list类介绍
list的底层是一个带哨兵位的双向循环链表结构对比forward_list的单链表结构，list的迭代器是一个双向迭代器与vector等顺序结构的容器相比，list在任意位置进行插入删除的效率更好，但是不支持任意位置的随机访问list是一个模板类，在使用的时候我们需要给出元素的类型
使用list类时，需要包含头文件<list>
1.2 list的常用接口
1.2.1 常用的构造函数
list();
list类的默认构造函数，构造一个空链表
例如：
list(size_type n, const value_type& val = value_type());
构造一个list对象并用n个val初始化
例如：
list(const list& x);
list类的拷贝构造函数
例如：
Template<class InputIterator>
list(InputIterator first, InputIterator last);
使用迭代器进行初始化构造
例如：
1.2.2 容量操作接口
（1）size
size_type size() const;
获取链表节点个数
例如：
（2）empty
bool empty() const;
判断链表是否为空
例如：
（3）resize
void resize(size_type n, value_type val = value_type());
缩减或增加节点个数为n
如果没有给出val，就用0作为元素
例如：
1.2.3 访问和遍历
（1）迭代器
iterator begin();
const_iterator begin() const;
iterator end();
const_iterator end() const;
迭代器，用于获取链表中第一个节点的位置和最后一个节点的下一个位置（即哨兵位）
例如：
（2）反向迭代器
reverse_iterator rbegin();
const_reverse_iterator rbegin() const;
reverse_iterator rend();
const_reverse_iterator rend() const;
反向迭代器，rbegin获取容器中最后一个节点的位置，rend获取容器中哨兵位的位置
例如：
需要注意，反向迭代器rit也要用++而不是--
（3）back
reference back();
const_reference back() const;
返回链表中最后一个节点存储的数据的引用
例如：
（4）front
reference front();
const_reference front() const;
返回链表中第一个节点存储的数据的引用
例如：
1.2.4 list的增删查改
（1）push_front
void push_front(const value_type& val);
从链表头部插入一个元素
例如：
（2）pop_front
void pop_front();
从链表头部删除一个元素
例如：
（3）push_back
void push_back(const value_type& val);
从链表尾部插入一个元素
例如：
（4）pop_back
void pop_back();
从链表尾部删除一个元素
例如：
（5）find
template <class InputIterator, class T>
InputIterator find(InputIterator first, InputIterator last, const T& val);
在两个迭代器区间寻找val并返回其所在处的迭代器
例如：
需要注意的是，该函数并非list的成员函数，是标准库中的函数，多个容器共用该find函数
可以看到，我们可以直接对list的迭代器进行解引用并修改其内容，但是迭代器不应该指向节点吗？为什么对其解引用能修改数据呢？
实际上list的迭代器并不是用原生态指针进行模拟实现的，需要进行底层的封装，这里会在list的模拟实现的源代码中体现。
（6）insert
iterator insert(iterator position, const value_type& val);
void insert(iterator position, size_type n, const value_type& val);
————————————————————————————————————————
template<class InputIterator>
void insert(iterator position, InputIterator first, InputIterator last);
在position位置的前面插入一个或多个元素
例如：
细心的读者可能已经发现了，list的insert操作是不会导致迭代器失效的，因为pos指向的节点不变，相对位置也不变。
但是list的删除操作一定会导致迭代器失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
（7）erase
iterator erase(iterator position);
iterator erase(iterator first, iterator last);
删除position位置的元素或者 [first，last) 区间的所有元素
例如：
（8）swap
void swap(vector& x);
交换两个list对象
例如：
（9）assign
template <class InputIterator>
void assign(InputIterator first, InputIterator last);
void assign(size_type n, const value_type& val);
为list指定新内容，替换其当前内容并修改节点个数
例如：
（10）clear
void clear();
删除链表所有节点
例如：
1.2.5 list的顺序修改接口
（1）sort
void sort();
template<class Compare>
void sort(Compare comp);
list由于结构的特殊性，是无法使用标准库中的sort函数的，因为迭代器无法进行相减的操作
并且在C++文档中，我们可以看到标准库中的sort也限定了迭代器的类型必须是可以进行随机访问（RandomAccess）的
迭代器有几个功能分类：
单向迭代器，只能进行++双向迭代器，可以++和--随机迭代器，可以++，--，+和-但是list的sort函数也是没什么必要的，因为直接对链表排序的效率比拷贝到vector进行排序再拷贝回链表要慢的多
（2）reverse
void reverse();
对链表进行逆置
例如：
二、模拟实现list类
学习了list类中各种常用接口的用法后，我们就可以开始自己手撕一个自己的list类了
为了不和标准库中的list类冲突，我们可以开一个自己的命名空间
#include <iostream>#include <assert.h>using namespace std;namespace Eristic{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _data;list_node(const T& x = T()) //匿名对象作为缺省值，变为默认构造函数:_next(nullptr),_prev(nullptr),_data(x){}}; template<class T, class Ref, class Ptr> //通过模板参数实现const迭代器和普通迭代器版本的复用 //和list类中迭代器的typedef配合阅读会较好理解struct __list_iterator //重点：迭代器的底层封装{typedef list_node<T> node;typedef __list_iterator<T, Ref, Ptr> self;node* _node; //node*本身不支持解引用等操作，对其进行封装就可以模仿原生态指针的行为__list_iterator(node* n):_node(n){}Ref& operator*(){ return _node->_data;}Ptr operator->() //误区：在使用箭头运算符的时候，为什么只需要一个箭头而不是两个？ //答：为了可读性，编译器会帮助我们省略一个箭头{ return &_node->_data;}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& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}//不需要写拷贝构造，因为我们用默认生成的进行浅拷贝就能完成需求//析构函数也不需要写，释放节点是list的事，与迭代器无关};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; //对应上面的多个模板参数void list_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){list_init();}list(int n, const T& x = T()){list_init();for (int i = 0; i < n; i++)push_back(x);}template<class iterator>list(iterator first, iterator last){list_init();while (first != last){push_back(*first);++first;}}list(const list<T>& lt){list_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}~list(){clear();delete _head;_head = nullptr;}list<T>& operator=(const list<T> lt){swap(lt);return *this;}int size(){iterator it = begin();int count = 0;while (it != end()){++it;++count;}return count;}void resize(size_t n, const T& x = T()){if (n < size())while (n < size())pop_back();else if (n > size())while (n > size())push_back(x);}void swap(list<T>& lt){std::swap(_head, lt._head);}T& front(){return _head->_next->_data;}const T& front() const{return _head->_next->_data;}T& back(){return _head->_prev->_data;}const T& back() const{return _head->_prev->_data;}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 insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* newnode = new node(x);cur->_prev = newnode;newnode->_next = cur;prev->_next = newnode;newnode->_prev = prev;}iterator erase(iterator pos){assert(pos != end()); //哨兵位不能删node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;return iterator(next);}iterator begin(){return iterator(_head->_next);}const_iterator begin() const{return const_iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}void clear(){iterator it = begin();while (it != end()){erase(it++);}}private:node* _head;};}如有错误，欢迎在评论区指出
完.
