1. 前言
本质重点:
本章重点讲解list的接口函数的熟悉
并且讲解list迭代器失效的特性
最后讲解迭代器的功能分类以及
算法库函数中谁能用谁不能用
STL标准库中的list是一个
带头双向循环链表
和vector不同,list没有支持[ ]访问
以及resize和reserve容量相关的函数
这是因为list不能随机访问数据
并且list的迭代器的底层明显不是指针了
那它的底层到底是啥?
list会和vector一样有迭代器失效问题吗?
带着这些疑问,我们来进入今天的学习分享
2. list的使用
我们还是在网站:cplusplus中查询字典
和vector一样,list也有两个模板参数
但是第二个模板参数是和内存效率相关的
所以现在的学习暂时不用管它(它有缺省值)
list的使用分为以下几个阶段进行:
- list的构造,析构,拷贝构造函数
- list迭代器的使用
- list容量相关的操作
- list的增删查改
2.1 list的构造函数
list的构造函数:
第一个是无参构造,直接跳过
第二个是用n个val初始化list对象
第三个是用一段迭代器区间构造
第四个是用一个初始值构造
看起来平平无奇,来实操一下:
list<int> l1;//无参构造 list<int> l2(10,5);//用10个5初始化链表 vector<int> vv{1,2,3,4,5,6}; list<int> l3(vv.begin(),vv.end());//用迭代器区间初始化 list<char> l4('a');//用一个字符来初始化
list的拷贝构造和析构函数在使用
list时不会显示调用,所以将它们忽略掉
2.2 list迭代器的使用
虽然list的迭代器底层不是指针
但是可以把它理解为指针来使用
这四个函数都是老朋友了,不多介绍了
唯一值得注意的是下图:
begin和rend的指向相同
end和rbegin的指向相同
迭代器遍历链表:
vector<int> vv{1,3,5,7,9,11,13,15}; list<int> l(vv.begin(),vv.end()); auto it = l.begin(); while(it!=l.end()) { cout << *it<< " "; it++; }
范围for遍历链表:
vector<int> vv{1,3,5,7,9,11,13,15}; list<int> l(vv.begin(),vv.end()); for(auto x : l) { cout << x<< " "; }
注:list不支持随机访问,不能用[]
一个小tips:
在写用迭代器遍历容器时,我们往往
会写it!=l.end(),而不是it<l.end()
这是因为在list中,空间并不连续,用小于
符号很大概率会出错,但是在string
和vector中,空间是连续的,用<也没问题
2.3 list容量相关操作
这里最简单,和vector一模一样
只有这四个函数接口比较常用!
2.4 list的增删查改
首先映入眼帘的头插/头删,尾插/尾删
这几个函数的意思很明了,直接跳过
insert插入:
insert函数要输入一个迭代去位置进行插入
可以插入一个数据或插入一段迭代器区间
erase删除:
erase函数可以删除一个迭代器的数据
或者删除一段迭代器区间
clear清空有效元素:
list不像vector一样有size和capacity
list的clear函数是将链表清空
(除头节点外)
增删查改实操:
vector<int> vv{1,5,10,15,20,100,120}; list<int> ll(vv.begin(),vv.end()); auto pos = find(ll.begin(),ll.end(),20); ll.insert(pos,250); ll.erase(ll.begin()+2); ll.clear();
3. list迭代器失效问题探讨
由于list的底层是双向带头循环链表
所以插入操作时,pos指向的节点的
位置始终都是一个位置,它们只改变
链接关系,并不连续,所以插入操作
并不会导致list迭代器失效
list迭代器失效只在erase删除时才会发生
erase删除的位置在空间上是唯一的
这个位置的数据被删除后,只是改变了
数据的链接关系,然而此位置已经不在
原先的链表中了,再次使用会出错!
STL库的erase提供了返回值来解决问题:
会返回被删除位置的下一个位置的迭代器
以后可以这样写代码来避免错误:
list<int> ll{1,2,3,4,5,6,7,8}; auto it=ll.begin(); while(it!=ll.end()) { if((*it)%2==0) { it=erase(it); } else { it++; } }
4. 算法库函数和list的关系
首先,迭代器从功能角度可以分类为:
- 正向迭代器: forward_iterator
- 双向迭代器: bidirectional_iterator
- 随机迭代器: random_iterator
它们分别支持且仅支持:
只支持++支持++和- -支持++,- -,+和-
常见的容器以及它们的迭代器类型:
| 容器 | 迭代器功能 |
| vector | 随机迭代器 |
| list | 双向迭代器 |
| stack | 不支持迭代器 |
| queue | 不支持迭代器 |
| deque | 随机迭代器 |
| set / multiset | 双向迭代器 |
| map / multimap | 双向迭代器 |
| priority_queue | 不支持迭代器 |
4.1 算法库函数的迭代器类型
现在再来看算法库的sort函数:
它的函数模板支持的是随机迭代器
再来看看算法库的reverse函数:
它的函数模板支持的是双向迭代器
我先给出以下的结论:
- 若函数模板给的随机迭代器
则只能传有随机迭代器的容器 - 若函数模板给的双向迭代器
则可以传有随机或者双向迭代器的容器 - 若函数模板给的单向迭代器
则三种迭代器都可以传进来!
可以看出它支持向上兼容!
4.2 list不能使用的算法库函数
可见,list是双向迭代器,而sort函数的
函数模板是随机迭代器
所以库函数中的sort无法排序链表
但是仔细查阅字典可以发现:
list类自己实现了一个不同于算法库的排序
此排序专门用于排序list中的数据!
虽然list有自己的sort函数来排序
但是当数据很多时,list自我实现的
sort的效率低的惊人!甚至还不如
将list的数据导入vector容器
再在vector容器中使用算法库的排序
排完序再导入到list中,这一步骤快!
5. 总结以及拓展
总的来说list的使用和vector大同小异
当然,要掌握list,list的模拟实现是不可少的
list的模拟实现将在下一节分享给大家
本章笔记:
- 请自行熟悉list接口函数
- list的insert不会导致迭代器失效
而erase会致使迭代器失效 - 迭代器从功能上可以划分为三种
它们向上兼容彼此 - list不能使用算法库中的sort
但list类中实现了专门排序链表的函数
拓展阅读:
? 下期预告:list的模拟实现以及对比vector的区别 ?
