21. C++STL 7(8000字详解list及其迭代器的模拟实现)

⭐本篇重点：STL中的list及其迭代器的模拟实现和测试

⭐本篇代码：c++学习 · 橘子真甜/c++-learning-of-yzc - 码云 - 开源中国 (gitee.com)

目录

一. list的节点

二. list的迭代器 

2.1 迭代器框架

 2.2 迭代器实现

三. list的实现

3.1 list的构造函数

3.2 insert

3.2 erase 

3.3 begin和end

3.4 push_back和push_front

3.5 pop_back和pop_front

3.6 clear和析构函数

3.7 测试代码1

3.8 拷贝构造函数和赋值运算符重载 

四. test.h 源代码

五. 测试自定义类型和类类型

5.1测试string类

5.2 测试自定义类

六. 下篇重点：stack和queue的使用与模拟实现

一. list的节点

        我们知道，list是一个带头的双向循环链表。所以这个节点应该包含以下成员变量。

    //表示链表的节点template<class T>struct ListNode{ListNode* _next;ListNode* _prev;T _data;//构造函数ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){};};

二. list的迭代器 

        我们模拟过string和vector，它两的迭代器都用原生指针就能实现。但是list的迭代器使用原生指针无法实现。比如我们++it，不能简单的让指针+1就行。

2.1 迭代器框架

        list迭代器结构体如下：

	//迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用template<class T, class Ptr, class Ref>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ptr, Ref> Self;Node* _node;//构造函数ListIterator(Node* node):_node(node){}//前置++Self& operator++(){}//后置++Self operator++(int){}//前置--Self& operator--(){}//后置--Self operator--(int){}//解引用，获取这个节点Ref operator*(){}//->，箭头获取的是节点的指针Ptr operator->(){}//判断是否相等bool operator==(const Self& self){}//判断是否不等bool operator!=(const Self& self){}};

 2.2 迭代器实现

operator++

在list中，++只需要让我们的指针指向当前节点的下一个节点即可

前置++

		//前置++Self& operator++(){	//返回++后的结果_node = _node->_next;return *this;	}

后置++。后置++注意要用中间变量保存并且不能引用返回！

		//后置++Self operator++(int){//返回++前的结果，需要保存++前的指针//注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！Node* tmp = _node;_node = _node->_next;return tmp;}

operator* 和 operator->

*返回当前节点的data，->返回当前节点data的地址（即一个指针） 

比如： *it = data         it-> = &data

		//解引用，获取这个节点Ref operator*(){return _node->_data;}//->，箭头获取的是节点的指针Ptr operator->(){return &_node->_data;}

根据上面的代码        --和== !=同理可以实现 

迭代器的全部实现代码如下：

	//迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用template<class T, class Ptr, class Ref>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ptr, Ref> Self;Node* _node;//构造函数ListIterator(Node* node):_node(node){}//前置++Self& operator++(){	//返回++后的结果_node = _node->_next;return *this;	}//后置++Self operator++(int){//返回++前的结果，需要保存++前的指针//注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！Node* tmp = _node;_node = _node->_next;return tmp;}//前置--Self& operator--(){_node = _node->_prev;return *this;}//后置--Self operator--(int){Node* tmp = _node;_node = _node->_prev;return tmp;}//解引用，获取这个节点Ref operator*(){return _node->_data;}//->，箭头获取的是节点的指针Ptr operator->(){return &_node->_data;}//判断是否相等bool operator==(const Self& it){return it._node == _node;}//判断是否不等bool operator!=(const Self& it){return it._node != _node;}};

三. list的实现

list的框架如下。位于 test.h中

	template<class T>class list{typedef ListNode<T> Node;	//typedef list的节点public://list 的迭代器typedef ListIterator<T, T*, T&> iterator;typedef ListIterator<T, const T*, const T&> const_iterator;private:Node* _head;	//list的头节点};

3.1 list的构造函数

         list是带头双向循环链表。只要在堆中开辟一个头节点，然后让它的next和prev都指向自己即可。注意头节点的data不存储任何值。

		//构造函数list():_head(new Node){_head->_next = _head;_head->_prev = _head;}

3.2 insert

        和vector一样，我们先定义出insert和erase。然后push_back和pop_back去复用insert和erase的代码可以提高代码的复用。

        思考一下list的insert中的pos是什么？        list没有下标，只能用迭代器表示pos

插入代码的逻辑图如下

我们只要让prev链接号newnode，再让newnode链接好cur即可 （注意提前保存好cur）

代码如下：

		//insert。在pos位置插入datavoid insert(const iterator& pos, const T& data){Node* newnode = new Node(data);Node* cur = pos._node;Node* pre = cur->_prev;//1.链接pre和newnodepre->_next = newnode;newnode->_prev = pre;//2.链接newnode和curnewnode->_next = cur;cur->_prev = newnode;}

即便只有一个头节点上面代码也没问题。逻辑图如下 

3.2 erase 

        erase比较简单。找到pos的前后节点pre和next，链接pre和next，然后删除cur即可

注意：返回的节点应该是next节点（即删除cur后，next处于pos的位置）

代码如下：

        //erase，删除pos位置的节点iterator erase(const iterator& pos){Node* cur = pos._node;Node* pre = cur->_prev;Node* next = cur->_next;pre->_next = next;next->_prev = pre;delete cur;return next;	//删除cur后，pos就处于next了}

3.3 begin和end

        begin返回第一个节点（头节点的next）的迭代器，end最后一个节点后一个的迭代器（就是头节点）

代码如下：

		iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}

3.4 push_back和push_front

        有了insert这两个函数就简单了。push_back直接在end()这个迭代器调用insert，push_front直接在begin()调用insert。

代码如下：

		//尾插void push_back(const T& data){insert(end(), data);}//头插void push_front(const T& data){insert(begin(), data);}

3.5 pop_back和pop_front

同理。调用erase即可。不过注意尾删是删除最后一个节点不是头节点！

		//头删void pop_front(){erase(begin());}//尾删void pop_back(){//erase(end());			//不是删除头节点，而是头节点的前一个节点（尾节点）erase(_head->_prev);}

3.6 clear和析构函数

        利用迭代器遍历链表，一个一个删除节点即可。clear不会删除头节点

		//clear清空链表void clear(){iterator it = begin();while (it != end()){erase(it++);	//后置++，it走到下一个节点后。返回前一个节点去删除即可}}

        析构函数。调用clear然后删除头节点即可。

		~list(){clear();delete _head;_head = nullptr;}

3.7 测试代码1

        到此为止，整个链表基本实现了。我们来测试一下

测试代码 test.cpp

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include "test.h"
using namespace std;void test1()
{YZC::list<int> l1;for (int i = 0; i < 5; i++)		// 0 1 2 3 4 l1.push_back(i);for (int i = 10; i < 15; i++)	// 14 13 12 11 10 0 1 2 3 4l1.push_front(i);	l1.pop_back();	// 14 13 12 11 10 0 1 2 3l1.pop_front();	// 13 12 11 10 0 1 2 3YZC::list<int>::iterator it = l1.begin();while (it != l1.end()){cout << *it << " ";++it;}cout << endl;
}int main()
{test1();return 0;
}

 运行结果如下

3.8 拷贝构造函数和赋值运算符重载 

        拷贝构造。遍历构造即可

		//拷贝构造list(const list<T>& l):_head(new Node){//1.初始化头节点_head->_next = _head;_head->_prev = _head;//2.遍历l，尾插节点即可for (auto const& e : l){push_back(e);}}

        赋值运算符重载。利用临时变量出函数销毁的特性 

		//operator=list& operator=(list<T> l){swap(_head, l._head);return *this;}

四. test.h 源代码

#pragma oncenamespace YZC
{//表示链表的节点template<class T>struct ListNode{ListNode* _next;ListNode* _prev;T _data;ListNode(const T& data = T()):_next(nullptr), _prev(nullptr), _data(data){};};//迭代器，T为节点的data，Ptr表示data的地址，Ref表示data的引用template<class T, class Ptr, class Ref>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T, Ptr, Ref> Self;Node* _node;//构造函数ListIterator(Node* node):_node(node){}//前置++Self& operator++(){	//返回++后的结果_node = _node->_next;return *this;	}//后置++Self operator++(int){//返回++前的结果，需要保存++前的指针//注意这里不可使用引用返回，tmp在栈中。属于局部变量，出函数会销毁！Node* tmp = _node;_node = _node->_next;return tmp;}//前置--Self& operator--(){_node = _node->_prev;return *this;}//后置--Self operator--(int){Node* tmp = _node;_node = _node->_prev;return tmp;}//解引用，获取这个节点Ref operator*(){return _node->_data;}//->，箭头获取的是节点的指针Ptr operator->(){return &_node->_data;}//判断是否相等bool operator==(const Self& it){return it._node == _node;}//判断是否不等bool operator!=(const Self& it){return it._node != _node;}};template<class T>class list{typedef ListNode<T> Node;	//typedef list的节点public://list 的迭代器typedef ListIterator<T, T*, T&> iterator;typedef ListIterator<T, const T*, const T&> const_iterator;//构造函数list():_head(new Node){_head->_next = _head;_head->_prev = _head;}//拷贝构造list(const list<T>& l):_head(new Node){//1.初始化头节点_head->_next = _head;_head->_prev = _head;//2.遍历l，尾插节点即可for (auto const& e : l){push_back(e);}}//operator=list& operator=(list<T> l){swap(_head, l._head);return *this;}//析构函数~list(){clear();delete _head;_head = nullptr;}//clear清空链表void clear(){iterator it = begin();while (it != end()){erase(it++);	//后置++，it走到下一个节点后。返回前一个节点去删除即可}}//insert。在pos位置插入datavoid insert(const iterator& pos, const T& data){Node* newnode = new Node(data);Node* cur = pos._node;Node* pre = cur->_prev;//1.链接pre和newnodepre->_next = newnode;newnode->_prev = pre;//2.链接newnode和curnewnode->_next = cur;cur->_prev = newnode;}//erase，删除pos位置的节点iterator erase(const iterator& pos){Node* cur = pos._node;Node* pre = cur->_prev;Node* next = cur->_next;pre->_next = next;next->_prev = pre;delete cur;return next;	//删除cur后，pos就处于next了}//尾插void push_back(const T& data){insert(end(), data);}//头插void push_front(const T& data){insert(begin(), data);} //头删void pop_front(){erase(begin());}//尾删void pop_back(){//erase(end());			//不是删除头节点，而是头节点的前一个节点（尾节点）erase(_head->_prev);}iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}private:Node* _head;	//list的头节点};
}

五. 测试自定义类型和类类型

5.1测试string类

测试代码和结果如下：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include "test.h"
using namespace std;void test1()
{YZC::list<string> l1;string s1 = "hello world!";string s2 = "YZC";string s3 = "yzc";string s4 = "list模拟实现";l1.push_back(s1);l1.push_back(s2);l1.push_back(s3);l1.push_back(s4);for (const auto& str : l1)cout << str << " ";cout << endl;//拷贝构造YZC::list<string> l2(l1);for (const auto& str : l2)cout << str << " ";
}int main()
{test1();return 0;
}

5.2 测试自定义类

 

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include "test.h"
using namespace std;struct Date
{int _year = 0;int _month = 1;int _day = 1;
};void test1()
{YZC::list<Date> l1;Date d1;Date d2;l1.push_back(d1);l1.push_back(d2);//1 测试迭代器的解引用auto it = l1.begin();while (it != l1.end()){cout << (*it)._year << "/" << (*it)._month << "/" << (*it)._day << endl;++it;}cout << endl;//测试赋值运算符和->YZC::list<Date>l2 = l1;auto it1 = l2.begin();while (it1 != l2.end()){cout << it->_year << "/" << it->_month << "/" << it->_day << endl;++it1;}
}int main()
{test1();return 0;
}

测试结果如下：

六. 下篇重点：stack和queue的使用与模拟实现

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

Docker打包SpringBoot项目

Docker打包SpringBoot项目

一、项目打成jar包 在进行docker打包之前&#xff0c;先确定一下&#xff0c;项目能够正常的打成JAR包&#xff0c;并且启动之后能够正常的访问。这一步看似是可有可无&#xff0c;但是能避免后期的一些无厘头问题。 二、Dockerfile 项目打包成功之后&#xff0c;需要编写Doc…
阅读更多...
零基础学鸿蒙开发--第九篇--网络请求

零基础学鸿蒙开发--第九篇--网络请求

12. ⽹络请求 鸿蒙系统提供了 http 模块 ⽤于发送 http 请求&#xff0c;另外&#xff0c; OpenHarmony社区基于该模块将前端开发中常⽤的⽹络请 求库 axios 移植到了鸿蒙系统&#xff0c;因此我们也可以在鸿蒙系统中使⽤ axios 发送 http 请求&#xff0c;下⾯重点为⼤家介绍…
阅读更多...
133.WEB渗透测试-信息收集-小程序、app（4）

133.WEB渗透测试-信息收集-小程序、app（4）

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;132.WEB渗透测试-信息收集-小程序、app&#xff08;3&#xff09; 输入命令&#xff1a;…
阅读更多...
Pointnet++改进71：添加LFE模块|高效长距离注意力网络

Pointnet++改进71：添加LFE模块|高效长距离注意力网络

简介：1.该教程提供大量的首发改进的方式，降低上手难度，多种结构改进，助力寻找创新点！2.本篇文章对Pointnet++特征提取模块进行改进，加入LFE模块，提升性能。3.专栏持续更新，紧随最新的研究内容。 目录 1.理论介绍 2.修改步骤 2.1 步骤一 2.2 步骤二 2.3 步骤三 1.理…
阅读更多...
Android仿美团左右联动购物列表

Android仿美团左右联动购物列表

Android仿美团左右联动购物列表 左右联动购物列表&#xff0c;不难。 一、思路&#xff1a; 两个RecycleView 二、效果图&#xff1a; 三、关键代码&#xff1a; public class MainActivity extends AppCompatActivity {private RecyclerView rl_left;private RecyclerVie…
阅读更多...
Mitel MiCollab 企业协作平台 任意文件读取漏洞复现(CVE-2024-41713)

Mitel MiCollab 企业协作平台 任意文件读取漏洞复现(CVE-2024-41713)

0x01 产品简介 Mitel MiCollab是加拿大Mitel（敏迪）公司推出的一款企业级协作平台，旨在为企业提供统一、高效、安全的通信与协作解决方案。通过该平台，员工可以在任何时间、任何地点，使用任何设备，实现即时通信、语音通话、视频会议、文件共享等功能，从而提升工作效率和…
阅读更多...
深度学习camp-第J3-1周：DenseNet算法 实现乳腺癌识别

深度学习camp-第J3-1周：DenseNet算法 实现乳腺癌识别

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 我的环境 语言环境&#xff1a;Python 3.12编译器&#xff1a;Jupyter Lab深度学习环境&#xff1a;Pytorch 2.4.1 Torchvision 0.19.1数据集&#xff1a;乳腺…
阅读更多...
Elasticsearch 单节点安全配置与用户认证

Elasticsearch 单节点安全配置与用户认证

Elasticsearch 单节点安全配置与用户认证 安全扫描时发现了一个高危漏洞&#xff1a;Elasticsearch 未授权访问 。在使用 Elasticsearch 构建搜索引擎或处理大规模数据时&#xff0c;需要启用基本的安全功能来防止未经授权的访问。本文将通过简单的配置步骤&#xff0c;为单节…
阅读更多...
Vulhub：Shiro[漏洞复现]

Vulhub：Shiro[漏洞复现]

目录 CVE-2010-3863(Shiro未授权) 使用浏览器访问靶场主页面 使用Yakit进行抓包 使用ffuf对靶机8080端口进行根路径FUZZ CVE-2016-4437(Shiro-550) 使用浏览器访问靶场主页面 使用Yakit进行抓包 使用Yakit反连中自带的Yso-Java Hack进行漏洞利用 首先运行脚本生成一个…
阅读更多...
数学拯救世界（一）———寻“数”记

数学拯救世界（一）———寻“数”记

一、 很久很久以前&#xff0c;在一个只认识整数和小数的国度&#xff0c;有一个很残暴的国王提了一个要求&#xff1a;要是不能表示出把一段1米的绳子三等分后的大小&#xff0c;就要把所有的大臣杀掉。 1➗3 0.333&#xff0c;怎么办呀&#xff1f;怎么办呀&#xff1f; 袁q…
阅读更多...
Codeforces Round 991 (Div. 3)题解

Codeforces Round 991 (Div. 3)题解

先随随便便写一点东西吧&#xff0c;毕竟只是一场div3 A. Line Breaks 思路&#xff1a;一道很简单的模拟题吧&#xff0c;就是遍历一遍&#xff0c;当大于x的时候就break&#xff0c;然后前面那个就是找到的前x个字的总长度不超过m #include<bits/stdc.h> using names…
阅读更多...
掌握谈判技巧，达成双赢协议

掌握谈判技巧，达成双赢协议

在当今竞争激烈且合作频繁的社会环境中&#xff0c;谈判成为了我们解决分歧、谋求共同发展的重要手段。无论是商业合作、职场交流&#xff0c;还是国际事务协商&#xff0c;掌握谈判技巧以达成双赢协议都具有极其关键的意义。它不仅能够让各方在利益分配上找到平衡点&#xff0…
阅读更多...
基于Matlab特征提取与浅层神经网络的数字图像处理乳腺癌检测系统(GUI界面+训练代码+数据集)

基于Matlab特征提取与浅层神经网络的数字图像处理乳腺癌检测系统(GUI界面+训练代码+数据集)

本研究提出了一种结合数字图像处理技术、特征提取与浅层神经网络的创新癌症检测系统&#xff0c;旨在为医学图像的分析和早期癌症检测提供有效支持。系统主要处理癌症与正常组织的医学图像&#xff0c;通过灰度共生矩阵&#xff08;GLCM&#xff09;等方法&#xff0c;从图像中…
阅读更多...
Backblaze 2024 Q3硬盘故障质量报告解读

Backblaze 2024 Q3硬盘故障质量报告解读

作为一家在2021年在美国纳斯达克上市的云端备份公司&#xff0c;Backblaze一直保持着对外定期发布HDD和SSD的故障率稳定性质量报告&#xff0c;给大家提供了一份真实应用场景下的稳定性分析参考数据&#xff1a; 以往报告解读系列参考&#xff1a; Backblaze发布2024 Q2硬盘故障…
阅读更多...
河工oj第七周补题题解2024

河工oj第七周补题题解2024

A.GO LecturesⅠ—— Victory GO LecturesⅠ—— Victory - 问题 - 软件学院OJ 代码 统计 #include<bits/stdc.h> using namespace std;double b, w;int main() {for(int i 1; i < 19; i ) {for(int j 1; j < 19; j ) {char ch; cin >> ch;if(ch B) b …
阅读更多...
[ABC234A] Weird Function

[ABC234A] Weird Function

解题思路 这是一道模拟题…… 设置一个函数 &#xff0c;返回值为 。 最后答案就是 。 代码 记得开 long long ! #include<bits/stdc.h> using namespace std;long long t; long long f(long long x) {return x*xx*23; }int main() {cin>>t;cout<<f(f(f…
阅读更多...
蓝牙键鼠无法被电脑识别

蓝牙键鼠无法被电脑识别

起因是我的键鼠是三模的&#xff0c;但是我蓝牙模式我只用过几次&#xff0c;基本一直使用的是有线模式&#xff0c;最近突然要用无线连接&#xff0c;如果使用收发器就显得过于繁琐&#xff0c;还占用usb口&#xff0c;因此想用蓝牙连&#xff0c;但是由于 win10更新了英特尔…
阅读更多...
【C#设计模式(18)——中介者模式(Mediator Pattern)】

【C#设计模式(18)——中介者模式(Mediator Pattern)】

前言 中介者模式&#xff1a;是两者之间通过第三者来帮助传话。 代码 //抽象接收者public abstract class Receiver{protected Mediator mediator;protected Receiver(Mediator mediator){this.mediator mediator;}public abstract void SendMessage(string message);public a…
阅读更多...
动态计算加载图片

动态计算加载图片

学习啦 别名路径&#xff1a;①npm install path --save-dev②配置 // vite.config,js import { defineConfig } from vite import vue from vitejs/plugin-vueimport { viteStaticCopy } from vite-plugin-static-copy import path from path export default defineConfig({re…
阅读更多...
Java HashMap用法详解

Java HashMap用法详解

文章目录 一、定义二、核心方法三、实例演示3.1、方法示例3.2、get()方法注意点&#xff01; 一、定义 Java 的 HashMap 是 Java 集合框架中的一个非常重要的类&#xff0c;它实现了 Map 接口。HashMap基于哈希表的数据结构&#xff0c;允许使用键-值对存储数据。这种存储方式使…
阅读更多...
最新文章

Copyright @ 2022~2023