【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改
文章目录
- 1.模拟实现list
- 1.1构造函数
- 1.2迭代器类的实现
- 1.3运算符重载
- 1.4增删查改
1.模拟实现list
list使用文章
1.1构造函数
析构函数
在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node,用于表示链表的节点。该结构体包含了指向前一个节点和后一个节点的指针以及节点的值。在list中保存了链表的头节点指针和链表长度大小。
namespace my_list
{ //用类模板定义一个list结点template<class T>struct _list_node{//list结点的构造函数,T()作为缺省值,当未转参时调用_list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}//list_node的成员函数,list为带头双向循环链表_list_node* _prev;_list_node* _next;T _val;};//用类模拟实现listtemplate<class T>class list{private:typedef _list_node<T> Node;public://list的构造函数,初始化头节点指针list(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}//析构函数~list(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;delete _head;_head = nullptr;}private://成员函数为list的头节点指针,和链表长度Node* _head;size_t _size;};
}
1.2迭代器类的实现
因为list的底层实现和之前的vector和string不同,vector和string是数组和顺序表,而list底层是链表。而对于数组和顺序表,我们可以直接使用指针来实现其迭代器,但是对于list类型就无法使用指针来实现它的迭代器,因为迭代器++无法访问到他的下一个节点。所以我们这里建立一个迭代器的结构体,用来封装node指针,来实现list的专属迭代器
这段代码定义了一个名为__list_iterator的迭代器结构体,用于遍历链表。该结构体模板有三个模板参数:T表示链表中节点的数据类型,Ref表示引用类型T&,Ptr表示指针类型 T* _node:指向链表节点的指针。构造函数__list_iterator(Node* node):用于初始化迭代器对象,将指针node赋值给_node。通过_node就可以实现各种操作符重载。
定义了一个迭代器结构体,用于在链表中进行遍历和操作。通过重载运算符,可以使用迭代器对象像指针一样访问链表中的元素。
//使用类进行封装Node*,来实现list的专属迭代器
//list迭代器和一些内置类型迭代器不一样,++无法准确访问到下一个位置
//typedef __list_iterator<T, T&> iterator;
//typedef __list_iterator<T, const T&> iterator;
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){}//重载*Ref operator*(){return _node->_val;}//重载->Ptr operator->(){return &_node->_val;}//重载前置++self& operator++(){_node = _node->_next;return *this;}//重载后置++self operator++(int){__list_iterator<T> 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& it) const{return _node != it._node;}//重载==bool operator==(const self& it) const{return _node == it._node;}
};
通过建立一个新的结构体来重载迭代器,我们即可实现list专属迭代器对其链表进行++、- -等操作。
typedef __list_iterator<T, T&, T*> iterator;
typedef __list_iterator<T, const T&, const T*> const_iterator;//list迭代器实现
iterator begin()
{//隐式类型转换,内置类型转换为自定义类型,实现迭代器功能//return _head->_next;return iterator(_head->_next);
}iterator end()
{//return _head;return iterator(_head);
}const_iterator begin() const
{//return _head->_next;return const_iterator(_head->_next);
}const_iterator end() const
{//return _head;return const_iterator(_head);
}
1.3运算符重载
迭代器的运算符重载在上面的代码中,已经都基本实现了。
赋值运算符重载函数operator=首先创建了一个临时的链表对象lt,并将传入的链表对象的副本赋值给lt。然后,调用swap函数,将当前链表对象和临时链表对象进行交换。这样做的原因是为了实现异常安全的赋值操作。通过将传入的链表对象的副本赋值给临时链表对象,可以确保在交换过程中不会影响到传入的链表对象。 最后,返回当前链表对象的引用。
通过这样的实现逻辑,可以实现链表对象之间的赋值操作,并且保证在异常发生时不会破坏数据的完整性。
//交换
void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}//赋值运算符重载
list<T>& operator=(list<T> lt)//list& operator=(list lt)
{swap(lt);return *this;
}
1.4增删查改
push_back
和带头双向循环链表的尾插一样。首先,创建一个新的链表节点newnode,节点的值为传入的参数x。然后,获取到链表的尾指针tail,即头节点的前一个节点。
接着,将新节点newnode插入到链表的尾部。首先,将新节点的前驱指针指向尾节点tail,将尾节点的后继指针指向新节点。这样就将新节点连接到了链表的尾部。
然后,将新节点的后继指针指向头节点,将头节点的前驱指针指向新节点。这样就将新节点连接到了链表的头部。
//尾插
void push_back(const T& x)
{//创建一个新的链表结点,且获取到链表的尾指针Node* newnode = new Node(x);Node* tail = _head->_prev;//连接尾结点newnode->_prev = tail;tail->_next = newnode;//连接头节点_head->_prev = newnode;newnode->_next = _head;++_size;
}
insert
和上面的逻辑类似。
//在pos位置之前插入
iterator insert(iterator pos, const T& x)
{Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;
}
erase
首先,通过断言判断传入的迭代器pos不等于链表的末尾迭代器。如果等于末尾迭代器,表示要删除的节点不存在,会导致错误。然后,根据传入的迭代器pos获取到要删除的节点cur,以及其前驱节点prev和后继节点next。
接着,将前驱节点的后继指针指向后继节点,将后继节点的前驱指针指向前驱节点。这样就将要删除的节点从链表中断开。然后,释放要删除的节点的内存。还要将链表的大小减1。
为了避免迭代器失效,返回下一个节点的指针作为新的迭代器。这样可以保证在删除节点后,仍然可以使用返回的迭代器进行遍历和操作。
//删除
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;--_size;//为了避免迭代器失效,返回下一个结点指针return next;
}
完整实现
#pragma once#include<assert.h>namespace my_list
{ //用类模板定义一个list结点template<class T>struct _list_node{//list结点的构造函数,T()作为缺省值,当未转参时调用_list_node(const T& val = T()):_next(nullptr), _prev(nullptr), _val(val){}//list_node的成员函数,list为带头双向循环链表_list_node* _prev;_list_node* _next;T _val;};//使用类进行封装Node*,来实现list的专属迭代器//list迭代器和一些内置类型迭代器不一样,++无法准确访问到下一个位置//typedef __list_iterator<T, T&> iterator;//typedef __list_iterator<T, const T&> iterator;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){}//重载*Ref operator*(){return _node->_val;}//重载->Ptr operator->(){return &_node->_val;}//重载前置++self& operator++(){_node = _node->_next;return *this;}//重载后置++self operator++(int){__list_iterator<T> 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& it) const{return _node != it._node;}//重载==bool operator==(const self& it) const{return _node == it._node;}};//实现const类型迭代器/*template<class T>struct __list_const_iterator{typedef list_node<T> Node;Node* _node;__list_const_iterator(Node* node):_node(node){}const T& operator*(){return _node->_val;}__list_const_iterator<T>& operator++(){_node = _node->_next;return *this;}__list_const_iterator<T> operator++(int){__list_const_iterator<T> tmp(*this);_node = _node->_next;return tmp;}bool operator!=(const __list_const_iterator<T>& it){return _node != it._node;}bool operator==(const __list_const_iterator<T>& it){return _node == it._node;}};*///用类模拟实现listtemplate<class T>class list{private:typedef _list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;//list迭代器实现iterator begin(){//隐式类型转换,内置类型转换为自定义类型,实现迭代器功能//return _head->_next;return iterator(_head->_next);}iterator end(){//return _head;return iterator(_head);}const_iterator begin() const{//return _head->_next;return const_iterator(_head->_next);}const_iterator end() const{//return _head;return const_iterator(_head);}//初始化void empty_init(){_head = new Node;_head->_prev = _head;_head->_next = _head;_size = 0;}//list的构造函数,初始化头节点指针list(){empty_init();}//拷贝构造list(const list<T>& lt)//list(const list& lt){empty_init();for (auto& e : lt){push_back(e);}}//交换void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}//赋值运算符重载list<T>& operator=(list<T> lt)//list& operator=(list lt){swap(lt);return *this;}//析构函数~list(){clear();delete _head;_head = nullptr;}//清理void clear(){iterator it = begin();while (it != end()){it = erase(it);}_size = 0;}//尾插void push_back(const T& x){//创建一个新的链表结点,且获取到链表的尾指针Node* newnode = new Node(x);Node* tail = _head->_prev;//连接尾结点newnode->_prev = tail;tail->_next = newnode;//连接头节点_head->_prev = newnode;newnode->_next = _head;++_size;//insert(end(), x);}//头插void push_front(const T& x){insert(begin(), x);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}//在pos位置之前插入iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;cur->_prev = newnode;newnode->_prev = prev;++_size;return newnode;}//删除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;--_size;//为了避免迭代器失效,返回下一个结点指针return next;}//返回sizesize_t size(){/*size_t sz = 0;iterator it = begin();while (it != end()){++sz;++it;}return sz;*/return _size;}private://成员函数为list的头节点指针,和链表长度Node* _head;size_t _size;};//打印函数void print(const list<int>& lt){list<int>::const_iterator it = lt.begin();while (it != lt.end()){// (*it) += 1;cout << *it << " ";++it;}cout << endl;}
}
测试代码
#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>
#include<list>
using namespace std;#include"list.h"void test_list1()
{//list<int> lt;//lt.push_back(1);//lt.push_back(2);//lt.push_back(3);//lt.push_back(4);//for (auto e : lt)//{// cout << e << " ";//}//cout << endl;my_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);my_list::list<int>::iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";++it;}cout << endl;auto itt = lt.begin();while (itt != lt.end()){++(*itt);++itt;}for (auto e: lt){cout << e << " ";}cout << endl;
}struct A
{A(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};void test_list2()
{my_list::list<A> lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));auto it = lt.begin();while (it != lt.end()){//cout << *(it)._a1 << " " << *(it)._a2 <<endl;cout << it->_a1 << " " << it->_a2 << endl;++it;}cout << endl;
}void test_list3()
{my_list::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);for (auto e : lt){cout << e << " ";}cout << endl;lt.push_front(5);lt.push_front(6);print(lt);lt.pop_front();lt.pop_back();print(lt);lt.clear();lt.push_back(10);lt.push_back(20);lt.push_back(30);lt.push_back(40);print(lt);cout << lt.size() << endl;}int main()
{//test_list1();//test_list2();test_list3();return 0;
}
相关文章:

【C++】STL——list的模拟实现、构造函数、迭代器类的实现、运算符重载、增删查改
文章目录 1.模拟实现list1.1构造函数1.2迭代器类的实现1.3运算符重载1.4增删查改 1.模拟实现list list使用文章 1.1构造函数 析构函数 在定义了一个类模板list时。我们让该类模板包含了一个内部结构体_list_node,用于表示链表的节点。该结构体包含了指向前一个节点…...
vscode 插件::EIDE
最新最全 VSCODE 插件推荐(2023版)_vscode_白墨石-华为云开发者联盟 (csdn.net) 超好用的开发工具-VScode插件EIDE_vscode eide_桃成蹊2.0的博客-CSDN博客 Setup | Embedded IDE For VSCode (em-ide.com)...
Python 网络编程
Python 网络编程 Python 提供了两个级别访问的网络服务: 低级别的网络服务支持基本的 Socket,它提供了标准的 BSD Sockets API,可以访问底层操作系统 Socket 接口的全部方法。高级别的网络服务模块 SocketServer, 它提供了服务器…...

SQL 数据科学:了解和利用联接
推荐:使用 NSDT场景编辑器助你快速搭建可编辑的3D应用场景 什么是 SQL 中的连接? SQL 联接允许您基于公共列合并来自多个数据库表的数据。这样,您就可以将信息合并在一起,并在相关数据集之间创建有意义的连接。 SQL 中的连接类型…...
(统计学习方法|李航)第五章决策树——四五节:决策树的剪枝,CART算法
目录 一,决策数的剪枝 二,CART算法 1.CART生成 (1)回归树的生成 (2)分类树的生成 2.CART剪枝 (1)剪枝,形成一个子树序列 (2)在剪枝得到的子…...
C语言--结构体定义
整型数,浮点数,字符串是分散的数据表示,有时候我们需要很多类型表示一个整体,比如学生信息。 数组是元素类型一样的数据集合,如果是元素类型不同的数据集合,就要用到结构体 结构体一般是个模板,…...

解决Element Plus中Select在El Dialog里层级过低的问题(修改select选项框样式)
Element Plus是Vue.js的一套基于Element UI的组件库,提供了丰富的组件用于构建现代化的Web应用程序。其中,<el-select>是一个常用的下拉选择器组件,但在某些情况下,当<el-select>组件嵌套在<el-dialog>…...

【数据结构】二叉树 链式结构的相关问题
本篇文章来详细介绍一下二叉树链式结构经常使用的相关函数,以及相关的的OJ题。 目录 1.前置说明 2.二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层次遍历 3.节点个数相关函数实现 3.1 二叉树节点个数 3.2 二叉树叶子节点个数 3.3 二叉树第k层节点个数 3…...

【无标题】云原生在工业互联网的落地及好处!
什么是工业互联网? 工业互联网(Industrial Internet)是新一代信息通信技术与工业经济深度融合的新型基础设施、应用模式和工业生态,通过对人、机、物、系统等的全面连接,构建起覆盖全产业链、全价值链的全新制造和服务…...
人工智能在心电信号分类中的应用
目录 1 引言 2 传统机器学习中的特征提取与选择 3 深度学习中的特征提取与选择...

【Linux 网络】网络层协议之IP协议
IP协议 IP协议所处的位置网络层要解决的问题IP协议格式分片与组装网段划分特殊的IP地址IP地址的数量限制私网IP地址和公网IP地址路由 IP协议所处的位置 IP指网际互连协议,Internet Protocol的缩写,是TCP/IP体系中的网络层协议。 网络层要解决的问题 网络…...
.meta 文件
.meta 文件的作用简单来说是建立 Unity 与资源之间的“桥梁”。 在游戏中引用一个游戏资源,Unity 并不是直接按照文件的路径或者名称,而是使用一个独一无二的 GUID 来指向工程里该资源文件。 这个 GUID 就是存储在 Unity 工程为每一个资源和文件…...

CRITICAL_SECTION 用法
#include <stdio.h> #include <windows.h> typedef RTL_CRITICAL_SECTION CRITICAL_SECTION; CRITICAL_SECTION g_cs; //声明关键段 // 共享资源 char g_cArray[10]; unsigned int g_Count 0; DWORD WINAPI ThreadProc10(LPVOID pParam) { // 进入临界区 …...

汇川运动控制产品故障排查
针对汇川伺服产品(IS600/IS620)的基本检测和一些出现频率较高的故障进行检测判断方法,适用于服务人员在现场排查/判断机器故障时,准确定位问题。 一、简单故障排查 注1:接线错误:1、UVW相序是否正确&#…...

【Groups】50 Matplotlib Visualizations, Python实现,源码可复现
详情请参考博客: Top 50 matplotlib Visualizations 因编译更新问题,本文将稍作更改,以便能够顺利运行。 1 Dendrogram 树状图根据给定的距离度量将相似的点组合在一起,并根据点的相似性将它们组织成树状的链接。 新建文件Dendrogram.py: …...

windows安装kafka配置SASL-PLAIN安全认证
目录 1.Windows安装zookeeper: 1.1下载zookeeper 1.2 解压之后如图二 1.3创建日志文件 1.4复制 “zoo_sample.cfg” 文件 1.5更改 “zoo.cfg” 配置 1.6新建zk_server_jaas.conf 1.7修改zkEnv.cmd 1.8导入相关jar 1.9以上配置就配好啦,接下来启…...

【Linux】五种IO模型
文章目录 1. IO基本概念2. 五种IO模型2.1 五个钓鱼的例子2.2 五种IO模型2.2.1 阻塞IO2.2.2 非阻塞IO2.2.3 信号驱动IO2.2.4 IO多路转接2.2.5 异步IO 1. IO基本概念 认识IO IO就是输入和输出,在冯诺依曼体系结构中,将数据从输入设备拷贝到内存就叫输入&am…...

SCT82A30DHKR_5.5V-100V Vin同步降压控制器
SCT82A30是一款100V电压模式控制同步降压控制器,具有线路前馈。40ns受控高压侧MOSFET的最小导通时间支持高转换比,实现从48V输入到低压轨的直接降压转换,降低了系统复杂性和解决方案成本。如果需要,在低至6V的输入电压下降期间&am…...

备忘录模式(C++)
定义 在不破坏封装性的前提下,捕获一-个对象的内部状态,并在该对象之外保存这个状态。这样以后就可以将该对象恢复到原先保存的状态。 应用场景 ➢在软件构建过程中,某些对象的状态在转换过程中,可能由于某种需要,要…...
二叉排序树(二叉查找树)
二叉排序树(二叉查找树)的性质: 若它的左子树不为空,则左子树上所有结点的值均小于它的根结点的值。若它的右子树不为空,则右子树上所有结点的值均大于它的根将诶点的值。它的左、右子树也分别为二叉排序树。 对二叉…...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...

shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

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

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...

【 java 虚拟机知识 第一篇 】
目录 1.内存模型 1.1.JVM内存模型的介绍 1.2.堆和栈的区别 1.3.栈的存储细节 1.4.堆的部分 1.5.程序计数器的作用 1.6.方法区的内容 1.7.字符串池 1.8.引用类型 1.9.内存泄漏与内存溢出 1.10.会出现内存溢出的结构 1.内存模型 1.1.JVM内存模型的介绍 内存模型主要分…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...

《Docker》架构
文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器,docker,镜像,k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...