C++中链表的底层迭代器实现

大家都知道在C++的学习中迭代器是必不可少的,今天我们学习的是C++中的链表的底层迭代器的实现,首先我们应该先知道链表的底层迭代器和顺序表的底层迭代器在实现上有什么区别,为什么顺序表的底层迭代器更加容易实现,而链表的底层迭代器不容易实现,接下来小编再来告诉大家如何来实现链表的底层迭代器,学完今天这篇我相信大家对C++中的迭代器一定会有一个更加深刻的认识!大家先看今天学习的内容:

一、顺序表和链表的底层迭代器的区别

为了知道它们两个的区别,先得告诉大家顺序表的底层迭代器是如何实现的,首先大家先得明白顺序表私有成员都有什么,好方便大家来理解它们的底层迭代器是如何实现的,请看下图顺序表的私有成员变量:

	private:iterator _start;iterator _finish;iterator _end_of_storage;

如图就是顺序表的私有成员变量 第一个 _start 是记录顺序表的起始位置的指针类型是 T*

_finish记录的是顺序表内末尾元素的下一个位置的指针类型是T*,_end_of_storage记录的是顺序表的目前的所有容量的下一个位置类型也是T*。

在明白了顺序表的私有成员变量的意义,并且顺序表的储存是连续的空间有点类似于数组的数据储存,所以大家也应该明白了顺序表的底层迭代器是如何实现的了吧,如果不懂请看下图操作及注释,如下图:

但是由于链表的物理结构不是连续的,所以想顺序表一样的底层迭代器实现方法是行不通的,这也是为什么在底层实现链表的迭代器中,不能通过给迭代器++来做到迭代器指向下一个元素的地址,因为链表的数据在空间中分布式随意的。那该如何去设计链表的底层迭代器呢,请大家继续往下看。

二、链表的底层迭代器该如何实现

首先先请大家看一下链表中的数据是如何分布的,如下图:

如图,可见链表中的数据是随意分布的,但是我们仍然可以用前一个节点找到下一个节点,但为什么这样子不行,不算迭代器呢,因为在C++中迭代器的定义就是通过 ++ 来找到下一个元素,接通过 * 号来拿到他这个位置的数据,这才是迭代器的规定,如下段代码的遍历效果:

如上链表的分布图,虽然我们可以拿到下一个节点的位置和这个节点的数据,但我们不是通过 ++ 和 * 来实现的,所以通过这样的方式做出的迭代器是不对的。那我们该如何实现呢,小编新学了一个方法,就是把迭代器底层封装成一个类,让它内部进项运算符重载来达到 ++ 实现像迭代器一样遍历的过程* 实现像迭代器一样拿出数据的过程,那么该如何实现呢,请大家继续往下看。

三、链表底层迭代器的实现

上面说到把迭代器封装成一个类,然后用运算符重载来达到 ++* 的过程,把它彻底改变为一个正规的迭代器,现在大家就和我一起实现这个迭代器的类:

1、首先大家要明白链表(带头双向循环链表)的结构,如下代码:

template<class T>
// 这里用结构体是因为ListNode中的每个成员都应该可以访问 没有私有成员
// 也可以使用友元来解决这个问题
struct ListNode
{T _data;ListNode* _next;ListNode* _prev;ListNode(const T& data = T()):_next(nullptr),_prev(nullptr), _data(data){}
};
	template<class T>class list{public:typedef ListNode<T> Node;private:Node* _head;};

如上图代码,在这里我们已经知道下一步需要把链表独特的遍历方式(用前一个指针找到后一个指针)用运算符重载的改为 ++  来实现遍历和拿到数据,保证它和迭代器的实现和用法一模一样。那该如何实现这个类呢。

2、实现迭代器的类

我们需要定义一个迭代器的类,因为有普通迭代器和不可修改的迭代器,它们两个的函数大多数相同,为了减少代码量,我们加入两个模板参数来帮我们减轻代码量

	// 这里加入 Ref 和 Ptr 是为了区分普通迭代器和const迭代器的区别// 本来要写两份迭代器,一份可修改,一份不可修改 现在直接交给编译器去做template<class T , class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ref, Ptr> Self;// 链表的迭代器应该是 Node* 类型的指针Node* _node;ListIterator(Node* node):_node(node){}// 前置++Self& operator++(){_node = _node->_next;return *this;}//前置--Self& operator--(){_node = _node->_prev;return *this;}Self operator++(int){Self tem(*this);_node = _node->_next;return tem;}Self operator--(int){Self tem(*this);_node = _node->_prev;return tem;}Ptr operator->(){return &(_node->_data);}Ref operator*(){return _node->_data;}bool operator!=(const Self& it){return _node != it._node;}bool operator==(const Self& it){return _node == it._node;}};

以上就是今天的所有内容,希望大家会喜欢!!!

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

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

相关文章

Golang | Leetcode Golang题解之第235题二叉搜索树的最近公共祖先

题目&#xff1a; 题解&#xff1a; func lowestCommonAncestor(root, p, q *TreeNode) (ancestor *TreeNode) {ancestor rootfor {if p.Val < ancestor.Val && q.Val < ancestor.Val {ancestor ancestor.Left} else if p.Val > ancestor.Val && q…

Dify中的工具

Dify中的工具分为内置工具&#xff08;硬编码&#xff09;和第三方工具&#xff08;OpenAPI Swagger/ChatGPT Plugin&#xff09;。工具可被Workflow&#xff08;工作流&#xff09;和Agent使用&#xff0c;当然Workflow也可被发布为工具&#xff0c;这样Workflow&#xff08;工…

解决fidder小黑怪倒出JMeter文件缺失域名、请求头

解决fidder小黑怪倒出JMeter文件缺失域名、请求头 1、目录结构&#xff1a; 2、代码 coding:utf-8 Software:PyCharm Time:2024/7/10 14:02 Author:Dr.zxyimport zipfile import os import xml.etree.ElementTree as ET import re#定义信息头 headers_to_extract [Host, Conn…

芋道框架万字详解(前后端分离)、若依框架、yudao-cloud保姆级攻略

♥️作者&#xff1a;小宋1021 &#x1f935;‍♂️个人主页&#xff1a;小宋1021主页 ♥️坚持分析平时学习到的项目以及学习到的软件开发知识&#xff0c;和大家一起努力呀&#xff01;&#xff01;&#xff01; &#x1f388;&#x1f388;加油&#xff01; 加油&#xff01…

STM32MP135裸机编程:定时器内核时钟频率计算方法

0 工具准备 STM32MP13xx参考手册 1 定时器内核时钟频率计算方法 1.1 定时器分组 STM32MP135的定时器按照时钟源不同分成了三组&#xff0c;如下&#xff1a; APB1: APB2: APB6&#xff1a; 1.2 定时器内核时钟频率计算方法 APB1DIV是APB1的分频系数&#xff0c;APB2DIV、…

51单片机9(使用左移实现流水灯编程)

一、序言&#xff1a;下面我们来给大家介绍一下这个流水灯&#xff0c;流水灯如何来实现&#xff1f;我们依然使用这个工程来完成它。 1、那要使用实现这个流水灯&#xff0c;那我们只需要让D1到D8逐个的点亮&#xff0c;那同样要实现它足够的点亮&#xff0c;也会涉及到延时&…

html设计(两种常见的充电效果)

第一种 完整代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title&…

tomcat和nginx实现动静分离

访问nginx就是静态页面&#xff0c;nginx代理index.jsp可以访问tomcat的动态页面。 实验 1、设备以及IP地址 nginx1 192.168.10.41 tomcat1 192.168.10.51 tomcat2 192.168.10.52 2、tomcat1 的配置 创建动态页面 cd /usr/local/tomcat/webapps 创建一个目录作为一个ser…

【LeetCode 链表合集】

文章目录 1. LeetCode 206 反转链表2. NC40 链表相加 1. LeetCode 206 反转链表 题目链接&#x1f517; 解题思路&#xff1a; &#x1f50d; &#x1f427;创建一个新的节点&#xff0c;使用链表头插的方法&#xff1b; 2. NC40 链表相加 题目链接&#x1f517; 解题思路…

C++入门基础(2)

C入门基础&#xff08;2&#xff09; 1.缺省函数2.函数重载3.引用3.1 引用的概念和定义3.2 引用的特性3.3 引用的使用3.3.1引用的特性 4 .const引用5. 指针和引用的关系6.inline 1.缺省函数 • 缺省参数是声明或定义函数时为函数的参数指定⼀个缺省值。在调用该函数时&#xf…

【服务器】在Linux查看运行的Python程序,并找到特定的Python程序

在Linux查看运行的Python程序并找到特定的Python程序 写在最前面1. 使用ps命令查看所有Python进程查看详细信息 2. 使用pgrep命令查找Python进程ID 3. 使用top或htop命令使用top命令使用htop命令 4. 使用lsof命令查找Python进程打开的文件 5. 使用nvidia-smi命令查看GPU使用情况…

【接口自动化_06课_Pytest+Excel+Allure完整框架集成】

一、logging在接口自动化里的应用 1、设置日志的配置&#xff0c;并收集日志文件 日志的设置需要在pytest.ini文件里设置。这个里面尽量不要有中文 2、debug日志的打印 pytest.ini文件的开关一定得是true才能在控制台打印日志 import allure import pytest from P06_PytestFr…

使用 YUM 仓库和 NFS 共享存储的详细指南

使用 YUM 仓库和 NFS 共享存储的详细指南 文章目录 使用 YUM 仓库和 NFS 共享存储的详细指南一、YUM 仓库服务1.1 YUM 介绍1.2 YUM 源的提供方式1.2.1 配置本地源仓库1.2.2 配置 FTP 源1.2.3 配置 HTTP 源 1.3 网络源配置1.3.1 清华源1.3.2 163 源1.3.3 阿里云源 1.4 YUM 命令1…

IntelliJ IDEA自定义菜单(Menus)、任务栏(toolbars)详细教程

本示例是基于IDEA2024.1Ultimate版本的New UI模式下 一、自定义菜单 1、打开Settings&#xff0c;找到Menus and Toolbars 2、点击右边的Main Menu&#xff0c;点击号&#xff0c;选择Add Action 3、弹出Add Action弹窗&#xff0c;搜索或者选择你要添加的指令 二、自定义工具…

Linux命令更新-Vim 编辑器

简介 Vim 是 Linux 系统中常用的文本编辑器&#xff0c;功能强大、可扩展性强&#xff0c;支持多种编辑模式和操作命令&#xff0c;被广泛应用于程序开发、系统管理等领域。 1. Vim 命令模式 Vim 启动后默认进入命令模式&#xff0c;此时键盘输入的命令将用于控制编辑器本身&…

OpenCV 寻找棋盘格角点及绘制

目录 一、概念 二、代码 2.1实现步骤 2.2完整代码 三、实现效果 一、概念 寻找棋盘格角点&#xff08;Checkerboard Corners&#xff09;是计算机视觉中相机标定&#xff08;Camera Calibration&#xff09;过程的重要步骤。 OpenCV 提供了函数 cv2.findChessboardCorners…

LeetCode 441, 57, 79

目录 441. 排列硬币题目链接标签思路代码 57. 插入区间题目链接标签思路两个区间的情况对每个区间的处理最终的处理 代码 79. 单词搜索题目链接标签原理思路代码 优化思路代码 441. 排列硬币 题目链接 441. 排列硬币 标签 数学 二分查找 思路 由于本题所返回的 答案在区间…

【C++】入门基础(引用、inline、nullptr)

目录 一.引用 1.引用的定义 2.引用的特性 3.引用的使用场景 4.const引用 5.引用和指针的区别 二.inline 三.nullptr 一.引用 1.引用的定义 引用不是新定义一个变量&#xff0c;而是给已经存在的变量取一个别名&#xff0c;编译器不会给引用变量开辟内存空间&#xff0c…

检测精度评价指标召回率和精确率

检测精度评价指标为&#xff1a; 1、召回率&#xff08;Recall Rate &#xff09; 2、平均精度均值&#xff08;mAP&#xff09; 3、平均对数漏检率&#xff08;MR-2&#xff09; 计算 TP 和 FP 的示例 假设你有一个目标检测模型&#xff0c;并使用它检测图像…

Git代码管理工具 — 3 Git基本操作指令详解

目录 1 获取本地仓库 2 基础操作指令 2.1 基础操作指令框架 2.2 git status查看修改的状态 2.3 git add添加工作区到暂存区 2.4 提交暂存区到本地仓库 2.5 git log查看提交日志 2.6 git reflog查看已经删除的记录 2.7 git reset版本回退 2.8 添加文件至忽略列表 1 获…