当前位置: 首页 > news >正文

【C++模拟实现】vector的模拟实现

【C++模拟实现】vector的模拟实现

目录

  • 【C++模拟实现】vector的模拟实现
      • vector模拟实现的标准代码
      • vector模拟实现中的要点
        • insert和erase会涉及到迭代器失效的问题
        • vector深度剖析
        • 关于模版template< class InputIterator >
        • 使用memcpy拷贝问题


作者:爱写代码的刚子

时间:2023.9.1

前言:模拟实现系列好久没更了,前来补更。

vector模拟实现的标准代码

namespace test
{template<class T>class vector{public:typedef T* iterator;typedef const T* const_iterator;iterator begin(){return _start;}iterator end(){return _finish;}const_iterator cbegin(){return _start;}const_iterator cend() const{return _finish;}vector():_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){}vector(int n, const T& value = T()){resize(n,value);}template<class InputIterator>vector(InputIterator first, InputIterator last):_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){//存疑,是否要reservewhile(first!=last){push_back(*first);++first;}}vector(const vector<T>& v)//这里是引用:_start(nullptr),_finish(nullptr),_endOfStorage(nullptr){reserve(v.capacity());for(auto e:v){push_back(e);}}vector<T>& operator= (vector<T> v){swap(v);return *this;}~vector(){delete[] _start;_start = nullptr;_finish = nullptr;_endOfStorage = nullptr;}size_t size() const{return _finish - _start;}size_t capacity() const{return _endOfStorage - _start;}void reserve(size_t n){if(n>capacity()) {iterator tmp = new T[n];//拷贝数据(手动)int sz = size();if(_start) {for (int i = 0; i < sz; i++) {tmp[i] = _start[i];}delete[] _start;//一定要记得}_start = tmp;_finish = _start + sz;_endOfStorage = _start + n;}}void resize(size_t n, const T& value = T()){if(n<capacity()){_finish=_start + n;}else{reserve(n);while(_finish!=_start+n){*_finish=value;++_finish;}}}T& operator[](size_t pos){assert(pos<size());return _start[pos];}const T& operator[](size_t pos)const{assert(pos<size());return _start[pos];}void push_back(const T& x){insert(end(),x);}void pop_back(){erase(--end());//注意是--end(),end()指向的是数据的下一个位置}void swap(vector<T>& v){std::swap(v._start,_start);std::swap(v._finish,_finish);std::swap(v._endOfStorage,_endOfStorage);}iterator insert(iterator pos, const T& x){assert(pos>=_start&&pos<=_finish);if(_finish==_endOfStorage){size_t len = pos - _start;size_t newcapacity = capacity()==0?4:capacity()*2;reserve(newcapacity);pos = _start + len;}iterator end = _finish - 1;while(end>=pos){*(end+1) = *end;--end;//--end不是++end()}*pos = x;++_finish;return pos;}iterator erase(iterator pos){assert(pos>=_start&&pos<=_finish);iterator it=pos+1;while(it!=_finish){*(it-1)=*it;++it;}--_finish;return pos;}private:iterator _start; // 指向数据块的开始iterator _finish; // 指向有效数据的尾iterator _endOfStorage; // 指向存储容量的尾};
}

vector模拟实现中的要点

insert和erase会涉及到迭代器失效的问题

迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了 封装,比如:vector的迭代器就是原生态指针T*。因此迭代器失效,实际就是迭代器底层对应指针所指向的 空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,程序可能会崩溃)。

有关迭代器失效的几种做法

  • 对于vector可能会导致其迭代器失效的操作有:

    1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、 push_back等。

      出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉, 而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的空间,而引起代码运行时崩溃。

      解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新赋值即可。

    2. 指定位置元素的删除操作–erase

      erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效了。(但Linux下g++可能不一样,因为迭代器使用了原生指针,没有像vs一样进行封装)

**迭代器失效解决办法:在使用前,对迭代器重新赋值即可。 **

涉及到底层空间改变时,需要考虑重置迭代器

vector深度剖析

在这里插入图片描述

关于模版template< class InputIterator >

为什么不使用自己之前定义的iterator?

  • 若使用iterator做迭代器,会导致初始化的迭代器区间[first,last)只能是vector的迭代器
  • 重新声明迭代器,迭代器区间[first,last)可以是任意容器的迭代器

使用memcpy拷贝问题

为什么在reserve接口中不能直接使用memcpy进行拷贝?

  1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
  2. 如果拷贝的是自定义类型的元素,memcpy即高效又不会出错,但如果拷贝的是自定义类型元素,并且自定义类型元素中涉及到资源管理时,就会出错,memcpy的拷贝实际是浅拷贝。

所以在模版模拟实现中慎用memcpy!!!

结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃。


【附】:范围for是C++11的

相关文章:

【C++模拟实现】vector的模拟实现

【C模拟实现】vector的模拟实现 目录 【C模拟实现】vector的模拟实现vector模拟实现的标准代码vector模拟实现中的要点insert和erase会涉及到迭代器失效的问题vector深度剖析关于模版template< class InputIterator >使用memcpy拷贝问题 作者&#xff1a;爱写代码的刚子 …...

go学习part21(3)redis连接池

连接池 1.介绍 每次使用数据就就建立链接再关闭可以&#xff0c;但是如果有大量客户端频繁请求连接&#xff0c;大量创建连接和关闭会非常耗费资源。 所以就建立一个连接池&#xff0c;里面存放几个不关闭的连接&#xff0c;谁要用就分配给谁。 说明:通过Golang 对 Redis操…...

乐理-笔记

乐理笔记整理 1、前言2、认识钢琴键盘及音名3、升降号、还原号4、如何区分同一音名的不同键&#xff1f;5、各类音符时值的关系6、歌曲拍号7、拍号的强弱规律8、歌曲速度&#xff08;BPM&#xff09;9、附点音符10、三连音12、唱名与简谱数字13、自然大调&#xff08;白键&…...

java八股文面试[数据库]——B树和B+树的区别

B树是一种树状数据结构&#xff0c;它能够存储数据、对其进行排序并允许以O(logn)的时间复杂度进行查找、顺序读取、插入和删除等操作。 1、B树的特性 B树中允许一个结点中包含多个key&#xff0c;可以是3个、4个、5个甚至更多&#xff0c;并不确定&#xff0c;需要看具体的实…...

2、Nginx 安装

文章目录 2、Nginx 安装2.1 官网下载2.2 安装 nginx2.2.1 第一步2.2.2 第二步2.2.3 第三步&#xff0c;安装 nginx2.2.4 第四步&#xff0c;修改防火漆规则 【尚硅谷】尚硅谷Nginx教程由浅入深 志不强者智不达&#xff1b;言不信者行不果。 2、Nginx 安装 2.1 官网下载 nginx…...

最适合 AI 的 Python Web 框架

迷途小书童的 Note 读完需要 4分钟 速读仅需 2 分钟 1 简介 本文将介绍 Gradio 库&#xff0c;它是 Python 的一个 web 框架&#xff0c;可以帮助我们快速构建交互式 AI 应用。我们将了解 Gradio 的应用场景、基本原理、功能介绍&#xff0c;并通过一个代码示例来演示如何使用 …...

算法通关村第十八关——回溯

回溯很大感觉就是多重递归&#xff0c;在递归的题目中&#xff0c;例如斐波那契数列&#xff0c;只需要考虑当前情况以及他的子情况。而在回溯中&#xff0c;要进行很多次递归&#xff0c;并且要对条件进行处理。 LeetCode257:给你一个二叉树的根节点root,按任意顺序&#xff…...

使用kafka还在依赖Zookeeper,kraft模式了解下

Kafka的Kraft模式 概述 ​ Kafka是一种高吞吐量的分布式发布订阅消息系统&#xff0c;它可以处理消费者在网站中的所有动作流数据。其核心组件包含Producer、Broker、Consumer&#xff0c;以及依赖的Zookeeper集群。其中Zookeeper集群是Kafka用来负责集群元数据的管理、控制器…...

【100天精通Python】Day52:Python 数据分析_Numpy入门基础与数组操作

目录 1 NumPy 基础概述 1.1 NumPy的主要特点和功能 1.2 NumPy 安装和导入 2 Numpy 数组 2.1 创建NumPy数组 2.2 数组的形状和维度 2.3 数组的数据类型 2.4 访问和修改数组元素 3 数组操作 3.1 数组运算 3.2 数学函数 3.3 统计函数 4 数组形状操作 4.1 重塑数组形…...

Day01-Java基础语法

目录 1. 人机交互 1.1 什么是cmd&#xff1f; 1.2 如何打开CMD窗口&#xff1f; 1.3 常用CMD命令 1.4 CMD练习 1.5 环境变量 2. Java概述 1.1 Java是什么&#xff1f; 1.2下载和安装 1.2.1 下载 1.2.2 安装 1.2.3 JDK的安装目录介绍 1.3 HelloWorld小案例 2.3.1 …...

代码随想录二刷day06

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、力扣242. 有效的字母异位词二、力扣349. 两个数组的交集三、力扣202. 快乐数四、力扣1两数之和 前言 一、力扣242. 有效的字母异位词 class Solution {pub…...

可扩展的Blender插件开发汇总

成熟的 Blender 3D 插件是令人惊奇的事情。作为 Python 和 Blender 的新手,我经常发现自己被社区中的人们创造的强大的东西弄得目瞪口呆。坦率地说,其中一些包看起来有点神奇,当自我怀疑或冒名顶替综合症的唠叨声音被打破时,很容易想到“如果有人能做出可以做xxx的东西就好…...

2023_Spark_实验二:IDEA安装及配置

一、下载安装包 链接&#xff1a;百度网盘 请输入提取码 所在文件夹&#xff1a;大数据必备工具--》开发工具(前端后端)--》后端 下载文件名称&#xff1a;ideaIU-2019.2.3.exe &#xff08;喜欢新版本也可安装新版本&#xff0c;新旧版本会存在部分差异&#xff09; IDEA …...

小赢科技,寻找金融科技核心价

如果说金融是经济的晴雨表&#xff0c;是通过改善供给质量以提高经济质量的切入口&#xff0c;那么金融科技公司&#xff0c;就是这一切行动的推手。上半年&#xff0c;社会经济活跃程度提高背后&#xff0c;金融科技公司既是奉献者&#xff0c;也是受益者。 8月29日&#xff0…...

NAT与代理服务器

1.DNS Domain Name System 是一整套从域名映射到IP的系统&#xff08;把域名转化为IP地址&#xff09; 2.域名简介 3.周鸿祎 傅盛 4.ICMP协议 用来网络故障排查原因 草图理解“位置” ping ICMP 是绕过TCP UDP传输协议的&#xff0c;没有端口号 traceroute 5.NAT技术 N…...

24.排序,插入排序,交换排序

目录 一. 插入排序 &#xff08;1&#xff09;直接插入排序 &#xff08;2&#xff09;折半插入排序 &#xff08;3&#xff09;希尔排序 二. 交换排序 &#xff08;1&#xff09;冒泡排序 &#xff08;2&#xff09;快速排序 排序&#xff1a;将一组杂乱无章的数据按一…...

Navicat16安装教程

注&#xff1a;因版权原因&#xff0c;本文已去除破解相关的文件和内容 1、在本站下载解压后即可获得Navicat16安装包和破解补丁&#xff0c;如图所示 2、双击“navicat160_premium_cs_x64.exe”程序&#xff0c;即可进入安装界面&#xff0c; 3、点击下一步 4、如图所示勾选“…...

【看表情包学Linux】初识文件描述符 | 虚拟文件系统 (VFS) 初探 | 系统传递标记位 | O_TRUNC | O_APPEND

爆笑教程《看表情包学Linux》&#x1f448; 猛戳订阅&#xff01;​​​​​ &#x1f4ad; 写在前面&#xff1a;通过上一章节的讲解&#xff0c;想必大家已对文件系统基本的接口有一个简单的了解&#xff0c;本章我们将继续深入讲解&#xff0c;继续学习系统传递标志位&…...

ssm+vue“魅力”繁峙宣传网站源码和论文

ssmvue“魅力”繁峙宣传网站源码和论文102 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 随着科学技术的飞速发展&#xff0c;各行各业都在努力与现代先进技术接轨&#xff0c;通过科技手段提高自身…...

Linux系统编程5(线程概念详解)

线程同进程一样都是OS中非常重要的部分&#xff0c;线程的应用场景非常的广泛&#xff0c;试想我们使用的视频软件&#xff0c;在网络不是很好的情况下&#xff0c;通常会采取下载的方式&#xff0c;现在你很想立即观看&#xff0c;又想下载&#xff0c;于是你点击了下载并且在…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

2021-03-15 iview一些问题

1.iview 在使用tree组件时&#xff0c;发现没有set类的方法&#xff0c;只有get&#xff0c;那么要改变tree值&#xff0c;只能遍历treeData&#xff0c;递归修改treeData的checked&#xff0c;发现无法更改&#xff0c;原因在于check模式下&#xff0c;子元素的勾选状态跟父节…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

spring Security对RBAC及其ABAC的支持使用

RBAC (基于角色的访问控制) RBAC (Role-Based Access Control) 是 Spring Security 中最常用的权限模型&#xff0c;它将权限分配给角色&#xff0c;再将角色分配给用户。 RBAC 核心实现 1. 数据库设计 users roles permissions ------- ------…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

前端高频面试题2:浏览器/计算机网络

本专栏相关链接 前端高频面试题1&#xff1a;HTML/CSS 前端高频面试题2&#xff1a;浏览器/计算机网络 前端高频面试题3&#xff1a;JavaScript 1.什么是强缓存、协商缓存&#xff1f; 强缓存&#xff1a; 当浏览器请求资源时&#xff0c;首先检查本地缓存是否命中。如果命…...

jdbc查询mysql数据库时,出现id顺序错误的情况

我在repository中的查询语句如下所示&#xff0c;即传入一个List<intager>的数据&#xff0c;返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致&#xff0c;会导致返回的id是从小到大排列的&#xff0c;但我不希望这样。 Query("SELECT NEW com…...

验证redis数据结构

一、功能验证 1.验证redis的数据结构&#xff08;如字符串、列表、哈希、集合、有序集合等&#xff09;是否按照预期工作。 2、常见的数据结构验证方法&#xff1a; ①字符串&#xff08;string&#xff09; 测试基本操作 set、get、incr、decr 验证字符串的长度和内容是否正…...