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

【C++】STL-list模拟实现

目录

1、本次需要实现的3个类即接口总览

2、list的模拟实现

2.1 链表结点的设置以及初始化

2.2 链表的迭代器

2.3 容量接口及默认成员函数


1、本次需要实现的3个类即接口总览

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct __List_node//创建一个T类型的链表结点
{__List_node(const T& data = T());//构造函数__List_node<T>* _next;__List_node<T>* _prev;T _data;
};
template<class T, class Ref, class Ptr>
struct __List_iterator//封装链表的迭代器
{typedef __List_node<T> Node;typedef __List_iterator<T, Ref, Ptr> Self;Node* _node;//成员变量__List_iterator(Node* node);//构造函数。将迭代器中的结点初始化成传过来的结点//各种运算符重载函数Ref operator*();Ptr operator->();Self& operator++();Self operator++(int);Self& operator--();Self operator--(int);bool operator!=(const Self& it);
};
template<class T>
class List//真正的链表
{
public:typedef __List_node<T> Node;//将链表结点的名称重命名为Nodetypedef __List_iterator<T, T&, T*> iterator;typedef __List_iterator<T, const T&, const T*> const_iterator;//带头双向循环链表//默认成员函数List();~List();List(const List<T>& lt);List<T>& operator=(List<T> lt);//插入删除函数void clear();//clear是清除除了头节点意外的所以结点void push_back(const T& x);//一定要用引用,因为T不一定是内置类型void pop_back();void push_front(const T& x);void pop_front();void insert(iterator pos, const T& x);void erase(iterator pos);//迭代器相关函数iterator begin();iterator end();const_iterator begin() const;const_iterator end() const;
private:Node* _head;
};

2、list的模拟实现

2.1 链表结点的设置以及初始化

list是双向带头循环链表,所以链表的结点的成员变量需要有一个数值,一个指向前一个结点的指针,一个指向后一个结点的指针。初始化时,需要创建一个不存放有效值的头节点,并让头节点的两个指针都指向自己

链表的成员变量只需要一个指向头节点的指针

结点的结构体当中也需要创建一个构造函数,因为在创建结点时可以传入值

template<class T>
struct __List_node//创建一个T类型的链表结点
{__List_node(const T& data = T())//构造函数:_data(data), _next(nullptr), _prev(nullptr){}__List_node<T>* _next;__List_node<T>* _prev;T _data;
};
List()
{_head = new Node;_head->_next = _head;_head->_prev = _head;
}

上面的构造函数一定要使用引用,因为T不一定是内置类型

2.2 链表的迭代器

在上面的总览中可以看到链表的迭代器倍封装成了一个类,并且这个类有3个参数

首先,解释为什么会倍封装成一个类呢?
在vector中,迭代器就是一个指针,当我们对这个指针解引用(即*),就可以拿到这个指针所指向的数据,对其++,就可以让指针往下一个数据走,但在list中不行。如果迭代器是指向一个结点的指针,那么当对这个指针解引用时,拿到的是一个类对象,即这个结点本身,并不能拿到其中的数据,当对这个指针++时,并不能往下一个结点走所以我们需要将迭代器封装成一个类,这个类中的成员变量仍然是一个指向结点的指针,只是我们会重载一下里面的运算符,让我们*或++等操作的时候,能够直接拿到里面的数据和让指针往下一个结点。所以我们封装这个类的原因,就是为了让我们在使用list时,与使用vector等是一样的,即更加方便。实际上,迭代器这个类里面的成员变量仍然是一个指向结点的指针。

其次,解释为什么会有3个参数呢?

我们可以看到在链表类中会对迭代器进行重命名

typedef __List_iterator<T, T&, T*> iterator;
typedef __List_iterator<T, const T&, const T*> const_iterator;

因为我们对于list和const list调用的迭代器是不同的,若我们只有一个参数T,那这个时候我们重命名是没办法重命名两个的,也就是说,若只有一个参数,则需要封装两个迭代器的类,而这两个类中只有operator*和operator->是不同的,所以弄成3个参数会更好一些。

template<class T, class Ref, class Ptr>
struct __List_iterator//封装链表的迭代器
{typedef __List_node<T> Node;typedef __List_iterator<T, Ref, Ptr> Self;Node* _node;//成员变量__List_iterator(Node* node)//构造函数。将迭代器中的结点初始化成传过来的结点:_node(node){}// *itRef operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}// ++itSelf& operator++(){_node = _node->_next;return *this;}// it++Self operator++(int){Self tmp(*this);//调用默认的拷贝构造,因为是指针类型所以直接用默认的//_node = _node->_next;++(*this);return tmp;}// --itSelf& operator--(){_node = _node->_prev;return *this;}// it--Self operator--(int){Self tmp(*this);//_node = _node->_prev;--(*this);return tmp;}// it != end()bool operator!=(const Self& it){return _node != it._node;}
};
iterator begin()
{return iterator(_head->_next);//使用这个结点去构造一个迭代器,并将这个迭代器返回
}
iterator end()
{return iterator(_head);
}
const_iterator begin() const
{return const_iterator(_head->_next);//使用这个结点去构造一个迭代器,并将这个迭代器返回
}
const_iterator end() const
{return const_iterator(_head);
}

当我们是list调用begin是,则会调用返回值是iterator的,而iterator是__List_iterator<T, T&, T*>的,也就是调用*和->时,拿到的都是可读可写的值,反之则是只读的

int main()
{//对于内置类型List<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);List<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}return 0;
}
class Date
{
public:int _year = 0;int _month = 1;int _day = 1;
};
int main()
{//对于自定义类型List<Date> lt;lt.push_back(Date());lt.push_back(Date());List<Date>::iterator it = lt.begin();while (it != lt.end()){cout << it->_year << " " << it->_month << " " << it->_day << endl;//也可以cout << (*it)._year << " " << (*it)._month << " " << (*it)._day << endl;it++;}return 0;
}

->通常是在链表中存储的是自定义类型才会使用,通过上面可知->返回的是这个结构体的数值域的地址,那不应该是it->->_year吗(因为前面的it->返回后是Date*)?为了可读性,倍编译器处理了一下

这里说明一下begin和end返回的结点分别是那个

2.3 容量接口及默认成员函数

~List()
{clear();delete _head;_head = nullptr;
}
List(const List<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prev = _head;//const_iterator it = lt.begin();//这里迭代器不需要指定是那个类域,因为就是在这个类中使用//while (it != lt.end())//{//	push_back(*it);//	++it;//}for (auto e : lt)//这里与上面用迭代器一样,因为最终也会被替换成迭代器push_back(e);
}
/*List<T>& operator=(const List<T>& lt)
{if (this != &lt){clear();for (ayto e : lt)push_back(e);}return *this;
}*/
List<T>& operator=(List<T> lt)
{swap(_head, lt._head);//原来的空间给这个临时变量,因为这个临时变量是自定义类型,出了作用域后会自动调用析构函数return *this;
}
void clear()//clear是清除除了头节点意外的所以结点
{iterator it = begin();while (it != end()){erase(it++);}
}
void push_back(const T& x)//一定要用引用,因为T不一定是内置类型
{Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;/*insert(end(),x);*/
}
void pop_back()
{Node* tail = _head->_prev;Node* prev = tail->_prev;delete tail;_head->_prev = prev;prev->_next = _head;//erase(--end());
}
void push_front(const T& x)
{Node* first = _head->_next;Node* newnode = new Node(x);_head->_next = newnode;newnode->_prev = _head;newnode->_next = first;first->_prev = newnode;//insert(begin(), x);
}
void pop_front()
{Node* first = _head->_next;Node* second = first->_next;delete first;_head->_next = second;second->_prev = _head;//erase(begin());
}
void insert(iterator pos, const T& x)
{Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;
}
void 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;cur = nullptr;
}
template<class T>
struct __List_node//创建一个T类型的链表结点
{__List_node(const T& data = T())//构造函数:_data(data), _next(nullptr), _prev(nullptr){}__List_node<T>* _next;__List_node<T>* _prev;T _data;
};
template<class T, class Ref, class Ptr>
struct __List_iterator//封装链表的迭代器
{typedef __List_node<T> Node;typedef __List_iterator<T, Ref, Ptr> Self;Node* _node;//成员变量__List_iterator(Node* node)//构造函数。将迭代器中的结点初始化成传过来的结点:_node(node){}// *itRef operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}// ++itSelf& operator++(){_node = _node->_next;return *this;}// it++Self operator++(int){Self tmp(*this);//调用默认的拷贝构造,因为是指针类型所以直接用默认的//_node = _node->_next;++(*this);return tmp;}// --itSelf& operator--(){_node = _node->_prev;return *this;}// it--Self operator--(int){Self tmp(*this);//_node = _node->_prev;--(*this);return tmp;}// it != end()bool operator!=(const Self& it){return _node != it._node;}
};
template<class T>
class List//真正的链表
{
public:typedef __List_node<T> Node;//将链表结点的名称重命名为Nodetypedef __List_iterator<T, T&, T*> iterator;typedef __List_iterator<T, const T&, const T*> const_iterator;//带头双向循环链表List(){_head = new Node;_head->_next = _head;_head->_prev = _head;}~List(){clear();delete _head;_head = nullptr;}List(const List<T>& lt){_head = new Node;_head->_next = _head;_head->_prev = _head;//const_iterator it = lt.begin();//这里迭代器不需要指定是那个类域,因为就是在这个类中使用//while (it != lt.end())//{//	push_back(*it);//	++it;//}for (auto e : lt)//这里与上面用迭代器一样,因为最终也会被替换成迭代器push_back(e);}/*List<T>& operator=(const List<T>& lt){if (this != &lt){clear();for (ayto e : lt)push_back(e);}return *this;}*/List<T>& operator=(List<T> lt){swap(_head, lt._head);//原来的空间给这个临时变量,因为这个临时变量是自定义类型,出了作用域后会自动调用析构函数return *this;}void clear()//clear是清除除了头节点意外的所以结点{iterator it = begin();while (it != end()){erase(it++);}}void push_back(const T& x)//一定要用引用,因为T不一定是内置类型{Node* tail = _head->_prev;Node* newnode = new Node(x);tail->_next = newnode;newnode->_prev = tail;newnode->_next = _head;_head->_prev = newnode;/*insert(end(),x);*/}void pop_back(){Node* tail = _head->_prev;Node* prev = tail->_prev;delete tail;_head->_prev = prev;prev->_next = _head;//erase(--end());}void push_front(const T& x){Node* first = _head->_next;Node* newnode = new Node(x);_head->_next = newnode;newnode->_prev = _head;newnode->_next = first;first->_prev = newnode;//insert(begin(), x);}void pop_front(){Node* first = _head->_next;Node* second = first->_next;delete first;_head->_next = second;second->_prev = _head;//erase(begin());}void insert(iterator pos, const T& x){Node* newnode = new Node(x);Node* cur = pos._node;Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;}void 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;cur = nullptr;}iterator begin(){return iterator(_head->_next);//使用这个结点去构造一个迭代器,并将这个迭代器返回}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head->_next);//使用这个结点去构造一个迭代器,并将这个迭代器返回}const_iterator end() const{return const_iterator(_head);}
private:Node* _head;
};

相关文章:

【C++】STL-list模拟实现

目录 1、本次需要实现的3个类即接口总览 2、list的模拟实现 2.1 链表结点的设置以及初始化 2.2 链表的迭代器 2.3 容量接口及默认成员函数 1、本次需要实现的3个类即接口总览 #pragma once #include<iostream> #include<assert.h> using namespace std; templ…...

Java 7大排序

&#x1f435;本篇文章将对数据结构中7大排序的知识进行讲解 一、插入排序 有一组待排序的数据array&#xff0c;以升序为例&#xff0c;从第二个数据开始&#xff08;用tmp表示&#xff09;依次遍历整组数据&#xff0c;每遍历到一个数据都再从tmp的前一个数据开始&#xff0…...

vue3 - 图灵

目录 vue3简介整体上认识vue3项目创建Vue3工程使用官方脚手架创建Vue工程[推荐] 主要⼯程结构 数据双向绑定vue2语法的双向绑定简单表单双向绑定复杂表单双向绑定 CompositionAPI替代OptionsAPICompositionAPI简单不带双向绑定写法CompositionAPI简单带双向绑定写法setup简写⽅…...

java设计模式八 享元

享元模式&#xff08;Flyweight Pattern&#xff09;是一种结构型设计模式&#xff0c;它通过共享技术有效地支持大量细粒度的对象。这种模式通过存储对象的外部状态在外部&#xff0c;而将不经常变化的内部状态&#xff08;称为享元&#xff09;存储在内部&#xff0c;以此来减…...

ELK原理详解

ELK原理详解 一、引言 在当今日益增长的数据量和复杂的系统环境中&#xff0c;日志数据的收集、存储、分析和可视化成为了企业运营和决策不可或缺的一部分。ELK&#xff08;Elasticsearch、Logstash、Kibana&#xff09;堆栈凭借其高效的性能、灵活的扩展性和强大的功能&…...

多线程学习Day09

10.Tomcat线程池 LimitLatch 用来限流&#xff0c;可以控制最大连接个数&#xff0c;类似 J.U.C 中的 Semaphore 后面再讲 Acceptor 只负责【接收新的 socket 连接】 Poller 只负责监听 socket channel 是否有【可读的 I/O 事件】 一旦可读&#xff0c;封装一个任务对象&#x…...

第33次CSP认证Q1:词频统计

&#x1f344;题目描述 在学习了文本处理后&#xff0c;小 P 对英语书中的 &#x1d45b;n 篇文章进行了初步整理。 具体来说&#xff0c;小 P 将所有的英文单词都转化为了整数编号。假设这 &#x1d45b;n 篇文章中共出现了 &#x1d45a;m 个不同的单词&#xff0c;则把它们…...

pytorch加载模型出现错误

大概的错误长下面这样&#xff1a; 问题出现的原因&#xff1a; ​很明显&#xff0c;我就是犯了第一种错误。 网上的修改方法&#xff1a; 我觉得按道理哈&#xff0c;确实&#xff0c;蓝色部分应该是可以把问题解决了的​。​但是我没有解决&#xff0c;因为我犯了另外一个错…...

如何在Mac上恢复格式化硬盘的数据?

“嗨&#xff0c;我格式化了我的一个Mac硬盘&#xff0c;而没有使用Time Machine备份数据。这个硬盘被未知病毒感染了&#xff0c;所以我把它格式化为出厂设置。但是&#xff0c;我忘了备份我的文件。现在&#xff0c;我想恢复格式化的硬盘驱动器并恢复我的文档&#xff0c;您能…...

华为OD机试 - 手机App防沉迷系统(Java 2024 C卷 100分)

华为OD机试 2024C卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷C卷&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测试…...

搜维尔科技:光学动作捕捉系统用于城市公共安全智慧感知实验室

用户名称&#xff1a;西安科技大学 主要产品&#xff1a;Optitrack Priime41 光学动作捕捉系统&#xff08;8头&#xff09; 在6米8米的空间内&#xff0c;通过8个Optitrack Priime41光学动作捕捉镜头&#xff0c;对人体动作进行捕捉&#xff0c;得到用户想要的人体三维空间坐…...

保研面试408复习 4——操作系统、计网

文章目录 1、操作系统一、文件系统中文件是如何组织的&#xff1f;二、文件的整体概述三、UNIX外存空闲空间管理 2、计算机网络一、CSMA/CD 协议&#xff08;数据链路层协议&#xff09;二、以太网MAC帧MTU 标记文字记忆&#xff0c;加粗文字注意&#xff0c;普通文字理解。 1、…...

实战攻防中关于文档的妙用

一、PPT钓鱼 简单制作一个用于钓鱼的PPTX文件 一般那种小白不知道PPT也能拿来钓鱼&#xff0c;这里主要是借用PPT中的”动作按钮”, 我们在插入的地方&#xff0c;选择“动作按钮” 然后在弹出的窗口处&#xff1a; 比如填入上线CS的语句&#xff1a;powershell.exe -nop -w …...

【使用ChatGPT的API之前】OpenAI API提供的可用模型

文章目录 一. ChatGPT基本概念二. OpenAI API提供的可用模型1. InstructGPT2. ChatGPT3. GPT-4 三. 在OpenAI Playground中使用GPT模型-ing 在使用GPT-4和ChatGPT的API集成到Python应用程序之前&#xff0c;我们先了解ChatGPT的基本概念&#xff0c;与OpenAI API提供的可用模型…...

【C语言】模拟实现深入了解:字符串函数

&#x1f525;引言 本篇将模拟实现字符串函数&#xff0c;通过底层了解更多相关细节 &#x1f308;个人主页&#xff1a;是店小二呀 &#x1f308;C语言笔记专栏&#xff1a;C语言笔记 &#x1f308;C笔记专栏&#xff1a; C笔记 &#x1f308;喜欢的诗句:无人扶我青云志 我自…...

钩子函数onMounted定义了太多访问MySQL的操作 导致数据库异常

先放几种后端遇到的异常&#xff0c;多数和数据库有关 pymysql.err.InternalError: Packet sequence number wrong - got 102 expected 1 127.0.0.1 - - [09/May/2024 17:49:37] "GET /monitorLastTenList HTTP/1.1" 500 AttributeError: NoneType object has no at…...

Excel文件解析---超大Excel文件读写

1.使用POI写入 当我们想在Excel文件中写入100w条数据时&#xff0c;使用XSSFWorkbook进行写入时会发现&#xff0c;只有将100w条数据全部加载到内存后才会用write()方法统一写入&#xff0c;效率很低&#xff0c;所以我们引入了SXXFWorkbook进行超大Excel文件读写。 通过设置 …...

TypeScript基础:类型系统介绍

TypeScript基础&#xff1a;类型系统介绍 引言 TypeScript&#xff0c;作为JavaScript的一个超集&#xff0c;引入了类型系统&#xff0c;这为开发大型应用程序带来了诸多好处。本文将介绍TypeScript类型系统的基础知识&#xff0c;帮助初学者理解其概念和用法。 基础知识 …...

【Unity】Unity项目转抖音小游戏(一) 项目转换

UnityWEBGL转抖音小游戏流程 业务需求&#xff0c;开始接触一下抖音小游戏相关的内容&#xff0c;开发过程中记录一下流程。 相关参考&#xff1a; 抖音文档&#xff1a;https://developer.open-douyin.com/docs/resource/zh-CN/mini-game/develop/guide/game-engine/rd-to-SC…...

element-ui 中修改loading加载样式

element-ui 中的 loading 加载功能&#xff0c;默认是全屏加载效果 设置局部&#xff0c;需要自定义样式或者修改样式&#xff0c;方法如下&#xff1a; import { Loading } from element-uiVue.prototype.$baseLoading (text) > {let loadingloading Loading.service({…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

SCAU期末笔记 - 数据分析与数据挖掘题库解析

这门怎么题库答案不全啊日 来简单学一下子来 一、选择题&#xff08;可多选&#xff09; 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘&#xff1a;专注于发现数据中…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)

目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关&#xff0…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...