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);}

 

 

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

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

相关文章

Mac操作系统Safari 17全新升级：秋季推出全部特性

Mac操作系统Safari 17全新升级：秋季推出全部特性

苹果的内置浏览器可能是Mac上最常用的应用程序&#xff08;是的&#xff0c;甚至比Finder、超级Mac Geeks还要多&#xff09;。因此&#xff0c;苹果总是为其浏览器Safari添加有用的新功能。在今年秋天与macOS Sonoma一起推出的第17版中&#xff0c;Safari可以帮助你提高工作效…
阅读更多...
活用 命令行通配符

活用 命令行通配符

本文是对 阮一峰老师命令行通配符教程[1]的学习与记录 通配符早于正则表达式出现,可以看作是原始的正则表达式. 其功能没有正则那么强大灵活,而胜在简单和方便. - 字符 切回上一个路径/分支 如图: !! 代表上一个命令, 如图: [Linux中“!"的神奇用法](https://www.cnblogs.…
阅读更多...
不会还有人排长队吃饭吧？用这招，快速搞定！

不会还有人排长队吃饭吧？用这招，快速搞定！

随着现代企业对员工福利和工作环境的关注不断增加&#xff0c;企业智慧食堂已经成为了企业管理的重要组成部分。 智慧收银系统的出现不仅使员工用餐变得更加便捷和高效&#xff0c;还提供了一种强大的管理工具&#xff0c;有助于企业更好地理解员工消费行为、优化食堂运营&…
阅读更多...
比较器的工作原理及性能指标介绍

比较器的工作原理及性能指标介绍

一、什么是比较器 比较器的功能是比较两个或更多数据项&#xff0c;以确定它们是否相等&#xff0c;或者确定它们之间的大小关系和排列顺序&#xff0c;这称为比较。可以实现此比较功能的电路或设备称为比较器。比较器是将模拟电压信号与参考电压进行比较的电路。比较器的两个…
阅读更多...
说说Flink中的State

说说Flink中的State

分析&回答 基本类型划分 在Flink中&#xff0c;按照基本类型&#xff0c;对State做了以下两类的划分&#xff1a; Keyed State&#xff0c;和Key有关的状态类型&#xff0c;它只能被基于KeyedStream之上的操作&#xff0c;方法所使用。我们可以从逻辑上理解这种状态是一…
阅读更多...
掌握逻辑漏洞复现技术，保护您的数字环境

掌握逻辑漏洞复现技术，保护您的数字环境

环境准备 这篇文章旨在用于网络安全学习&#xff0c;请勿进行任何非法行为&#xff0c;否则后果自负。 1、支付逻辑漏洞 攻击相关介绍 介绍&#xff1a; 支付逻辑漏洞是指攻击者利用支付系统的漏洞&#xff0c;突破系统的限制&#xff0c;完成非法的支付操作。攻击者可以采…
阅读更多...
ZKP硬件加速

ZKP硬件加速

1. 引言 本文重点关注&#xff1a; 1&#xff09;何为硬件加速&#xff1f;为何需要硬件加速&#xff1f;2&#xff09;ZKP的关键计算原语&#xff1a; Multiscalar MultiplicationNumber Theoretic TransformationArithmetic Hashes 3&#xff09;所需的硬件资源4&#xff0…
阅读更多...
2D-2D对极几何中的基本矩阵、本质矩阵和单应矩阵

2D-2D对极几何中的基本矩阵、本质矩阵和单应矩阵

本文主要参考高翔博士的视觉SLAM十四讲第二版中的7.3章节内容。文章目录 1 对极约束2 本质矩阵E3 单应矩阵 1 对极约束 现在&#xff0c;假设我们从两张图像中得到了一对配对好的特征点&#xff0c;如图7.9所示&#xff08;假如后面我们有若干对这样的匹配点&#xff0c;根据这…
阅读更多...
烟草企业物流管理信息系统的分析与设计(论文+源码)_kaic

烟草企业物流管理信息系统的分析与设计(论文+源码)_kaic

摘要 在经济高速发展的今天&#xff0c;物流业已经成为支撑国民经济的基础性产业。作为一种新型服务业&#xff0c;物流业集仓储、运输、信息等为一体&#xff0c;发展成为复合型战略性产业。S烟草企业设计的物流管理信息系统利用B/S模式的三层结构&#xff0c;基于JSP技术和J…
阅读更多...
Django(9)-表单处理

Django(9)-表单处理

django支持使用类创建表单实例 polls/forms.py from django import forms class NameForm(forms.Form):your_nameforms.CharField(label"Your name",max_length100)这个类创建了一个属性&#xff0c;定义了一个文本域&#xff0c;和它的label和最大长度。 polls/vi…
阅读更多...
go语言kafka入门

go语言kafka入门

消息队列&#xff1a;一种基于异步通信的解耦机制&#xff0c;用于在应用程序或系统组件之间传递消息和数据 消息队列相关概念&#xff1a; 生产者&#xff08;Producer&#xff09;&#xff1a;生成并发送消息到消息队列中的应用程序或系统组件。 消费者&#xff08;Consumer&…
阅读更多...
微服务事务管理（Dubbo）

微服务事务管理（Dubbo）

Seata 是什么 Seata 是一款开源的分布式事务解决方案&#xff0c;致力于提供高性能和简单易用的分布式事务服务。Seata 将为用户提供了 AT、TCC、SAGA 和 XA 事务模式&#xff0c;为用户打造一站式的分布式解决方案。 一、示例架构说明 可在此查看本示例完整代码地址&#x…
阅读更多...
【GO】LGTM_Grafana_Tempo(1)_架构

【GO】LGTM_Grafana_Tempo(1)_架构

最近在尝试用 LGTM 来实现 Go 微服务的可观测性&#xff0c;就顺便整理一下文档。 Tempo 会分为 4 篇文章&#xff1a; Tempo 的架构官网测试实操跑通gin 框架发送 trace 数据到 tempogo-zero 微服务框架使用发送数据到 tempo 第一篇是关于&#xff0c;tempo 的架构&#xff…
阅读更多...
0828|C++day6 菱形继承+虚继承+多态+抽象类+模板

0828|C++day6 菱形继承+虚继承+多态+抽象类+模板

一、思维导图 二、今日知识回顾 1&#xff09;多态 父类的指针或者引用&#xff0c;指向或初始化子类的对象&#xff0c;调用子类对父类重写的函数&#xff0c;进而展开子类的功能。 #include <iostream> using namespace std;class Zhou { private:string name;int age…
阅读更多...
eclipse/STS(Spring Tool Suite)安装CDT环境（C/C++）

eclipse/STS(Spring Tool Suite)安装CDT环境（C/C++）

在线安装 help -> eclipse marketplace 可以发现&#xff0c;我所使用eclipse给我推荐安装的CDT是10.5版本 离线安装 下载离线安装包 下载地址&#xff1a;https://github.com/eclipse-cdt/cdt/blob/main/Downloads.md 可以看到利息安装包主要有如下四大类&#xff0c;…
阅读更多...
【Kali Linux高级渗透测试】深入剖析Kali Linux：高级渗透测试技术与实践

【Kali Linux高级渗透测试】深入剖析Kali Linux：高级渗透测试技术与实践

&#x1f4d5;作者简介&#xff1a;热爱跑步的恒川&#xff0c;致力于C/C、Java、Python等多编程语言&#xff0c;热爱跑步&#xff0c;喜爱音乐的一位博主。 &#x1f4d7;本文收录于恒川的日常汇报系列&#xff0c;大家有兴趣的可以看一看 &#x1f4d8;相关专栏C语言初阶、C…
阅读更多...
(vue)Vue项目中使用jsPDF和html2canvas生成PDF

(vue)Vue项目中使用jsPDF和html2canvas生成PDF

(vue)Vue项目中使用jsPDF和html2canvas生成PDF 效果&#xff1a; 安装与使用 1.&#xff1a;安装jsPDF和html2canvas npm install jspdf html2canvas2.在需要生成PDF文档的组件中引入jsPDF和html2canvas <template><div><el-button type"primary"…
阅读更多...
Django(7)-项目实战-发布会签到管理系统

Django(7)-项目实战-发布会签到管理系统

本文使用django实现一个简单的发布会签到管理系统 登录功能 模板页面 sign/templates/index.html <!DOCTYPE html> <html> <head><title>Login Page</title> </head> <body><h1>发布会管理</h1><form action=&qu…
阅读更多...
视频融合平台EasyCVR视频汇聚平台关于小区高空坠物安全实施应用方案设计

视频融合平台EasyCVR视频汇聚平台关于小区高空坠物安全实施应用方案设计

近年来&#xff0c;随着我国城市化建设的推进&#xff0c;高楼大厦越来越多&#xff0c;高空坠物导致的伤害也屡见不鲜&#xff0c;严重的影响到人们的生命安全。像在日常生活中一些不起眼的小东西如烟头、鸡蛋、果核、易拉罐&#xff0c;看似伤害不大&#xff0c;但只要降落的…
阅读更多...
无涯教程-Android - DatePicker函数

无涯教程-Android - DatePicker函数

Android Date Picker允许您在自定义用户界面中选择由日,月和年组成的日期。为此功能,android提供了DatePicker和DatePickerDialog组件。 在本教程中,我们将通过DatePickerDialog演示日期选择器的用法, DatePickerDialog是一个包含DatePicker的简单对话框。 为了显示DatePicker…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023