当前位置: 首页 > news >正文

【C++】STL标准库之list

STL标准库之list

  • list类的简介
  • 常用的list类的接口
    • 构造
    • 迭代器
    • 容量
    • 访问
    • 修改
  • list和vector的区别

list类的简介

list是一种序列式容器,可以在任意位置插入和删除元素,并且其时间复杂度为O(1),在底层,list是双向链表结构,每个节点通过指针指向下一个节点,因此最大的缺陷是不支持随机访问,必须从已知位置开始迭代到该位置,同时节点除了存储val值之外,还要存储指针,因此需要一些额外的空间。
在这里插入图片描述
由于双向带头循环链表的存在,使得list在找尾时无需从头开始遍历,这样就有效降低了查找时候的时间复杂度。(头节点不存储数据,只是记录了当前list的第一个节点的地址和最后一个节点的地址)

常用的list类的接口

构造

函数名称功能
list(size_type n, const value_type& val = value_type())n个值为value的元素
list()空列表
list(const list& x)拷贝构造
list(InputIterator first, InputIterator last)用first和last进行区间构造

对应写法:

list<int> l(10, 5);
list<int> l2();
list<int> l3(l2);int arr[] = {1,2,3,4,5};
int n = sizeof(arr)/sizeof(arr[0]);
list<int> l4(arr, arr+n);

迭代器

函数名称功能
begin()+end()返回第一个元素的迭代器和最后一个元素的迭代器
rbegin()+rend()返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的reverse_iterator,即begin位置

在这里插入图片描述
从迭代器的在list中的位置可以看到,begin()实际上在第一个有效节点的位置,而end()在头节点的位置,那么为何要这样设置呢?

实际上,这样设置迭代器后,就可以很快速的找到当前链表的头和尾了,当需要找尾时,使用end()指向节点中的prev就可以快速找到,如果需要判断当前列表是否为空呢,实际上直接判断end()指向的值和begin()指向的值是否相等,如果相等,意味着head节点就是当前列表中唯一的节点,那么就说明当前列表为空。

在这里插入图片描述

判读是否为空就可以直接判断end和begin是否相等,因为当只有一个头节点的时候,prev和next指向的都是头节点。

容量

函数名称功能
empty判断是否为空列表
size计算当前列表中有多少个有效节点

访问

函数名称功能
front返回第一个节点中值的引用
back返回最后一个节点中值的引用

如果需要进行遍历,由于list特性,是不支持直接使用[]进行随机访问的,需要我们通过头节点逐个迭代。

修改

函数名称功能
push_front头插一个元素
pop_front头删一个元素
push_back尾插一个元素
pop_back尾删一个元素
insertpos位置插入元素
erasepos位置删除元素
swap交换两个list中的元素
clear清空list中的元素

请注意:针对迭代器失效的问题,在vector中我们说,任何可能会导致扩容的操作都可能会导致迭代器失效,同时删除也会导致删除当前位置以及后续所有的迭代器失效。但是在list中,由于使用链式存储方式,因此不存在扩容的情况,因此扩容不会导致迭代器失效,而删除操作会导致当前位置的迭代器失效,并不会影响后续的迭代器。

list和vector的区别

由于vector和list两个容器的底层结构不同,导致其特性以及应用场景不同。

vectorlist
底层结构动态的顺序表,一段连续空间带头节点的双向循环链表
随机访问支持随机访问,访问效率O(1)不支持,访问效率O(n)
插入和删除在任意位置插入和删除的效率低,需要整个搬移元素,时间复杂度为O(n),插入时可能要增容,效率低支持在任意位置的插入和删除时间复杂度都为O(1),并且无需扩容,拷贝元素,效率高
空间利用率底层为连续空间,不易造成内存碎片,空间利用率高,缓存利用率高底层动态开辟节点,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器例如需要进行++,迭代器为原生态的指针,指针++也就是向后偏移一个元素需要对指针进行封装,因为迭代器本身是不能通过++访问到下一个元素的(元素之间使用指针相连)
迭代器失效插入元素时,可能会导致扩容,这样就会使得所有的迭代器都失效,因此需要对迭代器重新赋值,删除元素时也需要重新赋值,否则也会失效插入元素不会扩容,只有删除元素会导致当前位置迭代器失效,其他位置迭代器没有影响
使用场景需要高效存储支持随机访问的场景,不关心插入删除的效率涉及到大量的插入和删除,不关心随机访问

相关文章:

【C++】STL标准库之list

STL标准库之list list类的简介常用的list类的接口构造迭代器容量访问修改 list和vector的区别 list类的简介 list是一种序列式容器&#xff0c;可以在任意位置插入和删除元素&#xff0c;并且其时间复杂度为O(1)&#xff0c;在底层&#xff0c;list是双向链表结构&#xff0c;…...

Nomogram | 盘点一下绘制列线图的几个R包!~(二)

1写在前面 不知道各位小伙伴的五一假期过的在怎么样&#xff0c;可怜的我感冒了。&#x1f637; 今天继续之前没有写完的列线图教程吧&#xff0c;再介绍几个制作列线图的R包。&#x1f920; 2用到的包 rm(list ls())library(tidyverse)library(survival)library(rms)library(…...

Django之定时任务django-crontab

Django之定时任务django-crontab crontab安装django-crontab注册应用定时时间格式定时时间示例设置定时任务符号方法解决crontab中文问题管理定时任务注意 crontab Django可以使用第三方库如django-crontab来实现定时任务的调度。该库允许使用类似于crontab文件格式的语法指定任…...

linux常见命令

ls&#xff1a;列出当前目录下的所有文件和子目录 cd&#xff1a;切换当前工作目录&#xff0c;例如 cd /home/user 进入 /home/user 目录 pwd&#xff1a;显示当前工作目录的路径 mkdir&#xff1a;创建一个新目录&#xff0c;例如 mkdir newdir 创建一个名为 newdir 的目录…...

【14.HTML-移动端适配】

移动端适配 1 布局视口和视觉视口1.1 设置移动端布局视口宽度 2 移动端适配方案2.1 rem单位动态html的font-size&#xff1b;2.2 vw单位2.3 rem和vw对比2.4 flex的弹性布局 1 布局视口和视觉视口 1.1 设置移动端布局视口宽度 避免布局视口宽度默认980px带了的缩放问题,并且禁止…...

平衡二叉树旋转机制

概念 平衡二叉树的旋转机制是一种通过对树进行旋转操作来保持其平衡的方法。 分类 平衡二叉树的旋转机制包括两种基本类型的旋转&#xff1a;左旋和右旋&#xff0c;以及它们的组合。 左旋 左旋是将一个节点的右子节点旋转到它的位置上&#xff0c;同时将该节点移到其左侧&…...

深入浅出C++ ——C++11

文章目录 一、C11简介二、列表初始化二、声明四、范围for循环五、STL中的变化六、右值引用和移动语义1. 什么是左值&#xff1f;什么是左值引用&#xff1f;2. 左值引用与右值引用比较3. 右值引用使用场景和意义4. 完美转发 新的类功能默认成员函数类成员变量初始化defaultdele…...

智能座舱3.0阶段,看全球巨头如何打造更具“价值”的第三空间

面向中国这一全球最大的汽车电动化与智能化单一市场&#xff0c;作为全球第七大汽车技术供应商的FORVIA佛瑞亚集团开始全面发力。 在2023年上海国际车展上&#xff0c;FORVIA佛瑞亚携旗下佛吉亚与海拉一系列突破性技术和互动体验亮相&#xff0c;展示了对电气化与能源管理、安…...

【Linux】入门介绍

&#x1f331;博客主页&#xff1a;大寄一场. &#x1f331;系列专栏&#xff1a;Linux &#x1f618;博客制作不易欢迎各位&#x1f44d;点赞⭐收藏➕关注​ 目录 前言 Linux背景介绍 1.发展史 UNIX发展的历史 Linux发展历史 2. 开源 3. 官网 4. 企业应用现状 5. 发行版…...

【Python】序列类型②-元组

文章目录 1.元组简介2.元组的定义2.1定义只有一个元素的元组 3.元组的下标访问4.元组的常用方法5.使用in判断是否存在元素6.多元赋值操作 1.元组简介 元组和列表一样可以存放多个,不同数据类型的元素 与列表最大的不同就是:列表是可变的,而元组不可变 2.元组的定义 元组的定义:…...

循环的数字

循环的数字 题目描述 你曾经因为看见一样的东西一遍又一遍地重复、循环而对电视节目感到厌烦么&#xff1f;好吧&#xff0c;虽然我并不关心电视节目的好坏&#xff0c;不过有时却也很像那样不断循环的数字。 让我们假定两个不同的正整数 ( n , m ) (n, m) (n,m) 是循环的&…...

MySQL查询之聚合函数查询

0. 数据源 student.sql文件。 /*Navicat Premium Data TransferSource Server : localhost_3306Source Server Type : MySQLSource Server Version : 80016Source Host : localhost:3306Source Schema : testdbTarget Server Type : MySQLTa…...

普通2本,去过字节外包,到现在年薪25W+的测试开发,我的2年转行心酸经历...

个人简介 我是一个普通二本大学机械专业毕业&#xff0c;17年毕业&#xff0c;19年转行&#xff0c;目前做IT行业的软件测试已经有3年多&#xff0c;职位是高级测试工程师&#xff0c;坐标上海… 我想现在我也有一点资格谈论关于转行这个话题&#xff1b;希望你在决定转行之前…...

util.callbackify

util.callbackify(original) 将 async 异步函数&#xff08;或者一个返回值为 Promise 的函数&#xff09;转换成遵循异常优先的回调风格的函数&#xff0c;例如将 (err, value) > ... 回调作为最后一个参数。 在回调函数中&#xff0c;第一个参数为拒绝的原因&#xff08;如…...

解决使用CLIP模型时TypeError: Cannot handle this data type: (1, 1, 224, 224), |u1

想提供Huggingface的transformer库实现多模态模型CLIP的推断&#xff0c;结果报错 (myenv) rootd27d1ff1836c:/home/model_test# python3 CLIP.py ftfy or spacy is not installed using BERT BasicTokenizer instead of ftfy. Traceback (most recent call last): File “/hom…...

Mysql第二章 多表查询的操作

这里写自定义目录标题 一 外连接与内连接的概念sql99语法实现 默认是内连接sql99语法实现左外连接&#xff0c;把没有部门的员工也查出来sql99语法实现右外连接&#xff0c;把没有人的部门查出来sql99语法实现满外连接&#xff0c;mysql不支持这样写mysql中如果要实现满外连接的…...

ESP32-CAM:TinyML 图像分类——水果与蔬菜

目录 故事 硬件参数: 在 Arduino IDE 上安装 ESP32-Cam 使用 BLINK 测试电路板 测试无线网络 运行您的 Web 服务器 水果与蔬菜-图像分类 下载数据集 使用 Edge Impulse Studio 训练模型...

如何防止订单重复支付

想必大家对在线支付都不陌生&#xff0c;今天和大家聊聊如何防止订单重复支付。 看看订单支付流程 我们来看看&#xff0c;电商订单支付的简要流程&#xff1a; 订单钱包支付流程 从下单/计算开始&#xff1a; 下单/结算&#xff1a;这一步虽然不是直接的支付起点&#xff0c;但…...

不是那么快乐的五一

大家好&#xff0c;我是记得诚。 五一假期结束了&#xff0c;明天开始上班了。 这个假期没休息好&#xff0c;也没出去玩。 放假前一天&#xff0c;接到通知让加班。 第一天就去公司加班了&#xff0c;属实很难受&#xff0c;我心想如果别人有了出远门的安排&#xff0c;还…...

Maven命令和配置详解

Maven命令和配置详解 1. pom基本结构2. build基本结构3. Maven命令详解3.1 打包命令3.2 常用命令3.3 批量修改版本-父子pom4. Maven配置详解4.1 settings.xml4.2 项目内的maven工程结构Maven POM构建生命周期工程实践1. pom基本结构 <?xml versi...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

Java多线程实现之Thread类深度解析

Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...

springboot整合VUE之在线教育管理系统简介

可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生&#xff0c;小白用户&#xff0c;想学习知识的 有点基础&#xff0c;想要通过项…...

苹果AI眼镜:从“工具”到“社交姿态”的范式革命——重新定义AI交互入口的未来机会

在2025年的AI硬件浪潮中,苹果AI眼镜(Apple Glasses)正在引发一场关于“人机交互形态”的深度思考。它并非简单地替代AirPods或Apple Watch,而是开辟了一个全新的、日常可接受的AI入口。其核心价值不在于功能的堆叠,而在于如何通过形态设计打破社交壁垒,成为用户“全天佩戴…...

Ubuntu Cursor升级成v1.0

0. 当前版本低 使用当前 Cursor v0.50时 GitHub Copilot Chat 打不开&#xff0c;快捷键也不好用&#xff0c;当看到 Cursor 升级后&#xff0c;还是蛮高兴的 1. 下载 Cursor 下载地址&#xff1a;https://www.cursor.com/cn/downloads 点击下载 Linux (x64) &#xff0c;…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

Spring Boot + MyBatis 集成支付宝支付流程

Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例&#xff08;电脑网站支付&#xff09; 1. 添加依赖 <!…...

高抗扰度汽车光耦合器的特性

晶台光电推出的125℃光耦合器系列产品&#xff08;包括KL357NU、KL3H7U和KL817U&#xff09;&#xff0c;专为高温环境下的汽车应用设计&#xff0c;具备以下核心优势和技术特点&#xff1a; 一、技术特性分析 高温稳定性 采用先进的LED技术和优化的IC设计&#xff0c;确保在…...

JavaScript 标签加载

目录 JavaScript 标签加载script 标签的 async 和 defer 属性&#xff0c;分别代表什么&#xff0c;有什么区别1. 普通 script 标签2. async 属性3. defer 属性4. type"module"5. 各种加载方式的对比6. 使用建议 JavaScript 标签加载 script 标签的 async 和 defer …...