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 安…...

XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战
前言 现在我们有个如下的需求,设计一个邮件发奖的小系统, 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式(Decorator Pattern)允许向一个现有的对象添加新的功能,同时又不改变其…...

CTF show Web 红包题第六弹
提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框,很难让人不联想到SQL注入,但提示都说了不是SQL注入,所以就不往这方面想了 先查看一下网页源码,发现一段JavaScript代码,有一个关键类ctfs…...
STM32+rt-thread判断是否联网
一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...

用docker来安装部署freeswitch记录
今天刚才测试一个callcenter的项目,所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲
文章目录 前言第一部分:体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分:体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...
C++.OpenGL (20/64)混合(Blending)
混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...