当前位置: 首页 > 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;任务成功或者…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

css的定位(position)详解:相对定位 绝对定位 固定定位

在 CSS 中&#xff0c;元素的定位通过 position 属性控制&#xff0c;共有 5 种定位模式&#xff1a;static&#xff08;静态定位&#xff09;、relative&#xff08;相对定位&#xff09;、absolute&#xff08;绝对定位&#xff09;、fixed&#xff08;固定定位&#xff09;和…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...