C++ vector模拟实现
目录
一.默认成员函数
二.扩容相关函数
三.[]重载
四.修改函数
五.迭代器
继上次写完string之后,可以写一个vector练练手以及熟悉其底层。vector是一个顺序表,相比普通数组不同点在于顺序表的数据必须是连续存放的。
一.默认成员函数
string是只存放字符,而vector需要存放内置类型和自定义类型,所以需要引入类模板。以下是vector的最外层框架。
template<class T>//类模板参数,T是接收外面转进来的类型,可以使内置也可以是自定义类型class vector{public://成员函数的定义private://内置成员变量是三个迭代器,vector的迭代器实际上还是指针iterator _start = nullptr; // 指向数据块的开始iterator _finish = nullptr; // 指向有效数据的尾iterator _endOfStorage = nullptr; // 指向存储容量的尾};
以下是vector的默认成员函数,重载&和const &重载一般不需要手动写。
vector()//默认构造函数{}vector(int n, const T& value = T())//构造一个包含n个元素的vector,每个元素都是value{resize(n, value);//直接用resize即可}template<class InputIterator>vector(InputIterator first, InputIterator last)//通过一个迭代器区间构造vector{while (first != last){push_back(*first);first++;}}vector(const vector<T>& v)//拷贝构造函数{vector tmp(v.begin(), v.end());//复用迭代器区间构造函数完成拷贝,然后再交换swap(tmp);}vector<T>& operator= (vector<T> v)//通过传值来完成拷贝,然后再交换{swap(v);return *this;}~vector()//析构函数{delete[] _start;//直接delete,由于是delete[]所以即使是多层嵌套(自定义类型或者vector或其他类型)也会调用他们的析构函数(这里需了解delete[]原理)_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}
二.扩容相关函数
扩容函数需要注意异地扩容时把原来空间的元素拷贝到新空间时需要使用赋值而不是memcpy或memmove。对于自定义类型并且实现了深拷贝的赋值就不会出现因为浅拷贝导致多次析构的问题。
size_t size() const{return _finish - _start;//返回当前元素个数}size_t capacity() const{return _endOfStorage - _start;//返回总容量大小}void reserve(size_t n)//扩容{if (n > capacity())//判断目标扩容大小有没有大于总容量{T* tmp = new T[n];//直接创建新空间,大小为nsize_t sz = size();//记录扩容前的元素个数if (_start)//如果_start不为空(如果为空也不用复制元素内容了){for (int i = 0; i < sz; i++){tmp[i] = _start[i];//这里如果用memmove或者memcopy对于自定义类型会发生多次析构的问题(相当于浅拷贝),所以还是用赋值,如果自定义类型有实现深拷贝就没问题}delete[] _start;//这里把原来的删除,如果是浅拷贝,这里的删除了,tmp里面的自定义类型指针就变成野指针了}_start = tmp;//修改_start_finish = tmp + sz;//记录sz的好处_endOfStorage = tmp + n;}}void resize(size_t n, const T& value = T())//扩容或减容至n个元素,扩容的话会用value填满所有空间{if (n < size())//判断目标扩容大小是不是小于当前元素个数{T* tmp = new T[n];//直接创建新空间,大小为nfor (int i = 0; i < n; i++){tmp[i] = _start[i];//一个个拷贝,这里用赋值和reserve原因完全一样}//下面也和reserve一样delete[] _start;_start = tmp;_finish = tmp + n;_endOfStorage = tmp + n;}else if (n > size())//这里是目标扩容大小大于当前元素个数{int i = size();//记录当前元素个数reserve(n);//扩容while (i < n){_start[i++] = value;//从当前元素的结尾开始填充,直到容量达到目标扩容大小}_finish = _start + n;//更新_finish}}
三.[]重载
[]重载需要断言是否越界,以及还要实现const版本。
T& operator[](size_t pos)//方括号重载{assert(pos < size());return _start[pos];}const T& operator[](size_t pos) const//const方括号重载{assert(pos < size());return _start[pos];}
四.修改函数
修改函数需要注意insert的pos迭代器失效问题以及erase的迭代器失效(对于外部的迭代器)。
void push_back(const T& x)//尾插{if (_finish == _endOfStorage){reserve(capacity() == 0 ? 4 : capacity() * 2);}_start[size()] = x;//结尾插入元素_finish++;//更新_finish//或者复用insert//insert(end(),x);}void pop_back()//尾删{erase(end());//直接调用erase函数尾删}void swap(vector<T>& v)//交换两个vector的成员变量{std::swap(_start, v._start);std::swap(_finish, v._finish);std::swap(_endOfStorage, v._endOfStorage);}iterator insert(iterator pos, const T& x)//在pos位置之前插入{assert(pos >= begin());//断言,防止pos越界assert(pos <= end());size_t sz = pos - _start;//计算并记录pos和_start的相对距离,也是待会要插入的位置if (_finish == _endOfStorage)//判断是否要扩容{reserve(capacity() == 0 ? 4 : capacity() * 2);}//重点注意,这里是insert迭代器可能失效的地方pos = _start + sz;//如果是异地扩容,那么pos所指的位置会被删除就变成野指针了,所以要更新pos位置,之前记录的sz就有用了if (size())//如果当前元素个数不为0的话{//从后往前走,然后把左边的数据挪到右边,需要注意下标的越界问题iterator end = _finish;while (end > pos){*end = *(end - 1);//左边的数据挪到右边end--;}}_start[sz] = x;//放入数据_finish++;//更新_finishreturn pos;//返回插入元素的下一个位置,也就是pos}iterator erase(iterator pos)//删除当前位置的元素{assert(pos >= begin());//判断pos是否越界assert(pos <= end());iterator prev = pos + 1;//记录pos位置的前一个位置//从左往右走,然后把右边的数据挪到左边,直接覆盖要删除的元素while (prev < end()){*(prev - 1) = *prev;//把右边的数据挪到左边prev++;}_finish--;//更新_finish//这里是第二个迭代器失效问题,如果外面的迭代器不接受erase返回的迭代器可能后面的删除会出问题return pos;//返回删除元素的下一个位置(其实还是pos)}
五.迭代器
vector迭代器就是原生指针,以及实现const迭代器。
typedef T* iterator;//vector的迭代器是原生指针,和string一样typedef const T* const_iterator;//const迭代器iterator begin(){return _start;}iterator end(){return _finish;}const_iterator begin() const{return _start;}const_iterator end() const{return _finish;}
以上就是vector的模拟实现,写完后不仅可以提升对代码的操作熟练度,对于顺序表这种数据结构也能有更深的理解。
相关文章:
C++ vector模拟实现
目录 一.默认成员函数 二.扩容相关函数 三.[]重载 四.修改函数 五.迭代器 继上次写完string之后,可以写一个vector练练手以及熟悉其底层。vector是一个顺序表,相比普通数组不同点在于顺序表的数据必须是连续存放的。 一.默认成员函数 string是只存放字符…...
BUUCTF:[GYCTF2020]FlaskApp
Flask的网站,这里的功能是Base64编码解码,并输出 并且是存在SSTI的 /hint 提示PIN码 既然提示PIN,那应该是开启了Debug模式的,解密栏那里随便输入点什么报错看看,直接报错了,并且该Flask开启了Debug模式&am…...
好玩的调度技术
好玩的调度技术 文章目录 好玩的调度技术前言一、乱金柝-空间剥离二、拖拽编辑三、全端兼容 前言 最近感觉自己抑郁了,生态技术实在太庞大太复杂,所以我决定先停一段时间,在停下写生态的这两天写了几个调度的小玩意换换脑子,很有…...
Android 自定义加解密播放音视频(m3u8独立加密)
文章目录 背景加密流程音视频解密音视频播放结语 背景 当涉及App内部视频的时候,我们不希望被别人以抓包的形式来爬取我们的视频大视频文件以文件方式整个加密的话需要完全下载后才能进行解密当前m3u8格式虽然支持加密,但是ts格式的小视频可以独立播放的…...
常见的文件格式
一、C:\fakepath\新建文本文档.txt [object String] 实现方式: <input onchange"test(this.value)" type"file"></input><script>function test(e){console.log(e,Object.prototype.toString.call(e))}</script> 二、…...
浏览器输入url后回车展开过程
当你在浏览器中输入一个URL并敲下回车后,浏览器会执行一系列步骤来访问并展示网页。下面是浏览器访问网页的一般流程: DNS解析:浏览器首先会提取URL中的主机名,然后向DNS服务器发送请求,将主机名解析为对应的IP地址。这…...
Docker 容器创建命令说明
使用命令如下: docker run -itd --name=cluster -v /home/ClusterApp/cluster:/home/ClusterApp/cluster --restart=always --privileged=true -p 12000:12000 python:3.8 命令说明: docker run 创建一个容器并运行 docker run --help 可以查看所有的参数: 命令中参数说明 -…...
西瓜书读书笔记整理(六)—— 第六章 支持向量机
第六章 支持向量机 6.1 间隔与支持向量6.1.1 什么是支持向量机6.1.2 支持向量与间隔6.1.3 支持向量机的求解过程 6.2 对偶问题(dual problem)6.2.1 什么是对偶问题6.2.2 如何求解支持向量机的对偶问题 6.3 核函数(kernel function)…...
蓝桥杯每日一题2023.9.23
4961. 整数删除 - AcWing题库 题目描述 分析 注:如果要进行大量的删除操作可以使用链表 动态求最小值使用堆,每次从堆中取出最小值的下标然后在链表中删除 注意long long 代码解释: while(k --){auto t q.top();q.pop();res t.first;i…...
C语言数组和指针笔试题(三)(一定要看)
目录 字符数组四例题1例题2例题3例题4例题5例题6例题7 结果字符数组五例题1例题2例题3例题4例题5例题6例题7结果字符数组六例题1例题2例题3例题4例题5例题6例题7 结果 感谢各位大佬对我的支持,如果我的文章对你有用,欢迎点击以下链接 🐒🐒🐒个…...
leetcode11 盛水最多的容器
题目 给定一个长度为 n 的整数数组 height 。有 n 条垂线,第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 找出其中的两条线,使得它们与 x 轴共同构成的容器可以容纳最多的水。 返回容器可以储存的最大水量。 示例 输入:[1,8,6,2,5,4,8,…...
进入数据结构的世界
数据结构和算法的概述 一、什么是数据结构二、什么是算法三、如何去学习数据结构和算法四、算法的时间复杂度和空间复杂度4.1 算法效率4.2 大O的渐进表示法4.3 时间复杂度4.4 空间复杂度4.5 常见复杂度对比 一、什么是数据结构 数据结构是计算机存储、组织数据的方式。&#x…...
stm32之看门狗
STM32 有两个看门狗,独立看门狗和窗口看门狗,独立看门狗又称宠物狗,窗 口看门狗又称警犬。可用来检测和解决由软件错误引起的故障。两个看门狗的原理都是当计数器达到给定的超时值时,产生系统复位,对于窗口型看门狗同…...
纤维蛋白单体(FM)介绍
纤维蛋白单体(FM)是血栓形成的早期产物,是纤维蛋白原(Fibrinogen,Fbg)在凝血酶(Thrombin)的作用下,脱掉肽A(Fibrinopeptide A,Fp A)与…...
知识图谱实战导论:从什么是KG到LLM与KG/DB的结合实战
前言 本文侧重讲解: 什么是知识图谱LLM与langchain/数据库/知识图谱的结合应用 比如,虽说基于知识图谱的问答 早在2019年之前就有很多研究了,但谁会想到今年KBQA因为LLM如此突飞猛进呢 第一部分 知识图谱入门导论 //待更.. 第二部分 LLM与…...
第5章 会话与会话技术
第5章 会话与会话技术 一. 单选题(共5题,50分)二. 判断题(共5题,50分) 一. 单选题(共5题,50分) (单选题) 阅读下面代码: Book book BookDB.getBook(id)…...
IDEA2023新UI回退老UI
idea2023年发布了新UI,如下所示 但是用起来真心不好用,各种位置也是错乱,用下面方法可以回退老UI...
ElasticSearch(三)
1.数据聚合 聚合(aggregations)可以让我们极其方便的实现对数据的统计、分析、运算。例如: 什么品牌的手机最受欢迎? 这些手机的平均价格、最高价格、最低价格? 这些手机每月的销售情况如何? 实现这些…...
【LinkedHashMap】146. LRU 缓存
146. LRU 缓存 解题思路 与普通的 HashMap 不同,LinkedHashMap 会保持元素的有序性。这可以在某些情况下提供更可预测的迭代顺序直接获取元素 因为使用到该元素 将该元素重新放入队尾 表示最近使用该元素写入元素,首先如果该元素原来存在 那么需要将ke…...
Opencv-python去图标与水印方案实践
RGB色彩模式是工业界的一种颜色标准,是通过对红(R)、绿(G)、蓝(B)三个颜色通道的变化以及它们相互之间的叠加来得到各式各样的颜色的,RGB即是代表红、绿、蓝三个通道的颜色ÿ…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Day131 | 灵神 | 回溯算法 | 子集型 子集
Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣(LeetCode) 思路: 笔者写过很多次这道题了,不想写题解了,大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...
安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件
在选煤厂、化工厂、钢铁厂等过程生产型企业,其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进,需提前预防假检、错检、漏检,推动智慧生产运维系统数据的流动和现场赋能应用。同时,…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)
目录 1.TCP的连接管理机制(1)三次握手①握手过程②对握手过程的理解 (2)四次挥手(3)握手和挥手的触发(4)状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
Spring Boot面试题精选汇总
🤟致敬读者 🟩感谢阅读🟦笑口常开🟪生日快乐⬛早点睡觉 📘博主相关 🟧博主信息🟨博客首页🟫专栏推荐🟥活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
探索Selenium:自动化测试的神奇钥匙
目录 一、Selenium 是什么1.1 定义与概念1.2 发展历程1.3 功能概述 二、Selenium 工作原理剖析2.1 架构组成2.2 工作流程2.3 通信机制 三、Selenium 的优势3.1 跨浏览器与平台支持3.2 丰富的语言支持3.3 强大的社区支持 四、Selenium 的应用场景4.1 Web 应用自动化测试4.2 数据…...
