【C++】vector模拟实现

目录

  • 简介:
  • 私有成员:
    • 迭代器:
  • 无参构造函数:
  • push_back:
    • reserve:
    • resize:
    • push_back:
  • operator[]重载:
  • begin && end:
  • size && capacity:
  • insert:
  • erase:
  • 带参构造:
  • 迭代器区间构造:
  • 拷贝构造 && 赋值运算符重载:
  • 析构函数:
  • 深浅拷贝的验证:

简介:

本文将利用C/C++模拟vector常用接口实现,可以更好的帮助理解vector底层。

主体的实现思路是先搭起来一个能跑的架子,再一点点的补充完善。

私有成员:

与我们曾经实现过得顺序表有些不一样,顺序表是一个malloc出来的指针指向数组,另外还有capacity与size

但在这里我们参照vector的原码进行模拟,使用三个迭代器进行控制这个动态数组。

	private:
		iterator start = nullptr;
		iterator finish = nullptr;
		iterator end_of_storage = nullptr;

故因此我们先要了解一下这个迭代器的设计,我们在模拟string时,由于string底层也是数组,由于虚拟地址的存在,我们认为数组在内存是连续的,故可以直接使用原生指针进行模拟迭代器,vector也是数组,我们当然也可以使用原生指针进行模拟迭代器

在这里插入图片描述
关于各个指针的含义

迭代器:

由于我们的vector需要支持不同类型,需要使用模版进行设计,故我们设置迭代器时如下图定义即可。

	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
	}

至于为什么设计两个类型迭代器是为了const对象也可以调用,更具体可以看一下string模拟实现中的迭代器。

无参构造函数:

无参的没什么好说的,直接全初始化为nullptr。

		vector()
			:start(nullptr)
			, finish(nullptr)
			, end_of_storage(nullptr)
		{}

push_back:

reserve:

因为push_back等很多操作涉及扩容的问题,故我们可以先实现一个reserve的接口,方便接下来使用:

		void reserve(size_t n)
		{
			size_t capacity = end_of_storage - start;
			if (capacity < n)
			{
				size_t size = finish - start;
				T* tmp = new T[n];
				//memcpy(tmp, start, size * sizeof(T));
				for (int i = 0; i < size; i++)
				{
					*(tmp + i) = *(start + i);
				}
				delete[] start;

				start = tmp;
				finish = tmp + size;
				end_of_storage = tmp + n;
			}
		}

关于为什么使用逐个赋值而不是直接memcpy是为了防止浅拷贝,在接下来会有演示

既然都实现了reserve那么resize也就顺便实现一下。

resize:

		void resize(size_t n, const T& val = T())
		{
			size_t capacity = end_of_storage - start;
			if (n > capacity)
			{
				reserve(n);
				size_t len = end_of_storage - finish;
				while (len--)
				{
					*finish = val;
					finish++;
				}
			}
			else
			{
				finish = start + n;
			}
		}

push_back:

		void push_back(const T& val)
		{
			if (finish == end_of_storage)
			{
				size_t capacity = end_of_storage - start;

				reserve(capacity == 0 ? 4 : capacity * 2);
			}
			*finish = val;
			finish++;
		}

这里针对嵌套类型也不用担心浅拷贝。
如果嵌套string类
*finish是一个string对象,赋值时会调用string内部的深拷贝。

operator[]重载:

		T& operator[](size_t pos)
		{
			return start[pos];
		}

		const T& operator[](size_t pos) const
		{
			return start[pos];
		}

由于const对象也会调用,故我们也要实现const版本的重载。

begin && end:

		iterator begin()
		{
			return start;
		}

		iterator end()
		{
			return finish;
		}

		const_iterator end() const
		{
			return finish;
		}

		const_iterator begin() const
		{
			return start;
		}

size && capacity:

		size_t size()
		{
			return finish - start;
		}

		size_t capacity()
		{
			return end_of_storage - start;
		}

		size_t size() const
		{
			return finish - start;
		}

		size_t capacity() const
		{
			return end_of_storage - start;
		}

insert:

		void insert(iterator pos, const T& val)
		{
			if (finish == end_of_storage)
			{
				int distance = pos - start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				pos = start + distance;
			}

			int i = 0;
			int count = finish - pos;
			while(count--)
			{
				*(finish - i) = *(finish - i - 1);
				i++;
			}
			finish++;
			*pos = val;
		}

erase:

		void erase(iterator pos)
		{
			assert(size());
			int count = finish - pos - 1;
			int i = 0;
			while (count--)
			{
				*(pos + i) = *(pos + i + 1);
				i++;
			}
			finish--;
		}

带参构造:

		vector(int n, const T& val = T())
		{
			reserve(n);

			while (n--)
			{
				push_back(val);
			}
		}

迭代器区间构造:

		template<class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}

拷贝构造 && 赋值运算符重载:

关于拷贝构造与赋值运算符重载一般有两种实现方案,一般方法与现代方法
下图是现代方法,龙我们已经写好的接口进行拷贝,不用自己开空间,自己赋值等操作。

		vector(const vector<T>& v)
		{
			for (auto& val : v)
			{
				push_back(val);
			}
		}

而赋值的做法更绝,因为传参不带引用会调用拷贝构造。我们直接利用拷贝构造的成果,进行swap,而等赋值拷贝结束会自动调用析构,帮助我们将旧的vector对象进行解决。

		void swap(vector<T>& v)
		{
			std::swap(start, v.start);
			std::swap(finish, v.finish);
			std::swap(end_of_storage, v.end_of_storage);
		}

		vector& operator= (vector<T> val)
		{
			swap(val);

			return *this;
		}

析构函数:

		~vector()
		{
			delete[] start;
			start = finish = end_of_storage = nullptr;
		}

深浅拷贝的验证:

当我们在vector内放置自定义类型,如果你的程序浅拷贝,那么大概率会报错
在这里插入图片描述
而深浅拷贝都会发生在扩容,我们的扩容依赖的都是reserve这个接口,故这个接口一定不能发生浅拷贝的问题。

就像我们在reserve哪里说的,不能使用memcpy,这样会发生浅拷贝
在这里插入图片描述
解决方法也很简单,利用自定义类型的深拷贝即可

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

PyQt ui2py 使用PowerShell将ui文件转为py文件并且将导入模块PyQt或PySide转换为qtpy模块开箱即用

前言 由于需要使用不同的qt环境&#xff08;PySide&#xff0c;PyQt&#xff09;所以写了这个脚本&#xff0c;使用找到的随便一个uic命令去转换ui文件&#xff0c;然后将导入模块换成qtpy这个通用库(支持pyside2-6&#xff0c;pyqt5-6)&#xff0c;老版本的是Qt.py(支持pysid…

论文阅读——Sat2Vid

Sat2Vid: Street-view Panoramic Video Synthesis from a Single Satellite Image 提出了一种新颖的方法&#xff0c;用于从单个卫星图像和摄像机轨迹合成时间和几何一致的街景全景视频。 即根据单个卫星图像和给定的观看位置尽可能真实地、尽可能一致地合成街景全景视频序列。…

Python+Django+Html河道垃圾识别网页系统

程序示例精选 PythonDjangoHtml河道垃圾识别网页系统 如需安装运行环境或远程调试&#xff0c;见文章底部个人QQ名片&#xff0c;由专业技术人员远程协助&#xff01; 前言 这篇博客针对《PythonDjangoHtml河道垃圾识别网页系统》编写代码&#xff0c;代码整洁&#xff0c;规…

如何编写属于自己的第一个exp

0x00 前言 在我们找到一个漏洞之后&#xff0c;可能会想着去fofa上搜语法进而扩大战果&#xff0c;而有些漏洞利用起来十分繁琐&#xff0c;这时候就需要一个exp来批量帮我们进行扫描工作&#xff0c;接下来就介绍一下如何进行exp的编写&#xff0c;这个过程中最重要的还是体现…

Docker简单介绍、特点、与虚拟机技术的区别、核心概念及在CentOS 7 中安装卸载Docker

目录 一、什么是Docker 二、特点 三、Docker与虚拟机技术的区别 四、Docker的核心概念 Docker仓库与仓库注册服务器的区别 五、CentOS7在线安装Docker 安装配置 卸载 一、什么是Docker Docker是一个开源的容器化平台&#xff0c;用于打包、部署和运行应用程序。它利用…

AI设计优化电机、电路与芯片?

一、AI进行电机本体设计 使用AI进行电机本体设计是一种前沿且具有潜力的方法&#xff0c;通过深度学习、强化学习、遗传算法等AI技术&#xff0c;可以实现电机设计的自动化和优化。具体应用可以包括以下几个方面&#xff1a; 此图片来源于网络 1. **参数优化**&#xff1a; …

硬件基础知识

CPU制作 cpu组成原理 CPU (Central Processing Unit - 中央处理单元): CPU 是计算机的核心&#xff0c;负责解释和执行程序指令以及处理数据。它由几个关键部分组成&#xff0c;如算术逻辑单元&#xff08;ALU&#xff09;、寄存器、和控制单元&#xff08;CU&#xff09;&…

游戏攻略|基于Springboot和vue的游戏分享平台系统设计与实现(源码+数据库+文档)

游戏攻略分享平台目录 基于Springboot的在线考试管理系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 2、后台 5.2.1管理员功能模块 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; …

国际体育日,一起运动起来吧

今天是国际体育日&#xff0c;是时候动一动&#xff0c;燃烧我们的卡路里啦&#xff01;说到运动&#xff0c;我得提提最近刚入手华为WATCH GT4&#xff0c;真心不赖&#xff01; 这个手表特别适合喜欢运动的人&#xff0c;它有100的运动模式&#xff0c;无论你是喜欢跑步、…

数据结构初阶:顺序表和链表

线性表 线性表 ( linear list ) 是 n 个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构,常见的线性表:顺序表、链表、栈、队列、字符串 ... 线性表在逻辑上是线性结构,也就说是连续的一条直线。但是在物理结构上并不一定是连续的, 线性…

Excel列匹配VLookUp功能使用

生活中很多关于excel多列数据进行匹配计算等场景,其中最常用的一个函数就是VLookUp了,下面直接上图: 得到结果如下: 得到结果如下: 注意: 1.在需要把计算完的数据粘贴到另一列或者另个sheet时,复制后,不要直接ctrlv粘贴,这样会把计算公式粘贴到对应的列.正确做法是:右键粘贴,选…

蓝桥杯每日一题:斐波那契(矩阵乘法)

在斐波那契数列中&#xff0c;Fib00,Fib11,FibnFibn−1Fibn−2(n>1) 给定整数 n&#xff0c;求 Fibnmod10000。 输入格式 输入包含不超过 100100 组测试用例。 每个测试用例占一行&#xff0c;包含一个整数 当输入用例 n−1时&#xff0c;表示输入终止&#xff0c;且该…

Python环境搭建—安装PyCharm开发工具

&#x1f947;作者简介&#xff1a;CSDN内容合伙人、新星计划第三季Python赛道Top1 &#x1f525;本文已收录于Python系列专栏&#xff1a; 零基础学Python &#x1f4ac;订阅专栏后可私信博主进入Python学习交流群&#xff0c;进群可领取Python视频教程以及Python相关电子书合…

JS详解-设计模式

工厂模式&#xff1a; 单例模式&#xff1a; // 1、定义一个类class SingleTon{// 2、添加私有静态属性static #instance// 3、添加静态方法static getInstance(){// 4、判断实例是否存在if(!this.#instance){// 5、实例不存在&#xff0c;创建实例this.#instance new Single…

rust项目组织结构和集成测试举例

概述 在学习rust的过程中&#xff0c;当项目结构略微复杂的时候&#xff0c;写集成测试的时候发现总是不能引用项目中的代码&#xff0c;导致编写测试用例失败。查阅了教程&#xff0c;一般举例都很简单。查阅了谷歌和百度以及ai&#xff0c;也没有找到满意的答案。这里记录一…

Spring Boot 接入 Redis

Spring Boot 接入 Redis 简介 Redis 是一种访问速度非常快的内存数据结构存储&#xff0c;用作数据库、缓存、消息代理和流引擎。提供 strings、hashes、lists、sets 等数据结构。可以解决会话缓存、消息队列、分布式锁、定期将数据集存储到硬盘等功能。 通过 Redis 设计实现…

win11 安全中心打开黑屏\白屏\打不开有效解决

文章目录 问题和解决思路解决方法 问题和解决思路 问题&#xff1a;在重装和或者初次安装系统后&#xff0c;win11安全中心无法成功启动解决思路&#xff1a;直接重装安全中心&#xff0c;解决问题&#xff08;作者尝试了修复和重置的功能–无效&#xff09;视频教程参考WIN11…

攻防世界:mfw[WriteUP]

根据题目提示考虑是git库泄露 这里在地址栏后加.git也可以验证是git库泄露 使用GitHack工具对git库进行恢复重建 在templates目录下存在flag.php文件&#xff0c;但里面并没有flag 有内容的只有主目录下的index.php index.php源码&#xff1a; <?phpif (isset($_GET[page…

Photoshop 2024 中文---专业图像处理软件的又一次飞跃

Photoshop 2024是一款功能强大的图像处理软件&#xff0c;广泛应用于创意设计和图像处理领域。它提供了丰富的绘画和编辑工具&#xff0c;包括画笔、铅笔、颜色替换、混合器画笔等&#xff0c;使用户能够轻松进行图片编辑、合成、校色、抠图等操作&#xff0c;实现各种视觉效果…

Nature正刊重磅!热带雨林正接近临界温度阈值:气候变化可能会使热带森林太热而无法进行光合作用

2023年8月23日&#xff0c;美国北亚利桑那大学生态信息学Doughty, Christopher E. 副教授及其研究组人员在国际知名学术期刊《Nature》发表了一项题为“Tropical forests are approaching critical temperature thresholds”的研究。提出了热带雨林正接近临界温度阈值的新见解。…