C++入门之stl六大组件--List源码深度剖析及模拟实现

文章目录

前言

一、List源码阅读

二、List常用接口模拟实现

1.定义一个list节点

2.实现一个迭代器

2.2const迭代器

3.定义一个链表,以及实现链表的常用接口

三、List和Vector

总结


前言

本文中出现的模拟实现经过本地vs测试无误,文件已上传gitee,地址:list: 模仿实现stl的list - Gitee.com


一、List源码阅读

首先我们阅读源码,阅读源码我按照如下方式:先找到单个节点的定义,再找到list里面的主要成员函数。

list_node链表节点的定义,如下:有三个成员,prev,next指针,数据域。

实现链表的接口:增删改查,回想我们用C语言实现的顺序表的时候,使用指针去实现。使用C++的时候,模拟实现string,也是使用迭代器。迭代器就是模拟指针的行为,但是链表直接使用指针++,不一定能访问到下一个节点,所以我们要封装一下原生指针--迭代器,去实现对list的访问。

阅读源码,_list_iterator这个迭代器,有三个模板参数,猜测T应该是类型,Ref是引用,Ptr是指针,为什么有三个模板参数?后续再分析。这个迭代器里实现了一个原生迭代器,一个const迭代器,const调用const对象,然后还有一个self,暂时不明白什么意思。继续往下。

 阅读到这里,重定义了一些参数。注意这里:

  • typedef _list_node<T> * link_type;  
  • link_type node;
  • _list_iterator(link type x):node(x){}

和C语言一样,这里定义了一个节点的指针,作为实现迭代器的最小单元

继续往下阅读,这里有一些运算符重载的函数,比较节点是否相等,以及引用,注意这里引用的返回值使用了reference,上面看出来将Ref重定义成了reference,所以这里可以猜测,ref就是返回引用的值

 这里实现了运算符重载函数,使用迭代器,去访问前后的节点。注意这里的返回值是self,前面读到self就是_list_iterator的一个模板参数。对比之前实现日期类的时候,日期类++,返回的就是一个日期类对象。这里使用迭代器进行++,猜测这里返回的就是一个迭代器。

继续查看迭代器的使用:在list的成员函数中,查看到begin:指向头节点的下一个,end指向头节点。rbegin指向头节点,rend指向头节点的下一个。

判断链表是否为空:判断头节点的下一个是否指向头节点

计算链表的size:根据begin,end去计算

 以及链表中最重要的插入insert,通过迭代器找到pos的位置,根据T去构建一个Node,再进行插入。头插尾插都可以复用Insert。头插头删的时候先保留现在的指针指向情况,再进行修改,修改完了之后再删除这个节点

 往下阅读,到了list的主体部分,有两个模板参数。alloc暂时不明白是什么

 这里实现了一种创建节点的成员函数,create_node:通过T类型的参数x创建一个节点.

empty_initialize 空的初始化,只创建一个节点

二、List常用接口模拟实现

通过上面阅读源码,我们来模仿实现list的一些常用接口。

1.定义一个list节点

template<class T>
struct list_node
{T _data;list_node<T> * _next;list_node<T> * _prev;
}

2.实现一个迭代器

 迭代器要么就是原生指针,要么就是自定义类型对原生指针的封装,模拟指针的行为。

list用一个节点的指针,去构造一个迭代器

template<class T>
struct _list_iterator
{typedef list_node<T> node;typedef _list_iterator<T> self;//定义一个指针,指向链表node * _node;//构造函数 用一个节点指针去构造迭代器_list_iterator(node * n):_node(n){}//实现迭代器的功能//指针++向后遍历,就如日期类,返回的还是一个日期类对象;迭代器++,返回一个迭代器对象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;}T& operator*(){return _ndoe->data;}bool operator == (const self& s){return _node == s._node;}bool operator !=(const self &s){return _node != s._node;}

2.2const迭代器

假设我们传了一个const对象,

  • void print_list(const list<int>&lt)。
  • 对象的类型是一个const list<int> * ,调用不了普通迭代器,是一个经典的权限放大,所以我们要对this加一个const。此时变成了const* _head,指针本身不能改变,但是指向的内容可以改变。即我们还是可以对对象进行改变。
  • 在stl库中,它使用const修饰*this,返回值也是一个const_iterator。但是,对于所有的成员函数都使用const修饰*this和返回值类型很冗余,所以我们这里增加了一个模板参数class Ref。
	template<class T>struct __list_const_iterator{typedef list_node<T> node;typedef __list_const_iterator<T> self;node* _node;__list_const_iterator(node* n):_node(n){}//保护返回的值不能被修改const T& operator*(){return _node->_data;}//... 其他成员函数都相同};
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 * n):_node(n){}Ref operator*(){return _ndoe->data;}//注意这里 如果我定义了一个AA类型的链表,通过迭代器去访问,指针类型为AA*// 现在要访问它的成员 可以这样: *(it)._a1; //也可以it->->a1 一个是运算符重载调用,it是自定义类型,无法直接使用箭头,it-> 就相当于运算符重载operator-> AA*//一个是找成员 //这里为了增强可读性 省略了一个箭头 it->_a1;Ptr operator->(){return &_node->data;}self& operator--(){}//其余运算符操作类似
}template<class T>
class list
{//注意这里模板参数 调用普通迭代器 T&传给ref, 调用const迭代器 const T& 传给ref typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T,const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);}const iterator begin(){return const_iterator(_head->_next);}//..其余类似
}

3.定义一个链表,以及实现链表的常用接口

template<class T>
struct _list
{typedef list_node<T> node;typedef _list_iterator<T> iterator;//list的成员node* _head;//list的构造 初始只有一个头节点list(){_head = new node;_head->_next = _head;_head->_prev = _head;}//list的一些成员函数 //通过迭代器定位begin和enditerator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}//通过迭代器对指定pos位置进行增删改查void  insert(iterator pos, const T& x){node new_node = new node(x);//iterator cur = pos;//这里是要通过pos的指针,找到这个节点 对pos进行解引用node * cur = pos._node;node * prev = cur->_prev;prev->_next = new_node;new_node->_prev = prev;new_node->_next = cur;cur->_prev = new_node;}void push_back(){insert(end(),x);}void push_front(){insert(begin(),x);}void 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;}void pop_back(){erase(end());}void pop_front(){erase(begin());}//打印void print_list(const list<T> & lt){iterator it = lt.begin();while(it != lt.end()){cout<<*it;++it;}cout<<endl;}}

三、List和Vector对比

vector与list都是stl中非常重要的序列容器,由于两个容器的底层结构不同,导致特性以及应用场景不同

vectorlist
底层结构动态顺序表,一段连续的空间带头节点的双向循环链表
随机访问支持随机访问,访问某个元素效率O(1)不支持随机访问,访问某个元素效率O(N)
插入和删除在任意位置插入删除元素效率较低,时间复杂度O(N),插入可能需要扩容,开辟新空间,拷贝元素,释放旧空间任意位置插入和删除效率高,不需要搬移元素。时间复杂度O(1)
空间利用率底层为连续空间,不容易造成内存碎片,空间利用率高,缓存利用率高底层节点动态开辟,小节点容易造成内存碎片,空间利用率低,缓存利用率低
迭代器原生指针对原生指针(节点指针)进行封装
迭代器失效在插入元素时,要给所有的迭代器重新赋值,因为插入元素有可能导致扩容,导致原来迭代器失效,删除时,也可能失效。需要重新给迭代器赋值插入元素不会导致迭代器失效,删除元素时,只会导致当前迭代器失效,因为那个节点已经被删除。其他迭代器不受影响
使用场景需要高效存储,支持随机访问,不关心插入删除效率大量插入和删除操作,不关心随机访问

总结

本文主要对stl源码中list内容进行阅读,并模拟实现。技术有限,如有错误请指正。

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

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

相关文章

FPGA优质开源模块 - SRIO

本文介绍一个FPGA常用模块&#xff1a;SRIO&#xff08;Serial RapidIO&#xff09;。SRIO协议是一种高速串行通信协议&#xff0c;在我参与的项目中主要是用于FPGA和DSP之间的高速通信。有关SRIO协议的详细介绍网上有很多&#xff0c;本文主要简单介绍一下SRIO IP核的使用和本…

【Shell】基础语法(二)

文章目录 一、Shell基本语法文件名代换命令代换算术代换转义字符引号 二、Shell脚本语法条件测试分支结构循环 三、总结 一、Shell基本语法 文件名代换 用于匹配的字符称为通配符&#xff08;Wildcard&#xff09;&#xff0c;如&#xff1a;* ? [ ] 具体如下&#xff1a; *…

mysql 数据库引擎介绍

一、数据库引擎 数据库引擎是用于存储、处理和保护数据的核心服务。利用数据库引擎可控制访问权限并快速处理事务&#xff0c;从而满足企业内大多数需要处理大量数据的应用程序的要求。 使用数据库引擎创建用于联机事务处理或联机分析处理数据的关系数据库。这包括创建用于存储…

分布式事务

事务是用户定义的一系列的数据库操作&#xff0c;这些操作可以视为一个完整的逻辑处理工作单元&#xff0c;要么全部成功&#xff08;全部执行&#xff09;&#xff0c;要么全部失败&#xff08;全都不执行&#xff09;&#xff0c;是不可分割的工作单元 分布式事务是指会涉及…

[NOIP2007 普及组] 纪念品分组

[NOIP2007 普及组] 纪念品分组 题目描述 元旦快到了&#xff0c;校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡&#xff0c;他要把购来的纪念品根据价格进行分组&#xff0c;但每组最多只能包括两件纪念品&#xff0c; 并且…

17、YML配置文件及让springboot启动时加载我们自定义的yml配置文件的几种方式

YML配置文件及加载自定义配置文件的几种方式 ★ YAML配置文件 其实本质和.properties文件的是一样的。 Spring Boot默认使用SnakeYml工具来处理YAML配置文件&#xff0c;SnakeYml工具默认就会被spring-boot-starter导入&#xff0c;因此无需开发者做任何额外配置。 YAML本质…

ip网络广播系统网络音频解码终端公共广播SV-7101

SV-7101V网络音频终端产品简介 网络广播终端SV-7101V&#xff0c;接收网络音频流&#xff0c;实时解码播放。本设备只有网络广播功能&#xff0c;是一款简单的网络广播终端。提供一路线路输出接功放或有源音箱。 产品特点 ■ 提供固件网络远程升级■ 标准RJ45网络接口&…

安装Win10操作系统时找不到任何驱动器的解决方法

安装Win10操作系统时找不到任何驱动器的解决方法 有时候在一台新电脑上使用U盘安装系统时提示&#xff1a;我们找不到任何驱动器。 如下图所示&#xff1a; 解决方法&#xff1a; 一、按F12&#xff08;不同电脑进入Bios的按键可能不同&#xff09;将电脑进入Bios画面&#x…

MySQL 的事件调度器

MySQL 的事件调度器可以通过以下方式进行管理&#xff1a; 1】查看事件调度器的状态 SHOW VARIABLES LIKE event_scheduler;2】启用/禁用事件调度器 SET GLOBAL event_scheduler ON;SET GLOBAL event_scheduler OFF; 注意&#xff1a;启用/禁用事件调度器需要具有 SUPE…

处理nacos、tomcat、nginx日志增长过快问题

1.nacos日志清理 修改nacos-logback.xml 将日志级别改为error级&#xff0c;减少info级日志产生量 将<maxHistory>调整为2以下&#xff0c;将 <totalSizeCap>调整为2GB左右 比如&#xff1a; [rootiZ0jlapur4hqjezy8waee0Z logs]# ll -h total 2.1G -rw-r--r-…

【Spring Boot】Thymeleaf模板引擎 — 表达式的语法

表达式的语法 模板的主要作用是将后台返回的数据渲染到HTML中。那么Thymeleaf是如何解析后台数据的呢&#xff1f;接下来从变量、方法、条件判断、循环、运算&#xff08;逻辑运算、布尔运算、比较运算、条件运算&#xff09;方面学习Thymeleaf表达式支持的语法。 1.赋值和拼…

RPC框架引入zookeeper服务注册与服务发现

Zookeeper概念及其作用 ZooKeeper是一个分布式的&#xff0c;开放源码的分布式应用程序协调服务&#xff0c;是Google的Chubby一个开源的实现&#xff0c;是大数据生态中的重要组件。它是集群的管理者&#xff0c;监视着集群中各个节点的状态根据节点提交的反馈进行下一步合理…

使用 LangChain 搭建基于 Amazon DynamoDB 的大语言模型应用

LangChain 是一个旨在简化使用大型语言模型创建应用程序的框架。作为语言模型集成框架&#xff0c;在这个应用场景中&#xff0c;LangChain 将与 Amazon DynamoDB 紧密结合&#xff0c;构建一个完整的基于大语言模型的聊天应用。 本次活动&#xff0c;我们特意邀请了亚马逊云科…

git 版本管理工具 学习笔记

git 学习笔记 目录 一、git是什么 二、创建仓库 三、工作区域和文件状态 四、添加和提交文件 五、回退版本 &#xff08;了解&#xff09; 六、查看差异 七、删除文件 八、.gitignore文件&#xff08;了解&#xff09; 九、github ssh-key配置 十、本地仓库和远程仓库内…

C++ STL vector

目录 一.认识vector 二.vector的使用 1.vector的构造函数 2.vector的迭代器 2.1 begin&#xff08;&#xff09;&#xff0c;end&#xff08;&#xff09; 2.2 rbegin&#xff08;&#xff09;&#xff0c;rend&#xff08;&#xff09; 2.3 迭代器初始化对象 3. vector…

pp-ocr报错记录

RESER 报错&#xff1a; distutils.errors.DistutilsError: Could not find suitable distribution for Requirement.parse(‘tomli>1.0.0’) 解决办法&#xff1a; 参考&#xff1a;https://stackoverflow.com/questions/67603407/distutilserror-could-not-find-suitable…

网络编程——MAC地址、IP地址和子网掩码

MAC地址、IP地址和子网掩码 一、MAC地址&#xff1a;硬件身份证 1、MAC地址的概念 MAC地址&#xff0c;即媒体访问控制地址&#xff08;Media Access Control Address&#xff09;&#xff0c;是一个用于唯一标识网络设备的物理地址。每个网络接口卡&#xff08;NIC&#xf…

RocketMQ 主备自动切换模式部署

目录 主备自动切换模式部署 Controller 部署​ Controller 嵌入 NameServer 部署​ Controller 独立部署​ Broker 部署​ 兼容性​ 升级注意事项​ 主备自动切换模式部署 该文档主要介绍如何部署支持自动主从切换的 RocketMQ 集群&#xff0c;其架构如上图所示&#xff…

TeeChart NET for MAUI Crack

TeeChart NET for MAUI Crack 跨平台图表-移动或桌面应用程序的核心图表代码相同。 图表集合-60多种图表类型和50多种财务和统计指标。 图表类型 60多种2D和3D图表类型以及多种组合&#xff0c;包括&#xff1a; 标准&#xff1a;线条(条形)、条形、区域、饼图、快线、点(散点…

24届近5年上海大学自动化考研院校分析

今天给大家带来的是上海大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、上海大学 学校简介 上海大学是上海市属的综合性研究型大学&#xff0c;是教育部与上海市人民政府共建高校&#xff0c;是国家“211 工程”重点建设高校、上海市高水平地方大学建设高校&a…