【C++】模拟list
list的模拟真的很震撼,第一次学习时给我幼小的心灵留下了极大地冲击
接下来我们一起看看list模拟究竟是怎样一回事
目录
- 节点的封装:
- list类的实现:
- 私有成员变量:
- 构造函数:
- push_back && pop_back:
- 迭代器类的实现:
- begin && end(不可被const对象调用):
- begin && end(可被const对象调用):
- 继续list类的实现:
- insert && erase:
- 带参构造函数:
- 迭代器区间构造:
- 拷贝构造:
- 赋值运算符重载:
- 析构函数:
节点的封装:
我们在之前没用CPP实现list时,是定义了一个struct node的结构体
typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;
那我们现在当然也需要定义一个结构体
template<class T>struct list_node{T _val;list_node<T>* _prev;list_node<T>* _next;list_node(const T& data = T()){_val = data;_prev = _next = nullptr;}};
但是要写一个默认构造函数,因为未来我们会new
节点,就像我们在C阶段malloc
的一样。
那么为什么要使用sruct
而不是class
呢,因为我们希望这个节点结构体
有了他的地址可以直接访问成员变量,而设置为class
时除非进行public
否则不是很方便。
list类的实现:
私有成员变量:
由于我们会使用模版,因此在写类型是比较不方便,于是可以define一下typedef list_node<T> node;
private:node* _head;
注意:我们的stl库中的list是有哨兵位的,故私有成员设为_head。
构造函数:
list(){empty_init();}
为什么要先写个空初始化呢?因为后边的成员函数有一些也需要进行初始化,因此写成一个函数进行复用。
void empty_init(){_head = new node();_head->_next = _head;_head->_prev = _head;}
push_back && pop_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;}
pop_back:
void pop_back(){node* prev = (it._node)->_prev;node* next = (it._node)->_next;delete it._node;prev->_next = next;next->_prev = prev;}
有了节点之后我们怎样进行访问?
没错就是使用迭代器。
迭代器类的实现:
我们的list的迭代器为什么要封装成一个类?
因为在vector那种底层虚拟地址是连续的,当我们有一个指定位置的指针,直接对指针进行++
、--
、*
…都是没问题的,因为我们的迭代器本质就是一个模仿指针行为的一个东西
但是我们的链表节点
的底层并不是连续的,是一个一个new
出来的,并不能保证底层虚拟地址的连续性,所以要对链表节点的指针
进行封装
,进行重载操作符进而可以模拟指针的行为!!
template<class T>struct list_iterator{typedef list_node<T> node;typedef list_iterator<T> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}T& operator*(){return _node->_val;}};
对需要进行相关运算符重载的都进行一遍。
如此我们一个最简单的list框架就已经搭建成功了。
不要忘记在list类中进行将list_iterator
typedef为iterator
,因为这样我们的代码才具有跨平台性。
同时要在list类中写上begin与end这两个获取迭代器的函数。
begin && end(不可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}
我们为啥可以这么写?_head的类型不是node*
?原生的类型显示为list_node<T>*
,可是迭代器的类型是list_iterator ,完全不一样啊,这是因为我们C++支持单参数的构造函数隐式类型转换,直接对_head这个指针利用iterator的构造函数构造成迭代器
但是我们这个list目前对于const对象是很难遍历的,所以当然要实现const迭代器。
我们有两种方式,第一种是将普通迭代器的复制一份改为const迭代器,对*
这个操作符重载返回const对象,这样就不怕const对象被修改了。
但是这样的代码是在是冗余,不要忘记我们还有模版的存在!
我们如果将迭代器的模版参数多设计一个T的引用
,在list类中将这个迭代器类进行typedef
!
typedef list_iterator<T, T&> iterator;
typedef list_iterator<T, const T&> const_iterator;
那么我们这样就可以很好解决当前代码重复度高,比较冗余的缺点。
template<class T, class Ref>//多传递的模版参数struct list_iterator{typedef list_node<T> node;typedef list_iterator<T, Ref> self;node* _node;list_iterator(node* Node){_node = Node;}self& operator++(){_node = _node->_next;return *this;}self operator--(int){self tmp = *this;_node = _node->_prev;return tmp;}self& operator--(){_node = _node->_prev;return *this;}self operator++(int){self tmp = *this;_node = _node->_next;return tmp;}bool operator!=(self it){return it._node != _node;}Ref operator*(){return _node->_val;}};
这样就可以根据是否为const对象而生成不同的迭代器类了!
begin && end(可被const对象调用):
iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}
继续list类的实现:
有了迭代器我们就可以写insert,erase等等函数,进而对push_back/front…等等函数的复用:
insert && erase:
void insert(iterator pos, const T& val){node* newnode = new node(val);node* prev = pos._node->_prev;node* cur = pos._node;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}iterator erase(iterator pos){node* prev = pos._node->_prev;node* next = pos._node->_next;delete pos._node;prev->_next = next;next->_prev = prev;return next;}
带参构造函数:
list(int n, const T& val = T()){empty_init();while (n--){push_back(val);}}
直接复用push_back
迭代器区间构造:
template <class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);first++;}}
拷贝构造:
list(const list<T>& lt){empty_init();list<T>::const_iterator it = lt.begin();while (it != lt.end()){push_back(*it);it++;}}
赋值运算符重载:
void swap(list<T> lt){std::swap(_head, lt._head);}list<T>& operator=(list<T> lt){swap(lt);return *this;}
析构函数:
~list(){clear();delete _head;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}
由此list类就模拟完毕,如果有不明白的地方可以尽管来找博主
相关文章:
【C++】模拟list
list的模拟真的很震撼,第一次学习时给我幼小的心灵留下了极大地冲击 接下来我们一起看看list模拟究竟是怎样一回事 目录 节点的封装:list类的实现:私有成员变量:构造函数:push_back && pop_back: 迭代器类的实…...

SAP项目任务一览表
根据SAP Activate项目管理方法论的主要精神,浓缩到一些主要的团队和任务。 主要的团队有: 项目管理(办公室)Project Management(office):项目经理团队,包括项目办公室。负责项目整体运行和监控,项目办公室负责项目的…...
130个学术网站和26个科研工具
我们平时可以见到不少学术资源,但是很多信息里会有一些重叠网站、无效网站,导致我们虽然收藏了很多网址,但是却并不都能用,学妹特地整合了130个学术资源网站和26个科研工具,每一个都是亲自试过有效的,希望能…...

《一键搞定!揭秘微信公众号文章批量下载的终极神器》
大家好!今天我要给大家介绍一个超级好用的小工具,能帮你轻松批量下载微信公众号的文章,还不需要安装任何证书哦!无论你是学生还是普通爱好者,只要你想保存一些精彩的公众号内容,这个工具都能帮到你。 概览 …...

鸿蒙入门02-首次安装和配置
注:还没有安装编辑器( deveco studio )的小伙伴请看鸿蒙入门01-下载和安装-CSDN博客 首次安装配置 编辑器( deveco studio )安装完毕以后需要进入配置界面进行相关配置配置完毕以后才可以正常使用 环境配置…...

软件工程 考研复试常考知识点总结
软件工程 什么是软件工程,这门课讲的什么? 软件工程就是把软件的开发、运行、维护的各个阶段进行系统化和规范化的过程,也就是把工程化的方法运用在软件技术之中,以构建和维护高质量的软件。 进一步,什么是工程化思想…...

Docker+Uwsgi+Nginx部署Django项目保姆式教程
之前,我和大家分享了在docker中使用uwsgi部署django项目的教程。这次,为大家带来的是使用DockerUwsgiNginx部署Django项目。废话不多说,我们开干。 步骤1:使用命令创建一个django项目 我这里python版本使用的是3.9.x 首先&#…...

[openGL] 高级光照-Gamma矫正
目录 一 Gamma是什么? 二 感知光度和物理光度 2.1 与Gamma的关系 2.3 存在问题和弊端? 三 Gamma矫正(逆Gamma) 3.1 Gamma矫正的两种方法 3.2 sRGB空间 3.3 重复校正 3.3.1 在着色器中处理重复校正 3.3.2 在加载纹理时就重复校正 3.3.3 校正前后效果 本章节Qt源码点…...

Prometheus+Grafana监控K8S集群(基于K8S环境部署)
目录 一.环境信息二.部署提前工作三.部署Prometheus监控系统四.部署Node_exporter组件五.部署Kube_state_metrics组件六.部署Grafana可视化平台七.Grafana接入Prometheus数据八.Grafana添加监控模板九.拓展 一.环境信息 1.服务器及k8s版本信息 IP地址主机名称角色版本192.168…...

[opencv]VideoWriter写出fourcc格式
fourcc支持的格式 fourcc全名Four-Character Codes,四字符代码,该编码由四个字符组成 cv2.VideoWriter_fourcc(O,O,O,O) cv2.VideoWriter_fourcc(*OOOO) 通常写法有上述两种形式,O代表一个字符,通常有 支持avi格式的有&#…...
软考中级网络工程师-网络技术
下列命令片段含义是( )。 system-view [HUAWEI] observe-port 1 interface gigabitethernet 0/0/1 [HUAWEI] interface gigabitethernet 0/0/2 [HUAWEI-GigabitEthernet0/0/2] port-mirroring to observe-port 1 inbound A 配置端口镜像 B 配置链路聚合 C 配置逻辑接口 D 配置访…...
cmake基础教程(12)函数和宏用法
参考: https://cmake.org/cmake/help/latest/command/function.html https://cmake.org/cmake/help/latest/command/macro.html#command:macro 文章目录 函数宏在CMake中,宏(macro)和函数(function)命令用于封装重复的任务,这些任务可能分散在你的CMakeLists文件中。一…...

SQLite的PRAGMA 声明(二十三)
返回:SQLite—系列文章目录 上一篇:SQLite从出生到现在(发布历史记录)(二十二) 下一篇:用于 SQLite 的异步 I/O 模块(二十四) PRAGMA 语句是特定于 SQLite 的 SQL 扩…...
Qt 实战(1)Qt 概述
一、Qt概述 1、什么是Qt? Qt(官方发音 [kju:t],音同 cute)是一个跨平台的 C 开发库,主要用来开发图形用户界面(Graphical User Interface,GUI)程序,也可以开发不带界面的…...

【练习】二分查找
1、704 (1)题目描述 (2)代码实现 package com.hh.practice.leetcode.array.demo_02;public class BinarySearch_704 {public int search(int[] nums, int target) {int i 0,j nums.length -1;while (i < j){int mid (ij) &…...

FactoryTalk View 上位机画面版本升级,还原和备份
FactoryTalk View 上位机画面版本升级,还原和备份 1 归档文件(尾缀.apa)升级2 画面文件(尾缀.sed)升级3 提示“目标工程中包含旧的HMI标签报警,FT View 10.0是最后一个......” 解决方法1 归档文件(尾缀.apa)升级 案例是FTVIEW5.0升级到FT VIEW12,需要用FT VIEW 6过渡升…...

【微信小程序】分包
整个小程序所有分包大小不超过 20M(开通虚拟支付后的小游戏不超过30M) 单个分包/主包大小不能超过 2M在小程序启动时,默认会下载主包并启动主包内页面,当用户进入分包内某个页面时,客户端会把对应分包下载下来…...
Golang教程六(单元测试,反射,网络编程,部署)
目录 一、单元测试 单元测试 子测试 TestMain 二、反射 类型判断 通过反射获取值 通过反射修改值 结构体反射 利用tag修改结构体的某些值 调用结构体方法 orm的一个小案例 对反射的一些建议 三、网络编程 socket编程 websocket编程 四、部署 打包命令 交叉编译…...

mybatis进阶篇-执行CRUD操作-typeAliases别名-接口绑定
目录结构 1.创建数据表(book) # 创建book表 create table book(id int auto_increment primary key,name varchar(255) ,price double ,num int );2.mybatis.xml配置文件 <?xml version"1.0" encoding"UTF-8" ?> <!DOC…...
C#面:泛型的主要约束和次要约束是什么
在 C# 中,泛型的约束是用来限制泛型类型参数的行为和能力的。 主要约束和次要约束是两种不同的约束方式。 主要约束(Primary Constraint): 主要约束指定了泛型类型参数必须满足的最基本的条件,它可以是一个类、一个接…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...
Java 8 Stream API 入门到实践详解
一、告别 for 循环! 传统痛点: Java 8 之前,集合操作离不开冗长的 for 循环和匿名类。例如,过滤列表中的偶数: List<Integer> list Arrays.asList(1, 2, 3, 4, 5); List<Integer> evens new ArrayList…...
Objective-C常用命名规范总结
【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名(Class Name)2.协议名(Protocol Name)3.方法名(Method Name)4.属性名(Property Name)5.局部变量/实例变量(Local / Instance Variables&…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...

【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...

如何理解 IP 数据报中的 TTL?
目录 前言理解 前言 面试灵魂一问:说说对 IP 数据报中 TTL 的理解?我们都知道,IP 数据报由首部和数据两部分组成,首部又分为两部分:固定部分和可变部分,共占 20 字节,而即将讨论的 TTL 就位于首…...

Mac下Android Studio扫描根目录卡死问题记录
环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中,提示一个依赖外部头文件的cpp源文件需要同步,点…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.
ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #:…...
Python竞赛环境搭建全攻略
Python环境搭建竞赛技术文章大纲 竞赛背景与意义 竞赛的目的与价值Python在竞赛中的应用场景环境搭建对竞赛效率的影响 竞赛环境需求分析 常见竞赛类型(算法、数据分析、机器学习等)不同竞赛对Python版本及库的要求硬件与操作系统的兼容性问题 Pyth…...