C++STL: list（双链表） 简单介绍，了解迭代器类型，list sort 的弊端

C语言数据结构中我们就学习过链表， 链表又分为单链表和双链表。这里我们主要讲双链表

1.list简单介绍

list的基本接口和前面讲的vector的接口基本一致，重点讲不一样的:

1.0 assign 赋值

assign支持 一段迭代器区间，或者n个val赋值，迭代器可以不是同类型的，比如可以是vector的迭代器。

1.1 insert，erase的迭代器失效

list 是针对节点进行操作，insert不涉及扩容问题，所以insert不会迭代器失效

erase会迭代器失效，删除了节点就没了。

1.2list不支持 operator[ ]

list没有operator[ ] 重载。[ ] 是为vector 和 string等其他容器使用的，不支持全部容器，比如list

1.3 算法库sort不支持list使用，原因是迭代器类型

list 有 sort函数 ，是排序，算法库也有一个sort

用算法库的sort会发现，不能排序 list ，算法库的sort会报错

原因是 算法库 的 sort底层 是用 迭代器 相减 ，list的迭代器不支持相减

接下来从迭代器角度，深度理解这个原因：

1.3.1迭代器类型

查文档可发现，双链表是双向迭代器，支持++，--，但不支持加 + 减 -

单链表 是 单向迭代器 只支持++

vector 是 随机迭代器，++，--，+，- 全部支持

结合容器的底层空间特性，也大概能猜到它是什么迭代器。

双链表，底层空间不连续，是由节点链接，迭代器 it+或- n 的时间复杂度是O（n）,性能很差（因为节点都是离散的，需要遍历多次++或--代替+，-的功能，才能找到节点），但是++，-- 是O（1）,性能很好，所以双链表是双向迭代器

单链表，和双链表几乎一样，区别是只能往前，只能支持 ++ 所以是单向迭代器

vector，底层空间连续，可以完全由指针充当迭代器，指针本身支持+，-，++，--，效率都是O（1）（直接通过地址计算，空间是连续的，不像双链表），所以是随机迭代器。

算法库的sort 的参数是 随机迭代器，因此list的不能使用

如果参数要求是双向迭代器，其实随机迭代器也能，因为是功能上包含关系

迭代器类型，其实是继承关系（继承和多态相关知识）。单向在双向内，单向，双向在随机内

再看一种特殊的迭代器类型：

IuputIterator ,这是什么鬼？

其实这是输入迭代器，C++高度抽象出来的一种特殊迭代器（后面的知识），还有只读迭代器。这里传单向，双向，随机都行

1.4unique 除去相邻重复元素

如标题，是除去 相邻 重复 元素 ，所以不相邻不行。那就需要和 sort 组合使用，把重复的挨在一起。

本质就是快慢双指针算法，判断元素是否相同，数据结构中讲过。了解这个函数

1.5 list 的 sort 函数 排序（不推荐，性能低）

单纯存储大量数据还是vector更好（不频繁插入，删除，挪动数据，且数据量巨大）。虽然他会扩容，但是扩容开销没想象那么大。扩容越扩容越慢

list 的 sort 是 底层是归并排序，它的时间复杂度是n*logn 库里的sort 快速排序也是n*logn ，看似一样，实际上性能相差了几倍。

时间复杂度只是告诉你他们在同一个量级，实际上还是有性能大小之分。

我们利用某种方法，测试list的 排序 和 库里的排序性能差异：

单位毫秒：

100万个数据：

这是debug版本下的测试。不具参考性，因为debug会添加很多调试信息，我们再用release版本：

如图，这说明list 的sort 效率比较低。 性能差异大，数据越大，性能差距越明显。

所以尽量不要用list sort

第二个测试：把 list 的值 通过迭代器区间构造 传给vector，然后再用std：：sort 排序vector，最后把数据还给 list 对照组是，直接用 list sort 排序，我们对比一下他们的性能差异：

测试结果：

如图，即使涉及两步多余的赋值，构造操作，std：：sort 仍比 list sort 快一倍。 这更说明了，vector更适合排序数据，存储数据。（前提是没有大量的插入，删除，挪动数据，数据量巨大） list sort 的弊端就是效率不高，请尽量小心使用