C++标准模板库（STL）——list的使用
文章目录
- C++标准模板库（STL）——list的使用
- 1、 标准库中的list
- 2、 list 的构造函数
- 3、 list迭代器的使用
- 迭代器的使用
- 迭代器封装
- 迭代器的分类
- 4、 list的容量
- empty
- size
- 5、 list的元素访问
- front
- back
- 6、 list的元素修改
- push_front
- pop_front
- push_back
- pop_back
- insert
- erase
- swap
- clear
- 7、 list迭代器失效问题
- 8、 vector与list的比较
1、 标准库中的list
list的文档介绍
使用list要包含#include头文件
- std::list 是带头双向循环链表容器，一个哨兵头节点和若干有效数据节点，哨兵头节点不储存数据，
其他节点储存一个数值（_data），以及指向前后元素的指针(_prev _next)。 - 如图T为储存元素的类型，Alloc为分配器类型。 分配器就是C++容器用来管理内存的工具，Alloc让你可以自定义list的内存分配方式，默认使用标准库自带的allocator就行
- 由于链表是双向的，使得在链表的任意位置插入删除数据时，时间复杂度为O（1）
- forward_list（单向链表）只能正向遍历，但是空间占用和效率更优，std::list（双向链表）可以双向遍历
- 和string、vector相比，list在任意位置的插入删除操作表现更好，但是随机访问的空间复杂度为O（n），string、vecotr的随机访问时O（1），比如查找某个元素
2、 list 的构造函数
#include<iostream>#include<vector>#include<list>using namespace std;int main(){//构造一个空的int类型链表list<int> l1;//创建有5个10的链表list<int> l2(5, 10);//使用迭代器，把v的元素复制到l3vector<int> v = { 1,2,3,4,5 };list<int> l3(v.begin(), v.end());//拷贝构造，拷贝l2给l4list<int> l4(l2);//c++11支持初始化列表构造list<int> l5 = { 1,2,3,4,5 };return 0;}
从监视窗口看，链表储存数据的方式很像数组，但其实这是监视窗口为了可视化方便才设计成这样，底层链表储存数据其实是一个一个结点
3、 list迭代器的使用
迭代器的使用
是的，list遍历容器依旧使用iterator迭代器，再次强调迭代器是C++容器统一的访问元素的方式
不过list的迭代器不再是单纯的指针，而是指针的封装，这个我们讲到list的底层实现的时候再解释
begin返回指向容器第一个元素的迭代器，end返回指向最后一个元素下一个位置的迭代器，这组接口用于正向遍历容器
rbegin返回指向最后一个元素的反向迭代器（即end位置的反向迭代），rend返回指向第一个元素前一个位置的反向迭代器，这组接口用于反向遍历容器
迭代器封装
- C++的三大特性之一封装，除了之前学习的类封装，还有迭代器封装。迭代器提供了通用的相似的遍历容器方式，并且封装屏蔽了容器结构的差异，和底层实现细节。使用迭代器时不需要关心容器是数组还是链表，只要拿着迭代器按照统一的方式遍历操作元素就行（如输出元素）
- 试想一下，如果没有迭代器，我们需要遍历vector、list,还得先要了解它们的底层差异，非常麻烦。得给 vector 写一个遍历函数（基于下标 v[i]），再给 list 写一个遍历函数（基于链表指针 node->next），代码会变得非常冗余
- 而且实现算法时用迭代器函数模板方式实现，跟底层容器解耦
#include<iostream>#include<vector>#include<list>using namespace std;//求容器所有元素之和//用模板函数，接收不同类型（vector,list等）的迭代器template<typename Iterator>int sum(Iterator begin, Iterator end){int s = 0;for (auto it= begin; it != end; ++it){s += *it;}return s;}int main(){//调用时vector和list完全无差别vector<int> v{ 1,2,3,4 };list<int> l{ 1,2,3,4 };cout << sum(v.begin(), v.end()) << endl; //输出10cout << sum(l.begin(), l.end()) << endl; //输出10return 0;}迭代器的分类
一个算法不是所有的容器都可以使用，算法对迭代器是有要求的，要求就隐藏在迭代器的名字中，如算法库的sort
sort算法中迭代器要求是RandomAccessIterator（随机访问迭代器），随机访问迭代器指的是list、vector这些类，而list（双向迭代器）就不适用了，list只能使用自身sort成员函数
#include<iostream>#include<vector>#include<list>#include<algorithm>using namespace std;int main(){vector<int> v = { 1,4,2,5,3 };list<int> l = { 1,4,2,5,3 };sort(v.begin(), v.end());//不能运行，编译报错//sort(l.begin(), l.end());//使用list成员函数sortl.sort();for (auto it : v) cout << it << " ";cout << endl;for (auto it : l) cout << it << " ";cout << endl;return 0;}类似有要求的算法还有很多
算法库文档
所以我们要想正确使用算法函数，得先去算法库看看函数使用的要求，此外我们还得了解不同容器的迭代器类型，同样可以去容器库查阅，如下图，list的迭代器是双向迭代器
| 分类 | 功能 | 容器 |
|---|---|---|
| 输出迭代器（Input Iterator） | 仅支持读操作、++、!= | 用于从容器中读取元素 |
| 输出迭代器（Output Iterator） | 仅支持写操作、++、!= | 用于向容器中写入元素 |
| 前向迭代器（Forward Iterator） | 支持读写、++、!=，单向遍历 | 单链表（forward_list）、哈希表 |
| 双向迭代器（Bidirectional Iterator） | 支持读写、++、–、!=，双向遍历 | 双向链表（list）、红黑树（map/set） |
| 随机访问迭代器（Random Access Iterator） | 支持读写、++、–、!=、[]、算术运算（+/-），随机访问 | 数组（array）、向量（vector）、双端队列（deque） |
不同迭代器的类型，由容器的底层结构决定。迭代器的分类是按功能从弱到强递进的，满足 “子类迭代器支持父类所有操作”（即 “is-a” 继承关系），现在我们可以暂时理解为包含于被包含关系，如随即迭代器的功能包含双向迭代器，随机访问迭代器同时支持双向迭代器的所有操作（++、-- 等)
4、 list的容量
empty
检测 list 是否为空，是返回true，否则返回false，用于判断链表是否没有有效元素，时间复杂度O(1)
size
返回list中有效节点个数，时间复杂度O(n)（需遍历计数）
5、 list的元素访问
front
返回 list 的第一个节点中值的引用，用于快速访问链表头元素，支持读写操作
back
返回 list 的最后一个节点中值的引用，用于快速访问链表尾元素，支持读写操作
6、 list的元素修改
push_front
在 list 首元素前插入值为val的元素。 链表头部插入，时间复杂度O(1)
pop_front
删除 list 中第一个元素。链表头部删除，时间复杂度O(1)
push_back
在 list 尾部插入值为val的元素，链表尾部插入，时间复杂度O(1)
pop_back
删除 list 中最后一个元素，链表尾部删除，时间复杂度O(1)
insert
在 list 的pos位置中插入值为val的元素, 支持在任意迭代器位置插入元素，时间复杂度O(1)
erase
删除 list的pos位置的元素，返回一个迭代器，该迭代器指向被删除元素的下一个元素。时间复杂度O(1)
swap
交换两个 list 中的元素, 时间复杂度O(1)，只需交换两个链表的头节点等核心指针即可
clear
清空 list 中的有效元素，遍历链表并逐个删除节点，时间复杂度O(n)
#include<iostream>#include<list>using namespace std;void print(const list<int>& l){for (auto it : l){cout << it << " ";}cout << endl;}int main(){//初始化空listlist<int> l;cout << "空list: ";print(l);//尾插、头插l.push_back(10);l.push_back(20);l.push_front(2);l.push_front(1);cout << "头插尾插后： ";print(l);//头删尾删l.pop_back();l.pop_front();cout << "头删尾删后：" ;print(l);//insert在任意位置插入auto it = l.begin();//it指向第一个元素++it; //it指向第二个元素l.insert(it, 8);cout << "insert插入后： ";print(l);//erase在任意位置删除it = l.begin();it++; //此时it指向8l.erase(it);cout << "erase删除后： ";print(l);//swap交换两个list元素list<int> l2 = { 11,22,33 };cout << "交换前l2：";print(l2);l.swap(l2);cout << "swap后的l: ";print(l);cout << "swap后的l2: ";print(l2);//clear清空所有有效元素l.clear();cout << "clear后l：" ;print(l);cout << "clear后是否为空: " << l.empty() << endl;return 0;}
7、 list迭代器失效问题
std::list是双向循环链表，迭代器失效指的是，迭代器指向的节点无效。因此插入操作不会导致迭代器失效；删除操作仅会使指向被删除节点的迭代器失效，其他迭代器不受影响。因此删除时，必须先备份下一个迭代器再删除
#include<iostream>#include<list>using namespace std;int main(){list<int> l = { 1,2,3,4,5 };auto it = l.begin();//该操作导致程序崩溃，因为erase执行后，it指向的节点已被删除，it无效//再给it++相当于使用野指针，程序崩溃/*while (it != l.end()){l.erase(it);++it;}*/while (it != l.end()){//erase返回一个指向被删除元素的下一个元素的迭代器it = l.erase(it);//也可以利用it++的先使用后自增的特性，在删除前先获取下一个节点的迭代器并备份// 删除操作后新的迭代器（备份的下一个节点迭代器）仍有效//l.erase(it++);}return 0;}8、 vector与list的比较
| vector | list | |
|---|---|---|
| 底层结构 | 动态顺序表，底层是一段连续的内存空间 | 带头结点的双向循环链表，节点是一小块一小块分散储存的 |
| 随机访问 | 支持随机访问（如 v[2]），时间复杂度 O(1) | 不支持随机访问，访问元素需遍历，时间复杂度 O(N) |
| 插入与删除 | 任意位置插入 / 删除需搬移元素，时间复杂度 O(N)，插入可能触发扩容（开辟新空间、拷贝元素、释放旧空间），进一步降低效率 | 任意位置插入 / 删除仅需修改节点指针，时间复杂度 O(1)，无搬移和扩容开销 |
| 空间利用率 | 连续内存空间，不易产生内存碎片，空间和缓存利用率高 | 节点动态开辟，小节点易产生内存碎片，空间和缓存利用率低 |
| 迭代器 | 原生态指针（本质是指向连续内存的指针） | 对节点指针的封装（需通过迭代器接口访问节点） |
| 迭代器失效 | 插入时若扩容，所有迭代器失效；删除时当前迭代器失效，需重新赋值 | 插入时迭代器不失效；删除时仅指向被删节点的迭代器失效，其他迭代器不受影响 |
| 使用场景 | 适合高效存储、需随机访问、对插入删除效率要求低的场景（如存储固定结构的数据集） | 适合大量插入 / 删除操作、对随机访问无要求的场景（如频繁增删的任务队列） |