C++:模拟实现STL的vector

目录

一.vector类

1.vector类的构造及析构

2.定义迭代器

3.size()和capacity()

4.operator [ ] 

5.resize()和reserve()

6.插入和删除

二.整体代码

1.vector.h

2.vector.cpp


上一节中了解了vector中部分接口的使用,在这里我们模拟实现vector,为了避免与库中的起冲突,在这里使用命名空间

一.vector类

1.vector类的构造及析构

vector类中我们有三个对象_start,_finish,_endofstorage

构造函数

	vector() :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
	{}

拷贝构造

	vector(const vector<T>& v)
	{
		_start = new T[v.capacity()];
		_finish = _start;
		_endofstorage = _start + v.capacity();
		for (size_t i = 0; i < v.size(); ++i)
		{
			*_finish = v[i];
			++_finish;
		}
	}

但是我们可以采取一个更简单的方法,将值插入要拷贝的对象中

	//v2(v1)
	vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
	{
		//将v1的数据插入v2
		for (const auto& ch : v)
		{
			reserve(v.capacity());
			push_back(ch);
		}
	}

赋值

我们可以选择将两个的值进行交换

vector<T>& operator=(vector<T> v)
{
	swap(v);
	return *this;
}

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

析构

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

2.定义迭代器

typedef T* iterator;
typedef const T* const_iterator;

	iterator begin()
	{
		return _start;
	}

	iterator end()
	{
		return _finish;
	}

	const_iterator begin() const
	{
		return _start;
	}

	const_iterator end() const
	{
		return _finish;
	}

3.size()和capacity()

 所以size只需要用_finish-_start,capacity用_endofstorage-_start

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

size_t capacity() const
{
	return _endofstorage - _start;
}

4.operator [ ] 

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

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

5.resize()和reserve()

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T) * sz);按字节拷贝,浅拷贝
			for (size_t i = 0; i < sz; ++i)
			{
				tmp[i] = _start[i];//调用operator=深拷贝
			}
			delete[] _start;
		}
		_start = tmp;
		_finish = tmp + sz;
		_endofstorage = tmp + n;
	}
}

void resize(size_t n, const T& val = T())
{
	if (n < size())
	{
		_finish = _start + n;
	}
	else
	{
		if (n > capacity())
		{
			reserve(n);
		}

		while (_finish < _start + n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

6.插入和删除

push_back

当容量不足时开辟新空间,在尾部插入即可,同时将_finish向后移动

void push_back(const T& x)
{
	if (_finish == _endofstorage)
	{
		size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
		reserve(newcapacity);
	}
	*_finish = x;
	++_finish;
}

pop_back

直接将_finish后移即可

	void pop_back()
	{
		assert(_start < _finish);
		--_finish;
	}

insert

	void insert(iterator pos, const T& x)
	{
		assert(pos <= _finish);

		if (_finish == _endofstorage)
		{
			size_t n = pos - _start;
			size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
			reserve(newcapacity);
			//如果增容原来的pos就失效了,需要重新计算位置
			pos = _start + n;
		}

		iterator end = _finish - 1;
		while (end >= pos)
		{
			*(end + 1) = *end;
			--end;
		}
		*pos = x;
		++_finish;
	}

当我们实现insert后,push_back就可以用复用实现

void push_back(const T& x)
{
	insert(_finish, x);
}

erase

iterator erase(iterator pos)
{
	assert(pos < _finish);

	iterator it = pos;
	while (it < _finish)
	{
		*it = *(it + 1);
		++it;
	}
	--_finish;

	return pos;
}

同样实现了erase,pop_back也可以复用

	void pop_back()
	{
		erase(_finish - 1);
	}

二.整体代码

1.vector.h

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;

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

		vector() :_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
		{}

		/*vector(const vector<T>& v)
		{
			_start = new T[v.capacity()];
			_finish = _start;
			_endofstorage = _start + v.capacity();
			for (size_t i = 0; i < v.size(); ++i)
			{
				*_finish = v[i];
				++_finish;
			}
		}*/

		//v2(v1)
		vector(const vector<T>& v):_start(nullptr), _finish(nullptr), _endofstorage(nullptr)
		{
			//将v1的数据插入v2
			for (const auto& ch : v)
			{
				reserve(v.capacity());
				push_back(ch);
			}
		}

		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

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

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

		iterator begin()
		{
			return _start;
		}

		iterator end()
		{
			return _finish;
		}

		const_iterator begin() const
		{
			return _start;
		}

		const_iterator end() const
		{
			return _finish;
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				T* tmp = new T[n];
				if (_start)
				{
					//memcpy(tmp, _start, sizeof(T) * sz);按字节拷贝,浅拷贝
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];//调用operator=深拷贝
					}
					delete[] _start;
				}
				_start = tmp;
				_finish = tmp + sz;
				_endofstorage = tmp + n;
			}
		}

		void resize(size_t n, const T& val = T())
		{
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}

				while (_finish < _start + n)
				{
					*_finish = val;
					++_finish;
				}
			}
		}

		void push_back(const T& x)
		{
			/*if (_finish == _endofstorage)
			{
				size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
				reserve(newcapacity);
			}
			*_finish = x;
			++_finish;*/
			insert(_finish, x);
		}

		void pop_back()
		{
			/*assert(_start < _finish);
			--_finish;*/
			erase(_finish - 1);
		}

		void insert(iterator pos, const T& x)
		{
			assert(pos <= _finish);

			if (_finish == _endofstorage)
			{
				size_t n = pos - _start;
				size_t newcapacity = capacity() == 0 ? 2 : capacity() * 2;
				reserve(newcapacity);
				//如果增容原来的pos就失效了,需要重新计算位置
				pos = _start + n;
			}

			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				--end;
			}
			*pos = x;
			++_finish;
		}

		iterator erase(iterator pos)
		{
			assert(pos < _finish);

			iterator it = pos;
			while (it < _finish)
			{
				*it = *(it + 1);
				++it;
			}
			--_finish;

			return pos;
		}

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

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

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

		size_t capacity() const
		{
			return _endofstorage - _start;
		}

	private:
		iterator _start;
		iterator _finish;
		iterator _endofstorage;
	};


	void test_vector1()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);

		cout << v.size() << endl;
		cout << v.capacity() << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;

		for (auto& ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;

		for (size_t i = 0; i < v.size(); ++i)
		{
			cout << v[i] << " ";
		}
		cout << endl;
	}

	void test_vector2()
	{
		vector<int> v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		v.insert(v.begin(), 0);
		for (auto& ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;

		vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				it = v.erase(it);
			}
			else
			{
				++it;
			}
		}

		for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;
	}

	void test_vector3()
	{
		vector<int> v;
		v.reserve(10);
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		v.push_back(5);
		v.push_back(6);

		for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;
		cout << v.size() << endl;
		cout << v.capacity() << endl << endl;

		v.resize(4);
		for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;
		cout << v.size() << endl;
		cout << v.capacity() << endl << endl;

		v.resize(8);
		for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;
		cout << v.size() << endl;
		cout << v.capacity() << endl << endl;

		v.resize(12);
		for (auto ch : v)
		{
			cout << ch << " ";
		}
		cout << endl;
		cout << v.size() << endl;
		cout << v.capacity() << endl << endl;
	}

	void test_vector4()
	{
		vector<int> v1;
		v1.push_back(1);
		v1.push_back(2);
		v1.push_back(3);
		v1.push_back(4);

		vector<int> v2(v1);
		for (auto ch : v1)
		{
			cout << ch << " ";
		}
		cout << endl;

		for (auto ch : v2)
		{
			cout << ch << " ";
		}
		cout << endl;

		vector<int> v3;
		v3.push_back(10);
		v3.push_back(20);
		v3.push_back(30);
		v3.push_back(40);
		v1 = v3;
		for (auto ch : v1)
		{
			cout << ch << " ";
		}
		cout << endl;
	}
}

2.vector.cpp

#include"vector.h"

int main()
{
	//wzyl::test_vector1();
	//wzyl::test_vector2();
	//wzyl::test_vector3();
	//wzyl::test_vector4();
}

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

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

相关文章

砥砺十年风雨路,向新而行创新程丨怿星科技十周年庆典回顾

10月24日&#xff0c;是一年中的第256天&#xff0c;也是程序员节&#xff0c;同时也是怿星的生日。2014年到2024年&#xff0c;年华似水匆匆一瞥&#xff0c;多少岁月轻描淡写&#xff0c;怿星人欢聚一堂&#xff0c;共同为怿星科技的十周年庆生&#xff01; 01.回忆往昔&…

Chrome与火狐哪个浏览器的移动版本更流畅

在当今的数字化时代&#xff0c;移动设备已经成为我们生活中不可或缺的一部分。而浏览器作为我们访问互联网的重要工具&#xff0c;其性能和用户体验直接影响到我们的使用感受。本文将对比Chrome和火狐&#xff08;Firefox&#xff09;两款主流浏览器的移动版本&#xff0c;探讨…

算法练习:1004. 最大连续1的个数 III

题目链接&#xff1a;1004. 最大连续1的个数 III。 题目要求&#xff0c;给定一个数组&#xff0c;这个数组里面只有0或1&#xff0c;然后计算有多少个连续的1的最大长度&#xff0c;同时给了一个条件就是&#xff0c;可以把k个0变成1&#xff0c;然后来计算长度。 暴力解法&a…

【大数据技术基础 | 实验七】HBase实验:部署HBase

文章目录 一、实验目的二、实验要求三、实验原理四、实验环境五、实验内容和步骤&#xff08;一&#xff09;验证Hadoop和ZooKeeper已启动&#xff08;二&#xff09;修改HBase配置文件&#xff08;三&#xff09;启动并验证HBase 六、实验结果七、实验心得 一、实验目的 掌握…

LLMs之LoLCATs:《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读

LLMs之LoLCATs&#xff1a;《LoLCATs: On Low-Rank Linearizing of Large Language Models》翻译与解读 导读&#xff1a;这篇论文的核心是提出了一种名为 LoLCATs (Low-rank Linear Conversion via Attention Transfer) 的方法&#xff0c;用于高效地将大型语言模型 (LLM) 线性…

linux命令详解,文件管理类

文件管理 stat 显示文件的详细信息&#xff0c;包括时间戳 stat filenametouch 主要用于更新文件的访问时间和修改时间&#xff08;时间戳&#xff09;。如果指定的文件不存在&#xff0c;touch 命令会创建一个新的空文件。 touch newfile参数 -t 更新文件的修改时间为特…

MySQL的其他函数

数学函数&#xff1a; 1.round 四舍五入 select round(1.45);//不管正负数,先将绝对值round,然后加正负号 select round(1.567,2); //表示小数点保留2位 2.ceil 向上取整 select ceil(-1.3); 3.floor 向下取整 4.truncate 截断 select truncate(1.65,1); // 结果保留小数…

@Excel若依导出异常/解决BusinessBaseEntity里面的字段不支持导出

今天发现所有实体类继承BusinessBaseEntity里面的这些通用字段不支持导出&#xff0c;debug时发现是这样&#xff1a; 导出效果 这里我把能查到的方法都汇总了&#xff0c;如果你也遇到这个异常&#xff0c;可以去逐步排查 1.先看库里有没有数据 2.看字段名是否对齐 3.所需要…

云数据中心基础环境-详细设计方案(364页WORD)

文档介绍&#xff1a; 随着云计算技术的飞速发展&#xff0c;云数据中心已成为企业数字化转型的核心基础设施&#xff0c;承载着数据存储、处理、分析和应用的重任。本设计方案旨在构建一个高性能、高可用、高安全性的云数据中心基础环境&#xff0c;以满足企业日益增长的业务需…

在 CSS 中,gap 是 布局容器(flex 或 grid)的属性。它用于设置容器内子元素之间的间距。

在 CSS 中&#xff0c;gap 是 布局容器&#xff08;flex 或 grid&#xff09;的属性。它用于设置容器内子元素之间的间距。以下是 gap 属性在不同布局中的应用&#xff1a; 1. 在 CSS Grid 布局中 gap 定义了网格行和列之间的间距。可以分别使用 row-gap 和 column-gap 设置行…

Python练习9

Python日常练习 题目&#xff1a; 编程序计算形式如&#xff1a;sumaaaaaaaaaa…aaa…aaa的表达式的值。 说明&#xff1a; 补充完整函数fun()&#xff0c;其中a为小于10的自然数&#xff0c;n为项数&#xff0c;给定 变量result作为函数返回值&#xff0c;变量ts作为…

浙江深大智能科技有限公司管控平台服务端存在任意文件上传漏洞

漏洞描述 智游宝是连接景区与分销商(OTA、旅行社)的公正、权威、可信的第三方服务平台。作为国内智慧景区第三方技术服务支撑平台&#xff0c;智游宝为景区提供了可控制分销商的管理环境&#xff0c;安全、便捷、高效地实现了电子票的生产、发送、检票、退换票以及票款回收等技…

Pr 视频过渡:沉浸式视频 - VR 默比乌斯缩放

效果面板/视频过渡/沉浸式视频/VR 默比乌斯缩放 Video Transitions/Immersive Video/VR Mobius Zoom VR 默比乌斯缩放 VR Mobius Zoom用于 VR 视频中的缩放式场景切换&#xff0c;通过缩小或放大的渐变效果在两个场景之间平滑过渡。 自动 VR 属性 Auto VR Properties 默认勾选…

Hive操作库、操作表及数据仓库的简单介绍

数据仓库和数据库 数据库和数仓区别 数据库与数据仓库的区别实际讲的是OLTP与OLAP的区别 操作型处理(数据库)&#xff0c;叫联机事务处理OLTP&#xff08;On-Line Transaction Processing&#xff09;&#xff0c;也可以称面向用户交易的处理系统&#xff0c;它是针对具体业务…

ssm063基于SSM框架的德云社票务系统的设计与实现+vue(论文+源码)_kaic

毕业设计&#xff08;论文&#xff09; 题 目&#xff1a; 基于SSM框架的德云社票务系统 专 题&#xff1a; 学 院&#xff1a; 班 级&#xff1a; …

基于vue框架的的民宿网站30lx7(程序+源码+数据库+调试部署+开发环境)系统界面在最后面。

系统程序文件列表 项目功能&#xff1a;用户,客房类型,民宿信息,民宿预订,民宿退订,续租信息,换房信息 开题报告内容 开题报告 题目&#xff1a;基于Vue框架的民宿网站开发 一、立论依据 选题背景与意义 随着旅游业的快速发展&#xff0c;民宿作为一种独特的住宿方式&…

Kubernetes的基本构建块和最小可调度单元pod-0

文章目录 一&#xff0c;什么是pod1.1pod在k8s中使用方法&#xff08;1&#xff09;使用方法一&#xff08;2&#xff09;使用方法二 1.2pod中容器的进程1.3pod的网络隔离管理&#xff08;1&#xff09;pause容器的作用 1.4 Pod分类&#xff1a;&#xff08;1&#xff09;自主式…

Centos Linux 7 搭建邮件服务器(postfix + dovecot)

准备工作 1. 一台公网服务器&#xff08;需要不被服务商限制发件收件的&#xff0c;也就是端口25、110、143、465、587、993、995不被限制&#xff09;&#xff0c;如有防火墙或安全组需要把这些端口开放 2. 一个域名&#xff0c;最好是com cn org的一级域名 3. 域名备案&am…

【论文翻译】TKDE 2024 | ST-MAN:用于交通预测的时空记忆增强的多级注意力网络

论文题目Spatio-Temporal Memory Augmented Multi-Level Attention Network for Traffic Prediction论文链接https://ieeexplore.ieee.org/document/10285880发表期刊/年份TKDE 2024关键词城市计算、时空预测、交通预测、记忆网络、注意力网络 摘要 交通预测是城市计算中一个重…

【每日一题】2009考研数据结构 - 求倒数第k个数的值

已知一个带有表头结点的单链表&#xff0c;结点结构为 data 和 link。假设该链表只给出了头指针 list。在不改变链表的前提下&#xff0c;请设计一个尽可能高效的算法&#xff0c;查找链表中倒数第 k 个位置上的结点&#xff08;k 为正整数&#xff09;。 要求&#xff1a; 若…