Cpp学习——list的模拟实现

 

目录

一,实现list所需要包含的三个类

二,三个类的实现

1.list_node

2.list类

 3.iterator_list类

三,功能实现

1.list类里的push_back()

  2.iterator类里的运算符重载

3,list类里面的功能函数

1.insert()

2.erase()函数

3.clear()与析构函数

4.拷贝构造函数赋值运算符重载

5.打印函数


一,实现list所需要包含的三个类

     因为list是一个带头双向循环链表。所以list的实现会比较的复杂一些。总得来说,实现一个双向带头循环链表需要构造三个类。1.list类,2.list_node类,3.list_iterator类。前两个类相信大家会比较的熟悉。第三个类大家会比较不熟悉,因为它是一个迭代器的类。也就是说这个类是迭代器的封装。它的实现很有价值,因为它能让我们在使用list时也可以像之前的数据结构一样方便。

二,三个类的实现

1.list_node

 这首先要实现的便是节点类。这个类是最容易实现的。这个类的作用便是给要产生的节点画一个图,定义一下这个节点的结构和类型。代码如下:

template<class T>//模板struct list_node{list_node(const T& val =T()//匿名对象 )//构造函数起初始化的作用:val(val), prev(nullptr), next(nullptr){}T val;list_node<T>* prev;list_node<T>* next;};

现在你看到了,这个节点的结构便是这样。其实这与之前实现的那个带头双向循环链表的结构差不多。不过,在cpp中引入了模板的概念,所以这个节点便可以调用模板参数来进行泛化。

2.list类

list类的定义可太简单了。list的成员变量只有一个参数,便是_head。这是哨兵位的头节点。当然还有一个无参的构造函数和一个功能函数。代码如下:

template<class T>class list{ public:typedef list_node<T> Node;void empty()//初始化功能函数。{_head = new Node;_head->prev = _head;_head->next = _head;}list()//构造函数{empty();}private:Node* _head;};

当然,这里的list类也是要用模板来进行泛化的。

 3.iterator_list类

这个类就算是比较复杂的一个类了。因为迭代器要实现两种重载版本:1.普通版本。2.const版本。所以迭代器类的模板参数会有三个:

template <class T, class Ref, class ptr>

这三个模板参数会重载两种版本的三个参数:T对象,T&,T指针类型。在这个类里面也只有一个成员:_node。类型与list类里面的成员类型相同。该类代码如下:

template <class T, class Ref, class ptr>struct iterator_list{typedef list_node<T> Node;iterator_list(Node* node):_node(node){}Node* _node;};

三,功能实现

1.list类里的push_back()

首先来实现一个push_back()函数,这个函数的作用便是实现尾插数据。逻辑十分简单,代码如下:

void push_back(const T& val){Node* newnode = new Node(val);Node* tail = _head->prev;tail->next = newnode;newnode->prev = tail;newnode->next = _head;_head->prev = newnode;}

写完这个以后,我便想要通过显示list里的数据来验证答案,但是很显然,我们做不到。因为list是一个自定义的类。但是我们有办法,所以我们便可以通过iterator来达到这个目的。所以我们必须在iterator类里面实现几个运算符重载。

  2.iterator类里的运算符重载

首先先实先这三个运算符重载:1.*,2.++,3.!=

代码如下:

        Ref operator *()//Ref代表T&{return _node->val;}self operator++(){_node = _node->next;return *this;}bool operator!=(self& it){return _node != it._node;}

然后再在list类里面实现begin()与end()函数之后便可以实现范围for的使用了,end与begin代码如下:

       //实现两个版本的begin与enditerator begin(){return _head->next;}iterator end(){return _head;}const_iterator begin()const{return _head->next;}const_iterator end()const{return _head;}

在实现了上面的代码以后,为了让迭代器的功能更加全面,那我们再实现几个函数重载。再iterator_list里面的全部运算符重载如下:

       Ref operator *(){return _node->val;}self& operator++()//前置++{_node = _node->next;return *this;}self operator++(int)//后置++{Node* tmp(*this);_node = _node->next;return tmp;}self& operator --()//前置--{_node = _node->prev;return *this;}self operator--(int)//后置--{Node* tmp(*this);_node = _node->prev;return tmp;}bool operator!=(const self& it)//若用引用便要加上const{return _node != it._node;}bool operator==(self& it){return _node == it._node;}self& operator+(int n){while (n){_node = _node->next;n--;}return *this;}ptr operator->()//箭头解引用{return &_node->val;}

在实现了这些运算符重载以后,list类里面的功能函数便好写了许多。

3,list类里面的功能函数

1.insert()

这个函数实现的功能便是在pos位置之前插入一个新的节点。这个pos的类型是迭代器类型。在list类里边的迭代器重定义为:

typedef iterator_list<T, T& ,T*> iterator;
typedef iterator_list<T, const T&, const T*> const_iterator;

我们只需要关注第一个迭代器即可,因为第二个迭代器修饰的对象是不可以修改的。所以insert的实现代码如下:

	iterator insert(iterator pos, const T& x)//在pos位置之前插入新节点{Node* newnode = new Node(x);Node* prev = pos._node->prev;prev->next = newnode;newnode->prev = prev;newnode->next = pos._node;pos._node->prev = newnode;return pos._node->prev;//防止迭代器失效,所以返回pos的前一个位置}

检验一下,检验代码如下:

void test_list2(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);for (auto e : l1){cout << e << " ";}cout << endl;l1.insert(l1.begin(), 9);l1.insert(l1.end(), 99);for (auto e : l1){cout << e << " ";}cout << endl;}

结果:正确

 在实现了insert()函数以后便可以复用实现push_back()与push_front()。代码如下:

        void push_back(const T& val){insert(begin(), val);}void push_front(const T& val){insert(end(), val);}

2.erase()函数

erase()函数实现的功能便是传入一个位置,然后将该位置上的节点删除掉。代码实现如下:

       iterator erase(iterator pos){Node* prev = pos._node->prev;Node* next = pos._node->next;Node* cur = pos._node;delete cur;prev->next = next;next->prev = prev;return iterator(next);//返回新的迭代器}

复用erase实现尾删与头删,代码如下:

​void pop_back(){erase(--end());//尾巴是--end()的位置}void pop_front(){erase(begin());}​

实验代码:

void test_list3(){list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);for (auto e : l1){cout << e << " ";}cout << endl;l1.insert(l1.begin(), 9);l1.insert(l1.end(), 99);for (auto e : l1){cout << e << " ";}cout << endl;l1.pop_back();l1.pop_front();for (auto e : l1){cout << e << " ";}cout << endl;}

结果:正确

3.clear()与析构函数

实现了erase()函数以后再接再厉,接着复用实现clear函数,代码如下:

        void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase()每次都会返回下一个位置}}

从上面代码的逻辑便可以看出clear()函数是不会删除掉头节点的。但是析构函数需要。于是复用clear()函数后析构函数代码如下:

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

4.拷贝构造函数赋值运算符重载

拷贝构造函数实现过程大概分三步,首先new出来一个空间。然后再复用push_back()函数将要赋值的数据拷贝到新节点内。实现代码如下:

	list(const list<T>& l1){empty();for (auto e : l1){push_back(e);}}

实现了拷贝构造以后,按照惯例,赋值也要被安排上了。赋值运算符重载实现代码如下:

     list<T>& operator =( list<T>& l1){if (this!= &l1){clear();for (auto e : l1){push_back(e);}}return *this;}

这是一个传统写法的运算符重载。如果想要更加精简可以写成现代写法,代码如下:

        void swap( list<T>& l1)//别加const{std::swap(_head, l1._head);//记得这个swap是std里面的swap}list<T>& operator=(list<T> l1){if (this != &l1){swap(l1);}return *this;}

5.打印函数

在这里,我们每次打印一个list对象时会很麻烦,每次都要用范围for来实现打印的功能。为了偷懒,我就想实现一个打印函数print来实现打印功能。实现代码如下:

template<class T>void print(list<T>& l1){typename list<T>::iterator it = l1.begin();//这里要用typename为前缀来告诉编译器等list<T>实例化以后再来执行这条语句for (auto e : l1){cout << e << " ";}cout << endl;}

但是上面的代码针对的类型时list类的泛型,如果想要实现能加载更多容器的print()函数那就得改一下类型,改为如下代码:

template <class Contains>void print(Contains& l1){typename Contains::iterator it = l1.begin();for (auto e : l1){cout << e << " ";}cout << endl;}

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

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

相关文章

2023国赛数学建模思路 - 案例:FPTree-频繁模式树算法

文章目录 算法介绍FP树表示法构建FP树实现代码 建模资料 ## 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 算法介绍 FP-Tree算法全称是FrequentPattern Tree算法&#xff0c;就是频繁模式树算法&#xff0c…

Linux常用命令——dig命令

在线Linux命令查询工具 dig 域名查询工具 补充说明 dig命令是常用的域名查询工具&#xff0c;可以用来测试域名系统工作是否正常。 语法 dig(选项)(参数)选项 <服务器地址>&#xff1a;指定进行域名解析的域名服务器&#xff1b; -b<ip地址>&#xff1a;当主…

Log4net在.Net Winform项目中的使用

引言&#xff1a; Log4net是一个流行的日志记录工具&#xff0c;可以帮助开发人员在应用程序中实现高效的日志记录。本文将提供一个详细的分步骤示例&#xff0c;来帮助您在.Net Winform项目中使用Log4net。 目录 一、安装Log4net二、配置Log4net三、在项目中使用Log4net四、初…

深入探索:Kali Linux 网络安全之旅

目录 前言 访问官方网站 导航到下载页面 启动后界面操作 前言 "Kali" 可能指的是 Kali Linux&#xff0c;它是一种基于 Debian 的 Linux 发行版&#xff0c;专门用于渗透测试、网络安全评估、数字取证和相关的安全任务。Kali Linux 旨在提供一系列用于测试网络和…

uniapp的uview-plus组件库的导入

uniapp的vue3中使用uview-plus组件库。在插件市场中找到该组件并点击如下所示绿色按钮&#xff0c;弹出弹窗选择要导入的项目后&#xff0c;就会在uni_modules文件中生成如下文件内容 关于插件的下载区别&#xff0c;可参考&#xff1a;https://uniapp.dcloud.net.cn/compone…

回归预测 | MATLAB实现SSA-SVM麻雀搜索算法优化支持向量机多输入单输出回归预测(多指标,多图)

回归预测 | MATLAB实现SSA-SVM麻雀搜索算法优化支持向量机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现SSA-SVM麻雀搜索算法优化支持向量机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09;效果一览基…

(三)行为型模式:3、解释器模式(Interpreter Pattern)(C++示例)

目录 1、解释器模式&#xff08;Interpreter Pattern&#xff09;含义 2、解释器模式的UML图学习 3、解释器模式的应用场景 4、解释器模式的优缺点 5、C实现解释器模式的实例 1、解释器模式&#xff08;Interpreter Pattern&#xff09;含义 解释器模式&#xff08;Interp…

《TCP IP网络编程》第二十四章

第 24 章 制作 HTTP 服务器端 24.1 HTTP 概要 本章将编写 HTTP&#xff08;HyperText Transfer Protocol&#xff0c;超文本传输协议&#xff09;服务器端&#xff0c;即 Web 服务器端。 理解 Web 服务器端&#xff1a; web服务器端就是要基于 HTTP 协议&#xff0c;将网页对…

C语言刷题指南(二)

&#x1f4d9;作者简介&#xff1a; 清水加冰&#xff0c;目前大二在读&#xff0c;正在学习C/C、Python、操作系统、数据库等。 &#x1f4d8;相关专栏&#xff1a;C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。 欢迎点赞 &#x1f44d…

设计模式 : 单例模式笔记

文章目录 一.单例模式二.单例模式的两种实现方式饿汉模式懒汉模式 一.单例模式 一个类只能创建一个对象,这样的类的设计模式就称为单例模式,该模式保证系统中该类只能有一个实例(并且父子进程共享),一个很典型的单例类就是CSTL的内存池C单例模式的基本设计思路: 私有化构造函数…

vector

1.vector的介绍及使用 vector的文档介绍 1. vector是表示可变大小数组的序列容器。 2. 就像数组一样&#xff0c;vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问&#xff0c;和数组一样高效。但是又不像数组&#xff0c;它的大小是可…

2023-08-19 LeetCode每日一题(两整数相加)

2023-08-19每日一题 一、题目编号 2235. 两整数相加二、题目链接 点击跳转到题目位置 三、题目描述 给你两个整数 num1 和 num2&#xff0c;返回这两个整数的和。 示例 1&#xff1a; 示例 2&#xff1a; 提示&#xff1a; -100 < num1, num2 < 100 四、解题代…

Python 的下一代 HTTP 客户端

迷途小书童 读完需要 9分钟 速读仅需 3 分钟 1 环境 windows 10 64bitpython 3.8httpx 0.23.0 2 简介 之前我们介绍过使用 requests ( https://xugaoxiang.com/2020/11/28/python-module-requests/ ) 来进行 http 操作&#xff0c;本篇介绍另一个功能非常类似的第三方库 httpx&…

板卡常用前端 数据表操作

两年前写的&#xff0c;现在看,有点想吐, 数据操作表,调试设备用 采用外挂的方法&#xff0c;以前设备的接口命令,简易&#xff0c;换个UI展示很容易 自己写着玩的,公司部分产品再用,前端展示,不涉密 index.html <!doctype html> <html><head><meta chars…

改变C++中私有变量成员的值

1、没有引用的情况&#xff1a; #include <iostream> #include <queue> using namespace std; class Person { public:queue<int>que; public:queue<int> getQueue(){return que;}void push(int a){que.push(a);}void pop(){que.pop();} };int main()…

自学C#,要懂得善用MSDN

很多初学者学习编程&#xff0c;都会通过看别人写的教程、或者录制的视频&#xff0c;来学习。 这是一个非常好的途径&#xff0c;因为这个是非常高效的。 但是这样&#xff0c;存在两个问题&#xff1a; 1、教程不够全面&#xff1a;任何再好的教程&#xff0c;都无法囊括所…

Gateway网关路由以及predicates用法(项目中使用场景)

1.Gatewaynacos整合微服务 服务注册在nacos上&#xff0c;通过Gateway路由网关配置统一路由访问 这里主要通过yml方式说明&#xff1a; route: config: #type:database nacos yml data-type: yml group: DEFAULT_GROUP data-id: jeecg-gateway-router 配置路由&#xff1a;…

USB隔离器电路分析,SA8338矽塔sytatek电机驱动,源特科技VPS8701,开关电源,电源 大师

一、 USB隔离器电路分析 进行usb隔离可以使用USB隔离模块 ADUM3160 ADUM4160 注意&#xff1a;B0505S 最大带载0.16A&#xff0c;副边需要带载能力需要改变方案 比如移动硬盘至少需要0.5A 用充电宝、18650、设计5V1A输出电源 二、 1A隔离电压方案

AgentBench——AI智能体基准测试和排行榜

如果您有兴趣了解有关如何对AI大型语言模型或LLM进行基准测试的更多信息,那么一种新的基准测试工具Agent Bench已成为游戏规则的改变者。这个创新工具经过精心设计,将大型语言模型列为代理,对其性能进行全面评估。该工具的首次亮相已经在AI社区掀起了波澜,揭示了ChatGPT-4目…