C++ vector顺序表模拟实现

目录

前言:

模拟实现:

 构造函数:

析构函数:

容量调整(reserve):

 resize函数:

尾插(push_back):

 尾删(pop_back):

插入(insert):

 销毁(erase):

[]重载:

交换(swap):

=重载:

 代码


前言:

  在学习vector的功能后,我自己模拟实现了一些vector的基本功能,这篇文章用来分享一下,也便于我后续的复习。

模拟实现:

  总所周知vector中迭代器是遍历vector的重要工具,既然我这里只是简单的模拟,那迭代器就用简单的指针来模拟,先typedef一下:

vector可以装很多类型,int,char,float,string......等,所以我们应该写一个类模板,大致框架如下:

 

先简单确定3个成员变量:

_start指向vector最前面的元素

_finish指向vector内所有有效数据的后一个

_endofstorage指向vector容量的最后一个 

给缺省值都为空指针: 

然后再来几个简单,但又很重要的函数:

 构造函数:

我这里只实现3种常用的构造函数:

1.vector<int> v(n,val):   v里面有3个元素,全初始化成val。

 

 这里的push_back函数也就是尾插函数后面会实现,这里先复用。

2.vector<int> v1(v2):   这个也就是拷贝构造函数:

同样这里的reserve函数也就是容量调整函数后面实现。

3.vector<int> v1(v2.begin(),v2.end()):   用另一个类的迭代器初始化:

注意这里另一个类不一定是vector,也有可能是string等,所以我们需要写一个模板函数:

 

析构函数:

这个很简单: 

容量调整(reserve):

思路请看注释,注意这里一定要记录旧空间size的大小后才能更新finish 

 resize函数:

功能:将有效数据个数调整到n,如果n<原来有效数据个数,则舍去多余的,如果n>有效数据个数,则多出的空间用val填充:

尾插(push_back):

尾插需要注意的是,尾插前要检查一下容量,不够的话就需要扩容:

 尾删(pop_back):

插入(insert):

注意,如果要扩容的话,就必须先记录pos的位置,如上图用len记录,扩容完再更新pos位置,因为扩容会指向新的空间,如果不更新pos,pos就还是指向旧的空间,但旧的空间已经被释放了,就会引起程序崩溃。 

 销毁(erase):

删除pos位置的数据,直接让pos后的数据挪动覆盖即可:

[]重载:

这里为了方便const类使用,所以多写了个const函数:

交换(swap):

 直接调用库里的swap函数交换3个指针即可

=重载:

 因为这里用的swap是我自己写的成员函数,所以只需传参v,就可完成交换,因为成员函数第一个参数是隐含的this指针。还有个巧妙的地方是这里赋值重载用的是传参输入,而不是传引用,这样做的好处,就是巧妙利用了拷贝,我举个例子如下:

v3=v1;将v1赋值给v3,进入上述函数后,v就是v1的拷贝,然后交换v3和v,这样就不会修改到v1的情况下,还赋值给了v3。

 代码:

#pragma once
#include<string.h>
#include<iostream>
#include<assert.h>
using namespace std;
namespace sxk
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		iterator begin()const
		{
			return _start;
		}

		iterator end()const
		{
			return _finish;
		}

		size_t size()const
		{
			return _finish - _start;
		}

		size_t capacity()const
		{
			return _endofstorage - _start;
		}
		//v2(v1)
		vector(const vector<T>& v)
		{
			reserve(v.capacity());//不管咋样先把容量变为一样的
			for (auto x : v)
			{
				push_back(x);
			}
		}

		vector(int n, const T& val = T())//缺省值为匿名模板类,因为val也可能是别的类
		{
			reserve(n);
			for (int i = 0;i < n;i++)
			{
				push_back(val);
			}
		}

		vector()
		{

		}

		bool empty()
		{
			return _start == _finish;
		}

		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}

		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}

		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}

		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return _start[pos];
		}
		
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}



		void reserve(size_t n)//将容量调整到n(这里只实现扩容)
		{
			if (n > capacity())//如果容量不够,扩容
			{
				T* tmp = new T[n];//先开辟容量为n的新空间
				size_t old_size = size();//记录原来空间的size,方便后续找到新空间finish的位置
				memcpy(tmp, _start, size() * sizeof(T));//将数据拷贝到新空间
				delete[] _start;//释放旧空间
				_start = tmp;//指向新空间
				_finish = tmp + old_size;
				_endofstorage = tmp + n;
			}
		}

		void resize(size_t n, const T& val = T())//因为val可以为别的类,所以用匿名模板对象当缺省值
		{
			if (n > size())//如果n大于原有效数据个数
			{
				reserve(n);//先扩容
				while (_finish != _start + n)//开始用val填充多的空间
				{
					*_finish = val;
					++_finish;
				}
			}
			else//如果n小于等于原有效数据个数
			{
				_finish = _start + n;//直接调整_finish的位置即可
			}
		}

		void push_back(const T& val)
		{
			if (_finish == _endofstorage)//如果容量不够
			{
				reserve(capacity() == 0 ? 4 : capacity() * 4);//扩容,防止原来容量为0,扩容不上
			}
			*_finish = val;//尾插
			_finish++;//更新finish
		}

		void pop_back()
		{
			assert(!empty());//防止vector为空
			--_finish;//直接--finish即可
		}

		void insert(iterator pos,const T& val)
		{
			if (_finish == _endofstorage)//如果要扩容
			{
				size_t len = pos - _start;//记录pos位置方便后续更新
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;//扩容完更新pos
			}
			iterator it = _finish - 1;//it初始指向最后一个元素
			while (it >= pos)//开始移动数据,把pos位置腾出来
			{
				*(it + 1) = *it;
				--it;
			}
			*pos = val;
			++_finish;
		}

		iterator erase(iterator pos)//删除pos位置的值
		{
			iterator it = pos + 1;//it初始指向pos后面一个位置的元素
			while (it <= _finish)
			{
				*(it - 1) = *it;
				it++;
			}
			--_finish;
			return pos;
		}
		template<class Inputiterator>//使用迭代器初始化
		vector(Inputiterator first, Inputiterator last)
		{
			while (first != last)
			{
				push_back(*first);
				first++;
			}
		}
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
	template<class T>
	void print_vector(vector<T>& v)
	{
		for (int i = 0;i < v.size();i++)
		{
			cout << v[i] << ' ';
		}
		cout << endl;
	}
}

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

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

相关文章

基于Spring boot+Vue的业余排球俱乐部会员管理系统

5 系统功能模块的具体实现 5.1超级会员角色 5.1.1 登录 超级管理员登录通过用户名和密码去数据库查询用户表&#xff0c;该名称是否在用户表中存在&#xff0c;如果存在&#xff0c;则通过用户名和密码查询密码是否正确&#xff0c;然后吧用户的信息存在jwt的负载里&#xf…

表1和表2怎么查找相同的内容?3种实用技巧赶紧学起来

-- 为啥会感觉给不了一个人幸福&#xff0c;而选择分开不打扰&#xff1f; 核对不同工作表中的数据&#xff0c;是大家在处理工作表时会遇到的高频场景&#xff0c;这篇文章跟大家分享一下如何查找不同工作表中的相同内容。 比对数据的方法有很多&#xff0c;这里跟大家分享3种…

LangChain - OpenGPTs

文章目录 MessageGraph 消息图认知架构AssistantsRAGChatBot 持久化配置新模型新工具astream_events总结 关键链接&#xff1a; OpenGPT GitHub 存储库YouTube 上的 OpenGPT 演练LangGraph&#xff1a;Python、JS 两个多月前&#xff0c;在 OpenAI 开发日之后&#xff0c;我们…

二维码门楼牌管理应用平台建设:打造便民服务热线新生态

文章目录 前言一、二维码门楼牌管理应用平台概述二、便民热线服务的构建三、便民热线服务的优势四、便民热线服务的潜在价值五、总结与展望 前言 随着信息技术的飞速发展&#xff0c;二维码门楼牌管理应用平台的建设已成为城市智慧化建设的重要组成部分。这一平台不仅为居民提…

区块链技术与数字身份:解析Web3的身份验证系统

在数字化时代&#xff0c;随着个人数据的日益增多和网络安全的日益关注&#xff0c;传统的身份验证系统面临着越来越多的挑战和限制。在这种背景下&#xff0c;区块链技术的出现为解决这一问题提供了全新的思路和解决方案。Web3作为一个去中心化的互联网模式&#xff0c;其身份…

MySQL学习笔记------多表查询

目录 多表关系 一对多 多对多 一对一 多表查询 概述 分类 内连接&#xff08;交集&#xff09; 隐式内连接 显式内连接 ​编辑 外连接&#xff08;from后为左表&#xff0c;join后为右表&#xff09; 左外连接 右外连接 自连接 联合查询&#xff08;union&#…

APP的UI设计规范

APP的设计规范是一系列原则和标准&#xff0c;旨在确保应用程序提供一致、易用且美观的用户体验。以下是一些关键的APP设计规范。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.一致性&#xff1a; 保持界面元素和交互行为的一致性…

Sketch是免费软件吗?这款软件支持导入!

Sketch 是一款针对网页、图标、插图等设计的矢量绘图软件。Sketch 的操作界面非常简单易懂&#xff0c;帮助全世界的设计师创作出许多不可思议的作品。但是同时&#xff0c;Sketch 也有一些痛点&#xff1a;使用 Sketch 需要安装 InVision、Abstract 、Zeplin 等插件&#xff0…

【LeetCode: 455. 分发饼干 + 贪心】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

Docker 引擎离线安装包采集脚本

文章目录 一、场景说明二、脚本职责三、参数说明四、操作示例五、注意事项 一、场景说明 本自动化脚本旨在为提高研发、测试、运维快速部署应用环境而编写。 脚本遵循拿来即用的原则快速完成 CentOS 系统各应用环境部署工作。 统一研发、测试、生产环境的部署模式、部署结构、…

鼠标不动N秒,电脑自动待机睡眠V1.0

鼠标不动N秒&#xff0c;电脑自动待机睡眠V1.0 开发背景&#xff1a;因为不关电脑多次被罚款&#xff0c;所以下决心做一个自动待机睡眠软件 win系统自带的睡眠小程序&#xff0c;在电脑正在运行其它程序时&#xff0c;只能关闭屏幕而不是电脑待机。 为了电脑深度睡眠待机&a…

基于LNMP环境上线QQ农场

目录 一.介绍 二. 环境准备 三.安装Mysql数据库 四.安装PHP 五.安装Nginx 六.测试Nginx服务于PHP服务是否能关联 七.项目上线 QQ农场源码&#xff1a;做本项目默认操作者有一定的基础知识与理解能力 链接&#xff1a;https://pan.baidu.com/s/1HF8GZ-yvNh7RbJ61nXOW-g?…

吴恩达最新活动演讲 :AI Agent不应该只是执行,而是能够自主思考工作流

AI Agent&#xff0c;作为一种能够感知环境、进行决策和执行动作的智能实体&#xff0c;正逐渐成为人工智能领域的重要发展方向。随着大型语言模型&#xff08;LLM&#xff09;技术的不断进步&#xff0c;AI Agent的应用潜力正在被逐步释放&#xff0c;它们不仅能够执行基于明确…

Linux操作系统上启动redis服务

一、下载安装redis 网上找教程。 二、修改redis.conf配置文件 1.先进入redis目录 2. ls查看文件 3.修改redis.conf中的配置&#xff0c;将daemonize no改成daemonize yes。 输入指令进行修改修改 vi redis.conf 保存退出。 三、启动redis服务 在下载的redis目录下执行以…

13 - Debian如何配置网络(1)

作者&#xff1a;网络傅老师 特别提示&#xff1a;未经作者允许&#xff0c;不得转载任何内容。违者必究&#xff01; Debian如何配置网络&#xff08;1&#xff09; 《傅老师Debian小知识库系列之13》——原创 前言 傅老师Debian小知识库特点&#xff1a; 1、最小化拆解Deb…

特别详细的Spring Cloud 系列教程1:服务注册中心Eureka的启动

Eureka已经被Spring Cloud继承在其子项目spring-cloud-netflix中&#xff0c;搭建Eureka Server的方式还是非常简单的。只需要通过一个独立的maven工程即可搭建Eureka Server。 我们引入spring cloud的依赖和eureka的依赖。 <dependencyManagement><!-- spring clo…

基于李雅普诺夫稳定性分析的一阶、二阶系统MATLAB仿真模型

李雅普诺夫稳定性定理 假设系统状态方程&#xff1a; 零状态为其平衡状态&#xff0c;即f(0,t)0 t&#xff1e;t0。如果存在一个具有连续的一阶偏导数的标量函数V (x,t)&#xff0c;并且满足下述条件&#xff1a; 1、V (x,t)是正定的&#xff1b; 2、沿状态方程轨线的V (x…

CV论文--2024.4.7

1、Know Your Neighbors: Improving Single-View Reconstruction via Spatial Vision-Language Reasoning 中文标题&#xff1a;了解你的邻居&#xff1a;通过空间视觉语言推理改进单视图重建 简介&#xff1a;在计算机视觉领域&#xff0c;从单个视图恢复三维场景几何是一个基…

30天拿下Rust之实战Web Server

概述 随着互联网技术的飞速发展&#xff0c;Web服务器作为承载网站与应用的核心组件&#xff0c;其性能、稳定性和安全性都显得至关重要。Rust语言凭借其独特的内存安全保证、高效的性能以及丰富的生态系统&#xff0c;成为了构建现代Web服务器的理想选择。 新建项目 首先&…

SVG图标显示

SVG图标显示 1.安装SharpVectors.Wpf包 2.添加引用 xmlns:svgc"http://sharpvectors.codeplex.com/svgc/"3.加载svg文件&#xff0c;生成操作选择资源(Resource) 4.UI界面显示SVG图像 <Button Click"OnSaveFileClick" ToolTip"Save Svg File…