【C++进阶五】list深度剖析
1.什么是list
STL标准库中的list是一个带头双向循环链表
和vector不同,list没有支持[ ]访问以及resize和reserve容量相关的函数，这是因为list不能随机访问数据，并且list的迭代器的底层不是指针
和vector一样,list也有两个模板参数，但是第二个模板参数是和内存效率相关的，所以现在的学习暂时不用管它(它有缺省值)
2.list的使用
2.1构造函数
list<int> l1;//无参构造
list<int> l2(10,6);//用10个6初始化链表
vector<int> v{1,2,3,4,5,6};
list<int> l3(v.begin(),v.end());//用迭代器区间初始化
list<char> l4('a');//用一个字符来初始化
2.2list迭代器
虽然list的迭代器底层不是指针，但是可以把它理解为指针来使用
迭代器遍历链表:
vector<int> v{1,3,5,7,9,11,13,15};
list<int> l(v.begin(),v.end());
auto it = l.begin();
while(it != l.end())
{
cout << *it << " ";
it++;
}
范围for遍历链表:
vector<int> v{1,3,5,7,9,11,13,15};
list<int> l(v.begin(),v.end());
for(auto x : l)
{
cout << x << " ";
}
注:list不支持随机访问,不能用[]
在写用迭代器遍历容器时，我们往往会写it!=l.end()，而不是it<l.end()，这是因为在list中，空间并不连续，用小于符号很大概率会出错，但是在string和vector中，空间是连续的，用<也没问题
2.3容量操作
和vector一样
常用的四个接口：
2.4增删查改
insert：insert函数要输入一个迭代器位置进行插入，可以插入一个数据或插入一段迭代器区间
erase：erase函数可以删除一个迭代器的数据或者删除一段迭代器区间
clear：list的clear函数是将链表清空(除头节点外)
因为list不像vector一样有size和capacity
vector<int> v{1,5,10,25,40,100,110};
list<int> l(v.begin(),v.end());
auto pos = find(l.begin(),l.end(),40);
l.insert(pos,250);
l.erase(l.begin()+2);
l.clear();
3.list迭代器失效
由于list的底层是双向带头循环链表，所以插入操作时，pos指向的节点的位置始终都是一个位置，它们只改变链接关系，并不连续，所以插入操作并不会导致list迭代器失效
list迭代器失效只在erase删除时才会发生
删除节点后，当前节点的指针1iterator失效，所以要更新iterator
STL库的erase提供了返回值来解决问题：
4.迭代器类型
迭代器从功能角度可以分类为：
- 正向迭代器: forward_iterator，只支持
++ - 双向迭代器: bidirectional_iterator，支持
++和-- - 随机迭代器: random_iterator，支持
++,- -,+和-
常见的容器以及它们的迭代器类型：
算法库的sort函数，它的函数模板支持的是随机迭代器
算法库的reverse函数，它的函数模板支持的是双向迭代器
结论：
- 若函数模板给的随机迭代器，则只能传有随机迭代器的容器
- 若函数模板给的双向迭代器，则可以传有随机或者双向迭代器的容器
- 若函数模板给的单向迭代器则三种迭代器都可以传进来
5.list不能使用的算法库函数
list的迭代器是双向迭代器,而sort函数的函数模板是随机迭代器，所以库函数中的sort无法排序链表
所以list类自己实现了一个不同于算法库的排序：
虽然list有自己的sort函数来排序，但是当数据很多时，list自我实现的sort的效率低的惊人，效率甚至还不如将list的数据导入vector容器，再在vector容器中使用算法库的排序，排完序再导入到list中