list部分接口模拟实现(c++)

List

  • list简介
  • list基本框架
    • list构造函数
      • list_node结构体的默认构造
      • list类的默认构造
    • push_back()
    • iteartor迭代器
    • 迭代器里面的其他接口
      • const迭代器
      • 通过模板参数实现复用
      • operator->()
    • insert()
    • erase()
    • clear()
    • 析构函数
    • 迭代器区间构造
    • 拷贝构造
    • operator=()

list简介

- list可以在常数范围内在任意位置进行插入和删除的序列式容器,并且容器可以双向迭代。
- list底层是一个带头双向链表结构,通过指针连接前一个和后一个元素。
- list支持在任意位置进行插入、删除元素,效率更好。
- list不支持随机访问

list基本框架

namespace xty
{//带头双向循环链表template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;};template<class T>class list{typedef list_node<T> node;private:node* _head;//头指针};
}

list构造函数

我们实现一个无参构造函数,但是在这之前我们需要做一些准备工作,先实现一个申请list_node的构造函数,在struct类里面实现。

list_node结构体的默认构造

	//带头双向循环链表template<class T>struct list_node{list_node<T>* _prev;list_node<T>* _next;T _data;//在创建list_node变量时,自动调用构造list_node(const T& val = T()):_prev(nullptr),_next(nullptr),_data(val){}};

为什么不使用class,而使用struct呢?
因为我们想达到这样一个目的:想要让别人自由的访问自己的成员函数,不做任何限制,就用struct。而list_node,list是要经常使用的,因此使用struct修饰list_node比较方便。

list类的默认构造

仅仅申请一个空的头结点,next都指向头

在这里插入图片描述

		list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->next = _head;_head->prev = _head;//_head->_data已经在new的时候调用构造了}

push_back()

先记录一下尾结点,插入更简单。

		void push_back(const T& x){//留记录尾结点node* tail = _head->_prev;node* new_node = new node(x);//传入x值tail->_next = new_node;new_node->_next = _head;_head->_prev = new_node;new_node->_prev = tail;}

iteartor迭代器

整体框架:

	//iteartortemplate<class T>struct __list_iterator{typedef list_node<T> node;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T& operator*(){return _node->_data;}//++返回相应的迭代器__list_iterator<T> operator++(){_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(__list_iterator<T> x){return _node != x._node;}};template<class T>class list{typedef list_node<T> node;public://迭代器重命名typedef __list_iterator<T> iterator;public://仅仅申请一个空的头结点,next都指向头list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->_next = _head;_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}iterator begin(){iterator it(_head->_next);return it;}iterator end(){return iterator(_head);}

语法细节理解:

  1. 为什么把iterator和list进行单独封装?写一块不好吗?
    首先list只会用到迭代器的begin()和end()函数。其他的像++,其实都是通过迭代器的对象调用的(并不是list的对象调用的)。把iterator从list中抽离出来,不仅可以减少list的复杂性,还能让人更加清楚,迭代器其实也是一个模板,它能被抽离出来,用以实现各种数据结构的迭代!而list内部的begin和end接口,千篇一律。这样就达到的封装的目的!所以,还是分开写的好,逻辑更清晰,更容易维护。
  2. struct __list_iterator结构体里面为什么要写构造函数呢?
    在c++里struct也被当做是类!类里有构造函数很正常,还可以有拷贝构造呢!只不过struct默认是public的。这样我们在声明该类型的变量时,函数会自动调用构造函数,使该结构体的数据自动是被初始化过的。
	xty::list<int>::iterator it = lt.begin();  //调用对象需要用list//xty::list<int>::iterator it(lt.begin());  //调用对象需要用listwhile (it != lt.end()){cout << *it << endl;++it;}

写了构造函数之后,第二种声明方式也是可以的。而第一种方式其实调用的是拷贝构造函数,但是编译器给优化成了拷贝构造,我们没有写拷贝构造,编译器会调用默认的拷贝构造,是一个浅拷贝。但是我们不是经常说浅拷贝会造成析构问题?这里为什么不会?因为我们没有写析构函数,而且析构函数。为什么不写析构函数呢?因为没有什么可以析构的,函数的结点是list里的内容,不需要迭代器的析构函数管,因此我们不写析构函数。

  1. 迭代器++返回的是迭代器的类型。
  2. 注意:_list_iterator是类名,_list_iterator才是类型!
  3. list里面的begin要返回迭代器类型,然而怎么由指针转化成迭代器类型呢?要利用迭代器的构造函数来返回。

迭代器里面的其他接口

		bool operator==(const __list_iterator<T>& x){return _node == x._node;}//i++__list_iterator<T> operator++(int){__list_iterator<T> tem(*this);_node = _node->_next;return tem;}__list_iterator<T> operator--(){_node = _node->_prev;return *this;}__list_iterator<T> operator--(int){__list_iterator<T> tem(*this);_node = _node->_prev;return tem;}

语法细节理解:

  1. 注意迭代器传进来的参数基本上都是迭代器,如果不更改,最好加上const和&。
  2. 如果命名空间冲突,注意在函数声明和定义的时候也要加上空间名。
void Print(xty::list<int>& lt);
  1. 我们发现__list_iterator 有点长,我们重命名一下。
	//iteartortemplate<class T>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T> self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}T& operator*(){return _node->_data;}//++返回相应的迭代器self operator++(){_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(const __list_iterator<T>& x){return _node != x._node;}bool operator==(const __list_iterator<T>& x){return _node == x._node;}//i++self operator++(int){self tem(*this);_node = _node->_next;return tem;}self operator--(){_node = _node->_prev;return *this;}self operator--(int){self tem(*this);_node = _node->_prev;return tem;}};

const迭代器

要实现const迭代器只需要再写一个const类即可。
记住是指针可以修改,但是内容不可以修改,因此不能在this那加const。

		//迭代器重命名typedef __list_iterator<T> iterator;typedef const__list_iterator<T> const_iterator;public:const_iterator begin()const{const_iterator it(_head->_next);return it;}const_iterator end()const{return const_iterator(_head);}

list里面的迭代器修改仅仅需要,typedef一下,然后将构造函数改成所需要的const类型即可。


而我们需要再实现一个const类型的iterator

	template<class T>struct const__list_iterator{typedef list_node<T> node;typedef const__list_iterator<T> self;node* _node;//成员变量//构造函数const__list_iterator(node* x):_node(x){}const T& operator*()  //值不仅可以修改!!{return _node->_data;}//++返回相应的迭代器self operator++()  //指针可以修改!!{_node = _node->_next;return *this;}//是位置是否相等,不是内容是否相等。bool operator!=(const self& x)const{return _node != x._node;}bool operator==(const self& x)const{return _node == x._node;}//i++self operator++(int)  //指针可以修改!!!{self tem(*this);_node = _node->_next;return tem;}self operator--()  //指针可以修改!!!{_node = _node->_prev;return *this;}self operator--(int)  //指针可以修改!!!{self tem(*this);_node = _node->_prev;return tem;}};

问题:代码写完之后,我们发现实际上只有operator*()的返回值加了const,其他的地方没有改,因此,我们利用模板参数赋用解决问题。

通过模板参数实现复用

	template<class T,class Ref>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref> self;node* _node;//成员变量//构造函数__list_iterator(node* x):_node(x){}Ref operator*(){return _node->_data;}...}template<class T>class list{typedef list_node<T> node;public://迭代器重命名typedef __list_iterator<T, T&> iterator;typedef __list_iterator<T,const T&> const_iterator;public://仅仅申请一个空的头结点,next都指向头list(){//两种申请方法都可以//_head = new list_node<T>_head = new node;_head->_next = _head;_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}}

在这里插入图片描述

通过增加类模板参数,这种问题被很巧妙的解决了。请好好体会!

operator->()

当我们遇到自定义类型数据链表时,访问数据就会比较麻烦。

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

如上例子所示,cout方式,在这里很是别扭,因为it是迭代器,我们能不能通过重载->来访问这样的数据呢?
显然是可以的!如下:

		T* operator->(){return &(_node->_data);}

所以我们通过如下方式打印链表的数据:

		xty::list<AA>::iterator it = lt.begin();while (it != lt.end()){//cout << (*it)._a1 << ":" << (*it)._a2 << endl;cout << it->_a1 << ":" << it->_a2 << endl;++it;}

但是这个代码是不是有一点别扭?没看出来的话,我再打印一次:

			//两种打印方式一样!!!cout << it->_a1 << ":" << it->_a2 << endl;cout << it.operator->()->_a1 << ":" << it.operator->()->_a2 << endl;

在这里插入图片描述
==解释:==之所以出现这样的原因,是因为编译器自动把两个连续的->优化成一个->,防止观感上的差异,这样设计能让人立马看出这个其实是在访问AA的数据。


为了适应const和非const两种迭代器,我们再设计一个模板参数。如下实例:

	//iteartortemplate<class T,class Ref, class Ptr>struct __list_iterator{typedef list_node<T> node;typedef __list_iterator<T,Ref,Ptr> self;node* _node;//成员变量Ptr operator->(){return &(_node->_data);}
...................}
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;public:

insert()

		//在pos位置前插入,返回插入位置的迭代器iterator insert(iterator pos, const T& x){node* new_node = new node(x);node* cur = pos._node;node* prev = cur->_prev;prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;return iterator(cur);}

erase()

返回删除元素的下一个位置的迭代器。

		iterator erase(iterator pos){//不能删头assert(pos._node!=_head);node* cur = pos._node;node* prev = cur->_prev;prev->_next = cur->_next;cur->_next->_prev = prev;delete cur;return iterator(prev->_next)}

注意:删除元素后,pos位置的数据就被删除了,会产生迭代器失效问题,如果再使用pos需要重新赋值。

clear()

清空list的内容,可以借助迭代器和erase()来删除。

		void clear(){iterator it = begin();while (it != end()){it = erase(it);//erase(it++);}}

析构函数

结合clear()来编写。

		~list(){clear();delete _head;_head = nullptr;}

迭代器区间构造

因为迭代器区间构造,也需要一个头结点,所以,我们方便复用,又定义了一个初始化函数,具体改动如下:

		list(){empty_init();//两种申请方法都可以//_head = new list_node<T>//_head = new node;//_head->_next = _head;//_head->_prev = _head;//_head->_data已经在new的时候调用构造了了}void empty_init(){_head = new node;_head->_next = _head;_head->_prev = _head;}template<class Iterator>list(Iterator first, Iterator last){empty_init();while (first != last){push_back(*first);++first;}}

拷贝构造

提供了两种方法,第一种方法效率较低,第二种利用swap提高了效率。

		lt2(lt)//list(const list<T>& lt)//{//	empty_init();//	for (auto e : lt)//	{//		push_back(e);//	}//}void swap(list<T>& tem){std::swap(_head, tem._head);}list(const list<T>& lt){empty_init();//初始化thislist<T> tem(lt.begin(), lt.end());swap(tem);}

operator=()

实现较为简单。

//注意这里不能传引用list<T>& operator=(list<T> lt){swap(lt);return *this;}

最后一个问题:

const list<int> lt;

这行代码能调用构造函数吗?
答案是肯定的,因为变量在最开始是没有const属性的,定义好了以后,才有const属性。否则const都没法定义出来了。

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

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

相关文章

使用 pubsub-js 进行消息发布订阅

npm 包地址 github 包地址 pubsub-js 是一个轻量级的 JavaScript 基于主题的消息订阅发布库 &#xff0c;压缩后小于1b。它具有使用简单、性能高效、支持多平台等优点&#xff0c;可以很好地满足各种需求。 功能特点&#xff1a; 无依赖同步解耦ES3 兼容。pubsub-js 能够在…

Angular 由一个bug说起之一:List / Grid的性能问题

在angular中&#xff0c;MatTable构建简单&#xff0c;使用范围广。但某些时候会出现卡顿 卡顿情景&#xff1a; 1&#xff1a;一次性请求太多的数据 2&#xff1a;一次性渲染太多数据&#xff0c;这会花费CPU很多时间 3&#xff1a;行内嵌套复杂的元素 4&#xff1a;使用过多的…

11月份 四川汽车托运报价已经上线

中国人不骗中国人!! 国庆小长假的高峰期过后 放假综合症的你还没痊愈吧 今天给大家整理了9条最新线路 广州到四川的托运单价便宜到&#x1f4a5; 核算下来不过几毛钱&#x1f4b0; 相比起自驾的漫长和疲惫&#x1f697; 托运不得不说真的很省事 - 赠送保险 很多客户第一次运车 …

LeetCode 17. 电话号码的字母组合 中等

题目 - 点击直达 1. 17. 电话号码的字母组合 中等1. 题目详情1. 原题链接2. 题目要求3. 基础框架 2. 解题思路1. 思路分析2. 时间复杂度3. 代码实现 3. 知识与收获 1. 17. 电话号码的字母组合 中等 1. 题目详情 1. 原题链接 LeetCode 17. 电话号码的字母组合 中等 2. 题目要…

unity line renderer绘制的颜色不是想要的红色

线条不是暗红色的&#xff0c;用的是默认的红色 将材质选则为如下即可

C# OpenCvSharp DNN HybridNets 同时处理车辆检测、可驾驶区域分割、车道线分割

效果 项目 代码 using OpenCvSharp; using OpenCvSharp.Dnn; using System; using System.Collections.Generic; using System.Drawing; using System.IO; using System.Linq; using System.Numerics; using System.Text; using System.Windows.Forms;namespace OpenCvSharp_D…

Python使用腾讯云SDK实现对象存储(上传文件、创建桶)

文章目录 1. 开通服务2. 创建存储桶3. 手动上传文件并查看4. python上传文件4.1 找到sdk文档4.2 初始化代码4.3 region获取4.4 secret_id和secret_key获取4.5 上传对象代码4.6 python实现上传文件 5 python创建桶 首先来到腾讯云官网 https://cloud.tencent.com/1. 开通服务 来…

vue项目pdf文件的预览

1.下载 您可以在以下网址下载pdfjsLib&#xff1a;https://github.com/mozilla/pdf.js pdfjsLib是一个开源项目&#xff0c;您可以在GitHub上找到其源代码和相关资源。 2.放置文件位置 3.进入 在index.html引入 <script src"<% BASE_URL %>static/pdfjs-dist/b…

C/C++输出硬币翻转 2021年6月电子学会青少年软件编程(C/C++)等级考试一级真题答案解析

目录 C/C硬币翻转 一、题目要求 1、编程实现 2、输入输出 二、算法分析 三、程序编写 四、程序说明 五、运行结果 六、考点分析 C/C硬币翻转 2021年6月 C/C编程等级考试一级编程题 一、题目要求 1、编程实现 假设有N个硬币(N为不大于5000的正整数)&#xff0c;从1…

ChatGPT 宕机?OpenAI 将中断归咎于 DDoS 攻击

您的 ChatGPT 已关闭吗&#xff1f;您是否遇到 ChatGPT 问题&#xff0c;例如连接问题或遇到“长响应时出现网络错误”&#xff1f;– ChatGPT 遭受了一系列 DDoS 攻击&#xff0c;显然是由匿名苏丹组织策划的。 OpenAI 的 ChatGPT 是一款流行的人工智能聊天机器人&#xff0c;…

工商银行卡安全码怎么看

工商银行的安全码&#xff0c;作为一项至关重要的安全措施&#xff0c;旨在保护用户的银行账户和交易安全。为了查看工商银行的安全码用户需要按照以下步骤操作&#xff1a; 首先&#xff0c;用户需要使用电脑或手机访问工商银行的网上银行平台。在平台首页&#xff0c;用户需要…

2023年A股借壳上市研究报告

第一章 借壳上市概况 1.1 定义 借壳上市作为一种独特的资本市场操作手法&#xff0c;历来是企业拓展融资渠道和实现市场战略目标的重要途径。具体来说&#xff0c;借壳上市可分为狭义与广义两种模式。在狭义的定义下&#xff0c;借壳上市是指一家已上市的公司的控股母公司&am…

JVM虚拟机-虚拟机性能监控、故障处理工具

1基础故障处理工具 jps&#xff08;JVM Process Status Tool&#xff09;是&#xff1a;虚拟机进程状况工具 作用&#xff1a;可以列出正在运行的虚拟机进程&#xff0c;并显示虚拟机执行主类&#xff08;Main Class&#xff0c;main()函数所在的类&#xff09;名称以及这些进…

基于遗传算法优化的直流电机PID控制器设计

PID控制器是工业控制中常用的一种控制算法&#xff0c;通过不断调节比例、积分和微分部分来实现对系统的稳定控制。然而&#xff0c;在一些复杂系统中&#xff0c;传统的PID参数调节方法可能存在局限性。本文将介绍一种基于遗传算法优化的直流电机PID控制器设计方法&#xff0c…

CSS3 多媒体查询、网格布局

一、CSS3多媒体查询&#xff1a; CSS3 多媒体查询继承了CSS2多媒体类型的所有思想&#xff0c;取代了查找设备的类型。CSS3根据设置自适应显示。 多媒体查询语法&#xff1a; media not|only mediatype and (expressions) { CSS 代码...; } not: not是用来排除掉某些特定…

系列二十二、idea Live Templates

一、idea Live Templates 1.1、Java Group 1.1.1、fast fast 快速在类上添加注解Data AllArgsConstructor NoArgsConstructor Accessors(chain true) ToString(callSuper true) 1.1.2、getThreadName getThreadName快速获取当前线程的名字Thread.currentThread().getName…

【Git】gui图形化界面的使用、ssh协议以及idea集成Git

目录 gui图形化界面的使用 介绍 特点 gui图形的使用 ssh协议 介绍 步骤及概念 ssh协议的使用 配置公钥 idea集成Git idea配置git IDEA安装gitee IDEA中登入Git ​编辑 项目分享 克隆分享的项目 ​编辑 ​编辑 idea上传远程 gui图形化界面的使用 介绍 GUI&#xff08…

Docker进阶——再次认识docker的概念 Docker的结构 Docker镜像结构 镜像的构建方式

前言 在微服务大量应用的互联网时代&#xff0c;经常能看到docker的身影。作为docker的爱好者&#xff08;在服务器安装MySQL&#xff0c;Redis。。。我用的都是docker&#xff09;&#xff0c;我也会持续深入学习和认识docker。 本篇博客再次介绍docker的基本概念&#xff0…

广州华锐互动:VR互动实训内容编辑器助力教育创新升级

随着科技的飞速发展&#xff0c;教育领域也正在经历一场深刻的变革。其中&#xff0c;虚拟现实(VR)技术为教学活动提供了前所未有的便利和可能性。在诸多的VR应用中&#xff0c;VR互动实训内容编辑器无疑是最具潜力和创新性的一种。广州华锐互动开发的这款编辑器以其独特的功能…

【星海出品】flask 与docker

import os from flask import Flask, request from flask import Response, make_response, jsonify import cv2 import base64 import io import uuid from main import eye ​ app Flask(__name__)​ app.route(/, methods[GET, POST]) # 添加路由blend def upload_file():…