【C++】list容器的基本使用

一、list是什么

list的底层结构是带头双向循环链表。

相较于 vector 的连续线性空间,list 就显得复杂很多,它是由一个个结点构成,每个结点申请的空间并不是连续的,它的好处是每次插入或删除一个数据,就配置或释放一个元素空间,我们不用在意扩容问题了,也不用单独写扩容函数了,list对于任何位置的元素进行插入或者元素移除,时间复杂度都是O(1)。

二、list容器的基本使用

1、构造函数

这里的allocator是空间配置器,我们这里先不用管它(认为它不存在),等到后面的篇章会具体讲解它的作用。 其中,(1)是默认构造 (2)是n个val构造 (3)是迭代器区间构造 (4)是拷贝构造。

2、析构函数

释放每个结点申请的空间资源。

3、赋值重载

它的操作数是两个已有的list对象。

4、迭代器

(1)使用

list的迭代器和vector的迭代器在用法上一模一样。

使用迭代器可以进行遍历:

#include <iostream>
#include <list>
using namespace std;void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{test_list1();return 0;
}

运行结果:

 

支持迭代器,就支持范围for,因为范围for的底层就是迭代器。

void test_list1()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt){cout << e << " ";}cout << endl;
}int main()
{test_list1();return 0;
}

运行结果:

 

(2)分类

迭代器从功能上进行分类,分为iterator、const_iterator、reverse_iterator、const_reverse_iterator这四类,它还可以从性质上进行分类,分为单向迭代器、双向迭代器、随机迭代器。

单向迭代器包括(forward):forward_list / unordered_map... 它只支持++

双向迭代器(bidirectional)包括:list / map / set... 它只支持++ / --

随机迭代器(random access)包括:vector / string / deque... 它支持++ / -- / + / -

它们的底层结构决定它们的性质,它们的底层结构也决定它们可以使用哪些算法。

比如:

C++标准库中sort的模板参数是RandomAccessIterator,从它的名字中可以看出它只接收随机迭代器,如果传一个单向迭代器,它也可以接收,但运行时会发生错误即程序不能正常运行。

C++标准库中reverse的模板参数是BidirectionalIterator,从它的名字中可以看出它只接收双向迭代器,如果传一个单向迭代器,它也可以接收,但运行时会发生错误即程序不能正常运行。如果传一个随机迭代器,也可以正常使用,因为随机迭代器的范围更广,凡是支持单向迭代器或者双向迭代器的都支持随即迭代器。

出现InputIterator,说明单向/双向/随机迭代器都可以使用这个函数。

5、成员函数

(1)empty()

判断容器内节点个数是否为空,若为空返回true,否则返回false。

(2)size()

返回容器内节点个数。

(3)front()

reference 就是list<T>中的T,T是模板参数。front就是用来返回第一个结点的值。

(4)back()

 返回最后一个结点的值。

(5)assign()

用于赋值。(1)是用一段迭代区间赋值 (2)是用n个val赋值

(6)push_front()

头插,头部插入一个新结点。

(7)pop_front()

头删,删除头部的结点。 

(8)push_back()

尾插,尾部插入一个新结点。

(9)pop_back()

尾删,删除尾部的结点。

(10)emplace_back()

它的功能和push_back()差不多,但有不同之处,现阶段我们就把它当作push_back()使用。

struct AA
{AA(int a1, int a2):_a1(a1), _a2(a2){}
private:int _a1;int _a2;
};void test_list2()
{list<AA> lt;AA aa1(1, 1);lt.push_back(aa1);lt.push_back(AA(2,2));//lt.push_back(3,3); //err,这里会报错lt.emplace_back(aa1);lt.emplace_back(AA(2,2));lt.emplace_back(3,3); //ok,与push_back()的不同之处,它支持直接传构造A对象的参数
}int main()
{test_list2();return 0;
}

(10)insert()

(1)是在pos位置前插入val (2)是在pos位置前插入n个val (3)是在pos位置前插入一段迭代区间。 

void test_list3()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;//在第3个位置前(整体位置是从0开始编号的)插入30//lt.insert(lt.begin() + 3, 30); //list容器不支持+,所以这行代码会报错list<int>::iterator it = lt.begin();int k = 3;while (k--){++it;//list容器支持++,所以这行代码会报错}lt.insert(it, 30);  //(1)for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list3();return 0;
}

运行结果: 

(11)erase()

 (1)删除pos位置上的值 (2)删除一段迭代区间

void test_list4()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;int x;cin >> x;list<int>::iterator it = find(lt.begin(),lt.end(),x);if (it != lt.end()) //找到了lt.erase(it); //(1)elsecout << "不存在:" << x << endl;for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list4();return 0;
}

输入4,运行结果: 

(12)clear()

清空所有结点数据。

(13)resize()

将结点个数更新到n,假设原先节点个数为k。

1、k > n

释放k - n个结点

2、k < n

增加n - k个节点,结点中的内容自己可以传,也可以不传,用默认的缺省值。

因为list的底层是链表,所以没有扩容这一说法。

(14)reverse()

逆置结点的顺序。

void test_list5()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.reverse();for (auto e : lt)cout << e << " ";cout << endl;//reverse(lt.begin(),lt.end()); //这里的算法库中的reverse也支持list容器的逆置
}int main()
{test_list5();return 0;
}

运行结果:

 

(15)sort()

 由于算法库中的sort不支持list容器的迭代器,所以这里它自己实现了一个。

void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//默认排升序lt.sort(); //(1)for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}

运行结果: 

 

如果想要排降序,就要借助仿函数:

void test_list6()
{list<int> lt;lt.push_back(20);lt.push_back(40);lt.push_back(50);lt.push_back(30);lt.push_back(10);for (auto e : lt)cout << e << " ";cout << endl;//排降序greater<int> gt;lt.sort(gt);for (auto e : lt)cout << e << " ";cout << endl;}int main()
{test_list6();return 0;
}

运行结果:

 

(16)merge()

合并两个链表,前提是这两个链表需要有序。 

void test_list7()
{list<int> first, second;first.push_back(3);first.push_back(6);first.push_back(1);second.push_back(2);second.push_back(5);second.push_back(4);first.sort();second.sort();first.merge(second); //合并后,second这个链表就空了,相当于将它移到first上了for (auto e : first)cout << e << " ";cout << endl;cout << "----------" << endl;for (auto e : second) //second中已经没有数据了cout << e << " ";cout << endl;cout << "----------" << endl;
}int main()
{test_list7();return 0;
}

运行结果: 

 

 (17)unique()

去重,删除容器中与val值一样的结点,只保留第一个。删除时要保证重复的数据紧挨着,否则会删不干净,建议删除前先排序。

void test_list8()
{list<int> lt;lt.push_back(5);lt.push_back(1);lt.push_back(4);lt.push_back(2);lt.push_back(4);lt.push_back(3);lt.push_back(3);lt.push_back(5);for (auto e : lt)cout << e << " ";cout << endl;lt.sort();lt.unique();for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list8();return 0;
}

运行结果: 

(18)remove()

对val进行查找,如果找到就删除,否则什么也不做。 

(19)remove_if()

给定一个条件,如果满足就删除,否则什么也不做。

(20)splice()

 (1)是将x中全部结点转移到当前容器中的pos位置之前的位置处 (2)是将x中i位置的结点转移到当前容器中的pos位置之前的位置处 (3)是将x中的一段迭代区间上的结点转移到当前容器中的pos位置之前的位置处

//将一个链表的结点转移给另一个链表
void test_list9()
{list<int> mylist1, mylist2;list<int>::iterator it;//先插入一些值for (int i = 1; i <= 4; ++i)mylist1.push_back(i);      // mylist1: 1 2 3 4for (int i = 1; i <= 3; ++i)mylist2.push_back(i * 10);   // mylist2: 10 20 30cout << "初始值:" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;it = mylist1.begin();++it;                     mylist1.splice(it, mylist2); //(1)// mylist1: 1 10 20 30 2 3 4// mylist2中的数据已经没有了// "it" 仍然指向2 cout << "第一次调用splice后:" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;mylist2.splice(mylist2.begin(), mylist1, it); //(2)// mylist1: 1 10 20 30 3 4// mylist2: 2// "it"现在是无效的cout << "第二次调用splice后:" << endl;for (auto e : mylist1)cout << e << " ";cout << endl;for (auto e : mylist2)cout << e << " ";cout << endl;cout << "---------------" << endl;
}int main()
{test_list9();return 0;
}

运行结果: 

根据它的功能,我们还可以调整当前链表的结点顺序:

//调整当前链表结点的顺序
void test_list10()
{list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout << "转移前:" << endl;for (auto e : lt)cout << e << " ";cout << endl;//现要求将6这个结点转移到1这个结点的前面去lt.splice(lt.begin(), lt, --lt.end());cout << "转移后:" << endl;for (auto e : lt)cout << e << " ";cout << endl;
}int main()
{test_list10();return 0;
}

三、排序效率

这里我们将list容器中的sort与算法库中的sort进行效率对比,看看哪个更优。

(1)对比一

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op1()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;vector<int> v;for (int i = 0;i < N;++i) //随机生成100万个数据{auto e = rand() + i;lt1.push_back(e);v.push_back(e);}int begin1 = clock();sort(v.begin(), v.end());int end1 = clock();int begin2 = clock();lt1.sort();int end2 = clock();cout << "vector sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op1();return 0;
}

在Debug环境下的运行结果:

可以看到list排序优势更大,那是因为在Debug环境下,优化不是很大,运行结果不具有参考价值,在release环境下,双方优化都是最大的,这才公平。

在Realse环境下运行结果:

实际上,算法库中的sort效率是更好的。 

(2)对比二

#include <vector>
#include <iostream>
#include <algorithm>
#include <list>
using namespace std;void test_op2()
{srand((unsigned int)time(0));const int N = 1000000;list<int> lt1;list<int> lt2;for (int i = 0;i < N;++i){auto e = rand() + i;lt1.push_back(e);lt2.push_back(e);}int begin1 = clock();vector<int> v(lt2.begin(), lt2.end()); //迭代器区间构造sort(v.begin(), v.end()); //用算法库中的sort进行排序lt2.assign(v.begin(), v.end()); //再拷贝回lt2int end1 = clock();int begin2 = clock();lt1.sort(); //直接调用list中的sort进行排序int end2 = clock();cout << "list copy vector sort copy list sort:" << end1 - begin1 << endl;cout << "list sort:" << end2 - begin2 << endl;
}int main()
{test_op2();return 0;
}

在Release环境下运行结果: 

这差距就出来了, 在begin1~end1这段时间内做的事情比begin2~end2这段时间内做的还要多,结果花费的时间还少,说明了当数据量比较大时,list中的sort排序效率很低。不如先把它的值拷贝给vector容器,然后排序,排完再拷贝回来。

四、结语

本篇内容到这里就结束了,主要讲了list容器的基本使用,希望对大家有些许收获,祝大家天天开心!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/428157.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

禁忌搜索算法(TS算法)求解实例---旅行商问题 (TSP)

目录 一、采用TS求解 TSP二、 旅行商问题2.1 实际例子&#xff1a;求解 6 个城市的 TSP2.2 **求解该问题的代码**2.3 代码运行过程截屏2.4 代码运行结果截屏&#xff08;后续和其他算法进行对比&#xff09; 三、 如何修改代码&#xff1f;3.1 减少城市坐标&#xff0c;如下&am…

游戏如何对抗定制挂

近年来&#xff0c;游戏安全对抗强度相比以往更加激烈&#xff0c;具体表现在“定制挂”趋势显著。在近期收集的近万款外挂样本中&#xff0c;定制挂约占比78%&#xff0c;常见的内存修改器、变速器等通用作弊手段占比正在下降。 所谓定制挂&#xff0c;是指针对某款游戏单独开…

初写MySQL四张表:(2/4)

今天&#xff0c;我们来写第二张表。因着这四张表以及后续有相应的拓展&#xff0c;这四张环环相扣&#xff0c;所以还未写出第一张表的同学&#xff0c;可以看完第一张表&#xff0c;再来此处&#xff1a; 初写MySQL四张表:(1/4)-CSDN博客 好&#xff0c;今日表格有三张&…

easy-es动态索引支持

背景 很多项目目前都引入了es&#xff0c;由于es弥补了mysql存储及搜索查询的局限性&#xff0c;随着技术的不断迭代&#xff0c;原生的es客户端使用比较繁琐不直观&#xff0c;上手代价有点大&#xff0c;所以easy-es框架就面世了&#xff0c;学习成本很低&#xff0c;有空大…

记忆化搜索专题——算法简介力扣实战应用

目录 1、记忆化搜索算法简介 1.1 什么是记忆化搜索 1.2 如何实现记忆化搜索 1.3 记忆化搜索与动态规划的区别 2、算法应用【leetcode】 2.1 题一&#xff1a;斐波那契数 2.1.1 递归暴搜解法代码 2.1.2 记忆化搜索解法代码 2.1.3 动态规划解法代码 2.2 题二&#xff1…

vue-使用refs取值,打印出来是个数组??

背景&#xff1a; 经常使用$refs去获取组件实例&#xff0c;一般都是拿到实例对象&#xff0c;这次去取值的时候发现&#xff0c;拿到的竟然是个数组。 原因&#xff1a; 这是vue的特性,自动把v-for里面的ref展开成数组的形式&#xff0c;哪怕你的ref名字是唯一的&#xff01…

后台数据管理系统 - 项目架构设计-Vue3+axios+Element-plus(0916)

接口文档: https://apifox.com/apidoc/shared-26c67aee-0233-4d23-aab7-08448fdf95ff/api-93850835 接口根路径&#xff1a; http://big-event-vue-api-t.itheima.net 本项目的技术栈 本项目技术栈基于 ES6、vue3、pinia、vue-router 、vite 、axios 和 element-plus http:/…

6.C++程序中的基本数据类型

数据类型是指在C中用于声明不同类型变量或函数的一个系统或抽象或者是一个分类&#xff0c;它决定了变量存储占用的内存空间以及解析存储的位模式。其实数据类型可以理解为固定内存大小的别名&#xff0c;是创建变量的模具&#xff0c;具体使用哪种模具&#xff08;包括自定义&…

Python安装不再难!全平台保姆级教程带你轻松搞定!

Python介绍 Python是一种功能强大且灵活的编程语言&#xff0c;被广泛应用于各个领域。以下是Python在不同应用领域的一些常见用途&#xff1a; 网络开发 Python提供了丰富的库和框架&#xff0c;使其成为网络开发的理想选择。诸如Django、Flask和Pyramid等框架可以帮助开发人员…

一张图解析FastAdmin中的表格列表(bootstrap-table)的功能(备份)

功能描述 请根据图片上的数字索引查看对应功能说明。 1.菜单名称和描述 默认生成的CRUD是没有菜单名称和描述显示的&#xff0c;如果需要显示则可以修改权限管理->菜单规则&#xff0c;给对应菜单的添加上备注信息后即可显示&#xff0c;支持HTML 2.TAB过滤选项卡 在一键…

Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式)

前言: 发个之前的库存… Linux之CentOS 7.9-Minimal部署Oracle 11g r2 安装实测验证(桌面模式) 本次验证的是CentOS_7_Minimal-2009桌面模式来部署Oracle 11g r2,大家可根据自身环境及学习来了解。 环境:下载地址都给你们超链好了 1、Linux系统镜像包: 1.1 CentOS-7-x86_…

Linux 删除文件不释放空间问题处理

背景&#xff1a; 服务器磁盘空间已经达到100%&#xff0c;删除存放日志路径下的文件后&#xff0c;发现空间并未释放&#xff01; 原因&#xff1a;在linux系统中&#xff0c;通过rm删除文件将会从文件系统的文件夹结构上解除链接(unlink)然后删除&#xff0c;然而假设文件是被…

探索Python的Excel世界:openpyxl的魔法之旅

文章目录 探索Python的Excel世界&#xff1a;openpyxl的魔法之旅背景&#xff1a;为什么选择openpyxl&#xff1f;什么是openpyxl&#xff1f;如何安装openpyxl&#xff1f;简单的库函数使用方法场景应用&#xff1a;openpyxl在实际工作中的应用常见bug及解决方案总结 探索Pyth…

如何利用视觉分析实现扬尘检测

随着城市化和工业化进程的加速&#xff0c;扬尘污染已成为全球各大城市面临的环境问题之一。建筑施工、道路交通以及工业活动产生的扬尘不仅影响空气质量&#xff0c;严重时还会引发呼吸道疾病&#xff0c;威胁公众健康。传统的扬尘检测手段多为传感器、采样仪等设备&#xff0…

【Echarts】vue3打开echarts的正确方式

ECharts 是一个功能强大、灵活易用的数据可视化工具&#xff0c;适用于商业报表、数据分析、科研教育等多种场景。那么该如何优雅的使用Echarts呢? 这里以vue3为例。 安装echarts pnpm i echarts封装公用方法 // ts-nocheck import * as echarts from echarts; // 我们这里借…

【C++指南】inline内联函数详解

&#x1f493; 博客主页&#xff1a;倔强的石头的CSDN主页 &#x1f4dd;Gitee主页&#xff1a;倔强的石头的gitee主页 ⏩ 文章专栏&#xff1a;《C指南》 期待您的关注 目录 引言 C为什么引入了inline来替代C语言中的宏 inline的基本用法 定义inline函数 inline的优势与…

IO模型---BIO、NIO、IO多路复用、AIO详解

本篇将想给详细解释一下什么是BIO、NIO、IO多路复用以及AIO~ 同步的阻塞(BIO)和非阻塞(NIO)的区别 BIO&#xff1a;线程发来IO请求后&#xff0c;一直阻塞着IO线程&#xff0c;需要缓冲区这边数据准备好之后&#xff0c;才会进行下一步的操作。 举个&#x1f330;&#xff1…

HarmonyOS应用开发者基础认证

目录 一、判断二、单选三、多选 一、判断 1、HarmonyOS提供了基础的应用加固安全能力&#xff0c;包括混淆、加密和代码签名能力。正确 2、可以通过ohpm uninstall 指令下载指定的三方库。错误 3、支持模块化开发是指一个应用通常会包含多种功能&#xff0c;将不同的功能特性…

【读书笔记-《30天自制操作系统》-23】Day24

本篇内容依然比较简单&#xff0c;主要是优化窗口功能以及开发定时器应用程序。首先是优化窗口的切换功能&#xff0c;实现通过键盘和鼠标切换窗口&#xff0c;然后是实现通过鼠标关闭窗口。接着实现不同窗口输入状态的切换&#xff0c;最后是实现定时器的API与应用程序。 1.…

Windows Server2016多用户登录破解

使用场景 很多时候&#xff0c;公司开发和测试运维会同时登录同一台windows服务器进行查询、更新、维护等操作&#xff0c;本文就来介绍一下Windows2016配置多人远程桌面登录实现&#xff0c;感兴趣的可以了解一下。 操作流程 &#xff08;1&#xff09;首先桌面需要安装远程…