目录
一、list介绍
二、list的使用
1、list的构造
2、list capacity
3、list element access
4、list iterator
5、list modifiers
5.1、insert
6、list Operations
6.1、sort
7、list的迭代器失效
三、list模拟实现
1、push_back
2、iterator
3、const iterator
4、Ptr
5、insert 及其复用
6、erase 及其复用
7、clear
8、构造函数
8.1、默认构造
8.2、迭代器构造
9、拷贝构造函数
10、析构函数
11、operator=
一、list介绍
二、list的使用
1、list的构造
| 构造函数（ (constructor)） | 接口说明 |
| list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
| list() | 构造空的list |
| list (const list& x) | 拷贝构造函数 |
| list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
2、list capacity
| 函数声明 | 接口说明 |
| empty | 检测list是否为空，是返回true，否则返回false |
| size | 返回list中有效节点的个数 |
3、list element access
| 函数声明 | 接口说明 |
| front | 返回list的第一个节点中值的引用 |
| back | 返回list的最后一个节点中值的引用 |
4、list iterator
此处，大家可暂时将迭代器理解成一个指针，该指针指向list中的某个节点。
| 函数声明 | 接口说明 |
| begin + end | 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器 |
| rbegin + rend | 返回第一个元素的reverse_iterator,即end位置，返回最后一个元素下一个位置的 reverse_iterator,即begin位置 |
注意：
begin与end为正向迭代器，对迭代器执行++操作，迭代器向后移动rbegin(end)与rend(begin)为反向迭代器，对迭代器执行++操作，迭代器向前移动5、list modifiers
| 函数声明 | 接口说明 |
| push_front | 在list首元素前插入值为val的元素 |
| pop_front | 删除list中第一个元素 |
| push_back | 在list尾部插入值为val的元素 |
| pop_back | 删除list中最后一个元素 |
| insert | 在list position 位置中插入值为val的元素 |
| erase | 删除list position位置的元素 |
| swap | 交换两个list中的元素 |
| clear | 清空list中的有效元素 |
5.1、insert
使用方法如下：
6、list Operations
| 函数声明 | 接口说明 |
| splice | 将元素从一个列表传输到另一个列表 |
| remove | 删除具有特定值的元素 |
| unique | 删除重复值 |
| merge | 合并排序列表 |
| sort | 对容器中的元素进行排序 |
| reverse | 反转元素的顺序 |
6.1、sort
list无法使用算法库里的 sort 函数，因为算法库里的 sort 函数底层实现如下图所示：
这里使用了减法运算，而list各个节点的地址都是不连续的，于是就发生了错误。除此之外，算法库里的 sort 函数底层使用快排实现，而快排有一个重要的组成部分：三数取中，也不适用于list。
文档里关于 sort 函数的说明，也暗示使用算法库里的 sort 函数时要传随机迭代器：
list中的 sort 用法如下：
功能没有任何问题，但是list的 sort 函数我们很少使用，因为它的效率非常的低。
我们使用如下代码进行证明：
可以看到，把相同的数据先拷贝到 vector 中排序，排好了之后再拷贝回来，都要比直接使用 list 排序要快。
7、list的迭代器失效
前面说过，此处大家可将迭代器暂时理解成类似于指针，迭代器失效即迭代器所指向的节点的无效，即该节点被删除了。因为list的底层结构为带头结点的双向循环链表，因此在list中进行插入时是不会导致list的迭代器失效的，只有在删除时才会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响。
三、list模拟实现
我们先来搭一个list的基本框架：
namespace bin{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 list{typedef list_node<T> node;public:list(){_head = new node;_head->_next = _head;_head->_prev = _head;}private:node* _head;};}
需要注意：在 list 类中定义私有成员变量时，一定要注意成员变量类型为类名 + 模板参数。
1、push_back
void push_back(const T& x){node* tail = _head->_prev;node* new_node = new node(x);tail->_next = new_node;new_node->_prev = tail;new_node->_next = _head;_head->_prev = new_node;}
具体底层逻辑可以参照文章《双向链表》 。
2、iterator
list的底层物理空间是不连续的，所以模拟实现迭代器时，就不能直接让指针 "++" 或 "--" 了，而应该实现迭代器 "++" 或 "--" 的重载：
template<class T>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T> self;node* _node;__list_iterator(node* n):_node(n){}T& operator*(){return _node->_data;}self& operator++(){_node = _node->_next;return *this;}bool operator!=(const self& s){return _node != s._node;}};
因为我们模拟实现的list类中的迭代器是使用原生指针实现的，且原生指针的类型为 _node* ，没办法直接实现，所以又定义了一个 __list_iterator 类进行封装。
实验运行结果正确：
红框框起的部分调用了一次拷贝构造，由于我们没有自己实现拷贝构造函数，所以这里是一次浅拷贝，而我们想要的就是浅拷贝。
这里浅拷贝之所以没有报错，是因为我们封装的迭代器类中没有实现析构函数，因为迭代器仅仅是使用list对象节点，而不是拥有list对象节点，它没有权利释放list的对象。
我们再来完善一下迭代器的其他功能：
template<class T>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T> self;node* _node;__list_iterator(node* n):_node(n){}T& 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;}};3、const iterator
先来看一下错误的写法：
直接在list类中定义 const 类型的成员函数。这种写法的错误之处在于，这些 const 类型成员函数所针对的是list类中的成员变量 _head ，虽然 _head 被 const 限制无法更改，但是 _head 所指向的 _data 仍然可以更改，即数据仍然可以被更改，不符合我们的预期。
我们较为容易想到的写法是直接再另外定义一个类，在这个新类中封装 const 类型的迭代器：
虽然这种写法可以实现功能且完全满足需求，但是代码太过于冗余，接下来我们来学习一种新的写法：
在迭代器模板中多增加了一个模板参数 Ref ，用于满足不同的调用需求。
4、Ptr
观察如下代码：
编译器报错，因为我们没有为自定义类型 AA 实现流插入重载，所以需要写成这种形式：
但是我们在写 C++ 代码时，一般没有写成这种形式的习惯，大多数都是通过 "->" 来实现解引用操作的，所以我们可以改变写法：
这种写法乍一看非常难以理解，这时因为为了增强可读性的缘故，在这里少写了一个 "->" ：
大家看一下完整版的写法就一定能够理解：
同理，为了满足不同的调用需求，应该为list类重载一个 const 类型的成员函数，为了不造成代码冗余，同样只需要为list类模板增加一个模板参数就可以了：
5、insert 及其复用
具体实现如下：
list的 insert 不会导致迭代器失效。
可以使用 insert 函数的复用来实现 push_back 与 push_front ：
6、erase 及其复用
具体实现如下：
list的 erase 会导致迭代器失效。
为了在使用 erase 函数后仍然可以找到该节点的下一个节点，我们使用返回值来返回需要的信息：
可以使用 erase 函数的复用来实现 pop_back 与 pop_front ：
7、clear
具体实现方法如下：
也可以使用下面这种写法：
8、构造函数
8.1、默认构造
void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}8.2、迭代器构造
void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}扩展内容：
const 类型的对象是无法调用 empty_init() 函数的，因为这属于权限放大。那么为什么我们写如下 const 类型对象的实例化不会报错呢？
这是因为该 const 对象在定义的时候并没有 const 属性，在该对象定义完成后，才被赋予了 const 属性，否则就没有办法对对象进行初始化操作了。
9、拷贝构造函数
传统写法如下：
void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list(const list<T>& lt){empty_init();for ( auto e : lt){push_back(e);}}这里再提供一份现代写法：
void swap(list<T>& tmp){std::swap(_head, tmp._head);}list(const list<T>& lt){empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}10、析构函数
实现代码如下：
~list(){clear();delete _head;_head = nullptr;}11、operator=
实现代码如下：
void swap(list<T>& tmp){std::swap(_head, tmp._head);}list<T>& operator=(list<T> lt){swap(lt);return *this;}
注意：这里的传参没有使用传引用传参，而是采用了传值传参。这是因为我们本来就期望在传参时发生一次拷贝构造，并把拷贝构造出的临时变量与 this 进行交换，这样不会影响到赋值运算符重载的右值本身。
关于list的使用和模拟实现的相关内容就讲到这里，欢迎同学们多多支持，如果有不对的地方欢迎大佬指正，谢谢！