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

C++模拟实现——list

一、成员变量及其基本结构

1.基本结构模型

本质是一个带头双向循环列表,将节点进行封装,并且为了方便使用,进行重定义

2.节点的封装定义

	template<class T>//定义节点struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;list_node(const T& x = T()) :_prev(nullptr),_next(nullptr),_data(x){}};

在定义节点时,要注意将初始化一起进行封装完成,提供默认构造函数

3.成员变量的定义

成员变量是一个哨兵位的头结点

typedef list_node<T> node;//对节点重命名,方便使用
private:list_node<T>* _head;

二、迭代器(重点)

1.介绍

list的迭代器用原生指针无法实现,需要对原生指针进行封装,然后对顺序表指针的行为操作进行模拟实现,是list模拟实现中最大的重点难点,此时从使用者的角度上看,依然能将iterator看作为指针去使用,但设计者的角度上看,其本质是一个指针的封装,是个自定义类型。

2.对指针的基本封装

template<class T>
struct __list_iterator
{typedef list_node<int> node;//将节点重定义方便使用typedef __list_iterator<int> self;//将类型重定义方便使用//成员变量node* _node;//初始化__list_iterator(node* n):_node(n){}//模拟实现指针操作...
}

以上对节点指针进行了封装处理,之后逐一实现常用的功能,例如:++ 、--、* 、 -> 、== 、!= 等等

3.++和--

要提供迭代器++和--的操作,需要对运算符进行重载,链表迭代器的++本质上是获得下一个节点的地址,--则是前一个节点的地址,并且要区分前置和后置

        //++slef& operator++(){_node = _node->_next;return *this;}slef operator++(int)//后置{slef tmp(*this);_node = _node-> _next;return tmp;}//--self& operator--(){_node = _node->_prev;return *this;}self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}

4.== 和 !=

迭代器的比较,本质是要比较其封装在内部的指针是否同一个

bool operator!=(const self& n)
{return _node != n._node;
}bool operator==(const self& n)
{return _node == n._node;
}

5. * 和 ->

对解引用操作符的重载,则需要考虑到常量迭代器的调用,常量迭代器去本质是对迭代器所指向的内容进行常量化,因此在这里,const_iterator 和 iterator 的核心区别在于解引用后返回的值是否常量,其他功能相同,因此可以使用类模板去控制这两个运算符重载返回值的区别,在定义部分加上两个新的模板参数即可。

template<class T,class Ref,class Ptr>
strucr __list_iterator
{...//定义和重命名等等Ref operator*()//  Ref == T&(迭代器) / const T&(常量迭代器){return _node->_data;}//对于->的重载,存在特殊处理,只需要返回Ptr operator->()// Ptr == T*(迭代器)/ const T*(常量迭代器){return& _node->_data;}
}// 迭代器定义部分,在list类内定义
// typedef __list_iterator<T,T&,T*> iterator;
// typedef __list_con_iterator<T,const T&,const T*>;

三、构造与析构

1.默认构造函数

默认构造需要初始化出一个哨兵位的头结点,并且让节点指针指向自己,为了方便其他构造函数初始化哨兵位的头结点,可以单独写一个函数进行复用

		void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}list()//直接的初始化{empty_init();}

2.用迭代器区间去构造

迭代器区间构造需要借助函数模板,任意类型的迭代器都可以将值拷贝到容器中

template<class Iterator>
list(Iterator first,Iterator last)
{//先得初始化容器empty_init();while(first != last){push_back(*first); // 底层是++first;}
}

3.拷贝构造

拷贝构造这里选择对上面的构造函数进行复用,深拷贝出一个tmp,在进行交换

		void swap(list<T>& lt){std::swap(_head, lt._head);}list(const list<T>& lt)//拷贝构造{empty_init();list<T> tmp(lt.begin(), lt.end());swap(tmp);}

4.赋值重载

赋值重载的底层实现,也是在传参的时候,调用了拷贝构造实现深拷贝后,在进行交换

		list<T>& operator=(list<T> lt)//赋值重载{swap(lt);return *this;}

5.析构函数

可以先实现clear,然后复用,底层就是将所有节点全部逐一释放,用迭代器遍历释放即可

		void clear(){iterator it = begin();while (it != end()){it = erase(it);}}~list()//析构{clear();delete _head;_head = nullptr;}

四、增删操作

对应增删操作,只需要实现insert和erase,其余的头插头删等等都可以对其进行复用,这里是用迭代器去实现的。

		void insert(iterator pos, const T& x){node* cur = pos._node;node* prev = cur->_prev;node* new_node = new node(x);//链接new_node->_prev = prev;prev->_next = new_node;new_node->_next = cur;cur->_prev = new_node;}iterator erase(iterator pos){assert(pos != end());node* cur = pos._node;node* prev = cur->_prev;node* next = cur->_next;delete cur;//链接prev->_next = next;next->_prev = prev;return iterator(next);}

需要注意的是,erase后迭代器会失效,因此为了部分场景下的方便,erase是有一个返回值的,返回的是下一个节点的迭代器;

总结

本章通过自行模拟实现了list,加深了类和对象以及list的相关知识,其中很重要的一个知识点就是对与list迭代器的封装和实现,本篇博客整理了整个实现过程的思路,方便今后复习和其他同学参考学习

相关文章:

C++模拟实现——list

一、成员变量及其基本结构 1.基本结构模型 本质是一个带头双向循环列表&#xff0c;将节点进行封装&#xff0c;并且为了方便使用&#xff0c;进行重定义 2.节点的封装定义 template<class T>//定义节点struct list_node{list_node<T>* _prev;list_node<T>…...

FPGA的音乐彩灯VHDL流水灯LED花样,源码和视频

名称&#xff1a;FPGA的音乐彩灯VHDL流水灯LED 软件&#xff1a;Quartus 语言&#xff1a;VHDL 代码功能&#xff1a; &#xff08;1&#xff09;设计一彩灯控制电路&#xff0c;按要求控制8路&#xff08;彩灯由发光 二极管代替&#xff0c;受实验箱限制&#xff0c;多路同…...

企业知识库软件,快速构建企业知识分享与团队协同的软件

企业知识库是一种特殊的在线协同文档工具&#xff0c;支持包括FAQ、文档、视频、知识图谱等。从本质上讲&#xff0c;它是基于企业知识库软件从而实现内部或外部知识的沉淀、集合、更新、共享等&#xff0c;能为员工或客户提供常见问题的标准回答。 今天我就基于HelpLook &…...

Java,输出一个10行的杨辉三角

据图可以发现&#xff0c;杨辉三角是每行的首元素和末元素都为1&#xff0c;中间的元素都是等于它上面的元素加上左上角的元素。 首先&#xff0c;先完成二数组的创建和初始化&#xff0c;第一行的长度为一&#xff0c;第二行的长度为二……以此类推。所以&#xff0c;外元素的…...

Java版Http请求post和get两种调用实现

在实际项目中常涉及到相互调用&#xff0c;对于http接口的调用&#xff0c;需要经过建立连接&#xff0c;拼接参数&#xff0c;调用等步骤&#xff0c;记录下来&#xff0c;方便查看。 第一步、引入jar包 pom中引入apache的httpclient包 <dependency><groupId>c…...

yjs demo: 多人在线协作画板

基于 yjs 实现实时在线多人协作的绘画功能 支持多客户端实时共享编辑自动同步&#xff0c;离线支持自动合并&#xff0c;自动冲突处理 1. 客户端代码&#xff08;基于Vue3&#xff09; 实现绘画功能 <template><div style"{width: 100vw; height: 100vh; over…...

虹科分享 | 赋能物流机器人:CANopen通信如何发挥重要作用?

现代物流领域迅速融入了技术进步&#xff0c;特别是随着自主机器人的兴起&#xff0c;这一趋势越发明显。确保这些机器人在复杂的仓库环境中精确运行的一个关键方面是CANopen通信协议。该协议集成了各种组件&#xff08;电机、传感器、摄像头和先进的电池系统&#xff09;&…...

南丁格尔玫瑰图

目录 由来 效果图 echarts官网找相似图 将南丁格尔玫瑰图引进html页面中 引入echarts 准备容器 初始化echarts实例对象 指定配置项和数据&#xff08;官网给的option&#xff09; 将配置项给echarts 自定义南格丁尔玫瑰图 修改颜色 修改玫瑰图大小 修改图的模式为半…...

vue 大文件切片下载

前提是你上传的时候也是切片上传&#xff0c;下载的时候后端给你返回的是一个文件id的数组&#xff0c;如果是你就可以用下面的方法 // 循环下载文件 // id是每个文件的id type 是一个类型&#xff0c;我传入是应为给不同的组件赋值getFile(id, type) {// 通过wen文件id去获取…...

2023年“绿盟杯”四川省大学生信息安全技术大赛

pyfile 先check源码&#xff0c;没什么发现&#xff0c;接着进行目录扫描&#xff0c;扫到路径 /download 下载备份文件得到 www.zip&#xff0c;解压得到app.py 大致审一下代码&#xff1a; 在read目录下给file传参进行请求&#xff0c;如果这个东西存在就会读取出来 这里…...

YOLOv8改进实战 | 更换主干网络Backbone(二)之轻量化模型GhostnetV2

前言 轻量化网络设计是一种针对移动设备等资源受限环境的深度学习模型设计方法。下面是一些常见的轻量化网络设计方法: 网络剪枝:移除神经网络中冗余的连接和参数,以达到模型压缩和加速的目的。分组卷积:将卷积操作分解为若干个较小的卷积操作,并将它们分别作用于输入的不…...

【C++代码】二叉搜索树的最近公共祖先,二叉搜索树中的插入操作,删除二叉搜索树中的节点--代码随想录

题目&#xff1a;二叉搜索树的最近公共祖先 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个结点 p、q&#xff0c;最近公共祖先表示为一个结点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽可能大&a…...

【ArcGIS微课1000例】0075:将AutoCAD(Dwg、Dxf)文件转换为shp、KML(kml、kmz)文件

文章目录 1. 加载DWG2. 导出为shp3. 投影变换4. 转为kml1. 加载DWG 打开ArcMap,点击添加符号: 选择地形图dwg数据,全选图层,也可以选择需要的图层。 提示位置的空间参考,点击确定即可。 加载效果。 2. 导出为shp 接下来我们演示将面状数据转为shp,选择Polygon图层,右键…...

Unigui中获取手机特征码

在Delphi Unigui中&#xff0c;您可以使用TUniDeviceInfo类来读取设备的一些基本信息&#xff0c;例如设备的操作系统版本、设备名称和分辨率等。但是&#xff0c;TUniDeviceInfo类并不提供设备的特征码信息。 如果您想要获取设备的特征码信息&#xff0c;您可以使用JavaScrip…...

Github Actions实现Spring Boot自动化部署(第二弹)

Github Actions实现Spring Boot自动化部署&#xff08;第二弹&#xff09; 前言 ​ 今天就来讲述一下如何使用GitHub结合Actions实现Spring Boot程序从提交代码到打包、容器化、部署全过程自动化。首先咱们得现有一个能够在本地运行的Spring Boot程序&#xff0c;并且在Githu…...

【Python机器学习】sklearn.datasets分类任务数据集

如何选择合适的数据集进行机器学习的分类任务? 选择合适的数据集是进行任何机器学习项目的第一步,特别是分类任务。数据集是机器学习任务成功的基础。没有数据,最先进的算法也无从谈起。 本文将专注于sklearn.datasets模块中用于分类任务的数据集。这些数据集覆盖了各种场…...

华为OD 数组去重和排序(100分)【java】A卷+B卷

华为OD统一考试A卷B卷 新题库说明 你收到的链接上面会标注A卷还是B卷。目前大部分收到的都是B卷。 B卷对应20022部分考题以及新出的题目&#xff0c;A卷对应的是新出的题目。 我将持续更新最新题目 获取更多免费题目可前往夸克网盘下载&#xff0c;请点击以下链接进入&#xff…...

黑客技术(网络安全)学习

1.网络安全是什么 网络安全可以基于攻击和防御视角来分类&#xff0c;我们经常听到的 “红队”、“渗透测试” 等就是研究攻击技术&#xff0c;而“蓝队”、“安全运营”、“安全运维”则研究防御技术。 2.网络安全市场 一、是市场需求量高&#xff1b; 二、则是发展相对成熟…...

【算法|动态规划No.28】leetcode1312. 让字符串成为回文串的最少插入次数

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

AWS SAP-C02教程10-其它服务

接下来介绍的内容是一些SAP-C02考试会涉及到的,但是目前无法很好将其归类,暂且放在其它服务中 目录 1 AWS WorkSpaces2 AWS APP Stream 2.02.1 WorkSpaces vs APP Stream 2.03 AWS Device Farm4 AWS AppSync5 AWS Outposts6 AWS WaveLength7 AWS Local Zones8 AWS Cloud Map…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

重启Eureka集群中的节点,对已经注册的服务有什么影响

先看答案&#xff0c;如果正确地操作&#xff0c;重启Eureka集群中的节点&#xff0c;对已经注册的服务影响非常小&#xff0c;甚至可以做到无感知。 但如果操作不当&#xff0c;可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

【学习笔记】erase 删除顺序迭代器后迭代器失效的解决方案

目录 使用 erase 返回值继续迭代使用索引进行遍历 我们知道类似 vector 的顺序迭代器被删除后&#xff0c;迭代器会失效&#xff0c;因为顺序迭代器在内存中是连续存储的&#xff0c;元素删除后&#xff0c;后续元素会前移。 但一些场景中&#xff0c;我们又需要在执行删除操作…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008&#xff1a;是version产品的大版本。 R006&#xff1a;是release产品特性版本。 C009&#xff1a;是通用版 B0014&#xff1a;是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存&#xff1a;1GB 以上 硬盘&#xf…...