C++ list介绍(迭代器失效)

一、常用接口

reverse逆置
sort排序(默认升序)
仿函数greater<int>
merge合并,可以全部合并,也可以一部分合并
unique:去重(先排序,再去重)
remove:删除e值,而不是erase的pos位置删
splice(粘接):其实就是transform(转移)
把某个位置i,转移到当前链表的某个position之前


list的sort效率很低,底层用归并,但是数据访问很低,因为是链表
vectror的sort更好一些,因为是连续的空间

二、迭代器封装问题


原生指针就是天生的迭代器(但是前提是物理空间是连续的)
为什么??
因为解引用就是该数据,++就是下一个数据
但是如果空间是不连续的就会出问题

例如list的原生指针就不能作为迭代器,因为不符合预期
因为list的原生指针式list*,但是list*++是错误的,因为不是连续的空间
解引用list*++,就是在原来地址位置,向后移动一个list类型大小的距离,指向该位置
但是因为不是连续的空间,所以,移动后的list*并不是下一个节点的地址
那怎么办呢?
改造一下
我们用一个类去封装这个原生指针,然后用这个类去控制这个原生指针
重载++list为移动到下一个节点的位置
需要处理的是这个部分

用类封装一个原生指针,这个原生指针也是一个模板
然后重定义这个原生指针为iterator
也就是说,这个itrator就是一个原生指针
这个原生指针也是一个模板
那么,当我们传入任意类型时,原生指针模板就会自动推导出其对应的指针
只是这个指针取了一个别名,叫做iterator,即迭代器
这就充分利用了类型的内涵
也就是说此处的迭代器底层还是一个指针
但是这个指针的行为不符合我们的预期
所以我们需要封装,重载行为

指针是内置类型
前置++和后置++是如何判断的呢?
因为函数重载只看参数列表,返回值不影响
所以,在后置++的重载参数列表加一个占位参数,int
这样就会区别两个函数
迭代器比较:就是比较指针,指针就是地址。地址相等,迭代器相等,否则不等
iterator的特点是不管底层是什么

三、list模拟实现(原码)

insert:
参数为iterator
找到当前的节点
记录前,后,插入即可

erase:参数pos也是iterator指针
删除节点后,当前节点的指针1iterator失效
所以要更新iterator
返回下一个节点的指针

pop_back:删除--end()
end是head,是头节点

resize:尾删和尾插

#pragma once
#include<assert.h>
#include<iostream>
using namespace std;namespace myspace
{//节点template <class T>struct list_node{list_node(const T& val = 0):_date(val), _next(nullptr), _prev(nullptr){}list_node<T>* _next;list_node<T>* _prev;T _date;};//迭代器template <class T, class Ref, class ptr>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref, ptr> self;//模板推导list_iterator(node* node):_node(node){}//++itself& operator++(){_node = _node->_next;return *this;}//it++self& operator++(int){self tmp = _node;_node = _node->_next;return tmp;}//--itself& operator--(){_node = _node->_prev;return *this;}//it--self& operator--(int){self tmp = _node;_node = _node->_prev;return  tmp;}//operatorT& operator*(){return _node->_date;}T* operator->(){return &_node->_date;}bool operator==(const self& it){return _node == it._node;}bool operator!=(const self& it){return _node != it._node;}node* _node;};//反向迭代器template <class T, class Ref, class ptr>struct list_reverse_iterator{typedef list_node<T> node;typedef list_reverse_iterator<T, Ref, ptr> self;//模板推导list_reverse_iterator(node* node):_node(node){}//++itself& operator++(){_node = _node->_prev;return *this;}//it++self& operator++(int){self tmp = _node;_node = _node->_prev;return tmp;}//--itself& operator--(){_node = _node->_next;return *this;}//it--self& operator--(int){self tmp = _node;_node = _node->_next;return  tmp;}//operatorT& operator*(){node* tmp = _node->_prev;_node = _node->_prev;return tmp->_date;}T* operator->(){node* tmp = _node->_prev;_node = _node->_prev;return &tmp->_date;}bool operator==(const self& it){return _node == it._node;}bool operator!=(const self& it){return _node != it._node;}node* _node;};//一般对象的iterator和const对象的const_iterator//由于两者对应的实现不同,因此,一般的方式是写两个类//但是,二者的区别只有*引用和->引用两者的不同//所以,如果要书写两个类,显的臃肿//所以,可以使用模板//在需要的地方使用模板推导template <class T>class list{typedef list_node<T> node;public:typedef list_iterator<T, T&, T*> iterator;//一般对象的iteratortypedef list_iterator<T, const T&, const T*> const_iterator;//const对象的iteratortypedef list_reverse_iterator<T, T&, T*> reserve_iterator;//reserve_iteratorvoid empty_init(){node* newnode = new node;newnode->_next = newnode;newnode->_prev = newnode;this->_head = newnode;_size = 0;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}bool empty(){return size() == 0;}size_t size(){return _size;}list(){empty_init();}//lt1(lt2)//需要重新搞出一个新的list//(this指针就是lt1)list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}~list(){clear();delete _head;_head = nullptr;}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}reserve_iterator rbegin(){return _head;}reserve_iterator rend(){return _head->_next;}//void swap(const list<T>& lt)//{//	std::swap(_head,lt._head);//	std::swap(lt._size, _size);//}void push_back(const T& val){insert(_head, val);}void push_front(const T& val){insert(begin(), val);}void pop_back(){erase(_head->_prev);}void pop_front(){erase(begin());}void insert(iterator pos, const T& val){node* tmp = new node(val);node* next = pos._node;node* prev = pos._node->_prev;prev->_next = tmp;tmp->_prev = prev;next->_prev = tmp;tmp->_next = next;++_size;}iterator erase(iterator pos){if (_size == 0)return nullptr;node* cur = pos._node;node* next = cur->_next;node* prev = cur->_prev;next->_prev = prev;prev->_next = next;delete cur;pos = nullptr;--_size;return  next;}private:node* _head;size_t _size;};//打印const对象void print(const list<int>& clt){list<int>::const_iterator it = clt.begin();while (it != clt.end()){cout << *it << " ";}cout << endl;}//正常的增删改void test1(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.insert(lt.begin(), 10);//lt.erase(lt.begin());lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_back();list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test2(){list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.clear();list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << lt.size() << endl;cout << endl;}void test3(){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;cout << lt.empty() << endl;}void test4(){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>::const_iterator it = lt.begin();//while (it != lt.end())//{//	cout << *it << " ";//	++it;//}cout << endl;cout << lt.empty() << endl;}void print_list(const list<int>& clt){//const对象的迭代器//const_iterator迭代器是一个单独的对象//为了区别于一般对象,单独搞了一个const_iterator类//这个const_iterator类的目的在于,可以正常进行遍历,但是不能对内部的内容进行修改//因为实现方法不同,一个类无法实现,因此可以考虑使用模板list<int>::const_iterator it = clt.begin();while (it != clt.end()){//*it += 10;cout << *it << " ";++it;}cout << endl;}void test5(){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_front(100);//lt.erase(lt.end());lt.pop_back();lt.pop_back();lt.pop_back();lt.pop_front();list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;}void test6(){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> lt2(lt);list<int> lt3;lt3.push_back(10);lt3.push_back(11);lt3.push_back(12);lt3.push_back(13);//lt3.swap(lt2);list<int>::iterator it = lt3.begin();while (it != lt3.end()){cout << *it << " ";++it;}cout << endl;}void test7(){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>::reserve_iterator rlt = lt.rbegin();while (rlt != lt.rend()){cout << *rlt << " ";}cout << endl;}}

四、相关细节

什么时候用struct,什么时候用class?
数据都是共有的时候就可以使用struct

模拟实现的时候,需要定义一个自己的命名空间,防止和库内冲突
将指针类型设置为模板,因为要支持不同数据的list

typedef ListNode<T> node #意为将节点设置为模板
但是,为了便于理解,我们编写代码的时候,还是使用node,便于理解
但是实际上,这个node其实是一个模板,我们用了一个typedef宏替换实现的
创建一个新节点的时候,也是,直接new node
这样就会直接开辟一个新空间节点出来,一个模板类型的空间节点

模板的理解:很简单
就是多了一个template<class T>而已
然后将对应的东西设置为T,再typedef就是了
例如:我要将list的节点设置为模板,那么:
typedef ListNode<T> node
节点设置为模板:ListNode<T>
换名字:typedef ListNode<T> node
不要把模板看的这么复杂
也不要吧typedef看的太复杂

list中at会检查越界,[]不会检查

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

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

相关文章

AI编码工具-通义灵码功能实测

AI编码工具-通义灵码功能实测 通义灵码功能介绍行级/函数级实时续写自然语言生成代码单元测试生成异常排错智能排查生成代码注释生成代码解释研发领域自由问答 在上一篇文章中&#xff0c;我介绍了通义灵码的功能以及支持的操作系统&#xff0c;主流IDE等&#xff0c;详细内容可…

密码口令初步

一&#xff0c;弱口令&#xff08;ctfhub&#xff09; 1.打开环境&#xff0c;发送到bp的instruder板块&#xff0c;一般id默认为admin&#xff0c;也可以用bp找出来&#xff0c;这里就是 2.先clear &#xff0c;再把password等号后面添加进来&#xff08;add&#xff09;&am…

H5视频付费点播打赏影视系统程序全开源运营版

这是一款视频打赏源码&#xff0c;勿做非法用途&#xff0c;由用户亲测功能完善&#xff0c;源码仅用于学习使用&#xff0c;分享链接是用户云盘&#xff0c;具有时效性&#xff0c;感兴趣的可以去学习。 thinkphp开发&#xff0c;前后端分离设计&#xff0c;支持游客登陆、VIP…

DInet

&#xff08;1&#xff09;数据&#xff1a; 1&#xff09;&#xff1a;随机获取5帧参考帧 2&#xff09;&#xff1a;处理这5帧连续帧&#xff0c;:source_frames:连续5帧的crop_moth b)audio_list:连续5帧的每一帧对应的5帧音频mel特征 c):refs:fintune 固定参考帧&#xff0…

千元投影仪高性价比机型又出新机?大眼橙C1D上市引领市场新潮流

近年来投影仪技术不断更新迭代&#xff0c;家用智能投影仪市场正迎来一场革新风暴。最明显的就是各家品牌都更快地推出自家的投影仪新品&#xff0c;4月底&#xff0c;极米推出了play5&#xff0c;大眼橙推出了c1d&#xff0c;小明推出了newq3pro……都是千元价位的投影仪新品&…

3D点云处理的并行化

在我们的项目中&#xff0c;我们研究了数百万级 3D 点云上的空间局部计算&#xff0c;并提出了两种主要方法&#xff0c;可以提高 GPU 的速度/吞吐量&#xff0c;同时保持最终结果的性能准确性。 通过空间局部&#xff0c;我们的意思是每个像素独立地基于其局部邻域中的点执行…

【3D目标检测】常见相关指标说明

一、mAP指标 mean Average Precision&#xff08;平均精度均值&#xff09;&#xff0c;它是目标检测和信息检索等任务中的重要性能指标。mAP 通过综合考虑精度和召回率来衡量模型的总体性能。 1.1 精度&#xff08;Precision&#xff09; 表示检索到的目标中实际为正确目标…

数据库大作业——基于qt开发的图书管理系统(二) 相关表结构的设计

前言 在上一篇文章中。我们完成了Qt环境的安装&#xff0c;同时完成了有关项目需求的分析并绘制了整体的项目架构图&#xff0c;而在图书管理系统中&#xff0c;其实我们主要完成的就是对数据的增删改查&#xff0c;并将这些功能通过信号与槽机制和可视化界面绑定在一起&#…

二、双fifo流水线操作——verilog练习与设计

文章目录 一、案例分析二、fifo_ctrl模块设计2.1 波形设计&#xff1a;2.2 代码实现2.2.1 fifo_ctrl2.2.2 顶层文件top_fifo_ctrl&#xff08;rx和tx模块省略&#xff09;2.2.3 仿真文件tb_fifo_ctrl 2.3波形仿真 一、案例分析 案例要求&#xff1a;写一个 fifo 控制器&#x…

WSL安装及使用

一、强烈推荐使用win11系统 二、优先参考官方链接 Install WSL | Microsoft Learn 三、其次参考链接 Manual installation steps for older versions of WSL | Microsoft Learn 四、本次测试安装过程记录 1:准备工作 Step 1 - Enable the Windows Subsystem for Linux dism.ex…

探索网站支付系统的奥秘,从Vue3和Spring Boot开始(入门级项目实战+在线教程)附赠项目源码!

你是否曾经在购物时&#xff0c;对着电脑屏幕前的“支付成功”四个字感到好奇&#xff1f;这背后的秘密究竟是什么&#xff1f; 今天&#xff0c;让我们一起揭开支付系统的神秘面纱&#xff0c;探索其背后的技术实现。 在这个基于Vue3和Spring Boot的支付项目实战中&#xff…

网贷大数据查询要怎么保证准确性?

相信现在不少人都听说过什么是网贷大数据&#xff0c;但还有很多人都会将它跟征信混为一谈&#xff0c;其实两者有本质上的区别&#xff0c;那网贷大数据查询要怎么保证准确性呢?本文将为大家总结几点&#xff0c;感兴趣的朋友不妨去看看。 想要保证网贷大数据查询的准确度&am…

经常使用的正则分割

背景&#xff1a; 工作中经常需要对一串数据进行分割&#xff0c;最简单的办法就是使用正则表达式。 常见符号&#xff1a; \&#xff1a;\后跟一个特殊字符&#xff0c;表示匹配这个字符&#xff0c;例如\$&#xff0c;表示匹配数据中的$。 ^&#xff1a;^后跟一个特殊字符&a…

virtualbox kafka nat + host-only集群 + windows 外网 多网卡

virtualbox kafka nat + host-only集群 + windows 映射访问 kafka集群搭建背景kafka集群搭建 背景 使用virtualbox搭建kafka集群,涉及到不同网络策略的取舍 首先 桥接 网络虽说 啥都可以,但是涉及到过多ip的时候,而且还不能保证使用的ip不被占用,所以个人选择kafka虚拟机…

用龙梦迷你电脑福珑2.0做web服务器

用龙梦迷你电脑福珑2.0上做web服务器是可行的。已将一个网站源码放到该电脑&#xff0c;在局域网里可以访问网站网页。另外通过在同一局域网内的一台windows10电脑上安装花生壳软件&#xff0c;也可以在外网访问该内网服务器网站网页。该电脑的操作系统属于LAMP。在该电脑上安装…

Mysql报错红温集锦(一)(ipynb配置、pymysql登录、密码带@、to_sql如何加速、触发器SIGNAL阻止插入数据)

一、jupyter notebook无法使用%sql来添加sql代码 可能原因&#xff1a; 1、没装jupyter和notebook库、没装ipython-sql库 pip install jupyter notebook ipython-sql 另外如果是vscode的话还需要安装一些相关的插件 2、没load_ext %load_ext sql 3、没正确的登录到mysql…

短视频矩阵系统源码/saas--总后台端、商户端、代理端、源头开发

短视频矩阵系统源码/saas--总后台端、商户端、代理端、源头开发 搭建短视频矩阵系统源码的交付步骤可以概括为以下几个关键环节&#xff1a; 1. **系统需求分析**&#xff1a;明确系统需要支持的功能&#xff0c;如短视频的上传、存储、播放、分享、评论、点赞等。 2. **技术选…

计算机体系结构:6、指令流水线

6.指令流水线 6.1 流水线概述 6.1.1 流水线的执行效率 ​ 一条指令的执行过程可被分为若干阶段&#xff0c;每个阶段由相应的功能部件完成。一般而言&#xff0c;一条指令的流水线由如下5个流水段组成&#xff1a; 取指令(IF):从存储器取指令指令译码(ID):产生指令执行所需…

QLabel 如何同时显示图片和文字?

效果: align="top"表示图片和文字底部对齐。 img src=":/img/qrc_img.png"表示此图片被添加到qrc的相对路径。 完整: QString content =QString("<html><head/><body><p><img src=\":/img/qrc_img.png\"…

Linux i2c工具——i2c_tools

1 简介 i2c-tools是一个用于处理I2C&#xff08;Inter-Integrated Circuit&#xff09;总线的工具集&#xff0c;它在Linux环境中广泛使用。这个工具集包含了一系列命令行工具&#xff0c;用于在I2C总线上执行各种操作&#xff0c;例如扫描设备、读取/写入寄存器、检测设备等。…