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

C++ list模拟实现

list模拟实现代码:

namespace djx
{template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}};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->_data;}Ptr operator->(){return &_node->_data;}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& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};template<class T>class list{typedef list_node<T> Node;public:typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}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);}}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;}~list(){clear();delete _head;_head = nullptr;}void clear(){iterator it = begin();while (it != end()){it = erase(it);}}void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}iterator insert(iterator pos, const T& x){Node* cur = pos._node;Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;return newnode;}iterator erase(iterator pos){Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;delete cur;prev->_next = next;next->_prev = prev;_size--;return next;}size_t size(){return _size;}private:Node* _head;size_t _size;};
}

源码中的list实现为带头双向链表

 

list类的对象有两个成员:指向头结点的指针_head,统计数据个数的_size

在模拟实现list之前,需要先模拟实现结点类,迭代器类

结点类:三个成员,_data _prev _next实现成struct(也是类,不过与class不同的是,它的成员都是公开的,都可以在类外访问),因为这三个成员,在迭代器类中都要使用访问,设it是迭代器,*it就会返回结点中值(_data)的引用,it++(要访问结点中的_next) , it--(要访问结点中的_prev)

    template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x = T())//x是匿名对象的引用,const延长了匿名对象的生命周期,x销毁,匿名对象才销毁,匿名对象会调用它的构造函数,完成初始化:_data(x),_prev(nullptr),_next(nullptr){}};

要写构造函数:list类中的push_back插入数据时,需要new一个结点,并传数值

                         调用构造函数时,若是直接使用编译器生成的默认构造函数,则无法传参

构造函数的参数设计成缺省参数:有传实参过来就使用此值,没有传参过来就用匿名对象去拷贝构造_data,使用匿名对象去拷贝构造_data的情形:list类中的无参构造函数-->让list中的成员变量_head指向一个new出来的头结点,头结点中不存储任何有效数据,故而new时无需传参

迭代器类:一个成员 _node(结点的指针)

设计成struct:在list类中设计insert和erase时,传参给它们的是iterator迭代器,我们要使用迭代器中的成员变量(结点的指针)即要访问迭代器中的成员,那么设计成struct会比设计成class类方便不少

list的迭代器与vector,string类不同,在模拟实现vector和string的迭代器时,它们可以用原生指针来实现,因为完美契合原生指针的行为,但是模拟实现list的迭代器时,它必须设计成一个类,是对原生指针的封装,原因:

若是list的迭代器就用原生指针来实现,那么*it(it是一个迭代器)得到的不是数据,而是结点

it++ 不能走向下一个数据,故而需要对原生指针进行封装,让*it得到数据,it++,走向下一个数据

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)//要写带参的构造,因为在list类中实现begin()时,返回值的类型是迭代器,但是我们返回的可以是结点的指针,单参数的构造函数支持隐式类型转换,也可以是迭代器,但是此迭代器中的成员变量(结点的指针)需要和第一个结点的指针一样:_node(node){}Ref operator*()//Ref可以是T&(普通迭代器) const T& (const迭代器){return _node->_data;}Ptr operator->()Ptr可以是T* (普通迭代器) const T* (const迭代器){return &_node->_data;}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& s){return _node != s._node;}bool operator==(const self& s){return _node == s._node;}};

迭代器有非const对象调用的,也有const对象调用的,二者的区别仅仅是能否修改的问题,*迭代器返回的是数据的引用,const对象调用的迭代器返回的也是数据的引用,但是const修饰的

迭代器-> 返回的是数据的地址,const对象调用的迭代器返回的是const修饰的数据地址

(迭代器可以看作是模拟原生指针的行为,若是数据为自定义类型,那么迭代器->就可以访问到自定义类型对象中的成员,实际上看成是原生指针的迭代器-> 无法做到,但是对原生指针封装而出现的迭代器可以做到,只要迭代器->返回的是数据的指针,那么有了自定义类型对象指针,不就可以访问它里面的成员了吗)

综上来看,我们只需要写一份迭代器类的模板,根据实例化参数的不同,生成不同的迭代器

迭代器需要三个模板参数:T(迭代器类中的成员变量是结点的指针,结点实例化需要)

模板参数 Ref  : 迭代器类中重载*运算符所用,重载*运算符的函数要返回数据的引用,而若是const对象的迭代器解引用,就要用const去修饰返回值

模板参数Ptr :迭代器类中重载->运算符所用,重载->运算符的函数返回数据的指针,而若是const对象的迭代器->,也要用const去修饰返回值

那么在list类中,设计普通迭代器,const对象调用的迭代器时,就可以用迭代器类的模板,实例化参数不同就会是完全不同的类型,普通迭代器用迭代器类的模板实例化,传参 T   T&   T*

const对象调用的迭代器用迭代器类的模板实例化,传参 T  const T&   const T*

构造函数:

1 无参的构造

    让list对象中的成员变量_head指向一个头指针(双向循环)

    参照源码list的实现:

 

        void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;_size = 0;}list(){empty_init();}

2 拷贝构造(深拷贝)

        list(const list<T>& lt){empty_init();for (auto e : lt){push_back(e);}}

析构函数:

        ~list(){clear();delete _head;//释放头结点_head = nullptr;}void clear()//清除数据{iterator it = begin();while (it != end()){it = erase(it);}}

赋值重载:

        void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)///lt是实参的深拷贝,lt销毁会释放掉原本由*this申请的空间{swap(lt);//交换*this和ltreturn *this;}

迭代器:

        typedef __list_iterator<T, T&, T*> iterator;typedef __list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin()const{return _head->_next;}const_iterator end()const{return _head;}

测试1:

void test1()
{djx::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);djx::list<int>:: iterator it = lt.begin();while (it != lt.end()){*it += 20;cout << *it << " ";it++;}cout << endl;for (auto e : lt){cout << e << " ";}cout << endl;
}

测试2:

void test2()
{djx::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);djx::list<int> lt1(lt);//拷贝构造for (auto e : lt){cout << e << " ";}cout << endl;for (auto e : lt1){cout << e << " ";}cout << endl;djx::list<int> lt2;lt2.push_back(100);lt2.push_back(200);lt2.push_back(300);lt2.push_back(400);lt2.push_back(500);lt1 = lt2;//赋值重载for (auto e : lt1){cout << e << " ";}cout << endl;for (auto e : lt2){cout << e << " ";}cout << endl;}

 

 

插入:

 1 push_back

        void push_back(const T& x){insert(end(), x);}

2 push_front

        void push_front(const T& x){insert(begin(), x);}

3 insert

        iterator insert(iterator pos, const T& x){Node* cur = pos._node;//当前节点的指针Node* newnode = new Node(x);Node* prev = cur->_prev;prev->_next = newnode;newnode->_prev = prev;newnode->_next = cur;cur->_prev = newnode;_size++;return newnode;//单参数的构造函数支持隐式类型转换//或者写成:iterator(newnode)}

删除:

1 pop_back

        void pop_back(){erase(--end());}

2 pop_front

        void pop_front(){erase(begin());}

3 erase

        iterator erase(iterator pos){Node* cur = pos._node;Node* next = cur->_next;Node* prev = cur->_prev;delete cur;prev->_next = next;next->_prev = prev;_size--;return next;//返回下一个数据的地址}

测试3:

struct AA
{AA(int a1 = 0, int a2 = 0):_a1(a1), _a2(a2){}int _a1;int _a2;
};void test3()
{djx::list<AA> lt;lt.push_back(AA(1, 1));lt.push_back(AA(2, 2));lt.push_back(AA(3, 3));djx::list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << " "<<(*it)._a2<<endl;cout << it->_a1 << " " << it->_a2 << endl;it++;}cout << endl;
}

题外:

 设计一个打印函数,打印任意list对象

template<typename T>//不可以用class
void print_list(const djx:: list<T>& lt)
{//list<T>未实例化的类模板,编译器不能去它里面去找//编译器就无法list<T>::const_iterator是内嵌类型,还是静态成员变量//前面加一个typename就是告诉编译器,这里是一个类型,等list<T>实例化,再去类里面找typename djx::list<T>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << " ";it++;}cout << endl;
}

打印任意容器

template<typename Container>
void print_container(const Container& con)
{typename Container::const_iterator it = con.begin();while (it != con.end()){cout << *it << " ";it++;}cout << endl;
}

测试4:

void test4()
{djx::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);
}

测试5:

void test5()
{djx::list<int> lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_container(lt);djx::list<string> lt1;lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");lt1.push_back("1111111111111");//print_list(lt1);print_container(lt1);vector<string> v;v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");v.push_back("222222222222222222222");print_container(v);}

 

 

相关文章:

C++ list模拟实现

list模拟实现代码&#xff1a; namespace djx {template<class T>struct list_node{T _data;list_node<T>* _prev;list_node<T>* _next;list_node(const T& x T()):_data(x),_prev(nullptr),_next(nullptr){}};template<class T,class Ref,class Pt…...

中国建筑出版传媒许少辉博士八一新书乡村振兴战略下传统村落文化旅游设计日京东当当畅销榜自由营九三学

中国建筑出版传媒许少辉博士八一新书乡村振兴战略下传统村落文化旅游设计日京东当当畅销榜自由营九三学...

C语言(第三十二天)

1. 递归是什么&#xff1f; 递归是学习C语言函数绕不开的一个话题&#xff0c;那什么是递归呢&#xff1f; 递归其实是一种解决问题的方法&#xff0c;在C语言中&#xff0c;递归就是函数自己调用自己。 写一个史上最简单的C语言递归代码&#xff1a; #include <stdio.h>…...

arcgis+postgresql+postgis使用介绍

关于arcgis在postgresql创建地理数据库我分享一下自己的经历&#xff1a; 众所周知&#xff0c;arcgis如果在oracle中创建地理数据库&#xff0c;必须要使用ArcToolbox里面的地理数据库工具去创建&#xff0c;在里面发现它还可以创建sql_server, postgresql数据库类型&#xf…...

机器视觉之开运算和闭运算

开运算&#xff08;Opening&#xff09;和闭运算&#xff08;Closing&#xff09;是数学形态学中常用的图像处理操作&#xff0c;通常用于去除图像中的噪声、连接物体、分离物体等操作。它们分别由两个基本操作组成&#xff1a;腐蚀&#xff08;Erosion&#xff09;和膨胀&…...

【python爬虫】—URL管理器的实现

python爬虫-url管理器 url管理器的作用python实现 url管理器的作用 在Python爬虫中&#xff0c;URL管理器&#xff08;URL Manager&#xff09;是一个重要的组件&#xff0c;用于有效管理爬取过程中所涉及的URL。它主要负责以下几个方面的任务&#xff1a; URL去重&#xff08;…...

Oracle 19C RAC安装PSU oui-patch.xml权限错误

Oracle 19C RAC安装PSU时&#xff0c;节点2安装失败&#xff0c;经排查错误原因为oui-patch.xml文件权限错误。 Oracle官方建议oui-patch.xml文件权限&#xff0c;改成660或者666&#xff1a; chmod 660 oui-patch.xml权限修改完成后&#xff0c;安装psu还是失败&#xff0c;…...

华为数通方向HCIP-DataCom H12-821题库(单选题:161-180)

第161题 以下关于 URPF(Unicast Reverse Path Forwarding) 的描述&#xff0c; 正确的是哪一项 A、部署了严格模式的 URPF&#xff0c;也能够可以同时部署允许匹配缺省路由模式 B、如果部署松散模式的 URPF&#xff0c;默认情况下不需要匹配明细路由 C、如果部署松散模式的…...

ResNet详解:网络结构解读与PyTorch实现教程

目录 一、深度残差网络&#xff08;Deep Residual Networks&#xff09;简介深度学习与网络深度的挑战残差学习的提出为什么ResNet有效&#xff1f; 二、深度学习与梯度消失问题梯度消失问题定义为什么会出现梯度消失&#xff1f;激活函数初始化方法网络深度 如何解决梯度消失问…...

ChatGPT 随机动态可视化图表分析

动态可视化图表分析实例如下图: 这样的动态可视化图表可以使用ChatGPT OpenAI 来实现。 给ChatGPT发送指令: 你现在是一个数据分析师,请使用HTML,JS,Echarts,来完成一个动态条形图,条形图方向横向,数据可以随机生成,并且随机生成10个不同的商品名称,每个类别分别用…...

国标视频融合云平台EasyCVR视频汇聚平台的应用场景及其功能说明

一、平台简介 EasyCVR国标视频融合云平台是一款基于端-边-云一体化架构的视频融合AI智能分析网关平台。EasyCVR平台支持视频汇聚、融合管理&#xff0c;兼容多类型设备、多协议接入。其提供的视频功能包括&#xff1a;视频监控、无插件直播录像、云存储、检索回放、智能告警、…...

后端面试话术集锦第三篇:spring cloud 面试话术

🚗后端面试集锦目录 💖后端面试话术集锦第 1 篇:spring面试话术💖 💖后端面试话术集锦第 2 篇:spring boot面试话术💖 💖后端面试话术集锦第 3 篇:spring cloud面试话术💖 💖后端面试话术集锦第 4 篇:ElasticSearch面试话术💖 💖后端面试话术集锦第 5 …...

React 18 选择 State 结构

参考文章 选择 State 结构 构建良好的 state 可以让组件变得易于修改和调试&#xff0c;而不会经常出错。以下是在构建 state 时应该考虑的一些建议。 构建 state 的原则 当编写一个存有 state 的组件时&#xff0c;需要选择使用多少个 state 变量以及它们都是怎样的数据格…...

LNMT与动静分离

目录 一、LNMT 一、部署tomcat 二、部署nginx 三、部署mariadb 四、配置nginx 二、操作流程及步骤 一、在第一台机器上进入 vim /etc/nginx/nginx.conf 更改配置文件 二、并查看端口是否成功启动 三、验证 四、再次来到网页验证 五、动静分离&#xff08;修改配置…...

【java】LinkedList 和 ArrayList的简介与对比

Java LinkedList和 ArrayList 在使用上&#xff0c;几乎是一样的。由于LinkedList是基于双向链表的&#xff0c;会多出list.getFirst();获取头部元素等方法 链表&#xff08;Linked list&#xff09;是一种常见的基础数据结构&#xff0c;是一种线性表&#xff0c;但是并不会按…...

机器学习基础14-算法调参(基于印第安糖尿病Pima数据集)

机器学习的模型都是参数化的&#xff0c;可以通过调参来提高模型的准确度。 模型有很多参数&#xff0c;如何找到最佳的参数组合&#xff0c;可以把它当作一个查询问题来处理&#xff0c;但是调整参数到何时为止呢&#xff1f;应该遵循偏差和方差协调的原则。 接下来将介绍在 s…...

ASUS华硕天选4笔记本电脑FA507XV原厂Windows11系统22H2

天选四FA507X原装系统自带所有驱动、出厂主题壁纸LOGO、Office办公软件 华硕电脑管家、奥创控制中心等预装程序&#xff0c;恢复出厂状态W11 链接&#xff1a;https://pan.baidu.com/s/1SPoFW7wR5KawGu-yMckNzg?pwdayxd 提取码&#xff1a;ayxd...

IET独立出版 | EI检索 | 2023年第三届机械、航空航天与汽车工程国际会议

会议简介 Brief Introduction 2023年第三届机械、航空航天与汽车工程国际会议&#xff08;CMAAE 2023&#xff09; 会议时间&#xff1a;2023年12月8 -10日 召开地点&#xff1a;中国南京 大会官网&#xff1a;www.cmaae.org 航天是当今世界最具挑战性和广泛带动性的高技术领域…...

【Pytorch】CUDA error: no kernel image is available for execution on the device

记录一下pytorch安装的cuda版本和GPU cuda不一致的解决。 RuntimeError: CUDA error: no kernel image is available for execution on the device 一般就是pytorch和cuda安装的不匹配。 如果我安装的torch配的cuda信息如下&#xff0c; torch.__version__: 1.8.1cu102 tor…...

dolphinschedule配置企微告警服务(WeChat群组)

一、前置说明 ds配置好工作流后&#xff0c;比较重要的一个就是上线后的监控报警服务&#xff0c;如果你是基于企微作为协同办公的&#xff0c;WeChat群组预警必须是要安排上的&#xff0c;文章基于自建应用配合群组方式构建预警群&#xff0c;接入后&#xff0c;任务成功或者…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

8k长序列建模,蛋白质语言模型Prot42仅利用目标蛋白序列即可生成高亲和力结合剂

蛋白质结合剂&#xff08;如抗体、抑制肽&#xff09;在疾病诊断、成像分析及靶向药物递送等关键场景中发挥着不可替代的作用。传统上&#xff0c;高特异性蛋白质结合剂的开发高度依赖噬菌体展示、定向进化等实验技术&#xff0c;但这类方法普遍面临资源消耗巨大、研发周期冗长…...

WEB3全栈开发——面试专业技能点P2智能合约开发(Solidity)

一、Solidity合约开发 下面是 Solidity 合约开发 的概念、代码示例及讲解&#xff0c;适合用作学习或写简历项目背景说明。 &#x1f9e0; 一、概念简介&#xff1a;Solidity 合约开发 Solidity 是一种专门为 以太坊&#xff08;Ethereum&#xff09;平台编写智能合约的高级编…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...

MFE(微前端) Module Federation:Webpack.config.js文件中每个属性的含义解释

以Module Federation 插件详为例&#xff0c;Webpack.config.js它可能的配置和含义如下&#xff1a; 前言 Module Federation 的Webpack.config.js核心配置包括&#xff1a; name filename&#xff08;定义应用标识&#xff09; remotes&#xff08;引用远程模块&#xff0…...

【WebSocket】SpringBoot项目中使用WebSocket

1. 导入坐标 如果springboot父工程没有加入websocket的起步依赖&#xff0c;添加它的坐标的时候需要带上版本号。 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-websocket</artifactId> </dep…...