C++之list容器介绍及使用方式
一、list底层结构
list底层是带头节点的双向循环链表
- 双向:可以从前往后,也可以从后往前遍历
- 循环:找尾节点的时间复杂度为O( 1 )
- 带头节点:代码实现简单,不用考虑链表为空等特殊情况,可令end()迭代器指向头节点的位置
二、构造方法
构造函数
list<int> l1; list<int> l2(5, 3); //迭代器 vector<int> v{ 1,2,3,4,5 }; list<int> l3(v.begin(), v.end()); //C++11 list<int> l4{ 1,2,3,4,5 };
拷贝构造函数
利用l1拷贝构造l2
list<int> l1{ 1,2,3,4,5 }; list<int> l2(l1);
三、元素访问和迭代器
back&front
list<int> l1{ 1,2,3,4,5 }; cout << l1.front() << endl; cout << l1.back() << endl;
三种遍历方式
list<int> l1{ 1,2,3,4,5 };
采用下面三种方式对下面这个list<int>类型的对象进行遍历打印:
1.迭代器
list<int>::iterator it = l1.begin(); for (it; it != l1.end(); it++) { cout << *it << " "; } cout << endl;
打印结果:
2.范围for
注意这里e是int类型,不用再进行解引用
//范围for for (auto e : l1) { cout << e << " "; } cout << endl;
打印结果:
3.反向迭代器
list<int>::reverse_iterator rit = l1.rbegin(); for (rit; rit != l1.rend(); rit++) { cout << *rit << " "; } cout << endl;
打印结果:
四、元素修改
尾插、头插、尾删、头删
insert、erase
list支持任意位置的插入,注意list对象的迭代器不支持加减数字,因为其底层空间不连续,如图:
如果要往一个位置进行插入,可以通过find函数返回位置进行,find是一个通用的函数模板,返回值是传入参数的迭代器类型,
list<int> l1{ 1,2,3,4,5 }; l1.insert(find(l1.begin(), l1.end(), 3), 10);//任意位置插入 l1.erase(find(l1.begin(), l1.end(), 10), l1.end());//任意位置的删除
swap
list内置的交换函数
list<int> l1{ 1,2,3,4,5 }; list<int> l2{ 5,6,7,8,9 }; l1.swap(l2);
resize
resize改变有效元素的个数,多的元素用第resize二个参数填充,如果没有给第二个参数,则默认用T()。
list<int> l1{ 0,1,2 }; l1.resize(5, 3);
五、特殊操作
remove
删除值为value的元素
list<int> l1{ 3,0,1,3,2,3 }; l1.remove(3);
remove_if
remove_if的参数是一个判断条件,可以是函数指针或者函数对象
//判断5的倍数 bool MultipleFive(int n) { return 0 == n % 5; } void Test10() { //此处传递函数指针 list<int> l1{ 10,0,1,3,5,7,20 }; l1.remove_if(MultipleFive); }
unique、sort
unique,去重,删除所有重复元素,使用unique之前要先调用sort进行排序,这里的sort是list内置的sort,不是标准库中的sort
void Test() { list<int> l1{ 1,3,3,5,4,0,2,5,4 }; l1.sort();//默认升序 l1.unique();//删除重复元素 }
结果:
对于sort的使用,还可以自定义函数,并将函数指针作为参数传递给sort函数进行排序:
reverse
对链表进行逆置
void Test() { list<int> l1{ 1,3,5,7,9 }; l1.reverse(); }
结果:
六、list迭代器失效问题
list底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
erase导致的迭代器失效
如图所示,it迭代器所指向的位置被删除后,迭代器失效:
改正方法:
while (it != l1.end()) { //it=l1.erase(it); l1.erase(it++); }
这里 l1.erase(it++)语句也能达到效果,因为后置++会将自增后的结果保存在临时变量中,而前置则不可以。
resize导致的迭代器失效
resize减少有效元素个数也会导致迭代器失效:
list<int> l1{ 1,3,5,7,9 }; auto it = l1.end(); l1.resize(3);
上面这个程序中,reseze减少有效元素个数后,it指向的位置元素已经被删除,迭代器失效,如果再使用该迭代器,则会出错。
七、vector与list对比
vector(动态顺序表)
list(带头结点的双向循环链表)
对比 | vector | list |
---|---|---|
底层结构 | 动态顺序表,连续空间 | 带头结点的双向循环链表 |
访问 | 支持随机访问,首地址+下标 | 不能随机访问,可通过find查找,访问随即元素时间复杂度O(N) |
插入删除 | 任意位置插入和删除效率低,需要搬移元素,时间复杂度为O(N),插入时有可能需要增容,增容:开辟新空间,拷贝元素,释放旧空间,导致效率更低 | 任意位置插入和删除效率高,不需要搬移元素,时间复杂度为O(1) |
空间利用率 | 底层为连续空间,不容易造成内存碎片,空间利用率较高,缓存利用率高。可以一次将一个数据附近的空间都加载到缓存,不用频繁地从内存读取数据 | 底层节点动态开辟,容易造成内存碎片,空间利用率低,缓存利用率低 |
迭代器 | 原生态指针 | 对指针进行了封装 |
迭代器失效 | 容量相关的操作都有可能导致迭代器失效,如插入引起的扩容,删除元素等 | 插入元素不会导致迭代器失效,删除节点会导致,且只影响当前迭代器,其他迭代器不受影响 |
使用场景 | 不关心插入和删除效率,支持随机访问 | 大量插入和删除操作,不关心随机访问的场景 |
总结
以上为个人经验,希望能给大家一个参考,也希望大家多多支持猪先飞。
原文出处:https://blog.csdn.net/qq_44631587/article/details/126413746
相关文章
Java8 实现stream将对象集合list中抽取属性集合转化为map或list
这篇文章主要介绍了Java8 实现stream将对象集合list中抽取属性集合转化为map或list的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-02-05- 这篇文章主要介绍了java8如何用Stream查List对象某属性是否有重复的操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-11
- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了C++中取余运算的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 这篇文章主要介绍了C#中list用法,结合实例形式分析了C#中list排序、运算、转换等常见操作技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Java8处理List的双层循环问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-19
- 这篇文章主要介绍了使用list stream:任意对象List拼接字符串操作,具有很好的参考价值,希望对大家有所帮助。如有错误或未考虑完全的地方,望不吝赐教...2021-09-09
- 这篇文章主要介绍了C++万能库头文件在vs中的安装步骤(图文),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-23
- 本篇文章小编并不是为大家讲解string类型的用法,而是讲解我个人比较好奇的问题,就是string 类型占几个字节...2020-04-25
- 这篇文章主要介绍了C# List 排序各种用法与比较的相关资料,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
- 这篇文章主要介绍了C++ bitset用法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-04-25
- 这篇文章主要介绍了Python 列表(List)的底层实现原理分析,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-09
- 这篇文章主要介绍了C++递归删除一个目录的实现方法,涉及到目录的操作及递归算法的应用,需要的朋友可以参考下...2020-04-25
- 虽然C++11引入了智能指针的,但是开发人员在与内存的斗争问题上并没有解放,如果我门实用不当仍然有内存泄漏问题,其中智能指针的循环引用缺陷是最大的问题。下面通过实例代码给大家介绍c++中的循环引用,一起看看吧...2020-04-25
- 这篇文章主要介绍了C++实现的O(n)复杂度内查找第K大数算法,结合实例形式分析了算法的原理以及具体实现方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++ 将数据转为字符串的几种方法,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
- Visual Studio Code是一款免费开源的现代化轻量级代码编辑器,支持几乎所有主流的开发语言的语法高亮、智能代码补全、自定义热键、括号匹配、代码片段、代码对比 Diff、GIT 等特性,这篇文章主要介绍了VSCode搭建C/C++编译环境,需要的朋友可以参考下...2020-05-15
Windows配置VSCode+CMake+Ninja+Boost.Test的C++开发环境(教程详解)
这篇文章主要介绍了Windows配置VSCode+CMake+Ninja+Boost.Test的C++开发环境,本文通过图文并茂的形式给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2020-05-12- Go 语言提供的基础容器,免不了要查询容器中的数据,那么是如何实现遍历的呢?本文将会介绍几种常用容易的遍历及其使用。感兴趣的可以了解一下...2021-06-13