目录
1.list的介绍及使用
1.1 list的介绍
1.2 list的使用
1.2.1 list的构造
1.2.2 list iterator的使用
1.2.3 capacity
1.2.4 list element access
1.2.5 list modifiers
1.2.6 list的迭代器失效问题
2.list的模拟实现
2.1 list的结构设计
2.2 list的结点设计
2.3 list的迭代器
关于三个模板参数的解释：
operator++前置
operator--前置
operator++后置
operator--后置
operator*
operator->
operator==
operator!=
2.4 list
list的基本框架
begin
end
insert
erase
push_back
push_front
pop_back
pop_front
3. list和vector的区别
1.list的介绍及使用
1.1 list的介绍
1）list是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。
2）list的底层是双向链表结构。
3）list和forward_list非常相似，最主要的不同在于forward_list是单链表，只能朝前迭代，以让其更简单高效。
4）与其他的序列容器相比(array, vector, deque)，list通常在任意位置进行插入、删除元素的执行效率更高。
5）与其他序列容器相比，list和forward_list的最大缺陷是不支持随机访问。另外list还需要额外的空间来保存前驱和后继指针。
1.2 list的使用
list的接口比较多，下面只列举一些常见的重要接口。
1.2.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 |
代码演示：
list<int> first(4, 100);//用4个100来构造list
list<int> second(); //构造空的list
list<int> third(first); //拷贝构造函数，用first来构造third
list<int> fourth(first.begin(), first.end());//用区间来构造fourth1.2.2 list iterator的使用
| 函数 | 接口说明 |
| begin() | 返回首元素的迭代器 |
| end() | 返回最后一个元素的下一个位置的迭代器 |
| rbegin() | 反向迭代器，返回最后一个元素的下一个位置的迭代器 |
| rend() | 反向迭代器，返回首元素的迭代器 |
正向迭代器和反向迭代器的区别
1）begin()和end()是正向迭代器，从容器的第一个元素开始，遍历到容器的最后一个元素，对正向迭代器进行++操作，迭代器指向下一个元素
2）rbegin()和rend()为反向迭代器，从容器的最后一个元素开始，遍历到容器的第一个元素，对反向迭代器进行++操作，迭代器指向上一个元素
代码演示：
正向迭代器
#include <list>
#include <iostream>
using namespace std;int main()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + 5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;return 0;
}
反向迭代器
#include <list>
#include <iostream>
using namespace std;int main()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + 5);list<int>::reverse_iterator rit = lt.rbegin();while (rit != lt.rend()){cout << *rit << " ";++rit;}cout << endl;return 0;
} 
1.2.3 capacity
| 函数 | 接口说明 |
| empty | 检查list是否为空，如果为空，返回true，不为空，则返回false |
| size | 返回list中有效结点的个数 |
1.2.4 list element access
| 函数 | 接口说明 |
| front | 返回第一个元素的引用 |
| back | 返回最后一个元素的引用 |
代码演示：
#include <list>
#include <iostream>
using namespace std;int main()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + 5);cout << lt.front() << endl;cout << lt.back() << endl;return 0;
}1.2.5 list modifiers
| 函数 | 接口说明 |
| push_front | 在首元素前插入一个元素 |
| pop_front | 删除list的第一个元素 |
| push_back | 在list的尾部插入一个元素 |
| pop_back | 删除list的最后一个元素 |
| insert | 在指定位置插入元素 |
| erase | 删除指定位置的元素 |
| swap | 交换list中的两个元素 |
| clear | 清空list中的有效元素 |
以上这些操作这里就不演示了，需要时可以参考文档~
1.2.6 list的迭代器失效问题
迭代器失效，归根结底就是野指针问题，也就是说迭代器指向的空间不再合法。因此我们可以很容易联想到什么情况下会出现迭代器实现的问题——如果容器的底层空间发生改变，就可能会导致迭代器失效。例如vector的扩容行为，就可能导致迭代器失效。在list中，插入操作是不会导致迭代器失效的，只有在删除的时候才会导致迭代器失效。原因在于该节点被删除了，迭代器所指向的空间不属于list了，但其他的迭代器不受影响。下面演示一下这种情况。
#include <list>
#include <iostream>
using namespace std;int main()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + 5);list<int>::iterator it = lt.begin();while (it != lt.end()){lt.erase(it);it++;}return 0;
}删除了it对应的结点后，it就变成了野指针，指向的空间已经不合法了，因此导致迭代器失效。
正确的做法：
#include <list>
#include <iostream>
using namespace std;int main()
{int arr[] = { 1,2,3,4,5 };list<int> lt(arr, arr + 5);list<int>::iterator it = lt.begin();while (it != lt.end()){lt.erase(it++);// 等价于it = lt.erase(it);}return 0;
}这里解释一下，list中erase的返回值是被删除元素的下一个元素的迭代器，到了list的模拟实现部分就更加明白了。
2.list的模拟实现
list是一个双向循环链表，所以只需要一个指针就可以完整的表现整个链表。在list的模拟实现中，最精华部分在于迭代器的模拟实现。至于要不要带上哨兵位的头结点，先明确这样一个规范，在传迭代器区间时，采用的都是“左闭右开”的方式——这是list的一个规范，如果带上哨兵位的头结点，我们将整个链表作为迭代区间时，就很好的符合规范了。所以，list是要带上哨兵位的头结点的。
2.1 list的结构设计
设计过list的人都知道，list本身和list的节点是不同的结构，需要分开设计。list结点的设计需要一个类，list本身需要一个类，list的迭代器需要一个类，所以一共需要三个类。
2.2 list的结点设计
以下是list结点的结构：
template <class T>struct __list_node{__list_node<T>* prev;__list_node<T>* next;T data;__list_node(const T& val = T()) : prev(nullptr), next(nullptr), data(val){}};
这里提供构造函数是为了创建节点的时候方便，直接new。
2.3 list的迭代器
迭代器，作为最精华的部分。list不能再像vector一样以普通指针作为迭代器，因为list的结点在空间上是不连续的，当结点Node++是，并不能满足我们的需求，Node++后指向的位置未必就是我们想要的，我们的需要的是：Node++后指向它的下一个结点next。所以这里就不得不用一个类来对普通指针进行封装，通过运算符重载来达到我们的需求。
迭代器的主要结构如下：
template <class T, class Ref, class Ptr>struct ListIterator{typedef __list_node<T> Node;typedef ListIterator<T, Ref, Ptr> Self;Node* _node;ListIterator(Node* node) :_node(node) {}//……};首先，迭代器这个类里面是肯定要有一个指向结点的指针的，这样才能维护链表。最大的以后可能是：为什么需要三个模板参数？
关于三个模板参数的解释：
如果只考虑普通迭代器，一个模板参数就够了，但是考虑到常量迭代器，也就是const迭代器，需要加上这两个模板参数——Ref(引用)、Ptr(指针)。首先理解一下const的迭代器的功能——只能遍历链表，但不能修改链表的内容。有了这个共识之后，我们再谈引入的原因。
上面已经说到引入Ref和Ptr的原因——为了适配const迭代器。那么有没有其他方法来解决这一问题？答案是有的，无非再写一个只需要一个模板参数的迭代器类，然后修改返回值为const T&和const T*(原先为T& 、T*)。请看代码：
template <class T>struct ListIterator{typedef __list_node<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node) :_node(node) {}T& operator*(){return _node->data;}T* operator->(){return &_node->data;}//……};再对比const迭代器的代码：
template <class T>struct ListIterator{typedef __list_node<T> Node;typedef ListIterator<T> Self;Node* _node;ListIterator(Node* node) :_node(node) {}const T& operator*(){return _node->data;}const T* operator->(){return &_node->data;}//……};只是返回值变了，其余一样，但也可以行得通。但是两份几乎完全一样的代码，SGI STL的大佬嫌麻烦，所以就并没有采用这种做法，而是添加了两个模板参数Ref、Ptr（这里我参考的是《STL源码剖析》一书）。好了，为什么有三个模板参数这一问题解释完毕。下面说说它为什么可以做到。以下是const迭代器：
typedef ListIterator<T, const T&, const T*> const_iterator;
就是在模板实例化时也实例化出一份const版本的，也就是说，生成了两个迭代器类，一个是普通迭代器类，另一个是常量迭代器类。从本质上来看，我们只是把活交给了编译器干，和我们自己再写一个const迭代器的类无本质区别。
operator++前置
Self& operator++()
{_node = _node->next;return *this;
}因为迭代器里就有指向链表节点的指针_node，所以要实现指向下一个结点的功能很简单，更新一下_node就可以。又因为考虑到可能会有连续赋值，所以返回了当前结点的迭代器。
operator--前置
Self& operator--()
{_node = _node->prev;return *this;
}operator++后置
Self operator++(int)
{Self tmp = *this;_node = _node->next;return tmp;
}后置++，先使用再++，返回的是++之前的内容。
operator--后置
Self operator--(int)
{Self tmp = *this;_node = _node->prev;return tmp;
}后置--，先使用再--，返回的是--之前的内容。
operator*
Ref operator*()
{return _node->data;
}解引用操作，返回的是数据的引用。
operator->
Ptr operator->()
{return &_node->data;
}返回数据的地址。
operator==
bool operator==(const Self& s)
{return s._node == _node;
}
operator!=
bool operator!=(const Self& s)
{return s._node != _node;
}2.4 list
list的基本框架
template <class T>class list{typedef __list_node<T> Node;public:typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//哨兵位list(){_head = new Node();_head->prev = _head;_head->next = _head;}//……protected:Node* _head;};begin
哨兵位头结点的下一个结点。
iterator begin()
{return iterator(_head->next);
}const_iterator begin() const
{return const_iterator(_head->next);
}end
哨兵位头结点本身就是。
iterator end()
{return iterator(_head);
}const_iterator end() const
{return const_iterator(_head);
}insert
在指定位置之前插入数据。因为传的是迭代器，迭代器里有指向链表节点的指针，所以插入操作就只需把新节点正确的连接上去就好。
iterator insert(iterator pos, const T& val)
{Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(val);prev->next = newnode;newnode->prev = prev;cur->prev = newnode;newnode->next = cur;return iterator(newnode);
}erase
删除指定结点，根据前面讲的，这里会有迭代器失效的问题，所以要返回被删除结点的下一个节点的迭代器。
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;return iterator(next);
}push_back
复用insert。
void push_back(const T& val)
{insert(end(), val);
}push_front
复用insert。
void push_front(const T& val)
{insert(begin(), val);
}pop_back
复用erase。
void pop_back()
{erase(--end());
}pop_front
复用erase。
void pop_front()
{erase(begin());
}3. list和vector的区别
| vector | list | |
| 底层结构 | 动态顺序表，一段连续的空间 | 带头结点的双向循环链表 |
| 随机访问 | 支持随机访问，访问某个元素的效率为O(1) | 不支持随机访问，访问某个元素的效率为O(n) |
| 插入和删除 | 任意位置插入和删除效率低，需要挪动数据，时间复杂度为O(n)，插入时有可能需要扩容，导致效率低 | 任意位置插入和删除数据效率高，不需要挪动数据，时间复杂度为O(1) |
| 空间利用率 | 底层为连续空间，不容易造成内存碎片，空间利用率高，缓存利用率高 | 底层节点动态开辟，小节点容易造成内存碎片，空间利用率低，缓存利用率低 |
| 迭代器 | 原生态指针 | 对原生指针进行封装的类 |
| 迭代器失效 | 插入元素时，可能会扩容，导致底层空间发生改变，进而导致迭代器失效 | 插入元素时，不会导致迭代器失效，只会在删除元素时导致当前迭代器失效，其他迭代器不受影响 |
| 使用场景 | 需要高效存储，支持随机访问，不关心插入删除效率 | 大量插入和删除操作，不关心随机访问 |
完~
