[C++]list的迭代器模拟实现

        下面是简单的实现list的迭代器功能,底层是带头双向循环的链表,主要关注的是list的迭代器问题。没有涉及内存池等复杂算法来提高效率。

一、list的概述

(一)、抽象数据类型的定义

容器:列表(list)

        list是一个顺序容器,它可以在任何位置频繁地进行插入和擦除数据的操作,并且支持双向迭代。

        list容器的行为就像双向链表那样,双向链表可以将每一个元素存储在不同和不连续的存储空间。其通过内部每个元素的前后链接关系保持其有序结构。

        list和其他的容器相比,list在任意位置的插入、删除和移动显得更高效。而list不支持随机访问,如果要访问链表中某个位置的值,需要遍历到该位置,并且会因为要维持元素前后的关联而开辟额外的空间。

模板类

template<class T>

操作

一、构造函数

list();        默认构造函数

list(int n, const T& value = T());        用n个val进行填充初始化

template <class Iterator>
list(Iterator first, Iterator last); 用迭代器区间进行初始化
list(std::initializer_list<T> ini_list);        参数初始化列表初始化

list(const list<T>& l);        拷贝构造函数

list<T>& operator=(const list<T>& l);        赋值构造函数

~list();        析构函数

二、迭代器

1、迭代器
iterator begin();
iterator end();
const_iterator begin() const;
const_iterator end() const;

2、反向迭代器
reverse_iterator rbegin();
reverse_iterator rend();
const_reverse_iterator rbegin() const;
const_reverse_iterator rend() const;

三、容量

size_t size()const;        返回当前容器存储的数据个数

bool empty()const;        检测当前容器是否为空

四、访问数据

T& front();        获取list的头结点元素的引用

const T&  front() const;        获取list的头结点的常引用

T& back();        获取list的尾结点元素的引用

const T& back const;        获取list的尾节点的常引用

五、修改操作
void push_back(const T& x);        尾插
void pop_back();        尾删
void push_fornt(const T& x);        头插
void pop_fornt();        头插
iterator insert(iterator pos,const T& x);        指定位置插入
iterator erase(iterator pos);        删除指定位置

void swap(list<T>& v);        交换两个链表的内容

(二)、成员变量 

//链表的节点
template<class T>
struct ListNode
{T _val;ListNode* _pPrev;ListNode* _pNext;//生成一个链表结点并用x进行初始化ListNode(const T& x = T()){_val = x;_pPrev = this;_pNext = this;//该结点一开始前后指针都指向自身}
};template<class T>
class list
{
public:typedef ListNode Node;
private:Node* _pHead;//指向哨兵位
};

二、具体实现 

        由于带头双向循环链表增删改操作比较简单,代码不进行具体讲解,只重点讲一下list的迭代器的具体实现。

(一)、list的迭代器

        list不像vector一样,vector存储的数据在内存中是连续的,可以使用数组的指针加减就可以完成vector的遍历,而list的数据在逻辑结构上是有序的,但是在其内存的存储上一般都是不连续的,无法使用指针的加减来对链表进行遍历,不能够使用原生数组的指针来作为list的迭代器,这个时候我们就需要使用类来帮助我们实现list的迭代器的功能,让其行为符合我们迭代器的需求。

1、正向迭代器

        在正向迭代器中,对迭代器进行++的操作,就是让迭代器指向当前结点的下一个结点,对迭代器进行--的操作,就是让迭代器指向当前结点的上一个结点,对迭代器进行解引用,得到该结点存储的数据。要满足这样的行为,需要自定义类型来实现

具体代码如下:

//声明定义正向迭代器
//Ref和Ptr用于辨别是普通迭代器还是const迭代器
template<class T,class Ref,class Ptr>
struct ListIterator
{
public:typedef ListIterator<T,Ref,Ptr> Self;typedef ListNode<T> Node;Node* _pNode;//迭代器指向当前结点的地址//默认构造ListIterator(Node* pNode = nullptr) :_pNode(pNode){; }//重载//前置++Self& operator++(){_pNode = _pNode->_pNext;//迭代器指向当前结点的下一个结点return *this;}//后置++Self operator++(int){Self temp(_pNode);_pNode = _pNode->_pNext;//迭代器指向当前结点的下一个结点return temp;}//前置--Self& operator--(){_pNode = _pNode->_pPrev;return *this;}//后置--Self operator--(int){Self temp(_pNode);_pNode = _pNode->_pNext;return temp;}//重载解引用Ref operator*(){return _pNode->_val;}//重载->操作符Ptr operator->(){return &(_pNode->_val);}//迭代器的比较方法(用来判断迭代停止)bool operator==(Self it) {return _pNode == it._pNode;}bool operator!=(Self it){return _pNode != it._pNode;}
};

2、反向迭代器

        在反向迭代器中,对迭代器进行++的操作,就是让迭代器指向当前结点上一个结点,对迭代器进行--的操作,就是让迭代器指向当前结点下一个结点,对迭代器进行解引用,得到该结点存储的数据。

具体代码如下: 

//适配反向迭代器
template<class T, class Ref, class Ptr>
struct ListReverseIterator
{
public:typedef ListReverseIterator<T, Ref, Ptr> Self;typedef ListNode<T> Node;typedef ListNode<T>* PNode;PNode _pNode;ListReverseIterator(PNode pNode = nullptr) :_pNode(pNode){; }//重载++Self& operator++(){_pNode = _pNode->_pPrev;return *this;}Self operator++(int){Self tem(_pNode);_pNode = _pNode->_pPrev;return tem;}//重载--Self& operator--(){_pNode = _pNode->_pNext;return *this;}Self operator--(int){Self tem(_pNode);_pNode = _pNode->_pNext;return tem;}//重载解引用Ref operator*() {return _pNode->value;}//重载->Ptr operator->() {return &(_pNode->value);}bool operator==(const Self& it) {return _pNode == it._pNode;}bool operator!=(const Self& it) {return _pNode != it._pNode;}
};

        注意:正向迭代器和反向迭代器之间由于类型不同,是不能直接进行比较的。

        在定义迭代器模板类时,指明其引用类型和指针类型,可以避免写重复的代码段。

(二)、list的具体实现

//带头双向循环list容器
template<class T>
class list
{
public:typedef ListNode<T> Node;typedef ListNode<T>* PNode;//迭代器typedef ListIterator<T, T&, T*> iterator;typedef ListIterator<T, const T&, const T*> const_iterator;//反向迭代器typedef ListReverseIterator<T, T&, T*> reverse_iterator;typedef ListReverseIterator<T, const T&, const T*> const_reverse_iterator;//初始化list(){_pHead = new Node;_pHead->_pNext = _pHead;_pHead->_pPrev = _pHead;}list(int n, const T& value = T()) :list(){for (int i = 0; i < n; i++){push_back(value);}}template <class Iterator>list(Iterator first, Iterator last) :list(){while (first != last){push_back(*first);first++;}}//参数初始化列表初始化list(std::initializer_list<T> ini_list) :list(){for (auto& e : ini_list){push_back(e);}}//拷贝构造list(const list<T>& l) :list(){for (auto& e : l){push_back(e);}}//赋值构造list<T>& operator=(const list<T>& l){list<T> tem(l);swap(tem);return *this;}//析构函数~list(){PNode pcur = _pHead->_pNext;PNode ptem;//记录销毁节点的下一个节点//std::cout << "销毁:";while (pcur != _pHead){ptem = pcur->_pNext;//cout << (pcur->value) << "->";delete pcur;pcur = ptem;}//std::cout << "nullptr" << std::endl;_pHead = nullptr;}//迭代器iterator begin(){return iterator(_pHead->_pNext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead->_pNext);}const_iterator end() const{return const_iterator(_pHead);}//反向迭代器reverse_iterator rbegin(){return reverse_iterator(_pHead->_pPrev);}reverse_iterator rend(){return reverse_iterator(_pHead);}const_reverse_iterator rbegin() const{return const_reverse_iterator(_pHead->_pPrev);}const_reverse_iterator rend() const{return const_reverse_iterator(_pHead);}// List Capacitysize_t size()const{PNode pcur = _pHead->_pNext;size_t n = 0;while (pcur != _pHead){n++;pcur = pcur->_pNext;}return n;}bool empty()const{return _pHead == _pHead->_pNext;}// List AccessT& front(){if (!empty())return _pHead->_pNext->value;elsereturn _pHead->value;}const T& front()const{if (!empty())return _pHead->_pNext->value;elsereturn _pHead->value;}T& back(){if (!empty())return _pHead->_pPrev->value;elsereturn _pHead->value;}const T& back()const{if (!empty())return _pHead->_pPrev->value;}//Modify//尾插void push_back(const T& x){//找到尾结点PNode pTail = _pHead->_pPrev;PNode newNode = new Node(x);newNode->_pNext = _pHead;newNode->_pPrev = pTail;pTail->_pNext = newNode;_pHead->_pPrev = newNode;}//尾删void pop_back(){if (empty())return;PNode tail = _pHead->_pPrev;tail->_pPrev->_pNext = tail->_pNext;tail->_pNext->_pPrev = tail->_pPrev;delete tail;}//头插void push_fornt(const T& x){PNode newNode = new Node(x);newNode->_pPrev = _pHead;newNode->_pNext = _pHead->_pNext;_pHead->_pNext->_pPrev = newNode;_pHead->_pNext = newNode;}//头删void pop_fornt(){if (empty())return;PNode pDel = _pHead->_pNext;pDel->_pPrev->_pNext = pDel->_pNext;pDel->_pNext->_pPrev = pDel->_pPrev;delete pDel;}//指定位置插入//不存在迭代器失效问题iterator insert(iterator pos, const T& x){PNode newNode = new Node(x);newNode->_pNext = pos._pNode;newNode->_pPrev = pos._pNode->_pPrev;pos._pNode->_pPrev->_pNext = newNode;pos._pNode->_pPrev = newNode;return iterator(newNode);}//指定位置删除//返回删除位置的下一个节点的迭代器,因为会存在迭代器失效问题iterator erase(iterator pos){iterator itNext(pos._pNode->_pNext);//连接前后节点pos._pNode->_pPrev->_pNext = pos._pNode->_pNext;pos._pNode->_pNext->_pPrev = pos._pNode->_pPrev;delete pos._pNode;return itNext;}//交换两个链表内容的操作void swap(list<T>& v1){std::swap(_pHead, v1._pHead);}
private://头节点指针PNode _pHead;//size_t _length;
};

        注意:在指定位置插入一个结点不会存在迭代器失效问题,而删除指定位置的结点时,就会存在迭代器失效的问题,此时迭代器指向不存在的结点。因此,在删除指定位置的结点时,应将其下一个结点的迭代器作为返回值返回,更新迭代器的值,防止迭代器失效问题。

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

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

相关文章

SALOME源码分析:View Model

作为一款开源的CAx(CAD/CAE/CAM)软件集成平台&#xff0c;为了实现各个Module支持不同的数据显示与交互方案&#xff0c;出于扩展性的考虑&#xff0c;SALOME引入了View Model&#xff0c;用以支持OpenGL、OCC、VTK、ParaView、Qwt等数据显示与交互实现。 本文将以OCCViewer、…

一文搞懂 java 线程池:ScheduledThreadPool 和 WorkStealingPool 原理

你好&#xff0c;我是 shengjk1&#xff0c;多年大厂经验&#xff0c;努力构建 通俗易懂的、好玩的编程语言教程。 欢迎关注&#xff01;你会有如下收益&#xff1a; 了解大厂经验拥有和大厂相匹配的技术等 希望看什么&#xff0c;评论或者私信告诉我&#xff01; 文章目录 一…

PHP宜邦家政服务管理系统-计算机毕业设计源码04426

目 录 摘要 1 绪论 1.1 选题背景与意义 1.2开发现状 1.3论文结构与章节安排 2 宜邦家政服务管理系统系统分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 操作可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非功能性分析 2.3 系统用…

力扣hot100 -- 动态规划(上)

目录 ❄技巧 &#x1f33c;爬楼梯 &#x1f354;杨辉三角 &#x1f30a;打家劫舍 &#x1f40e;完全平方数 &#x1f33c;零钱兑换 &#x1f33c;单词拆分 ❄技巧 动态规划dp-CSDN博客 &#x1f446;花 5 分钟快速刷一遍 花 10 分钟浏览一下 线性DP 背包DP&#x1f447…

VS展示6个错误中的0个解决方法

左键点击展示6个错误中的0个 左键点击展示23个警告中的0个

国产强大免费WAF, 社区版雷池动态防护介绍

雷池WAF&#xff0c;基于智能语义分析的下一代 Web 应用防火墙 使用情况 我司于2023年4月23日对雷池进行测试&#xff0c;测试一个月后&#xff0c;于2023年5月24日对雷池进行正式切换&#xff0c;此时版本为1.5.1。 里程碑纪念 后续一直跟随雷池进行版本升级&#xff0c;当前…

怎样使用js技术实现Chrome投屏功能?

在Web前端技术中&#xff0c;直接控制浏览器窗口或标签页从主屏投屏到副屏&#xff08;如PPT的演讲者模式&#xff09;并不简单&#xff0c;而且直接控制浏览器窗口从主屏投屏到副屏的功能超出了Web标准的范畴&#xff0c;并且涉及到用户系统级别的设置和权限&#xff0c;因此不…

ETCD概述--使用/特性/架构/原理

ETCD概述 ETCD是一个高度一致的分布式键值存储, 它提供了一种可靠的方式来存储需要由分布式系统或机器集群访问的数据(高可用, 强一致性)​全局的配置服务中心. 本文将介绍其特性、相关操作和常见的应用场景. 如果想了解更多, 请查阅我的技术博客: https://dingyuqi.com 特性 …

C语言分支和循环(下)

C语言分支和循环&#xff08;下&#xff09; 1. 随机数生成1.1 rand1.2 srand1.3 time1.4 设置随机数的范围 2. 猜数字游戏实现 掌握了前面学习的这些知识&#xff0c;我们就可以写⼀些稍微有趣的代码了&#xff0c;比如&#xff1a; 写⼀个猜数字游戏 游戏要求&#xff1a; 电…

git常用命令速查表

Git相关概念简述 版本库&#xff1a;git在本地开辟的一个存储空间&#xff0c;一般在 .git 文件里。工作区(workspace)&#xff1a; 就是编辑器里面的代码&#xff0c;我们平常开发直接操作的就是工作区。暂存区&#xff08;index/stage&#xff09;&#xff1a;暂时存放文件的…

13. Revit API: Filter(过滤器)

13. Revit API: Filter&#xff08;过滤器&#xff09; 前言 在讲Selection之前&#xff0c;还是有必要先了解一下的过滤器的。 对了&#xff0c;关于查找一些比较偏的功能或者API的用法&#xff0c;可以这样查找 关键词 site:https://thebuildingcoder.typepad.com/ site是…

C语言 -- 函数

C语言 -- 函数 1. 函数的概念2. 库函数2.1 标准库和头文件2.2 库函数的使用方法2.2.1 功能2.2.2 头文件包含2.2.3 实践2.2.4 库函数文档的一般格式 3. 自定义函数3.1 函数的语法形式3.2 函数的举例 4. 形参和实参4.1 实参4.2 形参4.3 实参和形参的关系 5. return 语句6. 数组做…

react ts 封装3D柱状图,支持渐变

留档&#xff0c;以防忘记 bar3D.tsx import React, { useEffect, useRef, useState } from react; import * as echarts from echarts; import echarts/lib/chart/bar; import echarts/lib/chart/pictorialBar; import echarts/lib/component/grid; import echarts/lib/comp…

Centos7 安装老版本的chrome

查看自己linux是哪个centos版本 使用以下命令&#xff1a; cat /etc/centos-release我这里是centOS 7。然后在安装最新版的google-chrome时&#xff0c;总是会报错显示存在依赖环境的问题&#xff0c;使得无法安装成功chrome。 Package: google-chrome-stable (/google-chro…

使用 Rustup 管理 Rust 版本

文章目录 安装 Rustup配置镜像源安装 Rustup 安装 RustVS Code插件创建项目代码示例 Rust 官网&#xff1a;https://www.rust-lang.org/zh-CN/Crates 包管理&#xff1a;https://crates.io/Rust 程序设计语言&#xff1a;https://kaisery.github.io/trpl-zh-cn/通过例子学 Rust…

如何对低代码平台进行分类?

现在市面上的低代码平台就像雨后春笋一样冒出来&#xff0c;而且源源不绝&#xff0c;但总结下来&#xff0c;大致的也就以下三类。 一、 aPaaS多引擎类&#xff08;有很多成熟引擎、做好东西要一起用&#xff09; 这类产品包括&#xff1a;织信Informat&#xff08;国内&…

使用 Smart-doc 记录 Spring REST API

如果您正在使用 Spring Boot 开发 RESTful API&#xff0c;您希望让其他开发人员尽可能容易地理解和使用您的 API。文档是必不可少的&#xff0c;因为它为将来的更新提供了参考&#xff0c;并帮助其他开发人员与您的 API 集成。很长一段时间以来&#xff0c;记录 REST API 的方…

uni-app上传失败超出文件限制解决方法-分包处理-预加载

分包背景 当你的上传出现一下错误&#xff1a; Error: 系统错误&#xff0c;错误码&#xff1a;80051,source size 2089KB exceed max limit 2MB [20240703 10:53:06][wxbf93dfb6cb3eb8af] [1.06.2405010][win32-x64] 说明你主包太大需要处理了&#xff0c;一下两种方法可以…

REGX52.H报错

keil cannot open source input file "REGX52.H": No such file or directory 选择下面这个目录 Keil\C51\INC\Atmel

SpringCloudAlibaba基础四 微服务调用组件OpenFeign

JAVA 项目中如何实现接口调用&#xff1f; 1&#xff09;Httpclient HttpClient 是 Apache Jakarta Common 下的子项目&#xff0c;用来提供高效的、最新的、功能丰富的支持 Http 协议的客户端编程工具包&#xff0c;并且它支持 HTTP 协议最新版本和建议。HttpClient 相比传统 …