5、链表 list
List 是每个节点包含前驱指针、后继指针和数据域三个部分的双向链表。List 不提供随机存取，访问元素需要按顺序走到需存取的元素，时间复杂度为 O(n)，在 list 的任何位置上执行插入或删除操作都非常迅速，只需在 list 内部调整一下指针。list 不仅是一个双向链表，而且还是一个环状双向链表。所以它只需要一个指针，便可以完整实现整个链表。（这里需要特别强调一下：list 到底是不是双向链表？有的书上说是，有的书上没说，所以大家注意一下，这里暂把 list 当作双向链表，等博主找到资料再做解释）
与向量 vector 相比，list 允许快速的插入和删除，且每次插入或删除一个元素，就配置或释放一个元素空间，对于任何位置的元素插入或元素移除，list 永远是常数时间。
List 不再能够像 vector 那样以普通指针作为迭代器，因为其节点不保证在储存空间中连续存在。list 迭代器必须有能力指向 list 的节点，并有能力进行正确的递增、递减、取值、成员存取等操作。所谓 list 迭代器正确的递增、递减、取值、成员取用操作是指，递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取用的是节点的成员。
List 有一个重要性质：插入操作（insert）和合并操作（splice）都不会造成原有的 list 迭代器失效。这在 vector 是不成立的，因为 vector 的插入操作可能造成记忆体重新配置，导致原有的迭代器全部失效。甚至 list 的元素删除操作（erase）也只有“指向被删除元素”的那个迭代器失效，其他迭代器不受任何影响。
在使用 list 类模版时，也必须包含相应的头文件：#include<list>，list 对象的声明与 vector 类似，这里仅仅介绍一下 list 的成员函数。
1、声明 list 容器
- list list1; // 声明一个空的 list1
- list list2 (4, 100); // 声明以个含 4 个 100 的 list2
- list list3 (list2.begin(), list2.end()); // 用 list2 的迭代器内容声明 list3
- list list4 (list3); // 声明 list4 为 list3 的一个副本
- list list5(size); // 声明一个含 size 个默认值为 0 的 list5
- list1.~list(); // 注销 list
2、list 与 vector 不相同的一些操作
List 与 vector 相同的一些操作，这里仅列出函数名，不再进行具体说明：Begin/end/rbegin/rend/empty/size/Max_size/resize/insert/erase/swap/clear。
以下这些函数是 list 与 vector 不同的函数：
list<int> list1;
1、访问 list 元素
- list1.front()：返回第一个元素的值。
- list1.back()：返回最后一个元素的值。
2、list 元素的插入与删除
- list1.push_front(x)：把元素 x 插入到链表头部。
- list1.pop_front()：删除第一个元素。
- list1.push_back(x)：把元素 x 插入到链表尾部。
- list1.pop_back()：删除最后一个元素。
- list1.remove(val)：删除链表中所有值为 val 的元素。
- list1.remove_if(pred)：删除链表中谓词 pred 为真的元素（谓词即为元素存储和检索的描述，如 std::less<>，std::greater<> 那么就按降序/升序排列，你也可以定义自己的谓词）。
- list1.unique()：删除链表中所有重复的元素（这个函数博主在 VS 上测试的时候，并没有删除所有重复的元素，大家使用的时候最好也亲测一下。。。）。
- list1.unique(pred)：根据谓词 pred 删除所有重复的元素，使链表中没有重复元素。
3、list 拼接操作
- splice()：链表拼接，参数 position 是迭代器而不是下标。
- list1.splice ( position, list2 )：将 list2 中的所有元素插入到 list1 中 position 处，list2 会被清空，position 仍然指向 list1 中的那个元素。
- list1.splice ( position, list2, iter )：将 list2 中 iter 处的元素插入到 list1 中 position 处，list2 会将 iter 指向的元素删除，iter 失效。
- list1.splice ( position, list2, first, last )：将 list2 中[first,last)位置处的元素插入到 list1 的 position 处。
4、list 合并操作
- merge(listref)：链表合并：把 listref 所引用的链表中的所有元素插入到链表中，可指定合并规则。
- OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result);
- OutputIterator merge (InputIterator1 first1, InputIterator1 last1, InputIterator2 first2, InputIterator2 last2, OutputIterator result, Compare comp); // 由于参数复杂，这里列出了 C++ 官网给出的原函数，具体的例子可以参考C++官网.
5、list 排序操作
- sort()：根据默认的谓词对链表排序，默认升序。
- sort(pred)：根据给定的谓词对链表排序。
3、vector 与 list 之间的区别
C++ 标准库中，容器 vector 和 list 都可以用来存放一组类型相同的数据。而且二者不同于数组的一点是，支持动态增长。但它们还是有几点不同：
- Vector 是顺序表，表示的是一块连续的内存，元素被顺序存储；list 是双向链表，在内存中不一定连续。
- 当数值内存不够时，vector 会重新申请一块足够大的连续内存，把原来的数据拷贝到新的内存里面，再释放旧空间；list 因为不用考虑内存的连续，因此新增开销比 vector 小。
- List 只能通过指针访问元素，随机访问元素的效率特别低，在需要频繁随机存取元素时，使用 vector 更加合适。
- 当向 vector 插入或者删除一个元素时，需要复制移动待插入元素右边的所有元素；因此在有频繁插入删除操作时，使用 list 更加合适。
- Vector 和 deque 支持随机访问，而 list 不支持随机访问，因此 list 不支持[ ]访问。