实现C++ Vector

手写C++ Vector,参考QVector

类声明

	template<typename T >
	class IteratorVector;

	template<typename T >
	class IteratorVectorConst;


	template<typename T >
	class Vector final :public ContainerBase
	{
	public:
		explicit Vector()noexcept;
		explicit Vector(uint size)noexcept;

		Vector(const Vector& t)noexcept;
		Vector(Vector&& t)noexcept;

		Vector& operator= (const Vector& t)noexcept;
		Vector& operator= (Vector&& t)noexcept;

		~Vector();

		Vector& append(const T& t)noexcept;
		Vector& removeAt(uint pos)noexcept;
		Vector& removeAt(uint pos, uint len)noexcept;
		Vector& insert(uint pos, const T& t)noexcept;
		const T& at(uint pos)const;
		void clear()noexcept;
		Vector& removeOne(const T& t, uint pos = 0, bool onlyOne = true)noexcept;
		uint size()const noexcept { return m_size; };
		uint maxSize()const noexcept { return m_maxSize; };
		void setStep(uint step)noexcept { m_step = step; };
		uint step()const noexcept { return m_step; };
		bool isEmpty()const noexcept { return m_size; };
		void resize(uint size)noexcept;
		void resize(uint size, const T& t)noexcept;
		void swap(uint first, uint second)noexcept;
		void removeFirst()noexcept;
		void removeLast()noexcept;
		const T& first()const;
		const T& last()const;
		T& first();
		T& last();
		bool contains(const T& t, uint pos = 0)const noexcept;
		size_t find(const T& t, uint pos = 0) const noexcept;
		template<typename Funtion>
		size_t find(const T& t, const Funtion& f, uint pos = 0) const noexcept;
		uint capacity() const noexcept { return m_capacity; };
		void reverse()noexcept;
		T& operator[](uint pos)noexcept;

		IteratorVector<T> begin()noexcept;
		IteratorVector<T> end()noexcept;

		IteratorVectorConst<T> begin()const noexcept;
		IteratorVectorConst<T> end()const noexcept;

	private:
		T* m_element;
		uint m_size;
		uint m_step;
		uint m_capacity;

		static constexpr uint m_stepUint = 10;
		static constexpr size_t m_npos = -1;

		void _throw(bool v)const
		{
			if (v)
				throw std::out_of_range("Vector request out of range");
		}

		void freeMemory()noexcept
		{
			if (m_element != nullptr)
			{
				delete[] m_element;
				m_element = nullptr;
			}
		}
	};


#define OverstepMaxAssert assert(m_capacity <= m_maxSize);
#define ElementSize sizeof(T) * m_size

函数实现

template<typename T >
	MContainer::Vector<T>::Vector() noexcept
		:Vector(0)
	{

	}

	template<typename T >
	MContainer::Vector<T>::Vector(uint size) noexcept
		:m_size(0)
		, m_step(m_stepUint)
		, m_capacity(size)
	{
		OverstepMaxAssert
			m_element = new T[m_capacity];
	}



	template<typename T >
	MContainer::Vector<T>::Vector(const Vector& t) noexcept
	{
		if (&t == this)
			return;

		this->m_element = new T[t.m_capacity];
		this->m_size = t.m_size;
		this->m_step = t.m_step;
		this->m_capacity = t.m_capacity;
		std::memcpy(this->m_element, t.m_element, ElementSize);


	}

	template<typename T >
	MContainer::Vector<T>::Vector(Vector&& t) noexcept
	{
		if (&t == this)
			return;


		this->m_element = t.m_element;
		this->m_size = t.m_size;
		this->m_step = t.m_step;
		this->m_capacity = t.m_capacity;

		t.m_element = nullptr;
		t.m_size = 0;
		t.m_capacity = 0;
	}

	template<typename T>
	inline Vector<T>& Vector<T>::operator=(const Vector& t) noexcept
	{
		if (&t == this)
			return *this;


		this->m_element = new T[t.m_capacity];
		this->m_size = t.m_size;
		this->m_step = t.m_step;
		this->m_capacity = t.m_capacity;
		std::memcpy(this->m_element, t.m_element, ElementSize);

		return *this;
	}

	template<typename T>
	inline Vector<T>& Vector<T>::operator=(Vector&& t) noexcept
	{
		if (&t == this)
			return *this;
		this->clear();
		this->m_element = t.m_element;
		this->m_size = t.m_size;
		this->m_step = t.m_step;
		this->m_capacity = t.m_capacity;

		t.m_element = nullptr;
		t.m_size = 0;
		t.m_capacity = 0;


		return *this;
	}

	template<typename T>
	inline Vector<T>::~Vector()
	{
		clear();
	}


	template<typename T>
	inline Vector<T>& Vector<T>::append(const T& t) noexcept
	{
		if (m_size + 1 > m_capacity)
		{
			assert(m_capacity + 1 <= m_maxSize);

			m_capacity = m_capacity + m_step > m_maxSize ? m_maxSize : m_capacity + m_step;

			T* newArray = new T[m_capacity];

			std::memcpy(newArray, m_element, ElementSize);

			freeMemory();
			m_element = newArray;
		}

		m_element[m_size++] = t;

		return *this;
	}

	template<typename T >
	Vector<T>& MContainer::Vector<T>::removeAt(uint pos, uint len) noexcept
	{
		if (pos < 0 || pos > m_size)
			return *this;

		if (len + pos > m_size)
			len = m_size - pos;

		uint range = pos + len;

		uint size = m_size - range;
		std::memmove(m_element + pos, m_element + range, sizeof(T) * size);
		m_size -= len;
		return *this;
	}


	template<typename T>
	inline Vector<T>& Vector<T>::removeAt(uint pos) noexcept
	{
		return removeAt(pos, 1);
	}

	template<typename T>
	inline Vector<T>& Vector<T>::insert(uint pos, const T& t)noexcept
	{
		uint size = m_size + 1;
		if (pos > size)
			return *this;

		if (size > m_capacity)
		{
			assert(m_capacity + 1 <= m_maxSize);

			m_capacity = m_capacity + m_step > m_maxSize ? m_maxSize : m_capacity + m_step;

			T* newArray = new T[m_capacity];

			std::memcpy(newArray, m_element, ElementSize);
			freeMemory();
			m_element = newArray;

		}
		uint count = m_size - pos;
		uint movePos = m_size;
		while (count)
		{
			m_element[movePos] = m_element[movePos - 1];
			movePos -= 1;
			count--;
		}
		m_element[pos] = t;
		m_size++;
		return *this;
	}

	template<typename T>
	inline const T& Vector<T>::at(uint pos) const
	{
		_throw(pos >= m_size);

		return m_element[pos];
	}

	template<typename T>
	inline void Vector<T>::clear()noexcept
	{
		freeMemory();
		m_size = 0;
		m_capacity = 0;
		m_step = m_stepUint;
	}

	template<typename T>
	inline Vector<T>& Vector<T>::removeOne(const T& t, uint pos, bool onlyOne)noexcept
	{
		if (pos >= m_size)
			return *this;

		for (size_t i = 0; i < m_size; i++)
		{
			if (m_element[i] == t)
			{
				removeAt(i);
				if (onlyOne)
					return *this;
			}
		}


		return *this;
	}

	template<typename T>
	inline T& Vector<T>::operator[](uint pos) noexcept
	{
		_throw(pos >= m_size);
		return m_element[pos];
	}

	template<typename T >
	T& MContainer::Vector<T>::last()
	{
		_throw(!m_size);
		return m_element[m_size - 1];
	}

	template<typename T >
	T& MContainer::Vector<T>::first()
	{
		_throw(!m_size);
		return m_element[0];
	}

	template<typename T >
	bool MContainer::Vector<T>::contains(const T& t, uint pos /*= 0*/)const noexcept
	{
		for (; pos < m_size; pos++)
		{
			if (t == m_element[pos])
				return true;
		}
		return false;
	}

	template<typename T >
	const T& MContainer::Vector<T>::last()const
	{
		_throw(!m_size);
		return m_element[m_size - 1];
	}

	template<typename T >
	const T& MContainer::Vector<T>::first()const
	{
		_throw(!m_size);
		return m_element[0];
	}

	template<typename T >
	void MContainer::Vector<T>::removeLast()noexcept
	{
		removeAt(m_size - 1);
	}

	template<typename T >
	void MContainer::Vector<T>::removeFirst()noexcept
	{
		removeAt(0);
	}

	template<typename T >
	void MContainer::Vector<T>::swap(uint first, uint second)noexcept
	{
		if (first == second
			|| first >= m_size
			|| second >= m_size)
			return;
		T tmp = m_element[first];
		m_element[first] = m_element[second];
		m_element[second] = tmp;
	}

	template<typename T >
	void MContainer::Vector<T>::resize(uint size, const T& t)noexcept
	{
		clear();
		m_capacity = size;
		m_size = size;
		m_element = new T[m_capacity]{ t };

	}

	template<typename T >
	void MContainer::Vector<T>::resize(uint size)noexcept
	{
		resize(size, {});
	}


	template<typename T >
	size_t MContainer::Vector<T>::find(const T& t, uint pos)const noexcept
	{
		for (; pos < m_size; pos++)
		{
			if (m_element[pos] == t)
				return pos;
		}
		return m_nopos;
	}


	template<typename T >
	template<typename Funtion>
	size_t MContainer::Vector<T>::find(const T& t, const Funtion& f, uint pos /*= 0*/)const noexcept
	{
		for (; pos < m_size; pos++)
		{
			if (f(this->at(pos), t))
				return pos;
		}
		return m_nopos;
	}


	template<typename T >
	void MContainer::Vector<T>::reverse() noexcept
	{
		if (isEmpty())
			return;
		T tmp;
		for (size_t i = 0; i < m_size / 2; i++)
		{
			tmp = m_element[i];
			m_element[i] = m_element[m_size - 1 - i];
			m_element[m_size - 1 - i] = tmp;
		}
	}


	template<typename T >
	IteratorVectorConst<T> MContainer::Vector<T>::end() const noexcept
	{
		return IteratorVectorConst<T>(m_element + m_size);
	}

	template<typename T >
	IteratorVectorConst<T> MContainer::Vector<T>::begin() const noexcept
	{
		return IteratorVectorConst<T>(m_element);
	}

	template<typename T >
	IteratorVector<T> MContainer::Vector<T>::end()noexcept
	{
		return IteratorVector<T>(m_element + m_size);
	}

	template<typename T >
	IteratorVector<T> MContainer::Vector<T>::begin()noexcept
	{
		return IteratorVector<T>(m_element);
	}

迭代器

template<typename T >
	class IteratorVector :public  std::iterator<std::random_access_iterator_tag, T>
	{
	private:
		friend  Vector<T>;
		T* m_ptr;
		IteratorVector<T>(T* t)
			:m_ptr(t)
		{
		
		}
	public:
		IteratorVector<T> operator++()
		{
			return ++m_ptr;
		}
		IteratorVector<T> operator++(int)
		{
			T * tmp = m_ptr;
			m_ptr++;
			return tmp;
		}
		IteratorVector<T> operator--()
		{
			return --m_ptr;
		}
		IteratorVector<T> operator--(int)
		{
			T * tmp = m_ptr;
			m_ptr--;
			return tmp;
		}
		T*operator->()
		{
			return m_ptr;
		}
		T& operator*()
		{
			return* m_ptr;
		}
		bool operator!=(const IteratorVector<T>& t)const
		{
			return m_ptr != t.m_ptr;
		}
		bool operator==(const IteratorVector<T>& t)const
		{
			return m_ptr == t.m_ptr;
		}
		bool operator<(const IteratorVector<T>& t)const
		{
			return m_ptr < t.m_ptr;
		}
		bool operator>(const IteratorVector<T>& t)const
		{
			return m_ptr > t.m_ptr;
		}
		IteratorVector<T> operator+=(difference_type size)const
		{
			T* tmp = m_ptr + size;
			return tmp;
		}
		IteratorVector<T> operator-=(difference_type size)const
		{
			T* tmp = m_ptr - size;
			return tmp;
		}
	};

	template<typename T >
	class IteratorVectorConst :public  std::iterator<std::random_access_iterator_tag, T>
	{
	private:
		friend  Vector<T>;
		T* m_ptr;
		IteratorVectorConst<T>(T* t)
			: m_ptr(t)
		{

		}
	public:
		IteratorVectorConst<T> operator++()
		{
			return ++m_ptr;
		}
		IteratorVectorConst<T> operator++(int)
		{
			T * tmp = m_ptr;
			m_ptr++;
			return tmp;
		}
		IteratorVectorConst<T> operator--()
		{
			-return -m_ptr;
		}
		IteratorVectorConst<T> operator--(int)
		{
			T * tmp = m_ptr;
			m_ptr--;
			return tmp;
		}
		const T *operator->()
		{
			return m_ptr;
		}
		const T& operator*()
		{
			return*m_ptr;
		}
		bool operator!=(const IteratorVectorConst<T>& t)const
		{
			return m_ptr != t.m_ptr;
		}
		bool operator==(const IteratorVectorConst<T>& t)const
		{
			return m_ptr == t.m_ptr;
		}
		bool operator<(const IteratorVectorConst<T>& t)const
		{
			return m_ptr < t.m_ptr;
		}
		bool operator>(const IteratorVectorConst<T>& t)const
		{
			return m_ptr > t.m_ptr;
		}
		IteratorVectorConst<T> operator+=(difference_type size)const
		{
			T* tmp = m_ptr + size;
			return tmp;
		}
		IteratorVectorConst<T> operator-=(difference_type size)const
		{
			T* tmp = m_ptr - size;
			return tmp;
		}
	};

验证 (与QVector对比)

template <typename T1, typename T2 >
void verify(T1& t1, T2& t2 /*标准容器*/)
{
	auto start = std::chrono::high_resolution_clock::now();


	std::mt19937 rng(std::random_device{}());
	std::uniform_int_distribution<int> dist(0, 0xFFFFF);

	int size = dist(rng);
	for (size_t i = 0; i < size; i++)
	{
		int number = dist(rng);
		if (number % 3 == 0)
		{
			t1.append(number);
			t2.append(number);
		}
		else if (number % 3 == 1
			&& number < t2.size())
		{
			t1.insert(number, number);
			t2.insert(number, number);
		}
		else
		{
			if (number < t2.size())
			{
				t1.removeAt(number);
				t2.removeAt(number);
			}
		}
	}

	if (t1.size() != t2.size())
	{
		std::cout << "size != " << '\n';
		return;
	}

	auto t1Itor = t1.begin();
	auto t2Itor = t2.begin();
	for (;t1Itor != t1.end() ; t1Itor++,t2Itor++)
	{
		if (*t1Itor != *t2Itor)
		{
			std::cout << "Value != ; "<< '\n';
		}
	}

	std::cout << "Verification complete!" << '\n';

	auto end = std::chrono::high_resolution_clock::now();
	std::chrono::duration<double> elapsed = end - start;

	std::cout << "Verification time: " << elapsed.count()  << std::endl;
}

测试结果

测试结果图

为学习数据结构编写,容器可能存在问题。有建议可以留言指出,谢谢。

GitHub

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

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

相关文章

如何使用Reqable脚本功能提高API开发效率

Reqable支持使用Python脚本对API开发和调试进行辅助&#xff0c;今天写一篇实战教程&#xff0c;由浅入深地演示下如何使用Reqable的脚本功能。 首先&#xff0c;电脑上需要安装Python软件包。一般情况下&#xff0c;系统都会预安装Python软件包&#xff0c;如果系统没有安装或…

大语言模型LLM应用篇

大模型席卷全球&#xff0c;彷佛得模型者得天下。对于IT行业来说&#xff0c;以后可能没有各种软件了&#xff0c;只有各种各样的智体&#xff08;Agent&#xff09;调用各种各样的API。在这种大势下&#xff0c;笔者也阅读了很多大模型相关的资料&#xff0c;和很多新手一样&a…

升级到 AGP7+,适配 assets 目录了吗

我们知道 assets 文件处理的任务是 merge[变体名称]ReleaseAssets&#xff0c;例如&#xff1a; mergeCommonReleaseAssetsmergeReleaseAssetsmergeDebugAssets 在 AGP 升级过程中&#xff0c;不同的 Android Gradle Plugin 版本打包过程中处理 assets 文件的临时目录可能存在…

[笔试训练](十七)

目录 049:小乐乐改数字 050:十字爆破 051:比那名局的桃子 049:小乐乐改数字 小乐乐改数字_牛客题霸_牛客网 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 把输入的数字当成字符串&#xff0c;按字符一个一个读&#xff0c;边读边按条件改成字符0或1。 #include &l…

2024 年 数维杯(A题)大学生数学建模挑战赛 | 多源机会信号建模| 数学建模完整代码+建模过程全解全析

2024数维杯数学建模A题B题C题思路模型代码&#xff08;开赛后第一时间更新&#xff09;及时留意关注哦 https://mbd.pub/o/bread/ZpWakpdq https://mbd.pub/o/bread/ZpWakpdq 2024数维杯数学建模A题B题C题思路模型代码&#xff08;开赛后第一时间更新&#xff09;及时留意关注…

每周一算法:无向图的最小环

题目链接 观光之旅 题目描述 给定一张无向图&#xff0c;求图中一个至少包含 3 3 3 个点的环&#xff0c;环上的节点不重复&#xff0c;并且环上的边的长度之和最小。 该问题称为无向图的最小环问题。 你需要输出最小环的方案&#xff0c;若最小环不唯一&#xff0c;输出…

SG3225EEN在PAM4光模块和400G,QSFP-DD光模块中的应用

爱普生晶振SG3225EEN&#xff0c;156.25MHz在PAM4光模块和QSFP-DD光模块中的应用。光模块市场已发展至400G光模块&#xff0c;那么PAM4光模块和400G QSFPDD光模块有哪些区别呢?SG3225EEN又是怎么应用在PAM4光模块和QSFP-DD光模块中的呢? 首先介绍的是PAM4光模块:PAM4是PAM(脉…

android基础-服务

同样使用intent来传递服务 oncreate是服务第一次启动调用&#xff0c;onStartCommand是服务每次启动的时候调用&#xff0c;也就是说服务只要启动后就不会调用oncreate方法了。可以在myservice中的任何位置调用stopself方法让服务停止下来。 服务生命周期 前台服务类似于通知会…

「ETL实战」搭建数仓,解决多源业务系统关联分析难题(定制化业务)

在大数据分析盛行的今天&#xff0c;关联分析作为数据挖掘和业务洞察的重要手段&#xff0c;受到了极大关注。然而&#xff0c;随着数据量的激增和源业务系统的复杂性增加&#xff0c;关联分析的性能问题逐渐成为了一个不可忽视的挑战。 本文将介绍借助ETL工具&#xff0c;如何…

Go 语言基础之常用包【flag、time、strconv、io】

1、命令行参数包 flag flag 包就是一个用来解析命令行参数的工具。 1.1、os.Args import ("fmt""os" )func main() {if len(os.Args) > 0 {for index, arg : range os.Args {fmt.Printf("args[%d]%v\n", index, arg)}} } 运行结果&#…

Windows程序设计课程作业-2(音乐文件播放功能)

目录 1、作业内容 要求1&#xff1a; 提示&#xff1a; 要求2&#xff1a; 提示&#xff1a; 作业提交方式: 2、主要思路 1&#xff09;准备工作 2&#xff09;提取音乐文件功能 3&#xff09;选择音乐进行播放 4&#xff09;异常信息进行处理 5&#xff09;停止播…

【最新点云数据增强综述】深度学习点云数据增强技术的进展

深度学习(DL)已成为点云分析任务(如检测、分割和分类)的主流和有效方法之一。为了减少深度学习模型训练过程中的过拟合,提高模型性能,尤其是在训练数据的数量和/或多样性有限的情况下,增强往往至关重要。虽然各种点云数据增强方法已被广泛应用于不同的点云处理任务中,但…

[muduo网络库]——muduo库的Reactor模型(剖析muduo网络库核心部分、设计思想)

一、前言 在学习 C 服务端的过程中&#xff0c;必不可少的一项就是熟悉一个网络库&#xff0c;包括网络库的应用和其底层实现。我们熟知的网络库有 libevent、libev、muduo、Netty 等&#xff0c;其中 muduo 是由陈硕大佬个人开发的 TCP 网络库&#xff0c;最近跟着课程正在深…

Springboot+Vue项目-基于Java+MySQL的车辆管理系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…

Java方法和数组

方法 Java中的方法就是c语言中的函数。 方法的定义 定义格式如下 修饰符 返回值 方法名([参数列表]){代码块[return 返回值;] } //方括号[]括起来代表可以没有&#xff0c;不是必须有的方法名采用小驼峰命名&#xff08;就是有多个单词&#xff0c;第一个单词首字母小写其…

Redis学习1——redis简介、基础

介绍 redis简介 Redis(Remote Dictonary Server) 是由Salvatore Sanfilippo开发的key-value缓存数据库&#xff0c;基于C语言开发。目前市面上&#xff0c;Redis和MongoDB是当前使用最广泛的NoSQL&#xff0c;而就Redis技术而言&#xff0c;它的性能十分优越&#xff0c;可以…

回溯法、全排列、子集等

回溯法 感想&#xff1a;回溯算法本质是一个循环&#xff0c;有点像while循环 一些回溯法&#xff08;递归&#xff09;的经典应用 1.全排列 2.子集 其实上面两个点&#xff0c;也是对应着高中数学里面的“排列”与“组合” 1.全排列问题 给定一个集合S{a,b,c}&#xff0…

mysql数据库标识符的使用

ddl CREATE TABLE student (id int(11) NOT NULL AUTO_INCREMENT COMMENT 学号,createDate datetime DEFAULT NULL,userName varchar(20) DEFAULT NULL,pwd varchar(36) DEFAULT NULL,phone varchar(11) DEFAULT NULL,age tinyint(3) unsigned DEFAULT NULL,sex char(2) DEFAU…

crmeb的分销推广如何用

CRMBE分销推广说明 1、CRMEB分销模式 分销模式&#xff1a; 指定分销、人人分销、满额分销 指定分销&#xff1a; 用户默认无分销权限&#xff0c;需要后台开通分销权限后&#xff0c;才可以通过推广下级获得返佣&#xff1b; 人人分销&#xff1a; 用户在商城注册后自动获得分…

SpringBoot的图片上传

简介 该文档旨在介绍一个基于Spring Boot框架的简单文件上传功能的实现方式。本文档将详细介绍相关代码的功能和配置以及如何使用它们。 样例 技术栈 Spring Boot&#xff1a;一个用于快速开发基于Spring的应用程序的框架。Thymeleaf&#xff1a;一个用于在Web应用程序中创建…
最新文章