【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.完结 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/12914.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

deepseek、qwen等多种模型本地化部署

deepseek、qwen等多种模型本地化部署

想要在本地部署deepseek、qwen等模型其实很简单，快跟着小编一起部署吧 1 环境搭建 1.1下载安装环境 首先我们需要搭建一个环境ollama，下载地址如下 ：Ollama 点击Download 根据自己电脑的系统选择对应版本下载即可 1.2 安装环境（window为例） 可以直接点击安装包进行安…
阅读更多...
穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞黄金矿工

穷举vs暴搜vs深搜vs回溯vs剪枝系列一＞黄金矿工

目录 决策树&#xff1a;代码设计代码&#xff1a; 决策树&#xff1a; 代码设计 代码&#xff1a; class Solution {boolean[][] vis;int ret,m,n;public int getMaximumGold(int[][] grid) {m grid.length;n grid[0].length;vis new boolean[m][n]; for(int i 0; i <…
阅读更多...
基于springboot河南省旅游管理系统

基于springboot河南省旅游管理系统

基于Spring Boot的河南省旅游管理系统是一种专为河南省旅游行业设计的信息管理系统&#xff0c;旨在整合和管理河南省的旅游资源信息&#xff0c;为游客提供准确、全面的旅游攻略和服务。以下是对该系统的详细介绍&#xff1a; 一、系统背景与意义 河南省作为中国的中部省份&…
阅读更多...
并发编程 - 线程同步（三）之原子操作Interlocked简介

并发编程 - 线程同步（三）之原子操作Interlocked简介

上一章我们了解了3种处理多线程中共享资源安全的方法&#xff0c;今天我们将更近一步&#xff0c;学习一种针对简单线程同步场景的解决方案——Interlocked。 在此之前我们先学习一个概念——原子操作。 01、原子操作 原子操作&#xff0c;其概念源于化学领域&#xff0c;原子…
阅读更多...
0205算法:最长连续序列、三数之和、排序链表

0205算法:最长连续序列、三数之和、排序链表

力扣128&#xff1a;最长连续序列 给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 class Solution {public int longestConsecutive(in…
阅读更多...
JAVA_内部类

JAVA_内部类

定义&#xff1a;在类的内部再定义一个类 特点&#xff1a;内部类可以直接访问外部类中的成员变量&#xff0c;即使是私有的。 外部类要想访问内部类中的成员变量&#xff0c;必须先创建内部类对象。 什么时候使用内部类&#xff1a;B类是A类的一部分&#xff0c;且B单独存在没…
阅读更多...
2024 JAVA面试题

2024 JAVA面试题

第一章-Java基础篇 1、你是怎样理解OOP面向对象 面向对象是利于语言对现实事物进行抽象。面向对象具有以下特征&#xff1a; 继承****&#xff1a;****继承是从已有类得到继承信息创建新类的过程 封装&#xff1a;封装是把数据和操作数据的方法绑定起来&#xff0c;对数据的…
阅读更多...
视频融合平台EasyCVR无人机场景视频压缩及录像方案

视频融合平台EasyCVR无人机场景视频压缩及录像方案

安防监控视频汇聚EasyCVR平台在无人机场景中发挥着重要的作用&#xff0c;通过高效整合视频流接入、处理与分发等功能&#xff0c;为无人机视频数据的实时监控、存储与分析提供了全面支持&#xff0c;广泛应用于安防监控、应急救援、电力巡检、交通管理等领域。 EasyCVR支持GB…
阅读更多...
2025最新软件测试面试大全

2025最新软件测试面试大全

前面看到了一些面试题&#xff0c;总感觉会用得到&#xff0c;但是看一遍又记不住&#xff0c;所以我把面试题都整合在一起&#xff0c;都是来自各路大佬的分享&#xff0c;为了方便以后自己需要的时候刷一刷&#xff0c;不用再到处找题&#xff0c;今天把自己整理的这些面试题…
阅读更多...
Hugging Face GGUF 模型可视化

Hugging Face GGUF 模型可视化

Hugging Face GGUF 模型可视化 1. Finding GGUF files (检索 GGUF 模型)2. Viewer for metadata & tensors info (可视化 GGUF 模型)References 无知小儿&#xff0c;仙家雄霸天下&#xff0c;依附强者才是唯一的出路。否则天地虽大&#xff0c;也让你们无路可走&#xff0…
阅读更多...
【C++】多态详细讲解

【C++】多态详细讲解

本篇来聊聊C面向对象的第三大特性-多态。 1.多态的概念 多态通俗来说就是多种形态。多态分为编译时多态(静态多态)和运⾏时多态(动态多态)。 编译时多态&#xff1a;主要就是我们前⾯讲的函数重载和函数模板&#xff0c;他们传不同类型的参数就可以调⽤不同的函数&#xff0c;通…
阅读更多...
oracle 基础语法复习记录

oracle 基础语法复习记录

Oracle SQL基础 学习范围 学习SQL基础语法 掌握SELECT、INSERT、UPDATE、DELETE等基本操作。 熟悉WHERE、GROUP BY、ORDER BY、HAVING等子句。 理解表连接&#xff1a; 学习INNER JOIN、LEFT JOIN、RIGHT JOIN、FULL OUTER JOIN等连接方式。 掌握聚合函数&#xff1a; 熟悉…
阅读更多...
配置@别名路径，把@/ 解析为 src/

配置@别名路径，把@/ 解析为 src/

路径解析配置 webpack 安装 craco npm i -D craco/craco 项目根目录下创建文件 craco.config.js &#xff0c;内容如下 const path require(path) module.exports {webpack: {// 配置别名alias: {// 约定&#xff1a; 使用 表示src文件所在路径: path.resolve(__dirname,src)…
阅读更多...
Vue前端开发-pinia之Actions插件

Vue前端开发-pinia之Actions插件

Store中的Actions部分&#xff0c;用于定义操作属性的方法&#xff0c;类似于组件中的methods部分&#xff0c;它与Getters都可以操作State属性&#xff0c;但在定义方法时&#xff0c;Getters是对State属性进行加工处理&#xff0c;再返回使用&#xff0c;属于内部计算;Action…
阅读更多...
Java NIO详解

Java NIO详解

一、NIO简介 NIO 中的 N 可以理解为 Non-blocking&#xff0c;不单纯是 New&#xff0c;是解决高并发、I/O高性能的有效方式。 Java NIO 是Java1.4之后推出来的一套IO接口&#xff0c;NIO提供了一种完全不同的操作方式&#xff0c; NIO支持面向缓冲区的、基于通道的IO操作。 …
阅读更多...
Java进阶笔记（中级）

Java进阶笔记（中级）

-----接Java进阶笔记&#xff08;初级&#xff09;----- 目录 集合多线程 集合 ArrayList 可以通过List来接收ArrayList对象&#xff08;因为ArrayList实现了List接口&#xff09; 方法&#xff1a;接口名 柄名 new 实现了接口的类(); PS: List list new ArrayList();遍历…
阅读更多...
21.2.2 保存

21.2.2 保存

版权声明&#xff1a;本文为博主原创文章&#xff0c;转载请在显著位置标明本文出处以及作者网名&#xff0c;未经作者允许不得用于商业目的。 如果打开某个Excel文件修改后&#xff0c;需要保存到原文件或者用新的文件名保存&#xff0c;在 Excel.Application.Quit() 前使用W…
阅读更多...
基于微信小程序的校园水电费管理平台设计与实现

基于微信小程序的校园水电费管理平台设计与实现

目录 摘要 系统展示 技术介绍 MySQL数据库 Vue框架 代码实现 管理员实现登录后端代码 连接数据库 前端代码实现 获取源码 摘要 随着社会的发展&#xff0c;社会的方方面面都在利用信息化时代的优势。互联网的优势和普及使得各种系统的开发成为必需。 本文以实际运用…
阅读更多...
基于springboot的体质测试数据分析及可视化设计

基于springboot的体质测试数据分析及可视化设计

作者&#xff1a;学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等 文末获取“源码数据库万字文档PPT”&#xff0c;支持远程部署调试、运行安装。 项目包含&#xff1a; 完整源码数据库功能演示视频万字文档PPT 项目编码&#xff1…
阅读更多...
离散时间傅里叶变换（DTFT）公式详解：周期性与连续性剖析

离散时间傅里叶变换（DTFT）公式详解：周期性与连续性剖析

摘要 离散时间傅里叶变换&#xff08;DTFT&#xff09;是数字信号处理领域的重要工具&#xff0c;它能将离散时间信号从时域转换到频域&#xff0c;揭示信号的频率特性。本文将深入解读DTFT公式&#xff0c;详细阐述其具有周期性和连续性的原因&#xff0c;帮助读者全面理解DT…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023