阅读量:2
在了解了vector之后，我们只需要简单学习List与vector不一样的接口即可
1.list的基本接口
1.1 iterator
list中，与vector最大的区别就是迭代器由随机迭代器变成双向迭代器
string和vector中的迭代器都是随机迭代器，支持+-等，而LIST的双向迭代器不支持双目运算+ -, 只支持弹幕运算++ --
vector中对于迭代器的解释：
list中对于迭代器的解释：双向带头链表(bidirectional iterator)
双向迭代器不支持+ -的原因：
效率低，毕竟链表无法随机访问 ，自然也无法方括号访问
1.2 sort
由于排序算法的底层是快排，而快排不支持随机迭代器“RandomAccessIterator”
并且双向迭代器不支持迭代器相减，快排中有一些三数取中的操作无法进行，所以不能使用std中的sort，否则在运行时会有运行错误：
因此链表中有自己的sort（底层是归并排序）：
升序：
降序（正如演示中的代码，链表的构造函数用法与vector一致）：
1.3两个建议先排序再使用的函数：
li.unique();
li.merge(li1);
unique，即去重，将重复的元素去掉。
先排序，再去重，否则去不干净
不排序就去重，在相同元素未连续的情况下是无法起到效果的
先降序：
merge,即合并
因为其原理是用双指针取小的尾差，所以先排序，再合并，就能将两个元素中一样的元素有序合并到一起
2.list中排序的效率问题
链表的排序复杂度和vector的排序复杂度都是O(nlogn)
但是vector的效率几乎稳定在list自带sort的2~5倍左右
测试代码：
void effciency_test() { srand(time(0));//初始化时间种子，避免伪随机数 int N = 100000000; vector<int> v; for (int i = 0; i < N; ++i) { v.push_back(i + rand()); } list<int> li; for (int i = 0; i < N; ++i) { li.push_back(rand() + i); } size_t begin1 = clock(); sort(v.begin(), v.end()); size_t end1 = clock(); size_t begin2 = clock(); li.sort(); size_t end2 = clock(); cout << "time of vector : " << end1 - begin1 << endl; cout << "time of list : " << end2 - begin2 << endl; }debug版本下，两倍左右：
realease版本下，五倍左右：
建议的方法是：先将链表的内容拷贝到一个vector，然后再对vector进行sort
我们拷贝之后再进行测试： 
只有少量数据时，不太在乎效率的时候使用list自带的sort
3.结合splice（剪切函数）
中间的list& x表示会有元素被转出的链表
注意，不是复制，就是把节点转移进去。
观察官网中的例子：
这样操作之后，链表1就是1 10 20 30 2 3 4
链表2就是empty
由于其不存在复制的问题，我们还可以通过splice函数的功能将其自己的元素调换位置
测试函数：
void test_of_splice() { list<int> li1{ 1,2,3,4,5 }; list<int> li2{ 1,2,3,4,5 }; list<int> li3{ 1,2,3,4,5 }; list<int> li{ 2,5,99,89,68 }; li1.splice(li1.begin(), li);//entire list //li2.splice(li2.begin(), li, --li.end());//single element //li3.splice(li3.begin(), li, li.begin(), find(li.begin(), li.end(), 89));//element range for (auto e : li1) { cout << e << " "; } cout << endl; for (auto e : li) { cout << e << " "; } cout << endl; for (auto e : li) { cout << e << " "; } cout << endl; }由于splice会让被移动的元素离开原链表，所以建议一次一次的测试。
