C++---list常用接口和模拟实现

list---模拟实现

  • list的简介
  • list函数的使用
    • 构造函数
    • 迭代器的使用
    • list的capacity
    • list element access
    • list modifiers
  • list的模拟实现
    • 构造函数,拷贝构造函数和=
    • 迭代器
    • begin和end
    • insert和erase
    • clear和析构函数
  • 源码

list的简介

list是用双向带头联表实现的一个容器,双向联表中每个元素存在互不相关的独立节点中,再节点中通过指针指向其前一个元素和后一个元素,并且可以再常数范围内再任意位置进行插入和删除的序列式容器。

list函数的使用

构造函数

构造函数( (constructor))接口说明
list (size_type n, const value_type& val = value_type())构造的list中包含n个值为val的元素
list()构造空的list
list (const list& x)拷贝构造函数
list (InputIterator first, InputIterator last)用[first, last)区间中的元素构造list
void ListTest2()
{std::list<int> a(4, 5);std::cout << "a的list" << ':';for (auto& e : a){std::cout << e << ' ';}std::cout << std::endl;std::list<int> b;//Emptystd::list<int> c(a.begin(), a.end());std::cout << "c的list" << ':';for (auto& e : c){std::cout << e << ' ';}}

在这里插入图片描述

迭代器的使用

函数声明接口说明
begin + end返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin + rend返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的 reverse_iterator,即begin位置
	std::list<int> a(4, 5);std::cout << "a的list" << ':';std::list<int>::iterator it = a.begin();while (it != a.end()){std::cout << *it << ' ';++it;}

在这里插入图片描述

list的capacity

函数声明接口说明
empty检测list是否为空,是返回true,否则返回false
size返回list中有效节点的个数

list element access

函数声明接口说明
front返回list的第一个节点中值的引用
back返回list的最后一个节点中值的引用

list modifiers

函数声明接口说明
push_front在list首元素前插入值为val的元素
pop_front删除list中第一个元素
push_back在list尾部插入值为val的元素
pop_back删除list中最后一个元素
insert在list position 位置中插入值为val的元素
erase删除list position位置的元素
swap交换两个list中的元素
clear清空list中的有效元素

list的模拟实现

要想模拟实现list,首先我们可以定义一个节点类。为什么要定义一个节点类呢,想想数据结构中的双链表,每个元素都在独立的节点中,通过节点的前驱指针和后继指针指向前后位置。

list的模拟实现跟vector和string实现是不一样的,vector本质上是一个数组,数组本身就是一个迭代器,而list是一个个的节点,通过指针联系在一起,所以vector类不用对迭代器进行封装,可以直接使用,list不一样,节点++是什么是不清楚的,这个时候可以使用运算符重载,对++,–,*等进行重载。

	template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};

再定义一个list类,再这个类中,完成其他函数的实现

	template<class T>class list{public:private:Node* _head;size_t _size;};

构造函数,拷贝构造函数和=

list的构造函数实现,跟双链表中的初始化是一样的,将next指针和prev指针都指向头节点,形成一个环。

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

拷贝构造函数再拷贝之前,要先开一个头节点的空间,然后再头节点后面依次把值进行尾插即可。

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

赋值重载=和vector里面的写法是一样的。

		list<T>& operator=(list<T> it){swap(it);return *this;}

通过传参创建出一个临时变量,然后将其交换。

迭代器

要想实现list的迭代器,需要将原生态指针进行封装。

list是由一个个的节点组成,节点++,解引用,–,等操作是找不到对应的数据的,所以需要用自定义类型对指针进行封装,从而完成一系列操作。

迭代器有一个const类型的迭代器,有一个无const类型的,再实现一个无const类型的迭代器之后,把代码赋值粘贴,也可以改成带const类型的迭代器,但这样显然是代码冗余的,重复的太多,这个时候,那些大佬们就通过增加模板参数,来解决代码冗余,根据参数的类型,实列化出不同的类。

	
//typedef __list_iterator<T, T&, T*> iterator;
//typedef __list_iterator<T,const T&,const T*> const_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){}//对节点解引用,是找不到我们存储的数据的,因为节点里面存的是val,next和prev,重载的目是使其对迭代器解引用可以找到有效数据Ref operator*(){return _node->_val;}Ptr operator->(){return &(_node->val);}//指针++,到下一个位置,其实就是让节点向后移动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 *this;}bool operator !=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._node;}};

以上就是用自定义的类,对指针进行封装。

begin和end

对指针进行封装之后,就可以实现begin和end了。

begin只要返回头节点的下一个节点即可

end就是头节点

		iterator begin(){return _head->_next;}iterator end(){return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}

insert和erase

有一个insert,就可以完成再任意位置插入。

		void push_back(const T& x){insert(end(), x);}void push_front(const T& x){insert(begin(), x);}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;newnode->_prev = prev;cur->_prev = newnode;return newnode;}

先找到当前节点cur和当前节点的上一个节点prev,再new出一个要插入的节点newnode,使得cur和newnode进行双向连接,prev和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;}

clear和析构函数

		void clear(){iterator it = begin();while (it != end()){it = earse(it);}_size = 0;}~list(){}

源码

#pragma once#include <assert.h>
#include <algorithm>namespace HaiFan
{template<class T>struct list_node{list_node<T>* _next;list_node<T>* _prev;T _val;list_node(const T& val = T()):_next(nullptr),_prev(nullptr),_val(val){}};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){}T& operator*(){return _node->_val;}T* operator->(){return &(_node->val);}T& operator++(){_node = _node->_next;return *this;}T operator++(int){self tmp(*this);_node = _node->_next;return tmp;}T& operator--(){_node = _node->_prev;return *this;}T operator--(int){self tmp(*this);_node = _node->prev;return *this;}bool operator !=(const self& it) const{return _node != it._node;}bool operator==(const self& it) const{return _node == it._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;}list(){EmptyInit();}list(const list<T>& it){EmptyInit();for (auto& e : it){push_back(e);}}list<T>& operator=(list<T> it){swap(it);return *this;}void swap(list<T>& it){std::swap(_head, it._head);std::swap(_size, it._size);}void clear(){iterator it = begin();while (it != end()){it = earse(it);}_size = 0;}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* prev = cur->_prev;Node* newnode = new Node(x);prev->_next = newnode;newnode->_next = cur;newnode->_prev = prev;cur->_prev = newnode;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;}size_t size(){return _size;}void EmptyInit(){_head = new Node();_head->_next = _head;_head->_prev = _head;_size = 0;}~list(){}private:Node* _head;size_t _size;};
}

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

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

相关文章

C—数据的储存(下)

文章目录 前言&#x1f31f;一、练习一下&#x1f30f;1.例一&#x1f30f;2.例二&#x1f30f;3.例三&#x1f30f;4.例四 &#x1f31f;二、浮点型在内存中的储存&#x1f30f;1.浮点数&#x1f30f;2.浮点数存储&#x1f4ab;&#xff08;1&#xff09;.二进制浮点数&#x…

提高生产线效率:PDM系统的工艺优化智慧

在现代制造业中&#xff0c;提高生产线效率是企业追求高质量和降低成本的重要目标。PDM系统&#xff08;Product Data Management&#xff0c;产品数据管理&#xff09;作为一款强大的数字化工具&#xff0c;发挥着工艺优化智慧的作用&#xff0c;帮助企业实现生产线效率的提升…

C# 回文链表

234 回文链表 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true 示例 2&#xff1a; 输入&…

TPlink云路由器界面端口映射设置方法?快解析内网穿透能实现吗?

有很多网友在问&#xff1a;TPlink路由器端口映射怎么设置&#xff1f;因为不懂端口映射的原理&#xff0c;所以无从下手&#xff0c;下面小编就给大家分享TPlink云路由器界面端口映射设置方法&#xff0c;帮助大家快速入门TP路由器端口映射设置方法。 1.登录路由器管理界面&a…

性能测试/负载测试/压力测试之间的区别

做测试一年多来&#xff0c;虽然平时的工作都能很好的完成&#xff0c;但最近突然发现自己在关于测试的整体知识体系上面的了解很是欠缺&#xff0c;所以&#xff0c;在工作之余也做了一些测试方面的知识的补充。不足之处&#xff0c;还请大家多多交流&#xff0c;互相学习。 …

Amazon Aurora Serverless v2 正式发布:针对要求苛刻的工作负载的即时扩展

我们非常兴奋地宣布&#xff0c;Amazon Aurora Serverless v2 现已面向 Aurora PostgreSQL 和 MySQL 正式发布。Aurora Serverless 是一种面向 Amazon Aurora 的按需自动扩展配置&#xff0c;可让您的数据库根据应用程序的需求扩展或缩减容量。 亚马逊云科技开发者社区为开发者…

Hudi Flink SQL源码调试学习(1)

前言 本着学习hudi-flink源码的目的&#xff0c;利用之前总结的文章Hudi Flink SQL代码示例及本地调试中的代码进行调试,记录调试学习过程中主要的步骤及对应源码片段。 版本 Flink 1.15.4Hudi 0.13.0 目标 在文章Hudi Flink SQL代码示例及本地调试中提到&#xff1a;我们…

2023网络安全学习路线 非常详细 推荐学习

首先咱们聊聊&#xff0c;学习网络安全方向通常会有哪些问题 1、打基础时间太长 学基础花费很长时间&#xff0c;光语言都有几门&#xff0c;有些人会倒在学习 linux 系统及命令的路上&#xff0c;更多的人会倒在学习语言上&#xff1b; 2、知识点掌握程度不清楚 对于网络安…

Qsys介绍

文章目录 前言一、为什么需要Qsys1、简化了系统的设计流程2、Qsys涉及的技术 二、Qsys真身1、一种系统集成工具2、何为Nios II1、内核架构2、Nios II选型 三、Qsys设计涉及到的软件&工具四、总结五、参考资料 前言 Qsys是Altera下的一个系统集成工具&#xff0c;可用于搭建…

使用tinyxml解析和修改XML文件

首先要清楚XML文件包含哪些元素&#xff1a; 他是由元素、文本或者两者混合物组成。元素可以拥有属性&#xff0c;元素是指从开始标签到结束标签的部分。 <?xml version"1.0" encoding"UTF-8" ?> <books><book id"1001">&…

新一代开源流数据湖平台Apache Paimon入门实操-上

文章目录 概述定义核心功能适用场景架构原理总体架构统一存储基本概念文件布局 部署环境准备环境部署 实战Catalog文件系统Hive Catalog 创建表创建Catalog管理表查询创建表&#xff08;CTAS&#xff09;创建外部表创建临时表 修改表修改表修改列修改水印 概述 定义 Apache Pa…

Nginx安装和Nginx配置虚拟主机

Nginx安装 源码包获取地址&#xff1a;http://nginx.org/download/ RPM包获取地址&#xff1a;http://nginx.org/packages/centos/7Server/x86_64/RPMS/ RPM安装 这里选择的RPM包是 nginx-1.22.0-1.el7.ngx.x86_64.rpm [rootlocalhost ~]# yum install nginx-1.22.0-1.el7.…

快速排序——“数据结构与算法”

各位CSDN的uu们好呀&#xff0c;今天又是小雅兰的数据结构与算法专栏啦&#xff0c;下面&#xff0c;就让我们进入快速排序的世界吧&#xff01;&#xff01;&#xff01; 快速排序 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法&#xff0c;其基本思想为&…

【C语言学习】数据类型转换

一、自动类型转换 1.当运算符两边的数据类型不同时&#xff0c;C语言会帮我们将其转换为较大的类型。即将数据转换成表达范围更大的类型。 将前一种类型转换为后一种类型 char --> short --> int --> long --> long long int --> float --> double2.对于…

C/C++的5大内存分区

1、堆区&#xff08;heap&#xff09;——由程序员分配和释放&#xff0c; 若程序员不释放&#xff0c;程序结束时可能由OS回收 。注意它与数据结构中的堆是两回事 2、栈区&#xff08;stack&#xff09;——由编译器自动分配释放 &#xff0c;存放函数的参数值&#xff0c;局…

python基础

本篇博客的内容是《python编程从入门到实践》的精简版&#xff0c;主要是书中&#xff08;本人认为的&#xff09;重点精简&#xff0c;以及自己学习的一些理解。 文章目录 更好的阅读体验变量和简单的数据类型变量字符串字符串的几种定义方法字符串拼接 列表简介列表是什么运…

ELK + Fliebeat + Kafka日志系统

参考&#xff1a; ELKFilebeatKafka分布式日志管理平台搭建_51CTO博客_elk 搭建 ELK 日志分析系统概述及部署&#xff08;上&#xff09;-阿里云开发者社区 ELK是三个开源软件的缩写&#xff0c;分别表示&#xff1a;Elasticsearch , Logstash, Kibana , 它们都是开源软件。…

python 数据分析面试题:求分组排第n名的记录数据

近期面试遇到一个面试题&#xff0c;分享给大家。 文中会提供详细的解题思路以及问题延伸 一、面试题 面试题&#xff1a;输出各学科总分第一名的学员姓名、年龄、分数数据&#xff1a; class_a {name: [学员1, 学员2, 学员3, 学员4,学员5],age: [23, 24, 26, 27,25],course…

05|Oracle学习(UNIQUE约束)

1. UNIQUE约束介绍 也叫&#xff1a;唯一键约束&#xff0c;用于限定数据表中字段值的唯一性。 1.1 UNIQUE和primary key区别&#xff1a; 主键/联合主键每张表中只有一个。UNIQUE约束可以在一张表中&#xff0c;多个字段中存在。例如&#xff1a;学生的电话、身份证号都是…

AB 压力测试

服务器配置 阿里云Ubuntu 64位 CPU1 核 内存2 GB 公网带宽1 Mbps ab -c100 -n1000 http://127.0.0.1:9501/ -n&#xff1a;在测试会话中所执行的请求个数。默认时&#xff0c;仅执行一个请求。 -c&#xff1a;一次产生的请求个数。默认是一次一个。 ab -c 100 -n 200 ht…