Ⅰ . list 的介绍和使用
01 初识 list
我们已经学习过 string 和 vector 了,想必大家已经把握了查文档的本领
如今我们去学习如何使用 list ,最好仍旧打开文档去学习
list - C++ Reference
① list 是一个顺序容器
允许在恣意位置进行 O(1) 插入和删除的顺序容器,并提供双向迭代器
② list 底层是双向链表
双向链表中每个元素存储在互不相关的独立结点中,在结点中通过两个指针指向其前后元素
③ list 与 forward_list 非常相似
最大的不同就是 forward_list 是单链表,只能向前迭代
④ 与其他序列式容器相比(array,vector,deque)
list 通常在恣意位置进行插入、删除元素的效率更高,由于是 O(1)
list 和 forward_list 最大的缺陷是不支持随机位置的随机访问 举个例子:
如果要访问 list 中的第六个元素,必须从已知位置(如头部或尾部)迭代到该位置
在这段位置上迭代需要线性时间的时间开销,同时,list 还需要一些额外空间
以保存每个结点的相关联信息
02 创建 list
代码实现:
- #include<iostream>
- #include<list>
- using namespace std;
- int main()
- {
- list<int> l;
- return 0;
- }
复制代码 Ⅱ . list 的修改操纵
01 修改操纵的函数
02 push_back
在 list 尾部插入值为 val 的元素
代码实现:
- #include<iostream>
- #include<list>
- using namespace std;
- int main()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- return 0;
- }
复制代码 我们如今来打印一下
起首思考一个标题,还能使用下标 + 方括号的方式遍历嘛?
不行 由于 list 是链表,是通过指针毗连的,所以不支持随机访问
而 string 和 vector 可以,由于它们的物理结构是连续的
迭代器遍历:
- #include<iostream>
- #include<list>
- using namespace std;
- int main()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- // 迭代器
- list<int>::iterator it = l.begin();
- while (it != l.end())
- {
- cout << *it << " ";
- ++it;
- }
- cout << endl;
- return 0;
- }
复制代码 运行结果如下:
范围 for 就更简单了:
- // 范围for
- for (auto e : l)
- cout << e << " ";
- cout << endl;
复制代码 如果我们想倒着遍历,我们可以使用反向迭代器
使用 rbegin() 和 rend()
反向迭代器:
- // 反向迭代器
- list<int>::reverse_iterator rit = l.rbegin();
- while (rit != l.rend())
- {
- cout << *rit << " ";
- ++rit;
- }
- cout << endl;
复制代码 运行结果如下:
03 push_front
在 list 头部插入值为 val 的元素
代码实现:
- void list_test2()
- {
- list<int> l;
- l.push_front(1);
- l.push_front(2);
- l.push_front(3);
- l.push_front(4);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
04 pop_back
删除 list 中的末了一个元素
- void list_test3()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- cout << "删除前:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.pop_back();
- cout << "删除后:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
如果表内没有元素,进行删除操纵,会触发断言
05 pop_front
删除 list 中的第一个元素
- void list_test4()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- cout << "删除前:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.pop_front();
- cout << "删除后:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
06 insert
在上一节讲授 vector 实现的时候,我们对迭代器失效的标题进行了简单探究
这里 list 的 insert 同样会涉及迭代器失效的标题,我们在模拟实现的时候再进行探究
07 clear
清空 list 中的有用元素,使容器巨细的 size 变为 0
代码演示:
- void list_test5()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- cout << "清空前:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.clear();
- cout << "清空后:";
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
08 erase
代码演示:
- void list_test6()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- list<int>::iterator it = find(l.begin(), l.end(), 4);
- if (it != l.end())
- {
- l.erase(it);
- }
- else
- {
- cout << "没找到";
- }
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
Ⅲ . list 容量操纵
01 size 返回有用结点个数
代码演示:
- void list_test7()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- cout << "有效节点个数:";
- cout << l.size() << endl;
- }
复制代码 运行结果如下:
02 empty 检测容器是否为空
empty 是用来检测容器是否为空的,如果为空则返回 true,否则返回 false。
代码演示:
- void list_test8()
- {
- list<int> l;
- l.empty() == true ? cout << "为空" : cout << "不为空";
- }
复制代码 运行结果如下:
03 resize 调整容器巨细
list 中的 resize 和之前的 resize 的 "扩容" 有点不一样,它没有容量。
这里的 resize 是调整容器的巨细,使其包罗 个元素。
代码演示:
- void list_test9()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.resize(10, 5);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
Ⅳ . list 的其他操纵
01 reverse 逆置
代码演示:
- void list_test10()
- {
- list<int> l;
- l.push_back(1);
- l.push_back(2);
- l.push_back(3);
- l.push_back(4);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.reverse();
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
02 sort 排序
代码演示:
- void list_test11()
- {
- list<int> l;
- l.push_back(4);
- l.push_back(2);
- l.push_back(6);
- l.push_back(1);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.sort();
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
03 unique 去重
去重之前是有要求的,去重之前肯定要先排序,如果不排序可能会去不干净
代码演示:
- void list_test12()
- {
- list<int> l;
- l.push_back(2);
- l.push_back(1);
- l.push_back(2);
- l.push_back(1);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- l.sort();
- cout << "去重后:";
- l.unique();
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
如果不排序,会导致去不干净:
- void list_test12()
- {
- list<int> l;
- l.push_back(2);
- l.push_back(1);
- l.push_back(2);
- l.push_back(1);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- //l.sort();
- cout << "去重后:";
- l.unique();
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码
04 remove
remove 只需要给一个元素的值,它就可以本身找本身删
代码演示:
- void list_test13()
- {
- list<int> l;
- l.push_back(10);
- l.push_back(20);
- l.push_back(30);
- l.push_back(40);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- // 如果删一个存在的元素
- l.remove(10);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- // 如果待删元素不存在
- l.remove(0);
- for (auto e : l)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
05 splice 接合
简单来说就是把一个链表转移到另一个链表中
代码演示:
- void list_test14()
- {
- list<int> l1;
- l1.push_back(1);
- l1.push_back(2);
- l1.push_back(3);
- cout << "l1:";
- for (auto e : l1)
- cout << e << " ";
- cout << endl;
- list<int> l2;
- l2.push_back(10);
- l2.push_back(20);
- l2.push_back(30);
- cout << "l2:";
- for (auto e : l2)
- cout << e << " ";
- cout << endl;
- list<int>::iterator pos = l1.begin();
- // 把l2的内容接到l1的begin()前面
- l1.splice(pos, l2);
- cout << "接合后";
- for (auto e : l1)
- cout << e << " ";
- cout << endl;
- }
复制代码 运行结果如下:
免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!更多信息从访问主页:qidao123.com:ToB企服之家,中国第一个企服评测及商务社交产业平台。 |