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&,但也可表示constPtr:表示指向节点的指针类型,通常情况下为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…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...
大模型多显卡多服务器并行计算方法与实践指南
一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
dify打造数据可视化图表
一、概述 在日常工作和学习中,我们经常需要和数据打交道。无论是分析报告、项目展示,还是简单的数据洞察,一个清晰直观的图表,往往能胜过千言万语。 一款能让数据可视化变得超级简单的 MCP Server,由蚂蚁集团 AntV 团队…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
《C++ 模板》
目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板,就像一个模具,里面可以将不同类型的材料做成一个形状,其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式:templa…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时,性能会显著下降。以下是优化思路和简易实现方法: 一、核心优化思路 减少 JOIN 数量 数据冗余:添加必要的冗余字段(如订单表直接存储用户名)合并表:将频繁关联的小表合并成…...
