C++从入门到起飞之——list模拟实现 全方位剖析!

​ ​

 

🌈个人主页:秋风起,再归来~
🔥系列专栏:C++从入门到起飞          
🔖克心守己,律己则安

目录

​ ​1、list的整体框架

2、list迭代器

>整体分析

>整体框架

 >成员函数

>运算符->重载 

>const迭代器

>迭代器类的一些问题的思考

3、成员函数

4、完结散花


1、list的整体框架


list就是我们所熟悉的数据结构链表,通过查看源码以及我们对链表的了解我们知道在类模版list中的成员变量一个是指向有效链表的哨兵卫头结点_head,另一个是记录有效元素个数的_size,而链表中的有效元素的存储地址空间不是连续的,所以并没有容量capacity的概念!
而我们又知道链表是由一个又一个的节点组成的,而我们要实现的是带头双向循环链表,所以每个节点里面都存储着数据val、前驱指针pre、后继指针next!
所以我们可以先大概写出list的整体框架!

//链表的节点
template<class T>
struct list_node
{list_node(const T& val = T()):data(val),pre(nullptr),next(nullptr){}T data;//数据list_node<T>* pre;//前驱指针list_node<T>* next;//后继指针
};
/双向循环带头链表
template<class T>
class list
{
public:typedef list_node<T> node;//给节点取别名//成员函数//………………private:node* _head=nullptr;//带哨兵卫的头结点size_t _size = 0;//记录节点个数
};

2、list迭代器


>整体分析


为了后续方便遍历容器打印结果检测我们程序的正确性,我们先来实现list的迭代器!
我们知道我们之前模拟的string和vector的迭代器都是原生的指针,那是因为他们底层结构的优越性允许他们这样实现。但是,list如果我们还是使用原生指针的话就完全做不到迭代器的效果,因为我们对节点指针*取到的是节点本身,而不是节点里面的数据,对节点++或--,因为链表不是连续的物理空间,所以我们并不能拿到前一个或后一个的迭代器反而让迭代器成了野指针!
那怎么办呢!我们可以对list的迭代器进行封装,而迭代器的底层原理还是使用节点的指针!只不过,我们要在迭代器里面对*、++、--、==、!= 等操作进行运算符重载!


>整体框架


那我们先实现迭代器的整体框架!
因为该迭代器只是给list使用,外面根本不知道,所以我们干脆用struct定义,将所有成员公开!

//链表的迭代器
template<class T>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_iterator<T> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//成员函数//………………};

 >成员函数

//返回T&
T& operator*()
{return it->data;
}//(前置++)++it
self& operator++()
{it = it->next;return *this;
}//(前置--)--it
self& operator--()
{it = it->pre;return *this;
}//(后置++) it++
self operator++(int) 
{self tmp(*this);it = it->next;return tmp;//一定不能用引用接收,不然会有野指针!
}//(后置--) it--
self operator--(int) 
{self tmp(*this);it = it->pre;return tmp;
}//比较迭代器里面的it指针相不相等
bool operator==(const self& comp)
{return it==comp.it;
}
bool operator!=(const self& comp)
{return it!=comp.it;
}


>运算符->重载 

如果节点中存储的是自定义类型Pos(坐标类)

struct Pos
{int _row;int _col;Pos(int row, int col):_row(row), _col(col){}
};

​如果我们想要方便访问坐标,那我们可以重载->操作符

T* operator->()
{return &(it->data);
}
list<Pos> lt;
lt.push_back(Pos(1, 1)); 
lt.push_back(Pos(2, 2));
lt.push_back(Pos(3, 3));
lt.push_back(Pos(4, 4));auto it = lt.begin();
while (it != lt.end())
{cout << it->_col << " " << it->_row << endl;++it;
}
​

上面的->实际上的完整调用是下面的模式

auto it = lt.begin();
while (it != lt.end())
{cout << it.operator->()->_row << " " << it.operator->()->_col << endl;++it;
}

it先调用重载的->,返回Pos类型的原生指针指针后再调用原始指针的->。而为了方便与可读性,编译器允许我们省略一个->调用! 


>const迭代器

我们在上面只实现了一个普通的迭代器,如果我们要再实现一个const的常量迭代器,我们是不是就要再自己实现一个迭代器类呢?雀氏行的通!

//链表的迭代器
template<class T>
struct list_const_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_const_iterator<T> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_const_iterator(node* node):it(node){}//成员函数//………………};

不过,在内部的成员函数实现中,只有一些函数的返回值是不同的,而函数体的是一样的!想这样俩个相似度高度集中的类,我们就可以使用类模版的方法将俩个类进行合并!
而我们具体的做法则是增加模版参数!

合并后的完整代码:

//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef     list_iterator<T, ref, ptr> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//返回T*ptr operator->(){return &(it->data);}//返回T&ref operator*(){return it->data;}//(前置++)++itself& operator++(){it = it->next;return *this;}/*self operator++(){it = it->next;return it;}*///(前置--)--itself& operator--(){it = it->pre;return *this;}/*self operator--(){it = it->pre;return it;}*///(后置++) it++self operator++(int) {self tmp(*this);it = it->next;return tmp;//一定不能用引用接收,不然会有野指针!}//(后置--) it--self operator--(int) {self tmp(*this);it = it->pre;return tmp;}//比较迭代器里面的it指针相不相等bool operator==(const self& comp){return it==comp.it;}bool operator!=(const self& comp){return it!=comp.it;}};

>迭代器类的一些问题的思考

(1) 类中是否需要写析构函数?
这个迭代器类不要写析构函数,因为这里的节点不是迭代器的,是链表的,不用把它释放。我们使用begin,end返回节点给迭代器,是借助迭代器修改,访问数据,所以我们不需要释放。
(2) 类中是否需要写拷贝构造进行深拷贝和写赋值拷贝?
这里也不需要写拷贝构造进行深拷贝,因为这里要的就是浅拷贝。begin返回了第一个节点的迭代器给it,这里就是用默认生成的拷贝构造,浅拷贝给it,那这两个迭代器就指向同一个节点,所以这里用默认的拷贝构造和赋值拷贝就可以了。

3、成员函数

对于list的常见成员函数的实现我们已近轻车熟路了!这里就直接给源码了!

//链表的节点
template<class T>
struct list_node
{list_node(const T& val = T()):data(val),pre(nullptr),next(nullptr){}T data;//数据list_node<T>* pre;//前驱指针list_node<T>* next;//后继指针
};//链表的迭代器
template<class T, class ref,class ptr>
struct list_iterator
{typedef  list_node<T> node;//给节点取别名typedef	 list_iterator<T, ref, ptr> self;//给自己取别名node* it;//链表中的迭代器其实就是一个节点的指针//只不过其访问和迭代操作要用一个类封装起来list_iterator(node* node):it(node){}//返回T*ptr operator->(){return &(it->data);}//返回T&ref operator*(){return it->data;}//(前置++)++itself& operator++(){it = it->next;return *this;}/*self operator++(){it = it->next;return it;}*///(前置--)--itself& operator--(){it = it->pre;return *this;}/*self operator--(){it = it->pre;return it;}*///(后置++) it++self operator++(int) {self tmp(*this);it = it->next;return tmp;//一定不能用引用接收,不然会有野指针!}//(后置--) it--self operator--(int) {self tmp(*this);it = it->pre;return tmp;}//比较迭代器里面的it指针相不相等bool operator==(const self& comp){return it==comp.it;}bool operator!=(const self& comp){return it!=comp.it;}};//双向循环带头链表
template<class T>
class list
{
public:typedef list_node<T> node;//给节点取别名typedef list_iterator<T, T&, T*> iterator;//普通迭代器typedef list_iterator<T, const T&, const T*> const_iterator;//常量迭代器//sizesize_t size() const{return _size;}//beginiterator begin(){return _head->next;}//enditerator end(){return _head;}//cbeginconst_iterator begin() const{return _head->next;}//cendconst_iterator end() const{return _head;}//clearvoid clear(){auto it = begin();while (it!= end()){it=erase(it);}}//swapvoid swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//emptybool empty(){return _size == 0;}//空初始化void emptyInit(){_head = new node;_head->next = _head->pre = _head;_size = 0;}//无参的默认构造list(){emptyInit();}//拷贝构造list(const list<T>& lt){emptyInit();//先空参构造_headfor (auto& e : lt){push_back(e);}/*auto it = lt.begin();while (it != lt.end()){push_back(*it);++it;}*/}//赋值运算符重载list<T>& operator=(list<T> tmp){swap(tmp);return *this;}//析构~list(){clear();delete _head;_head = nullptr;}//insertiterator insert(iterator pos, const T& val){node* newNode = new node(val);node* cur = pos.it;node* pre = cur->pre;newNode->next = cur;newNode->pre = pre;pre->next = newNode;cur->pre = newNode;_size++;return newNode;}//push_front(头插)void push_front(const T& val){insert(begin(), val);}//push_back(尾插)void push_back(const T& val)//传引用减少拷贝构造{/*node* newNode = new node(val);node* tail = _head->pre;tail->next = newNode;newNode->next = _head;newNode->pre = tail;_head->pre = newNode;++_size;*/insert(end(), val);}//eraseiterator erase(iterator pos){assert(pos != end());node* next = pos.it->next;node* pre = pos.it->pre;pre->next = next;next->pre = pre;delete pos.it;pos.it = nullptr;_size--;return next;}//pop_front(头删)void pop_front(){erase(begin());}//pop_back(尾删)void pop_back(){erase(--end());}private:node* _head=nullptr;//带哨兵卫的头结点size_t _size = 0;//记录节点个数
};

4、完结散花

好了,这期的分享到这里就结束了~

如果这篇博客对你有帮助的话,可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话,可以点点关注,避免找不到我了呢~

我们下期不见不散~~

​​​​​​

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

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

相关文章

windows安全软件之火绒杀毒的密码忘记后处理

一、问题描述 某次&#xff0c;想升级系统补丁&#xff0c;但多次尝试后都失败&#xff0c;排查杀毒软件影响过程中&#xff0c;发现火绒杀毒配置了密码保护&#xff0c;但因时间太久&#xff0c;密码已无从考证&#xff0c;那我们应该怎样处理这种情况呢&#xff1f; 二、处…

开发知识付费小程序的秘诀:从设计到上线一步到位

在移动互联网时代&#xff0c;知识付费小程序成为内容创作者和教育者的热门选择。它不仅降低了用户的使用门槛&#xff0c;还具备高效传播的优势。本文将带你一步步了解如何开发一个功能齐全的知识付费小程序&#xff0c;从设计规划到技术实现&#xff0c;最后顺利上线。 一、…

QT接收并解析GPS模块串口数据

目录 一、QT读取串口数据 二、解析数据 目标&#xff1a; 使用QT&#xff0c;读取gps模块的串口数据&#xff0c;并解析其中的经纬高数据&#xff0c;然后进行处理 一、QT读取串口数据 变量定义 QSerialPort *serial; QSerialPortInfo SerialPortInfo; QByteArray lineData…

RKNPU2从入门到实践 --- 【10】RKNPU2零拷贝API实现RKNN模型在RK3588开发板上的部署

目录 一、为什么叫零拷贝API&#xff1f; 二、零拷贝API执行流程&#xff08;代码解读&#xff09; 2.1 前奏工作 2.2 main.cc文件的编写&#xff08;代码的编写&#xff09; 2.2.1 第一步&#xff1a;rknn_init接口创建rknn_context对象、加载RKNN模型 2.2.2 第二步…

C# 传值参数

传值参数 1.值类型 值参数创建变量的副本&#xff1a;当传递值参数时&#xff0c;实际上是创建了原始变量的一个副本&#xff0c;然后将副本传递给方法。对值参数的操作永远不影响变量的值&#xff1a;由于是复制了一份新的副本&#xff0c;所以对副本进行操作不会影响原始变量…

python,json数据格式,pyecharts模块,pycharm中安装pyecharts

json数据格式 JSON是一种轻量级的数据交互格式 可以按照JSON指定的格式去组织和封装数据 JSON本质上是一个带有特定格式的字符串 主要功能&#xff1a; json就是一种在各个编程语言中流通的数据格式&#xff0c;负责不同编程语言中的数据传递和交互. 类似于&#xff1a; 国…

普元Devops-在云主机上拉取harbor的docker镜像并部署

1 前言 本文讲解如何从普元Devops配置构建&#xff0c;从而实现在云主机上拉取Docker镜像&#xff0c;然后运行Docker容器&#xff0c;实现云主机的Docker部署。 2 主要步骤说明 首先&#xff0c;我们有一个Devops服务器&#xff0c;还有一个云主机服务器&#xff0c;还有一个…

【微信小程序】如何触发按钮事件,例如调起微信客服

需求 实现一个如下图的效果, 点击客服按钮, 调起微信客服功能, 需要和button组合使用 效果图 实现思路 客服只能通过button按钮调起, 所以我们需要写一个button按钮, open-type“contact”, 然后把它隐藏起来。给客服图标加一个label, 设置for“btnId”, 这样点击图片就会触…

在ElementUI项目中集成iconfont图标库

在前端项目开发中经常会遇到使用的组件库提供的ICON图标不够用的情况。最常见的解决方案无非就是把设计图的图标切图引入到项目中。还有就是使用svg图标&#xff0c;封装一个渲染组件在项目里面直接引入这个组件。 本文将介绍另一种方法&#xff0c;即集成iconfont图标库的图标…

养老小程序源码家政服务小程序开发方案

预约上门养老小程序&#xff0c;是php开发预约&#xff0c;前端是uniapp&#xff0c;有开发好的小程序案例&#xff0c;可源码&#xff0c;也可以二开&#xff0c;也可以定制开发。 一 用户端&#xff1a;服务分类、服务内容详情介绍、在线下单支付&#xff0c;管理我的订单。…

前缀和差分【算法 13】

在算法领域中&#xff0c;前缀和与差分数组是两种高效处理区间问题的技术。它们能在特定问题场景下将时间复杂度从 (O(n)) 降到 (O(1))&#xff0c;适用于频繁的区间查询与修改操作。本文将简要介绍这两种技术及其应用。 1. 前缀和 (Prefix Sum) 前缀和是指一个数组的第 (i)…

利用TOPSIS算法进行生长素和施肥量对农作物各指标影响力的分析

文章目录 1 摘要2 问题的重述1&#xff0e; 背景介绍2&#xff0e; 问题的产生及进行数学建模的意义 3 TOPSIS算法1. TOPSIS算法介绍2. TOPSIS算法使用步骤 4 问题的分析1. 对问题一的分析及解答2. 对问题二的分析及解答3. 对问题三的分析及解答 5 模型的改进1. 验证2.模型改进…

整理了几十家高频面试题,让你避坑软件测试公司面试的套路,收藏收藏刷起来...

俗话说金九银十&#xff0c;就要到找工作的高峰期了 年前找我拿面试题的姐妹已经收到offer了&#xff0c;准备换工作的抓紧背起来哦 去面试的&#xff0c;一定要提前了解一下&#xff0c;这些面试题。可能不是特别全面&#xff0c;但是已经够用了。你们面试时还遇到了哪些奇葩…

Redis中的数据类型及应用场景(面试版)

五种常用数据类型介绍 Redis中存储的都是key-value对结构的数据&#xff0c;其中key都是字符串类型&#xff0c;value有5种常用的数据类型&#xff1a; 字符串 string 哈希 hash 列表 list 集合 set 有序集合 sorted set / zset 各种数据类型特点 解释说明&#xff1a; …

【C++】vector(下)--上篇

个人主页~ vector&#xff08;上&#xff09;~ vector 二、vector的模拟实现1、了解组成2、vector.h&#xff08;1&#xff09;为什么有了size_t参数的vector构造函数还要再写一个int参数的重载vector构造函数&#xff08;2&#xff09;为什么reserve不用memcpy&#xff08;3&…

DAMA数据管理知识体系(第3章 数据治理)

课本内容 3.1 引言 数据治理&#xff08;Data Governance&#xff0c;DG&#xff09;的定义是在管理数据资产过程中行使权力和管控&#xff0c;包括计划、监控和实施。数据治理项目的范围和焦点 战略 定义、交流和驱动数据战略和数据治理战略的执行制度 设置与数据、元数据管理…

MySQL编译安装

1.源码包地址 2.编译/安装 3.设置环境变量 4.初始化/登录 地址: MYSQL源码包下载 右键复制链接 使用wget 下载到/usr/local/src下 再使用rpm –ivh 安装 --这个时候跳转到 cd /root/rpmbuild/SOURCES 使用ll查看有什么东西 yum -y install gcc gcc-c ncurses ncurses-d…

Tensorflow实现深度学习8:猫狗识别

本文为为&#x1f517;365天深度学习训练营内部文章 原作者&#xff1a;K同学啊 一 导入数据 import matplotlib.pyplot as plt import tensorflow as tf # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 plt.rcParams[axes.unicode_minus] Fals…

本地部署Xinference实现智能体推理工作流(二)

第二篇章 Dify接入 Xinference 部署的本地模型 1. 安装Dify 克隆 Dify 源代码至本地。 git clone https://github.com/langgenius/dify.git 2. 启动Dify 进入 Dify 源代码的 docker 目录&#xff0c;执行一键启动命令&#xff1a; cd dify/docker cp .env.example .env d…

Linux学习(15)-网络编程:滑动窗口、拥塞控制、udp

本节学习内容 1.滑动窗口&#xff08;1.滑动窗口的作用2.如果如果接收端填充的接收窗口为0&#xff0c;发送端接下来怎么处理3.糊涂窗口综合征4.tcp中nagle算法是什么&#xff09; 2.拥塞控制 3.udp协议特点及编程流程 本节可能会用到的指令 ifconfig查看自己的ip地址 pi…