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

【C++】STL——list底层实现

目录

💕1.list的三个类介绍

💕2.list——节点类 (ListNode)

💕3.list——链表类 (List)

💕4.list——迭代器类(重点思考)(ListIterator)

💕5. list遍历(迭代器,const迭代器)

💕6.整体代码 

💕7.测试用例

💕8.完结 


一个人的坚持到底有多难 

    声明:此文内容基于此文章->:【C++】STL——list的使用

💕1.list的三个类介绍

在list中存在着三个类,而我们使用的list就是这三个类相辅相成形成的功能

它们分别是节点类,链表类,迭代器类


节点类用来代表每一个节点的内容

迭代器类用来实现链表的遍历,成员为单个节点的地址

而链表类就是用来实现各种链表功能,成员为头结点


💕2.list——节点类 (ListNode)

节点类是每一个节点的内容,因此需要有前一个节点的地址,后一个节点的地址,以及数据

但因为它的内容需要频繁运用,因此最好用struct,struct中所有都为public,因此很方便,当然class也没有问题,只不过需要显示public

因此需要这样写->:

template<class T>
struct ListNode
{ListNode* prev;ListNode* next;T data;//1.T& x可以让形参不开辟新的空间,时间和空间上都有节省//2.const保护引用不被修改//3.T()是因为节点内容不一定是什么类型,而T()可以更好地初始化//例:int(),自动初始化为0,double(),string()ListNode(const T& x = T()):data(x),prev(nullptr),next(nullptr){}
};

💕3.list——链表类 (List)

链表类的实现主要是具体功能,而我们知道链表是有一个头结点的,因此可以在链表类中实现

	template<class T>class List{typedef ListNode<T> Node;//将节点类重命名为Node//创建头节点,让其指向自己List(){phead = new Node();phead->next = phead;phead->prev = phead;}private:Node* phead;};

💕4.list——迭代器类(重点思考)(ListIterator)

迭代器类需要实现的是链表的遍历,想要实现遍历,必不可少的就是begin()函数,正常来说,begin()函数的返回类型应该是节点的地址,但是仔细思考一下,如果返回的是节点的地址,那这个节点的地址++后,不一定是下一个节点的地址,因此,begiin()函数不应该使用节点的地址作为返回值


新的思路:我们可以利用对象进行遍历,什么意思?

我们在进行遍历时,每一次begin()返回的是一个对象,通过访问这个对象中的节点地址,加上运算符重载,来进行遍历,因为利用这个对象中的节点地址,就进而可以通过这个节点地址访问到节点的数值


因此可以这样写->:

	template<class T>struct ListIterator{typedef ListNode<T> Node;Node* node;//单个节点的地址};

为什么是结构体?先不要在意,请看后面

💕5. list遍历(迭代器,const迭代器)

我们的思路是,通过对象进行遍历,因此我们需要实现对象的++,--运算符重载,来一个一个的遍历每一个节点对象


	template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;ListIterator(Node* x){node = x;}//前置++,作用是遍历,不可以返回节点地址,因为无法进行下一次++,不一定会指向下一个节点//利用对象进行遍历,因此返回的应该是一个对象,迭代器类的对象,因为要用迭代器类中的单个节点的地址来遍历Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}//后置--//后置--需要利用一个临时变量来表示原来的值,首先传参传给来的是对象的地址,即thisSelf operator--(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->prev;return tep;//后置的返回值不可以用引用,因为临时变量tep出了函数就销毁了,用引用会导致空引用}Self operator++(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->next;return tep;}T& operator*(){return this->node->data;}bool operator!=(const Self& it){return this->node != it.node;}bool operator==(const Self& it){return this->node == it.node;}Node* node;//单个节点的地址};


接下来是begin函数与end函数,写在List类中

		iterator begin(){//phead->next的类型是Node*类型,而返回类型需要是iterator类型,也就是对象//利用匿名对象,将phead->next传给ListIterator的构造函数,使它变为一个匿名对象,再return回去return iterator(phead->next);}iterator end(){return iterator(phead);}

如何实现const迭代器?

我们可以新建一个const的迭代器类,通过const修饰constIterator类中的成员变量,进而实现const迭代器的效果


具体实现如下->:
 

// 新增 const 迭代器
template<class T>
struct ListConstIterator
{typedef const ListNode<T> Node;typedef ListConstIterator<T> Self;ListConstIterator(Node* x):node(x){}// 前置++Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}// 后置++Self operator++(int){Self tep(*this);node = node->next;return tep;}Self operator--(int){Self tep(*this);node = node->prev;return tep;}const T& operator*() const{return node->data;}bool operator!=(const Self& it) const{return node != it.node;}bool operator==(const Self& it) const{return node == it.node;}//把节点定义为const类,因为const迭代器要实现的是const T* ,限制的是解引用const Node* node;
};
template<class T>
class List
{public:typedef ListNode<T> Node;//将节点类重命名为Nodetypedef ListIterator<T> iterator;//将迭代器类重命名为iteratortypedef ListConstIterator<T> const_iterator; // 新增 const_iterator//创建头节点,让其指向自己const_iterator begin() const{return const_iterator(phead->next);}const_iterator end() const{return const_iterator(phead);}
};

至此难点就全部完成了,剩下的就只剩拷贝构造等,看看整体代码即可

💕6.整体代码 

#pragma
#include<assert.h>
namespace yzq
{template<class T>struct ListNode{ListNode* prev;ListNode* next;T data;//1.T& x可以让形参不开辟新的空间,时间和空间上都有节省//2.const保护引用不被修改//3.T()是因为节点内容不一定是什么类型,而T()可以更好地初始化//例:int(),自动初始化为0,double(),string()ListNode(const T& x = T()):data(x),prev(nullptr),next(nullptr){}};template<class T>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;ListIterator(Node* x){node = x;}//前置++,作用是遍历,不可以返回节点地址,因为无法进行下一次++,不一定会指向下一个节点//利用对象进行遍历,因此返回的应该是一个对象,迭代器类的对象,因为要用迭代器类中的单个节点的地址来遍历Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}//后置--//后置--需要利用一个临时变量来表示原来的值,首先传参传给来的是对象的地址,即thisSelf operator--(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->prev;return tep;//后置的返回值不可以用引用,因为临时变量tep出了函数就销毁了,用引用会导致空引用}Self operator++(int){//Self* tep = this;//这种写法不可取,因为两块地址一样,任意一个修改全修改了所以没区别Self tep(*this);//拷贝构造函数创建临时对象,但是需要注意区分,这个对象的地址和*this的地址是不一样的,但是它们里面的node地址是一样的node = node->next;return tep;}T& operator*(){return this->node->data;}bool operator!=(const Self& it){return this->node != it.node;}bool operator==(const Self& it){return this->node == it.node;}Node* node;//单个节点的地址};// 新增 const 迭代器template<class T>struct ListConstIterator{typedef const ListNode<T> Node;typedef ListConstIterator<T> Self;ListConstIterator(Node* x):node(x){}// 前置++Self& operator++(){node = node->next;return *this;}Self& operator--(){node = node->prev;return *this;}// 后置++Self operator++(int){Self tep(*this);node = node->next;return tep;}Self operator--(int){Self tep(*this);node = node->prev;return tep;}const T& operator*() const{return node->data;}bool operator!=(const Self& it) const{return node != it.node;}bool operator==(const Self& it) const{return node == it.node;}//把节点定义为const类,因为const迭代器要实现的是const T* ,限制的是解引用const Node* node;};template<class T>class List{public:typedef ListNode<T> Node;//将节点类重命名为Nodetypedef ListIterator<T> iterator;//将迭代器类重命名为iteratortypedef ListConstIterator<T> const_iterator; // 新增 const_iterator//创建头节点,让其指向自己const_iterator begin() const{return const_iterator(phead->next);}const_iterator end() const{return const_iterator(phead);}List(){phead = new Node();phead->next = phead;phead->prev = phead;}//拷贝构造函数,可以开辟新空间然后直接尾插//因为l2是const类型的,所以auto时需要const类型的迭代器//遍历 const 对象需要 const 迭代器List(const List<T>& l2){phead = new Node();phead->next = phead;phead->prev = phead;for (const auto& e : l2){push_back(e);}}//赋值运算符重载//直接更改头结点,后面的访问就全更改了List<T>& operator=(List<T> lt){swap(phead, lt.phead);return *this;}//析构函数~List(){clear();delete phead;phead = nullptr;}//全部遍历一遍s释放void clear(){auto it = begin();while (it != end()){it = erase(it);}}//头删void pop_back(){erase(--end());}//头插void push_front(const T& x){insert(begin(), x);}//头删void pop_front(){erase(begin());}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}iterator begin(){//phead->next的类型是Node*类型,而返回类型需要是iterator类型,也就是对象//利用匿名对象,将phead->next传给ListIterator的构造函数,使它变为一个匿名对象,再return回去return iterator(phead->next);}iterator end(){return iterator(phead);}iterator insert(iterator pos, const T& x){Node* cur = pos.node;Node* newnode = new Node(x);Node* prev = cur->prev;// prev  newnode  curprev->next = newnode;newnode->prev = prev;newnode->next = cur;cur->prev = newnode;return iterator(newnode);}// erase 后 pos失效了,pos指向节点被释放了iterator erase(iterator pos){assert(pos != end());Node* cur = pos.node;Node* prev = cur->prev;Node* next = cur->next;prev->next = next;next->prev = prev;delete cur;return iterator(next);}private:Node* phead;};
}

💕7.测试用例

#define _CRT_SECURE_NO_WARNINGS 
#include <iostream>
using namespace std;
#include"list.h"
int main() {yzq::List<int> l1;l1.push_back(2);l1.push_back(3);l1.insert(l1.begin(), 5);l1.erase(l1.begin());yzq::List<int> l2(l1);//遍历输出: 2 3for (auto e : l2) {std::cout << e << " ";}return 0;
}

💕8.完结 

相关文章:

【C++】STL——list底层实现

目录 &#x1f495;1.list的三个类介绍 &#x1f495;2.list——节点类 &#xff08;ListNode&#xff09; &#x1f495;3.list——链表类 &#xff08;List&#xff09; &#x1f495;4.list——迭代器类&#xff08;重点思考&#xff09;(ListIterator) &#x1f495;5…...

Java 进阶day14XML Dom4j 工厂模式 Base64

目录 知识点1、XML 概念XML约束 知识点2、XML解析 Dom4j&#xff08;Dom for java&#xff09;XPath 知识点3、工厂模式知识点4、Base64 知识点1、XML 概念 XML的全称为&#xff08;eXtensible Markup Language&#xff09;&#xff0c;是一种可扩展的标记语言。 XML的作用&…...

100.6 AI量化面试题:如何评估AI量化模型的过拟合风险?

目录 0. 承前1. 解题思路1.1 性能验证维度1.2 统计检验维度1.3 实践验证维度 2. 样本内外性能对比2.1 基础性能指标计算2.2 策略收益对比 3. 参数敏感性分析3.1 参数网格搜索3.2 稳定性评估 4. 白噪声测试4.1 随机数据测试 5. Deflated Sharpe Ratio5.1 DSR计算 6. 交易成本敏感…...

C++模板:泛型编程的魔法钥匙

前言 本篇博客将详细介绍C的模板 &#x1f496; 个人主页&#xff1a;熬夜写代码的小蔡 &#x1f5a5; 文章专栏&#xff1a;C 若有问题 评论区见 &#x1f389;欢迎大家点赞&#x1f44d;收藏⭐文章 ​ 一&#xff1a;引言&#xff1a;为什么需要模板&#xff1f; 1.复杂代码…...

unordered_map/set的哈希封装

【C笔记】unordered_map/set的哈希封装 &#x1f525;个人主页&#xff1a;大白的编程日记 &#x1f525;专栏&#xff1a;C笔记 文章目录 【C笔记】unordered_map/set的哈希封装前言一. 源码及框架分析二.迭代器三.operator[]四.使用哈希表封装unordered_map/set后言 前言 哈…...

机器学习专业毕设选题推荐合集 人工智能

目录 前言 毕设选题 开题指导建议 更多精选选题 选题帮助 最后 前言 大家好,这里是海浪学长毕设专题! 大四是整个大学期间最忙碌的时光&#xff0c;一边要忙着准备考研、考公、考教资或者实习为毕业后面临的升学就业做准备,一边要为毕业设计耗费大量精力。学长给大家整理…...

软件工程导论三级项目报告--《软件工程》课程网站

《软件工程》课程网站 摘要 本文详细介绍了《软件工程》课程网站的设计与实现方案&#xff0c;包括可行性分析、需求分析、总体设计、详细设计、测试用例。首先&#xff0c;通过可行性分析从各方面确认了该工程的可实现性&#xff0c;接着需求分析明确了系统的目标用户群和功能…...

物联网领域的MQTT协议,优势和应用场景

MQTT&#xff08;Message Queuing Telemetry Transport&#xff09;作为轻量级发布/订阅协议&#xff0c;凭借其低带宽消耗、低功耗与高扩展性&#xff0c;已成为物联网通信的事实标准。其核心优势包括&#xff1a;基于TCP/IP的异步通信机制、支持QoS&#xff08;服务质量&…...

缓存类为啥使用 unordered_map 而不是 map

性能考虑&#xff1a; std::unordered_map 是基于哈希表实现的&#xff0c;而 std::map 是基于红黑树实现的。对于查找操作&#xff0c;std::unordered_map 的平均查找时间复杂度是 O ( 1 ) O(1) O(1)&#xff0c;而 std::map 的查找时间复杂度是 O ( l o g n ) O(log n) O(l…...

产品经理的人工智能课 02 - 自然语言处理

产品经理的人工智能课 02 - 自然语言处理 1 自然语言处理是什么2 一个 NLP 算法的例子——n-gram 模型3 预处理与重要概念3.1 分词 Token3.2 词向量化表示与 Word2Vec 4 与大语言模型的交互过程参考链接 大语言模型&#xff08;Large Language Models, LLMs&#xff09;是自然语…...

2024年MySQL 下载、安装及启动停止教程(非常详细),涉及命令行net start mysql80提示发生系统错误5的解决方案

一、安装包下载 官方网址&#xff1a; https://www.mysql.com/ MySQL 官方提供了两种不同的版本&#xff1a; 1.社区版本&#xff08; MySQL Community Server &#xff09; &#xff1a;免费&#xff0c; 但MySQL 不提供任何技术支持 2.商业版本&#xff08; MySQL Enterp…...

19.[前端开发]Day19-王者荣项目耀实战(二)

01_(掌握)王者荣耀-main-banner展示实现 完整代码 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewpor…...

lmk内存压力测试工具mem-pressure源码剖析

背景&#xff1a; android系统开发过程中&#xff0c;经常会遇到一些low memory kill的问题&#xff0c;在分析这些系统低内存导致被杀问题时候&#xff0c;经常因为不好复现而成为一个比较烦恼的阻碍。因为这种低内存问题本身就不属于一种功能操作类型的问题&#xff0c;属于…...

企业四要素如何用Java进行调用

一、什么是企业四要素&#xff1f; 企业四要素是在企业三要素&#xff08;企业名称、统一社会信用代码、法定代表人姓名&#xff09;的基础上&#xff0c;增加了一个关键要素&#xff0c;通常是企业注册号或企业银行账户信息。这种接口主要用于更全面的企业信息验证&#xff0c…...

修剪二叉搜索树(力扣669)

这道题还是比较复杂&#xff0c;在递归上与之前写过的二叉树的题目都有所不同。如果当前递归到的子树的父节点不在范围中&#xff0c;我们根据节点数值的大小选择进行左递归还是右递归。为什么找到了不满足要求的节点之后&#xff0c;还要进行递归呢&#xff1f;因为该不满足要…...

一款由 .NET 官方团队开源的电子商务系统 - eShop

项目介绍 eShop是一款由.NET官方开源的&#xff0c;基于.NET Aspire构建的用于参考学习的服务架构电子商务系统&#xff0c;旨在展示如何利用.NET框架及其相关技术栈构建一个现代化的电子商务网站。该项目采用服务架构&#xff0c;将应用程序分解为多个独立的服务&#xff0c;…...

论最新技术编程类有什么,值得关注的点有什么呢?

在2025年的编程领域,新技术层出不穷。编程语言方面,Zig作为新一代系统级编程语言,凭借无隐藏控制流、出色的优化性能以及良好的C语言兼容性,被视作C语言强有力的替代者;Rust的应用范围不断拓展,在系统开发和Web后端开发中表现亮眼,其“零成本抽象”特性在保障内存安全的…...

Java入门进阶

文章目录 1、常用API 1.1、Math1.2、System1.3、Object1.4、Arrays1.5、基本类型包装类 1.5.1、基本类型包装类概述1.5.2、Integer1.5.3、int和String相互转换1.5.4、自动装箱和拆箱 1.6、日期类 1.6.1、Date类1.6.2、SimpleDateFormat类 1.6.2.1、格式化&#xff08;从Date到…...

Java并发编程面试题:ThreadLocal(8题)

&#x1f9d1; 博主简介&#xff1a;CSDN博客专家&#xff0c;历代文学网&#xff08;PC端可以访问&#xff1a;https://literature.sinhy.com/#/?__c1000&#xff0c;移动端可微信小程序搜索“历代文学”&#xff09;总架构师&#xff0c;15年工作经验&#xff0c;精通Java编…...

Zabbix7.0安装(Ubuntu24.04+LNMP)

1.选择版本 下载Zabbix 2.安装虚拟机 这里选择在Ubuntu24.04上安装Zabbix. 安装链接https://blog.csdn.net/weixin_58189050/article/details/145446065 配置源 vim /etc/apt/sources.list deb https://mirrors.aliyun.com/ubuntu/ noble main restricted universe multive…...

【杂谈】-递归进化:人工智能的自我改进与监管挑战

递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

算法:模拟

1.替换所有的问号 1576. 替换所有的问号 - 力扣&#xff08;LeetCode&#xff09; ​遍历字符串​&#xff1a;通过外层循环逐一检查每个字符。​遇到 ? 时处理​&#xff1a; 内层循环遍历小写字母&#xff08;a 到 z&#xff09;。对每个字母检查是否满足&#xff1a; ​与…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

基于Springboot+Vue的办公管理系统

角色&#xff1a; 管理员、员工 技术&#xff1a; 后端: SpringBoot, Vue2, MySQL, Mybatis-Plus 前端: Vue2, Element-UI, Axios, Echarts, Vue-Router 核心功能&#xff1a; 该办公管理系统是一个综合性的企业内部管理平台&#xff0c;旨在提升企业运营效率和员工管理水…...