STL---list
目录
1. list的介绍及使用
1.1 list的介绍
1.2 list的使用注意事项
2.list接口介绍及模拟实现
2.1构造编辑
2.2容量
2.3修改
3.list迭代器
4.迭代器失效
5.模拟实现
6.vector和list的区别
1. list的介绍及使用
1.1 list的介绍
list的文档介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。
2. list的底层是带头双向循环链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。
4. 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用注意事项
1.list不支持随机访问,不能使用[ ]来访问元素。
2.list.sort()使用的是归并排序,默认为升序,如果需要排降序
// 降序
list<int> lt;
greater<int> it;
lt.sort(it);//匿名对象
lt.sort(greater<int> ());
但是使用list的sort排序效率不是很高,在处理数据量较多的情况下,可以将数据拷贝到vector中,再使用vector.sort(),再将数据拷贝回去。
list<int> lt;vector<int> v(lt.begin(), lt.end());
sort(v.begin(), v.end());
lt.assign(v.begin(), v.end());
2.list接口介绍及模拟实现
2.1构造

void empty_init()
{head = new Node;head->next = head;head->prev = head;_size = 0;
}list()
{empty_init();
}list(const list& lt)
{empty_init();for (auto e : lt){push_back(e);}
}
2.2容量
bool empty()
{return head->next == head;
}size_t size()
{return _size;
}
2.3修改
void push_front(const T& value)
{insert(begin(), value);
}void push_back(const T& value)
{insert(end(), value);
}void pop_front()
{erase(begin());
}void pop_back()
{erase(--end());
}void insert(iterator pos, const T& value = T())
{Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(value);prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;++_size;
}iterator erase(iterator pos)
{Node* cur = pos._node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;--_size;return next;
}void swap(list<T>& lt)
{std::swap(lt.head);std::swap(lt.size);
}void clear()
{iterator cur = begin();while (cur != end()){cur = erase(cur);}
}
3.list迭代器
与vector和string不同,list的迭代器需要自己实现,list迭代器可以理解为一个指针,指向list中的某个结点,而链表的每个结点在物理空间上并不连续,所以当迭代器++的时候,并不能直接到下一个结点的位置,并且*的时候,并不知道访问的是链表中的哪个数据,所以我们需要自己实现,将迭代器进行封装。
template<class T, class Ref, class Ptr>
struct _list_iterator
{typedef _list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node): _node(node){}Ref operator*(){return _node->date;}Ptr operator->(){return &_node->date;}self& operator++(){_node = _node->next;return *this;}self& operator--(){_node = _node->prev;return *this;}bool operator!=(const self& lt){return _node != lt._node;}
};
需要注意的是,类模板参数有三个,是为了同时能实现迭代器和const迭代器,在list类中直接传不同的参数即可。
4.迭代器失效
此处大家可将迭代器暂时理解成类似于指针,迭代器失效即迭代器所指向的节点的无效,即该节点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。
void TestListIterator1()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){// erase()函数执行后,it所指向的节点已被删除,因此it无效,在下一次使用it时,必须先给其赋值l.erase(it);++it;}
}//修改void TestListIterator()
{int array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };list<int> l(array, array+sizeof(array)/sizeof(array[0]));auto it = l.begin();while (it != l.end()){it = l.erase(it);}
}
5.模拟实现
namespace cola
{template<class T>struct _list_node{T date;_list_node<T>* next;_list_node<T>* prev;_list_node(const T& value = T()): date(value), next(nullptr), prev(nullptr){}};template<class T, class Ref, class Ptr>struct _list_iterator{typedef _list_node<T> Node;typedef _list_iterator<T, Ref, Ptr> self;Node* _node;_list_iterator(Node* node): _node(node){}Ref operator*(){return _node->date;}Ptr operator->(){return &_node->date;}self& operator++(){_node = _node->next;return *this;}self& operator--(){ _node = _node->prev;return *this;}self operator++(int){self temp(*this);_node = _node->next;return temp;}self operator--(int){self temp(*this);_node = _node->prev;return temp;}bool operator!=(const self& lt){return _node != lt._node;}bool operator==(const self& lt){return _node == lt._node;}};template<class T>class list{typedef _list_node<T> Node;public:typedef _list_iterator<T, T&, T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return head->next;}iterator end(){return head;}const_iterator begin() const{return head->next;}const_iterator end() const{return head;}void empty_init(){head = new Node;head->next = head;head->prev = head;_size = 0;}list(){empty_init();}~list(){clear();delete head;}list(const list& lt){empty_init();for (auto e : lt){push_back(e);}}list& operator=(const list& lt){if (head != lt.head){clear();for (auto e : lt){push_back(e);}}return *this;}void push_front(const T& value){insert(begin(), value);}void push_back(const T& value){insert(end(), value);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}void insert(iterator pos, const T& value = T()){Node* cur = pos._node;Node* prev = cur->prev;Node* newnode = new Node(value);prev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;++_size;}iterator erase(iterator pos){Node* cur = pos._node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;--_size;return next;}void swap(list<T>& lt){std::swap(lt.head);std::swap(lt.size);}void clear(){iterator cur = begin();while (cur != end()){cur = erase(cur);}}bool empty(){return head->next == head;}size_t size(){return _size;}private:Node* head;size_t _size;};//打印函数(适用于任何容器)template<typename Container>void print_container(const Container& lt){typename Container::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}
}
6.vector和list的区别
相关文章:

STL---list
目录 1. list的介绍及使用 1.1 list的介绍 1.2 list的使用注意事项 2.list接口介绍及模拟实现 2.1构造编辑 2.2容量 2.3修改 3.list迭代器 4.迭代器失效 5.模拟实现 6.vector和list的区别 1. list的介绍及使用 1.1 list的介绍 list的文档介绍 1. list是可以在常…...

python判断ip所属地区 python 判断ip 网段
前言 IP地址是互联网中唯一标识一个设备的地址,有时候需要判断一个IP地址所属的地区,这就需要用到IP地址归属查询。本文将介绍Python如何通过IP地址查询所属地区并展示代码。 一、 IP地址归属查询 IP地址归属查询又称IP地址归属地查询、IP地址归属地定…...

大数据分析案例-基于LightGBM算法构建糖尿病确诊预测模型
🤵♂️ 个人主页:艾派森的个人主页 ✍🏻作者简介:Python学习者 🐋 希望大家多多支持,我们一起进步!😄 如果文章对你有帮助的话, 欢迎评论 💬点赞Ǵ…...

Mysql查询重复数据常用方法
在平常的开发工作中,我们经常需要查询数据,比如查询某个表中重复的数据,那么,具体应该怎么实现呢?常用的方法都有哪些呢? 测试表中数据: 1:查询名字重复的数据 having: …...
Go framework-GORM
目录 一、GORM 1、GORM连接数据库 2、单表的增删改查 3、结构体名和表名的映射规则 4、gorm.Model匿名字段 5、结构体标签gorm 6、多表操作 7、常用方法 8、支持原生SQL 9、Gin整合GORM 一、GORM ORM:即Object-Relational Mapping,它的作用是在…...

FirmAE 工具安装(解决克隆失败 网络问题解决)
FirmAE官方推荐使用Ubuntu 18.04系统进行安装部署,FirmAE工具的安装部署十分简单,只需要拉取工具仓库后执行安装脚本即可。 首先运行git clone --recursive https://kgithub.com/pr0v3rbs/FirmAE命令 拉取FirmAE工具仓库,因为网络的问题&…...
css实现九宫格布局
要使用CSS实现九宫格布局,可以创建一个包含九个元素的容器,并使用display: grid属性将其设置为网格布局。然后,使用grid-template-columns和grid-template-rows属性来定义网格的行和列布局。接下来,使用grid-gap属性来设置网格的行…...

linux下系统问题排查基本套路
文章目录 总结常用命令原文GC相关网络TIME_WAITCLOSE_WAIT 总结常用命令 top 查找cpu占用高的进程ps 找到对应进程的pidtop -H -p pid 查找cpu利用率较高的线程printf ‘%x\n’ pid 将线程pid转换为16进制得到 nidjstack pid |grep ‘nid’ -C5 –color 在jstack中找到对应堆栈…...

想解锁禁用的iPhone?除了可以使用电脑之外,这里还有不需要电脑的方法!
多次输入错误的密码后,iPhone将显示“iPhone已禁用”。这种情况看起来很棘手,因为你现在不能用iPhone做任何事情。对于这种情况,我们提供了几种有效的方法来帮助你在最棘手的问题中解锁禁用的iPhone。你可以选择使用或不使用电脑来解锁禁用的iPhone。 一、为什么你的iPhone…...
基于Springboot+Thymeleaf学生在线考试管理系统——LW模板
摘 要 随着当前大数据时代的飞速发展,信息技术以及数据科学不断的普及,教育界也随之更新换代。无粉尘黑板以及电子化考试都已经是在各种学校中普及使用,而且因为操作简单以及对环境没有任何影响,这也将是未来发展的重大趋势。而由…...

STM32f103c6t6/STM32f103c8t6寄存器开发
目录 资料 寻址区 2区 TIMx RTC WWDG IWDG SPI I2S USART I2C USB全速设备寄存器 bxCAN BKP PWR DAC ADC 编辑 EXTI 编辑 GPIO AFIO SDIO DMA CRC RCC FSMC USB_OTG ETH(以太网) 7区 配置流程 外部中断 硬件中断 例子 点灯 …...
MySQL Connection not available.
Mysql 报错 最近部署在服务器上的mysql总是报这种错。 但是在服务器上,使用命令行是可以登录进mysq的。 cursor db.cursor() File “/home/ubuntu/miniconda3/envs/chatbot_env/lib/python3.9/site-packages/mysql/connector/connection_cext.py”, line 700, in …...

PHP反序列化 字符串逃逸
前言 最近在打西电的新生赛,有道反序列化的题卡了很久,今天在NSS上刷题的时候突然想到做法,就是利用字符串逃逸去改变题目锁死的值,从而实现绕过 为了研究反序列化的字符串逃逸 我们先简单的测试下 原理 <?php class escape…...

DockerFile解析
1. 是什么 Dockerfile是田来构建Docker镜像的文本文件,是由一条条构建镜像所需的指令和参数构成的脚本 1.1 概述 1.2 官网 Dockerfile reference | Docker Documentation 1.3 构建三步骤 1. 编写dockerfile文件 2. docker build命令构建镜像 3. docker run依镜像运…...

斯坦福大学医学院教授:几年内ChatGPT之类的AI将纳入日常医学实践
注意:本信息仅供参考,分享此内容旨在传递更多信息之目的,并不意味着赞同其观点或证实其说法。 在一项新研究中,斯坦福大学研究人员发现,ChatGPT在复杂临床护理考试题中可以胜过一、二年级的医学生。此项研究显示&#…...
golang 命令行 command line (flag,os,arg,args)
目录 1. golang 命令行 command line1.1. Introduction1.2. Parsing Arguments from the command line (os package)1.2.1. Get the number of args1.2.2. Iterate over all arguments 1.3. Using flags package1.3.1. Parse Typed Flags1.3.2. Set flags from the script1.3.3…...

Shell语法揭秘:深入探讨常见Linux Shell之间的语法转换
深入探讨常见Linux Shell之间的语法转换 一、引言二、Linux常用Shell:Bash、Zsh、Ksh、Csh、Tcsh和Fish的简介2.1、Bash、Zsh、Ksh、Csh、Tcsh和Fish的特点和用途2.2、语法差异是常见Shell之间的主要区别 三、变量和环境设置的语法差异3.1、变量定义和使用的不同语法…...
Python3 基础语法
Python3 基础语法 编码 默认情况下,Python 3 源码文件以 UTF-8 编码,所有字符串都是 unicode 字符串。 当然你也可以为源码文件指定不同的编码: # -*- coding: cp-1252 -*- 上述定义允许在源文件中使用 Windows-1252 字符集中的字符编码&…...

spring boot分装通用的查询+分页接口
背景 在用spring bootmybatis plus实现增删改查的时候,总是免不了各种模糊查询和分页的查询。每个数据表设计一个模糊分页,这样代码就造成了冗余,且对自身的技能提升没有帮助。那么有没有办法实现一个通用的增删改查的方法呢?今天…...
【OpenCV】OpenCV环境搭建,Mac系统,C++开发环境
OpenCV环境搭建,Mac系统,C开发环境 一、步骤VSCode C环境安装运行CMake安装运行OpenCV 安装CMakeList 一、步骤 VSCode C环境安装CMake 安装OpenCV 安装CmakeList.txt VSCode C环境安装运行 访问官网 CMake安装运行 CMake官网 参考文档 OpenCV 安…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解
突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 安全措施依赖问题 GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...
基础测试工具使用经验
背景 vtune,perf, nsight system等基础测试工具,都是用过的,但是没有记录,都逐渐忘了。所以写这篇博客总结记录一下,只要以后发现新的用法,就记得来编辑补充一下 perf 比较基础的用法: 先改这…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
C++ 基础特性深度解析
目录 引言 一、命名空间(namespace) C 中的命名空间 与 C 语言的对比 二、缺省参数 C 中的缺省参数 与 C 语言的对比 三、引用(reference) C 中的引用 与 C 语言的对比 四、inline(内联函数…...
相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)
【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...