C++ ——STL容器【list】模拟实现
代码仓库:
list模拟实现
list源码
数据结构——双向链表
文章目录
- 🍇1. 节点结构体
- 🍈2. list成员
- 🍉3. 迭代器模板
- 🍊4. 迭代器
- 🍋5. 插入删除操作
- 🍌5.1 insert & erase
- 🍌5.2 push_back & push_front & pop_back & pop_front
- 🍍6. 构造 & 析构 & 拷贝构造
- 🥭7. 赋值重载
- 🍓8. 获取元素个数
🍇1. 节点结构体
源码的list是双向带头循环链表,所以我们定义两个节点,一个指向下一个,一个指向前一个
template<class T>
struct list_node
{list_node<T>* _next; //指向下一个节点list_node<T>* _prev; //指向前一个T _val; //数据list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}
};
🍈2. list成员
list类包含一个_head
头节点,然后为了方便查出当前有多少个节点,还能多定义一个_size
template<class T>
class list
{typedef list_node<T> Node;
public:// 各类操作方法//...
private:Node* _head;size_t _size;
}
🍉3. 迭代器模板
源码的迭代器设置了三个模板参数:
T
:表示指向list
节点的数据类型Ref
:迭代器的引用类型,通常情况为T&
,但也可表示const
Ptr
:表示指向节点的指针类型,通常情况下为T*
,但也可表示const
迭代器,避免代码的冗余
对于string
或者是vector
的迭代器,对其解引用就可以表示当前的数据;而list
是链表,解引用之后表示的一个节点,所以相对会麻烦一点
//Ref T& / const T&
//Ptr T* / const T*
template<class T, class Ref, class Ptr>
struct __list_iterator
{typedef __list_iterator<T, Ref, Ptr> self;typedef list_node<T> Node;Node* _node;__list_iterator(Node* node):_node(node){}Ref operator*(){return _node->_val;}Ptr operator->(){return &_node->_val;}//前置++self& operator++(){_node = _node->_next;return *this;}//后置++self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}//前置--self& operator--(){_node = _node->_prev;return *this;}//后置--self operator--(int){self tmp(*this);_node = _node->_prev;return tmp;}bool operator!=(const self& lt){return _node != lt._node;}bool operator==(const self& lt){return _node == lt._node;}};
Tips:
迭代器并没有写拷贝构造,那么就是默认浅拷贝。这无关影响,因为我们就是希望通过这个迭代器找到这个节点
void test1() {list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);//浅拷贝list<int>::iterator it = lt.begin();while(it!=lt.end()){cout<< *it << " ";++it;}cout<<endl; }
这里没有奔溃也是因为迭代器没有写析构函数,迭代器只是负责访问,并不负责管理
🍊4. 迭代器
const const_iterator begin() const
{//单参数构造函数 隐式类型转换return _head->_next;
}
const const_iterator end() const
{return _head;
}iterator begin()
{//单参数构造函数 隐式类型转换return _head->_next;
}
iterator end()
{return _head;
}
🍋5. 插入删除操作
🍌5.1 insert & erase
这里插入删除操作之后,也会存在当前迭代器失效,所以传修改完毕之后的迭代器位置
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* tmp = new Node(x);Node* prev = cur->_prev;prev->_next = tmp;tmp->_next = cur;cur->_prev = tmp;tmp->_prev = prev;++_size;return tmp;
}
iterator erase(iterator pos)
{assert(pos != end());Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;prev->_next = next;next->_prev = prev;delete cur;--_size;return next;
}
🍌5.2 push_back & push_front & pop_back & pop_front
写了指定位置插入删除之后,直接复用即可
void push_back(const T& x)
{insert(end(), x);
}void push_front(const T& x)
{insert(begin(), x);
}void pop_back()
{Node* tail = _head->_prev;erase(tail);
}
void pop_front()
{erase(begin());
}
🍍6. 构造 & 析构 & 拷贝构造
查看源码发现list
的构造和析构都采用了复用
清空链表
void clear()
{iterator it = begin();while (it != end()){it = erase(it);}//_size = 0;
}
复用
void empty_init()
{_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;
}list()
{empty_init();
}list(const list<T>& lt)
{empty_init();for (auto& e : lt){push_back(e);}
}
~list()
{clear();delete _head;_head = nullptr;
}
🥭7. 赋值重载
这里还是采用现代的写法,交换完毕之后,自动调用析构函数
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
list<T>& operator=(list<T> lt)
{swap(lt);return *this;
}
🍓8. 获取元素个数
size_t size()
{return _size;
}
以上就是list
的基本功能实现,实质上就是双向带头循环链表,迭代器这块有点复杂。
那本期分享就到这里咯,我们下期再见,如果还有下期的话。
相关文章:

C++ ——STL容器【list】模拟实现
代码仓库: list模拟实现 list源码 数据结构——双向链表 文章目录 🍇1. 节点结构体🍈2. list成员🍉3. 迭代器模板🍊4. 迭代器🍋5. 插入删除操作🍌5.1 insert & erase🍌5.2 push_…...
ubuntu 16.04 安装mujoco mujoco_py gym stable_baselines版本问题
ubuntu 16.04系统 Python 3.7.16 mujoco200 (py37mujoco) abc123:~/github/spinningup$ pip list Package Version Editable project location ----------------------------- --------- --------------------------- absl-py …...
自然语言处理(NLP)技术
自然语言处理技术是一种人工智能技术,它的目标是使计算机能够理解、分析、处理和生成自然语言(人类使用的语言)。NLP技术包括文本分类、情感分析、机器翻译、语音识别、语音合成、信息检索、信息抽取、问答系统等。NLP技术的应用非常广泛&…...

如何将ubuntu LTS升级为Pro
LTS支持周期是5年; Pro支持周期是10年。 Ubuntu Pro专业版笔记 步骤: 打开“软件和更新” 可以看到最右侧的标签是Ubuntu Pro。 在没有升级之前,如果使用下面两步: sudo apt updatesudo apt upgrade 出现如下提示ÿ…...

如何学习ARM嵌入式开发?
ARM和单片机还是有许多区别的,可以说比单片机的应用更为复杂吧,往往在单片机里只需要对一个寄存器赋值就可以的初始化,在ARM下就要调用库函数了。甚至每个引脚其功能都多了许多,相应的配置也会更为麻烦,但如果做多了AR…...
二、使用运行自己的docker python容器环境
第一篇参考: https://blog.csdn.net/weixin_42357472/article/details/131953866 运行容器同时执行命令或脚本 1)这是打开一个对外的jupyter notebook容器环境 docker run -d --name my_container -p 8090:8888 mynewpythonimage jupyter notebook --…...

mac版窗口管理 Magnet for mac中文最新
magnet mac版是一款运行在苹果电脑上的一款优秀的窗口大小控制工具,拖拽窗口到屏幕边缘可以自动半屏,全屏或者四分之一屏幕,还可以设定快捷键完成分屏。这款专业的窗口管理工具当您每次将内容从一个应用移动到另一应用时,当您需要…...

Redis(五)—— Redis进阶部分
一、Redis配置文件详解 注意这是Redis服务本身的配置文件,相当于maven的settings.xml,而不是我们在springboot去配置Redis的那个application.yml。 核心部分include 引入其他redis配置文件,相当于spring的<import>bind 设置IP…...
Go Ethereum源码学习笔记000
Go Ethereum源码学习笔记 前言时代的弄潮儿: Blockchain为什么要研究以太坊& Go-Ethereum 的原理 前言 这个专栏的内容是免费的,因为自己这边都是基于开源库和开源内容整理的学习笔记,在这个过程中进行增删改查,将自己的理解融入其中&am…...
layui 设置选中时间为当天时间最大值23:59:59、laydate设置选中时间为当天时间最大值23:59:59
既是涨知识的一天,又是干前端的一天! laydate.render({ elem: #validityPeriod, //type: datetime,//类型要一定要相匹配 type: date, // 设置日期选择模式 trigger: click, format: yyyy-MM-dd HH:mm:ss, // 设置日期的显示格式 min: startDate, max: …...
HTML+CSS+JavaScript:验证码60秒倒计时按钮
一、需求 1、打开浏览器时,按钮禁用,按钮内容为60秒倒计时 2、倒计时结束时,按钮禁用被取消 二、应用场景 1、60秒内不得重新发送验证码 2、我已阅读用户协议(5s) 三、完整代码 <!DOCTYPE html> <html l…...

互联网医院系统开发:打造便捷高效的医疗服务平台
随着互联网技术的飞速发展,互联网医院系统的出现为医疗行业带来了许多新的机遇和优势。互联网医院系统是一种基于互联网技术的医疗服务平台,旨在提供便捷、高效、个性化的医疗服务。下面将介绍互联网医院系统开发的优势。 提供便捷的医疗服务&#x…...

章节5:SQL注入之WAF绕过
章节5:SQL注入之WAF绕过 5.1 SQL注入之WAF绕过上 WAF拦截原理:WAF从规则库中匹配敏感字符进行拦截。 5.2 SQL注入之WAF绕过下 (原理简单了解) 关键词大小写绕过 有的WAF因为规则设计的问题,只匹配纯大写或纯小写的…...

iphone卡在恢复模式怎么办?修复办法分享!
iPhone 卡在恢复屏幕问题是 iPhone 用户在软件更新或恢复期间的常见问题。如果你也遇到此问题,不要着急,接下来我们将探讨 iPhone 卡在恢复屏幕上的主要原因,以及如何轻松修复它。 iPhone卡在恢复屏幕问题上没有一个特别的原因,但…...
uniApp禁止遮罩弹窗下的页面滚动
文章目录 问题解决代码 问题 最近用uniApp开发一款软件,页面是可以滚动的长列表,自定义组件弹窗遮罩出来后,滑动屏幕,页面也跟着滚动。研究了网上的解决办法 在遮罩层的最外层的view元素中加入 touchmove.stop.prevent"moveH…...

【Huawei】WLAN实验(三层发现)
拓扑图如上,AP与S1在同一VLAN,S1与AC在同一VLAN,AP采用三层发现AC,AP与客户的DHCP由S1提供。 S1配置 vlan batch 10 20 30 dhcp enable ip pool apgateway-list 192.168.20.1network 192.168.20.0 mask 255.255.255.0option 43 sub-option …...

Windows 10 安装 PostgreSQL 12.x 报错 ‘psql‘ 不是内部或外部命令 由于找不到文件libintl-9.dll等问题
目录 序言一、问题总结问题 1 psql 不是内部或外部命令,也不是可运行的程序或批处理文件。问题 2 “由于找不到文件libintl-9.dll,无法继续执行代码,重新安装程序可能会解决此问题。“1、卸载2、安装3、安装 Stack Builder (这个可…...
在CSDN学Golang云原生(持续交付Argo)
一,Argo安装配置 Argo是一个基于Kubernetes的容器本地工作流引擎,可以帮助用户在Kubernetes上创建、运行和维护容器化应用程序。下面是Argo安装配置的步骤: 首先确保你已经安装了kubectl和helm添加chart仓库 $ helm repo add argo https:/…...
安全运维 -- splunk 集群配置归档
0x00 背景 splunk 集群索引服务器容量满了以后,为了防止数据丢失,需要对旧数据进行归档保存。 0x01 原理 指定一台大容量服务器,创建共享文件夹,并将集群里的所有indexer指向这个归档共享目录。 0x02 实施 集群的每个indexer都…...
使用kind在mac本地搭建k8s及istio
序 之前使用multipass装ubuntu,然后再用microk8s搭建k8s,这会直接用orbstack及kind在本地搭建k8s及istio 安装 orbstack 通过orbstack这个地址下载,主要是开销低,用来替代docker desktop 添加国内源 ~/.orbstack/config/dock…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

K8S认证|CKS题库+答案| 11. AppArmor
目录 11. AppArmor 免费获取并激活 CKA_v1.31_模拟系统 题目 开始操作: 1)、切换集群 2)、切换节点 3)、切换到 apparmor 的目录 4)、执行 apparmor 策略模块 5)、修改 pod 文件 6)、…...

IT供电系统绝缘监测及故障定位解决方案
随着新能源的快速发展,光伏电站、储能系统及充电设备已广泛应用于现代能源网络。在光伏领域,IT供电系统凭借其持续供电性好、安全性高等优势成为光伏首选,但在长期运行中,例如老化、潮湿、隐裂、机械损伤等问题会影响光伏板绝缘层…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...

HashMap中的put方法执行流程(流程图)
1 put操作整体流程 HashMap 的 put 操作是其最核心的功能之一。在 JDK 1.8 及以后版本中,其主要逻辑封装在 putVal 这个内部方法中。整个过程大致如下: 初始判断与哈希计算: 首先,putVal 方法会检查当前的 table(也就…...

【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...

Axure 下拉框联动
实现选省、选完省之后选对应省份下的市区...

快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
验证redis数据结构
一、功能验证 1.验证redis的数据结构(如字符串、列表、哈希、集合、有序集合等)是否按照预期工作。 2、常见的数据结构验证方法: ①字符串(string) 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...