一、list 的介绍
- list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
- list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。
- list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。
- 与其他的序列式容器相比(array，vector，deque)，list通常在任意位置进行插入、移除元素的执行效率更好。
- 与其他序列式容器相比，list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list 的第6个元素，必须从已知的位置(比如头部或者尾部)迭代到该位置，在这段位置上迭代需要线性的时间开销；list 还需要一些额外的空间，以保存每个节点的相关联信息(对于存储类型较小元素的大 list 来说这可能是一个重要的因素)。
二、list 的模拟实现
list 学习时也要学会查看文档：list 文档介绍，在实际中我们熟悉常见的接口就可以，下面我们直接开始模拟实现，在模拟实现中我们实现的是常见的接口，并且会在实现中讲解它们的使用以及注意事项。
首先跟以往不一样的是，list 是一个个节点连接起来的，所以它不是连续的物理空间，这也就意味着，它不用扩容，每次插入的时候只需要申请一个节点，然后连接起来即可；
其次，list 底层的迭代器实现也跟 string和 vector 不一样，它们两个的迭代器可以说是原生指针，但是 list 的迭代器是要让节点指向下一个节点，所以底层实现也不一样；例如我们想让迭代器 it，往后迭代，就是 ++it，但是底层的实现却不是真的让节点++，因为它们的空间不是连续的，所以我们要把 list 迭代器封装成一个类。
首先我们先创建一个自己的命名空间，把 list 节点的类，list 迭代器的类，list 类都放进去；
1. list 节点类
list 节点类如下，因为是双向链表，所以应该有一个数据，两个指针；
namespace Young { // list 节点类 template <class T> struct list_node { T _data; list_node<T>* _next; list_node<T>* _prev; list_node(const T& x = T()) :_data(x) ,_next(nullptr) ,_prev(nullptr) {} }; }
2. list 正向迭代器类
首先我们先定义一个类模板，其参数有三个，分别是类型、类型的引用(const 和 非const) 、类型的指针(const 和 非const) ；
为什么要定义三个模板参数呢，因为考虑到 const 迭代器，const 迭代器和普通迭代器不是同一个类，不能直接在 iterator 前直接加 const，如 const iterator ，这不是 const 迭代器，因为这里的 const 修饰的是迭代器本身，就是迭代器本身不能修改，但是我们期望的是迭代器本身可以被修改，如 it++、++it，只是期望迭代器指向的内容不能被修改，如 *it = 10、it->10 ；
这就类比 const T* 和 T* const ， const T* 中 const 是修饰指向的内容不能被修改，而 T* const 中 const 修饰的是指针本身不能被修改；而我们需要实现的 const 迭代器 是要满足第一种的，所以 list 中普通迭代器和 const 迭代器 是两个完全不一样的类，应该写成两个类，但是我们可以通过增加两个模板参数 类型的引用(const 和 非const) 、类型的指针(const 和 非const) 来复用普通迭代器，具体实现如下：
// list 迭代器类 template <class T,class Ref,class Ptr> struct __list_iterator { typedef list_node<T> Node; typedef __list_iterator<T, Ref, Ptr> self; Node* _node; // 迭代器构造函数 __list_iterator(Node* node) :_node(node) {} }
首先我们先将节点类起别名为 Node，再将自己的类起别名为 self；迭代器本身也是一个指针，只是它内部实现不一样，所以我们需要一个 _node 节点的指针，构造函数实例化一个节点的指针，比如说 list<int>::iterator it = lt.begin();，这里的 it 就会调构造函数，实例化一个 lt.begin() 节点的指针，其实 lt.begin() 就是指向头节点的指针。
接着我们重载一些迭代器常用的运算符：
（1）前置++
就是让迭代器往后迭代，具体的实现就是让节点的指针指向下一个节点：
// 前置 ++ self& operator++() { _node = _node->_next; return *this; }
（2）后置++
跟前置++的区别就是，后置++需要拷贝，返回++以前的迭代器，所以一般都不用后置++；
// 后置 ++ self operator++(int) { self tmp(*this); _node = _node->_next; return tmp; }
（3）前置- -、后置- -
前置- -、后置- - 与 ++ 的区别就是， - -返回上一个节点的迭代器；
// 前置 -- self& operator--() { _node = _node->_prev; return *this; } // 后置-- self operator--(int) { self tmp(*this); _node = _node->_prev; return tmp; }
（4）!= 和 == 运算符重载
!= 运算符重载就是比较它们的节点是否相等；== 运算符就相反；
// != 运算符重载 iterator it != lt.begin(); bool operator!=(const self& s) { return s._node != _node; } // == 运算符重载 iterator it == lt.begin(); bool operator==(const self& s) { return s._node == _node; }
（5）* 解引用重载 和 -> 重载
解引用重载 和 -> 重载 就是改变迭代器指向内容的两个运算符，所以我们定义的三个模板参数，就在这里起作用了；比如我们实例化的模板参数是 const 迭代器 的 __list_iterator<T, const T&, const T*>，这里的 const T& 就是 Ref，const T* 就是 Ptr，这里就可以直接用 Ref （解引用重载）和 Ptr（箭头重载） 作返回值；
如果是 非const 迭代器的 __list_iterator<T, T&, T*>，T& 就是 Ref，T* 就是 Ptr；所以就可以根据它们的类型返回对应的迭代器类型，就不需要我们自己写两个迭代器的类了。
// * 解引用重载 Ref operator*() { return _node->_data; } // -> 重载 Ptr operator->() { return &_node->_data; }
解引用 和 -> 重载的使用：
假设 list 里面存的类型是一个自定义类型，这个自定义类型中有两个成员变量，那么我们在使用 解引用 和 -> 重载的时候，应该访问哪一个呢？这时候就需要我们指定访问了，如下代码：
struct AA { AA(int a1 = 0, int a2 = 0) :_a1(a1) , _a2(a2) {} int _a1; int _a2; }; void test4() { Young::list<AA> lt; lt.push_back(AA(1, 1)); lt.push_back(AA(2, 2)); lt.push_back(AA(3, 3)); Young::list<AA>::iterator it = lt.begin(); while (it != lt.end()) { // 使用解引用 //cout << (*it)._a1<<" "<<(*it)._a2 << endl; //使用 -> cout << it->_a1 << " " << it->_a2 << endl; ++it; } cout << endl; }
上面的 cout << it->_a1 << " " << it->_a2 << endl; 调用了->重载，实际上是 cout << it.operator->()->_a1 << " " << it.operator->()->_a2 << endl;，本来应该是有两个 -> 的，即 it->->_a1 但是这样写可读性不好，所以编译器特殊处理，省略了一个 ->。
3. list 反向迭代器类
list 的反向迭代器可以复用 list 的正向迭代器，就不需要我们重新写一个反向迭代器的类了。我们先简单看一下 list 的反向迭代器的使用：
与正向迭代器相反，反向迭代器的 ++ 是倒着走的，反向迭代器的 rbegin 是正向迭代器 end 位置的前一个位置；rend 的位置就是 begin 的前一个位置。
我们先看一下反向迭代器的类：
// list 反向迭代器类 template<class Iterator, class Ref, class Ptr> class ReverseIterator { public: typedef ReverseIterator<Iterator, Ref, Ptr> Self; // 反向迭代器的构造函数 ReverseIterator(Iterator it) :_it(it) {} private: Iterator _it; // 定义一个类成员为正向迭代器的对象，复用正向迭代器的类 };
（1）前置++
反向迭代器的 ++ 是使迭代器从后往前走，我们底层只需要改成 – 即可：
// 前置++ Self& operator++() { --_it; return *this; }
（2）后置++
// 后置++ Self operator++(int) { _it--; return *this; }
（3）前置- -
// 前置-- Self& operator--() { ++_it; return *this; }
（4）后置- -
// 后置-- Self operator--(int) { _it++; return *this; }
（5）解引用重载
直接复用正向迭代器的解引用重载即可：
// 解引用重载 Ref operator*() { return *_it; }
（6）-> 重载
复用正向迭代器的 -> 重载：
// 箭头重载 Ptr operator->() { return _it.operator->(); }
（7）== 和 != 重载
bool operator!=(const Self& s) { return _it != s._it; } bool operator==(const Self& s) { return _it == s._it; }
4. list 类
list 类首先将 const 迭代器和非 const 迭代器类型起别名为 const_iterator 和 iterator ，反向迭代器同上；成员变量有 _head 哨兵位节点和 _size 记录链表的长度，如下：
// 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; // 反向迭代器 typedef ReverseIterator<iterator, T&, T*> reverse_iterator; typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator; private: Node* _head; size_t _size; };
（1）迭代器
注意，begin() 是哨兵位的下一个节点，end() 是哨兵位节点。
begin() 和 end() 返回的类型也是一个迭代器，这里 iterator(_head->_next) 是调用迭代器类的构造函数，构造一个节点的指针返回；也可以写成 _head->_next，因为支持隐式类型的转换；
// 非 const 反向迭代器 reverse_iterator rbegin() { return reverse_iterator(--end()); } reverse_iterator rend() { return reverse_iterator(end()); } // const 反向迭代器 const_reverse_iterator rbegin() const { return const_reverse_iterator(--end()); } const_reverse_iterator rend() const { return const_reverse_iterator(end()); } // 非 const 正向迭代器 iterator begin() { return iterator(_head->_next); } iterator end() { return iterator(_head); } // const 正向迭代器 const_iterator begin() const { return const_iterator(_head->_next); } const_iterator end() const { return const_iterator(_head); }
（2）修改相关的接口
swap()
交换链表数据，需要借助标准库的 swap 函数实现：
// 交换链表数据 void swap(list<T>& lt) { std::swap(_head, lt._head); std::swap(_size, lt._size); }
insert()
在 pos 迭代器插入节点；新开一个节点，然后插入指定迭代器的位置，连接好 prev 和 cur 的位置即可；因为 list 的底层结构为带头结点的双向循环链表，因此在 list 中进行插入时是不会导致 list 的迭代器失效的；
// 插入节点 iterator insert(iterator pos, const T& x) { Node* newnode = new Node(x); Node* cur = pos._node; Node* prev = cur->_prev; prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; ++_size; return newnode; }
erase()
删除 pos 迭代器位置的节点；在删除时迭代器会失效，并且失效的只是指向被删除节点的迭代器，其他迭代器不会受到影响，所以 erase() 函数执行后，it 所指向的节点已被删除，因此 it 无效，在下一次使用 it 时，必须先给其赋值；
// 删除节点 iterator erase(iterator pos) { Node* prev = pos._node->_prev; Node* next = pos._node->_next; prev->_next = next; next->_prev = prev; delete pos._node; pos._node->_next = pos._node->_prev = nullptr; --_size; return next; }
push_back、push_front、pop_back、pop_front
只需要复用 insert() 和 erase() 即可，实现如下：
// 尾插 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()); }
clear()
清空链表数据，删除除了哨兵位的节点即可；
// 清空链表数据 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } }
以上修改接口配合迭代器的使用如下图：
（3）空链表初始化
// 空链表初始化 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; _size = 0; }
（4）构造函数
构造函数只需要创建一个哨兵位即可；
// 构造函数 list() { empty_init(); }
（5）拷贝构造函数
拷贝构造函数直接初始化，然后插入数据即可；
// 拷贝构造函数 -- lt2(lt1) list(const list<T>& lt) { empty_init(); for (auto e : lt) { push_back(e); } }
（6）赋值运算符重载
现代写法，传参的时候调用拷贝构造，然后交换数据即可；
// 赋值运算符重载 -- lt2 = lt1 list<T>& operator=(list<T> lt) { swap(lt); return *this; }
（7）析构函数
清空链表数据之后再释放哨兵位的节点即可；
// 析构函数 ~list() { clear(); delete _head; _head = nullptr; }
4. 打印容器的接口
（1）打印链表整型的接口
像 vector、list 这些容器都没有重载流插入运算符，所以我们可以自己实现一个打印的接口函数；我们先来实现一下打印链表整型的接口：
// 打印链表 -- 只能针对 int 类型 void print_list(const list<int>& lt) { list<int>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it = 10; error cout << *it << " "; ++it; } cout << endl; }
此接口可以打印链表的数据，但是只能针对 int 类型，我们可以对它进行改造一下，使用模板。
（2）打印 list 的接口
我们学了模板，就可以利用模板实现泛型编程，将类型改为模板的泛型，即可打印 list 中的不同类型，如下：
// 打印链表 -- 只能打印 list 容器 template<typename T> void print_list(const list<T>& lt) { typename list<T>::const_iterator it = lt.begin(); while (it != lt.end()) { //*it = 10; error cout << *it << " "; ++it; } cout << endl; }
这里的模板参数使用了 typedef 关键字，这里必须使用 typedef 关键字，而且在指定类域前还要加上 typedef 关键字，如 typename list<T>::const_iterator it = lt.begin();；因为在模板还没有进行实例化的时候， const_iterator 就到 list<T> 的类域中寻找类型，此时类中还没有实例化参数 T，所以编译器分不清它是类型还是静态变量，不能去 list<T> 里面找，所以在前面加 typedef 关键字就说明它是个类型，编译器在等 list<T> 实例化后，再去类里面去取根据类型去取类型。
但是上面的接口还是不够完美，要是我想打印 vector 呢？那还是不能打印出来，所以我们可以实现一个专门打印容器的接口；
（3）打印容器的接口
我们使用模板参数代表容器，让编译器到指定容器去取它的迭代器即可；
// 打印容器 -- 能打印各种容器 template<typename container> void print_container(const container& con) { typename container::const_iterator cit = con.begin(); while (cit != con.end()) { cout << *cit << " "; ++cit; } cout << endl; }
使用如下图：
