当前位置: 首页 > news >正文

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. 迭代器模板

image-20230730105307091

源码的迭代器设置了三个模板参数:

  • 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的构造和析构都采用了复用

image-20230730115520781
清空链表

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】模拟实现

代码仓库&#xff1a; list模拟实现 list源码 数据结构——双向链表 文章目录 &#x1f347;1. 节点结构体&#x1f348;2. list成员&#x1f349;3. 迭代器模板&#x1f34a;4. 迭代器&#x1f34b;5. 插入删除操作&#x1f34c;5.1 insert & erase&#x1f34c;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)技术

自然语言处理技术是一种人工智能技术&#xff0c;它的目标是使计算机能够理解、分析、处理和生成自然语言&#xff08;人类使用的语言&#xff09;。NLP技术包括文本分类、情感分析、机器翻译、语音识别、语音合成、信息检索、信息抽取、问答系统等。NLP技术的应用非常广泛&…...

如何将ubuntu LTS升级为Pro

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

如何学习ARM嵌入式开发?

ARM和单片机还是有许多区别的&#xff0c;可以说比单片机的应用更为复杂吧&#xff0c;往往在单片机里只需要对一个寄存器赋值就可以的初始化&#xff0c;在ARM下就要调用库函数了。甚至每个引脚其功能都多了许多&#xff0c;相应的配置也会更为麻烦&#xff0c;但如果做多了AR…...

二、使用运行自己的docker python容器环境

第一篇参考&#xff1a; https://blog.csdn.net/weixin_42357472/article/details/131953866 运行容器同时执行命令或脚本 1&#xff09;这是打开一个对外的jupyter notebook容器环境 docker run -d --name my_container -p 8090:8888 mynewpythonimage jupyter notebook --…...

mac版窗口管理 Magnet for mac中文最新

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

Redis(五)—— Redis进阶部分

一、Redis配置文件详解 注意这是Redis服务本身的配置文件&#xff0c;相当于maven的settings.xml&#xff0c;而不是我们在springboot去配置Redis的那个application.yml。 核心部分include 引入其他redis配置文件&#xff0c;相当于spring的<import>bind 设置IP&#xf…...

Go Ethereum源码学习笔记000

Go Ethereum源码学习笔记 前言时代的弄潮儿: Blockchain为什么要研究以太坊& Go-Ethereum 的原理 前言 这个专栏的内容是免费的&#xff0c;因为自己这边都是基于开源库和开源内容整理的学习笔记&#xff0c;在这个过程中进行增删改查&#xff0c;将自己的理解融入其中&am…...

layui 设置选中时间为当天时间最大值23:59:59、laydate设置选中时间为当天时间最大值23:59:59

既是涨知识的一天&#xff0c;又是干前端的一天&#xff01; 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、打开浏览器时&#xff0c;按钮禁用&#xff0c;按钮内容为60秒倒计时 2、倒计时结束时&#xff0c;按钮禁用被取消 二、应用场景 1、60秒内不得重新发送验证码 2、我已阅读用户协议&#xff08;5s&#xff09; 三、完整代码 <!DOCTYPE html> <html l…...

互联网医院系统开发:打造便捷高效的医疗服务平台

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

章节5:SQL注入之WAF绕过

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

iphone卡在恢复模式怎么办?修复办法分享!

iPhone 卡在恢复屏幕问题是 iPhone 用户在软件更新或恢复期间的常见问题。如果你也遇到此问题&#xff0c;不要着急&#xff0c;接下来我们将探讨 iPhone 卡在恢复屏幕上的主要原因&#xff0c;以及如何轻松修复它。 iPhone卡在恢复屏幕问题上没有一个特别的原因&#xff0c;但…...

uniApp禁止遮罩弹窗下的页面滚动

文章目录 问题解决代码 问题 最近用uniApp开发一款软件&#xff0c;页面是可以滚动的长列表&#xff0c;自定义组件弹窗遮罩出来后&#xff0c;滑动屏幕&#xff0c;页面也跟着滚动。研究了网上的解决办法 在遮罩层的最外层的view元素中加入 touchmove.stop.prevent"moveH…...

【Huawei】WLAN实验(三层发现)

拓扑图如上&#xff0c;AP与S1在同一VLAN,S1与AC在同一VLAN&#xff0c;AP采用三层发现AC&#xff0c;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 不是内部或外部命令&#xff0c;也不是可运行的程序或批处理文件。问题 2 “由于找不到文件libintl-9.dll&#xff0c;无法继续执行代码&#xff0c;重新安装程序可能会解决此问题。“1、卸载2、安装3、安装 Stack Builder &#xff08;这个可…...

在CSDN学Golang云原生(持续交付Argo)

一&#xff0c;Argo安装配置 Argo是一个基于Kubernetes的容器本地工作流引擎&#xff0c;可以帮助用户在Kubernetes上创建、运行和维护容器化应用程序。下面是Argo安装配置的步骤&#xff1a; 首先确保你已经安装了kubectl和helm添加chart仓库 $ helm repo add argo https:/…...

安全运维 -- splunk 集群配置归档

0x00 背景 splunk 集群索引服务器容量满了以后&#xff0c;为了防止数据丢失&#xff0c;需要对旧数据进行归档保存。 0x01 原理 指定一台大容量服务器&#xff0c;创建共享文件夹&#xff0c;并将集群里的所有indexer指向这个归档共享目录。 0x02 实施 集群的每个indexer都…...

使用kind在mac本地搭建k8s及istio

序 之前使用multipass装ubuntu&#xff0c;然后再用microk8s搭建k8s&#xff0c;这会直接用orbstack及kind在本地搭建k8s及istio 安装 orbstack 通过orbstack这个地址下载&#xff0c;主要是开销低&#xff0c;用来替代docker desktop 添加国内源 ~/.orbstack/config/dock…...

接口测试中缓存处理策略

在接口测试中&#xff0c;缓存处理策略是一个关键环节&#xff0c;直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性&#xff0c;避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明&#xff1a; 一、缓存处理的核…...

[2025CVPR]DeepVideo-R1:基于难度感知回归GRPO的视频强化微调框架详解

突破视频大语言模型推理瓶颈,在多个视频基准上实现SOTA性能 一、核心问题与创新亮点 1.1 GRPO在视频任务中的两大挑战 ​安全措施依赖问题​ GRPO使用min和clip函数限制策略更新幅度,导致: 梯度抑制:当新旧策略差异过大时梯度消失收敛困难:策略无法充分优化# 传统GRPO的梯…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

地震勘探——干扰波识别、井中地震时距曲线特点

目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波&#xff1a;可以用来解决所提出的地质任务的波&#xff1b;干扰波&#xff1a;所有妨碍辨认、追踪有效波的其他波。 地震勘探中&#xff0c;有效波和干扰波是相对的。例如&#xff0c;在反射波…...

TDengine 快速体验(Docker 镜像方式)

简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能&#xff0c;本节首先介绍如何通过 Docker 快速体验 TDengine&#xff0c;然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker&#xff0c;请使用 安装包的方式快…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

ios苹果系统,js 滑动屏幕、锚定无效

现象&#xff1a;window.addEventListener监听touch无效&#xff0c;划不动屏幕&#xff0c;但是代码逻辑都有执行到。 scrollIntoView也无效。 原因&#xff1a;这是因为 iOS 的触摸事件处理机制和 touch-action: none 的设置有关。ios有太多得交互动作&#xff0c;从而会影响…...

【JavaSE】多线程基础学习笔记

多线程基础 -线程相关概念 程序&#xff08;Program&#xff09; 是为完成特定任务、用某种语言编写的一组指令的集合简单的说:就是我们写的代码 进程 进程是指运行中的程序&#xff0c;比如我们使用QQ&#xff0c;就启动了一个进程&#xff0c;操作系统就会为该进程分配内存…...