【C++】vector容器初步模拟

在这里插入图片描述
送给大家一句话：
努力一点，漂亮—点，阳光一点。早晚有一天，你会惊艳了时光，既无人能替，又光芒万丈。

vector容器初步模拟

  • 1 认识vector
    • 开始了解
    • 底层实现
  • 2 开始实现
    • 成员变量
    • 构造函数 析构函数
    • 尾插
    • 迭代器
    • 插入 删除 寻找操作
    • 操作符重载
    • swap函数
  • 总结
  • Thanks♪(･ω･)ﾉ谢谢阅读！！！
  • 下一篇文章见！！！

今天我我来进行vector的模拟实现，先简单的实现一下初步功能，使其对内置类型可以适配。（大部分与string很类似）

1 认识vector

开始了解

  1. vector是表示可变大小数组的序列容器。
  2. 就像数组一样，vector也采用的连续存储空间来存储元素。也就是意味着可以采用下标对vector的元素进行访问，和数组一样高效。但是又不像数组，它的大小是可以动态改变的，而且它的大小会被容器自动处理。
  3. 本质讲，vector使用动态分配数组来存储它的元素。当新元素插入时候，这个数组需要被重新分配大小为了增加存储空间。其做法是，分配一个新的数组，然后将全部元素移到这个数组。就时间而言，这是一个相对代价高的任务，因为每当一个新的元素加入到容器的时候，vector并不会每次都重新分配大小。
  4. vector分配空间策略：vector会分配一些额外的空间以适应可能的增长，因为存储空间比实际需要的存储空间更大。不同的库采用不同的策略权衡空间的使用和重新分配。但是无论如何，重新分配都应该是对数增长的间隔大小，以至于在末尾插入一个元素的时候是在常数时间的复杂度完成的。
  5. 因此，vector占用了更多的存储空间，为了获得管理存储空间的能力，并且以一种有效的方式动态增长。
  6. 与其它动态序列容器相比（deque, list and forward_list）， vector在访问元素的时候更加高效，在末尾添加和删除元素相对高效。对于其它不在末尾的删除和插入操作，效率更低。比起list和forward_list统一的迭代器和引用更好。

使用STL的三个境界：能用，明理，能扩展 ，那么下面学习vector，我们也是按照这个方法去学习

底层实现

我们来了解一下vector的底层实现是如何做到，首先就要了解其类成员是如何定义的，这样我们才能更好的复刻vector（以下是1996年的STL版本，还比较简单）：

protected:
  typedef simple_alloc<value_type, Alloc> data_allocator;
  iterator start; 
  iterator finish;
  iterator end_of_storage //容量结束;

可以看到受保护的内部成员变量是由三个迭代器构成的。
迭代器的底层是：

typedef T value_type;
typedef value_type* iterator;

也就是说底层是指针，T是模版类的参数。接下来我们在观察一下构造函数是如何操作的(参考一部分)：

 vector() : start(0), finish(0), end_of_storage(0) {}
 vector(size_type n, const T& value) { fill_initialize(n, value); }
 vector(int n, const T& value) { fill_initialize(n, value); }
 vector(long n, const T& value) { fill_initialize(n, value); }

这个fill_initialize又是什么呢？？？是初始化函数，（在工程文件中，经常使用一层又一层的嵌套，由于我还没有丰富的工程经验，我看起来还是很费劲，晕乎乎的）。我们看一部分即可，现在我们开始手搓vector，针对内置类型进行操作。

2 开始实现

我们开始逐步进行实现。

成员变量

根据我们刚才所查看的源码，我们要使用三个迭代器，要使用迭代器，我们可以使用指针进行模拟。

//使用模版 兼容各种类型
template<typename T>
class vector {
public:
	//重命名 指针即可模拟迭代器 常量与非常量都要提供哦
	typedef T* iterator;
	typedef const T* const_iterator;
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _end = nullptr;
	};

写出三个迭代器（指针）后，我们对构造函数应该也有了大致思路：需要初始化三个迭代器，所以我们给与初始值nullptr。让后进行开辟空间。

构造函数 析构函数

这里的构造函数我设置三个接口，一个是空构造，一个是开辟 N 个空间并初始化为val，一个是拷贝构造:

//空构造
vector() 
{}
//开辟 N 个空间并初始化为val
vector(size_t n,T val = T()) {
	iterator tmp = new T[n];
	_start = tmp;
	for (iterator it = begin(); it < _start + n ;it++) {
		 *it= val;
	}
	_finish = _start + n;
	_end = tmp + n ;

}
/拷贝构造
vector(vector<T>& v) {
	//依次尾插即可完成操作
	for (auto s : v) {
		push_back(s);
	}
}

析构函数就是简单的释放空间即可：

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

我们完成了构造函数和析构函数，为了能够进行测试，我们现在来实现尾插操作：

尾插

尾插操作之前，根据我们实现string的经验来说，我们需要做一些准备工作，实现一些常用接口（size(),capacity(),reserve(),resize()）:
注意：如果对象中涉及到资源管理时，千万不能使用memcpy进行对象之间的拷贝，因为memcpy是浅拷贝，否则可能会引起内存泄漏甚至程序崩溃。

		//注意const 保证不会进行权限的放大
		size_t size() const{
			return _finish - _start;
		}
		size_t capacity() const{
			return _end - _start;
		}
		bool empty(){
			return size() == 0;
		}
		//扩容
		void reserve(size_t newcapacity) {
			//记录位置
			size_t n = _finish - _start;
			T* tmp = new T[newcapacity];
			//拷贝
			memcpy(tmp, _start, size() * sizeof(T));
			_start = tmp;
			_finish = _start + n;
			_end = _start + newcapacity;
		}
		//改变大小
		void resize(size_t n, T val = T()) {
			//x需要扩容
			if ( n > size())
			{
				reserve(n);
				 ;
				while (_finish != _end) {
					*_finish = val;
					_finish++;
				}
				
			}
			//不需扩容
			else 
			{
				_finish = _start + n;
			}
		}

实现了这些接口，就可以顺畅的进行尾插的书写，通过size（）和capacity（）可以判断是否需要扩容，reserve可以进行扩容。然后再_finish位置插入新的数据，再移动_finish即可。

		//尾插
		void push_back(T val) 
		{
			if (size() == capacity()) {
				//扩容
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}
			*_finish = val;
			_finish++;
		}

接下来我们在完善一下迭代器。

迭代器

迭代器的实现很简单，对指针进行重命名即可（真正的迭代器没有这么简单）

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; }

完成了begin（） 和end()函数，就可以使用基于范围的for循环了。
我们进行一个简单的测试，来看看我们写的构造，尾插是否正常。

template<class T>
void print_vector(const vector<T> v) {
	for (size_t i = 0; i < v.size(); i++) {
		cout << v[i] << " ";
	}
	cout << endl;
}
//构造，尾插测试
void vector_test1() {
	cout << "---------构造 ，尾插测试---------\n";
	vector<int> v1;
	vector<int> v2(4);

	v2.push_back(1);
	v2.push_back(2);
	v2.push_back(3);
	v2.push_back(4);

	print_vector(v2);

	v1.push_back(5);
	v1.push_back(6);
	print_vector(v1);
	cout << v1.size() << endl;
	cout << v1.capacity() << endl;

	vector<int> v3(v1);
	print_vector(v3);
}

看一下效果：

在这里插入图片描述
没有问题！！！

插入 删除 寻找操作

这个也很简单，对数据进行挪动就可以完成：

//任意位置插入
void insert(size_t pos = 0,T val = T()) {
//保证在数据范围之内
	assert(pos >= 0);
	assert(pos <= size());
	//检查
	if (size() == capacity()) {
		//扩容
		reserve(capacity() == 0 ? 4 : 2 * capacity());
	}

	iterator it = end();
	//依次后移 然后插入
	while (it >= begin() + pos) {
		*(it + 1) = *it;
		it--;
	}
	it++;
	*it = val;
	_finish++;
}
void erease(size_t pos) 
{
//保证在数据范围之内
	assert(pos >= 0);
	assert(pos <= size());

	iterator it = begin() + pos;
	//依次前移
	while (it < end()) {
		*it = *(it + 1);
		it++;
	}
	_finish--;

}
//尾删
void pop_back() {
	erease(size());
			
}
size_t find(T val = T()) 
{
	//依次寻找
	for (iterator it = _start; it < _finish;it++) {
		if (*it == val) return it - _start;
	}
	return -1;
}

操作符重载

vector容器最重要的操作符应该就是[ ]操作了吧，此外重载一个 = ：

//提供常量与非常量
T& operator[](size_t n) { assert(n >= 0); assert(n < size()); return *(_start + n); }
const T& operator[](size_t n) const { assert(n >= 0); assert(n < size()); return *(_start + n); }
//类似拷贝
vector<T>& operator=(vector<T>& v){

	T* tmp = new T[v.capacity()];
	memcpy(tmp, v._start, v.size() * sizeof(T));
	size_t pos = v.size();
	size_t n = v.capacity();

	_start = tmp;
	_finish = _start + pos;
	_end = _start + capacity();

	return *this;
}

这样就完成了：
我们进行一个测试来看看是否可行：

void vector_test2() {
	cout << "---------resize find insert erase测试---------\n";
	
	vector<int> v1;

	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	print_vector(v1);
	cout << v1.find(2) << endl;

	v1.resize(10, 0);
	print_vector(v1);
	v1.insert(0, 0);
	print_vector(v1);
	v1.erease(5);
	print_vector(v1);
	
}

来看效果：
在这里插入图片描述
成功！！！

swap函数

接下来在提供一个swap 函数以供交换，注意一定是深拷贝！！！

		void swap(vector& v) {

			T* tmp = new T[v.capacity()];
			memcpy(tmp, v._start, v.size() * sizeof(T));
			size_t pos = v.size();
			size_t n = v.capacity();

			v._start = _start;
			v._finish = _finish;
			v._end = _end;

			_start = tmp;
			_finish = _start + pos;
			_end = _start + capacity();


		}

来进行一个简单测试：

//交换测试
void vector_test3() {
	cout << "---------swap 测试---------\n";
	vector<int> v1;

	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	v1.push_back(6);
	print_vector(v1);
	vector<int> v2(4);

	v2.push_back(1);
	v2.push_back(3);
	v2.push_back(1);
	v2.push_back(4);
	print_vector(v2);
	v2.swap(v1);

	print_vector(v1);
	print_vector(v2);

}

来看效果：
在这里插入图片描述
成功交换！！！

总结

我们初步完成了对vector 的模拟实现，但是依然有问题，比如不支持string等特殊类型。所以下一篇文章我们来一起完善一下。

Thanks♪(･ω･)ﾉ谢谢阅读！！！

下一篇文章见！！！

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

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

相关文章

FX110网：FCA揭露Admirals的克隆实体！冒充正规平台行骗

FX110网：FCA揭露Admirals的克隆实体！冒充正规平台行骗

近日&#xff0c;英国金融行为监管局&#xff08;FCA&#xff09;曝光了多个网址&#xff0c;揭露克隆实体fxsadmiral / admiral-fx / admiralsfx。这些克隆公司复制授权公司Admiral Markets UK Ltd的重要信息&#xff0c;试图让人们相信他们的公司是真实的。FCA本次披露的克隆…
阅读更多...
记录西门子200：PUT和GET通讯测试

记录西门子200：PUT和GET通讯测试

GET/PUT&#xff1a;S7-200SMART之间专有通讯协议。 准备两台Smart-PLC&#xff0c;这里使用的ST60和CR40。外加一个交换机。 CR40的地址设置是&#xff1a;192.168.2.1 用来读 ST60的地址设置是&#xff1a;192.168.2.2 用来写 打开软件&#xff0c;选择CPU-CR4配…
阅读更多...
深入探索Java并发库（JUC）中的ReentrantReadWriteLock

深入探索Java并发库（JUC）中的ReentrantReadWriteLock

码到三十五 &#xff1a; 个人主页 心中有诗画&#xff0c;指尖舞代码&#xff0c;目光览世界&#xff0c;步履越千山&#xff0c;人间尽值得 ! 在Java并发编程的世界中&#xff0c;锁是一种用于同步访问共享资源的机制。Java并发库&#xff08;JUC&#xff09;为我们提供了多…
阅读更多...
简易指南：国内ip切换手机软件怎么弄

简易指南：国内ip切换手机软件怎么弄

在网络访问受到地域限制的情况下&#xff0c;使用国内IP切换手机软件可以帮助用户轻松访问被屏蔽的内容&#xff0c;扩展网络体验。以下是虎观代理小二分享的使用国内IP切换手机软件的简易指南。并提供一些注意事项。 如何在手机上使用国内IP切换软件 步骤一&#xff1a;选择I…
阅读更多...
PHP连接达梦数据库

PHP连接达梦数据库

PDO是一种在PHP中连接数据库的接口&#xff0c;可以通过PDO接口使用PHP连接达梦数据库。 1、安装PHP环境 检查当前环境是否安装PHP [rootlocalhost ~]# php -v 当前环境并未安装PHP&#xff0c;需要进行安装&#xff0c;选择安装PHP7.3版本。 2、安装 epel-release源和源管…
阅读更多...
工程信号的去噪和（分类、回归和时序）预测

工程信号的去噪和（分类、回归和时序）预测

&#x1f680;【信号去噪及预测论文代码指导】&#x1f680; 还为小论文没有思路烦恼么&#xff1f;本人专注于最前沿的信号处理与预测技术——基于信号模态分解的去噪算法和深度学习的信号&#xff08;回归、时序和分类&#xff09;预测算法&#xff0c;致力于为您提供最精确、…
阅读更多...
【Python爬虫】网络爬虫：信息获取与合规应用

【Python爬虫】网络爬虫：信息获取与合规应用

这里写目录标题 前言网络爬虫的工作原理网络爬虫的应用领域网络爬虫的技术挑战网络爬虫的伦理问题结语福利 前言 网络爬虫&#xff0c;又称网络爬虫、网络蜘蛛、网络机器人等&#xff0c;是一种按照一定的规则自动地获取万维网信息的程序或者脚本。它可以根据一定的策略自动地浏…
阅读更多...
常用的6个的ChatGPT网站，国内可用！

常用的6个的ChatGPT网站，国内可用！

GPTGod &#x1f310; 链接&#xff1a; GPTGod &#x1f3f7;️ 标签&#xff1a; GPT-4 免费体验 支持API 支持绘图 付费选项 &#x1f4dd; 简介&#xff1a;GPTGod 是一个功能全面的平台&#xff0c;提供GPT-4的强大功能&#xff0c;包括API接入和绘图支持。用户可以选择免…
阅读更多...
【阿里魔搭】modelscope包下载安装

【阿里魔搭】modelscope包下载安装

最终解决方案&#xff1a;使用源码安装modelscope 这里写目录标题 问题描述&#xff1a;pip安装包冲突安装步骤 问题描述&#xff1a;pip安装包冲突 一开始的是在3.11的虚拟环境下使用命令行pip install "modelscope[nlp]" -f https://modelscope.oss-cn-beijing.al…
阅读更多...
DUSt3R：简化三维重建

DUSt3R：简化三维重建

3D 重建是从二维 (2D) 图像创建对象或场景的 3D 虚拟表示的任务&#xff0c;可用于模拟、可视化或本地化等多种目的。 它广泛应用于计算机视觉、机器人和虚拟现实&#xff08;VR&#xff09;等多个领域。 在基本设置中&#xff0c;3D 重建方法输入一对图像 I1 和 I2&#xff0c…
阅读更多...
字体测试集：选取、应用与兼容性指南

字体测试集：选取、应用与兼容性指南

1. 字体测试集 本人非专业字体工作者&#xff0c;字体测试集为个人经验总结整理&#xff0c;仅供参考 那时&#xff0c;天下人的口音、言语都是一样。 南去經三國&#xff0c;東來過五湖 南去经三国&#xff0c;东来过五湖 永东国酬爱郁灵鹰袋 0Oo1lI ga The quick brown fox j…
阅读更多...
6个免费的ChatGPT网站

6个免费的ChatGPT网站

AI 大模型的出现给时代带来了深远的影响&#xff1a; 改变了产业格局&#xff1a;AI 大模型的发展推动了人工智能技术在各行业的广泛应用&#xff0c;改变了传统产业的运作方式&#xff0c;促进了新兴产业的崛起&#xff0c;如智能驾驶、医疗健康、金融科技等。提升了科学研究…
阅读更多...
微软发布首款AI PC ，产业链有望迎来新一轮量价齐升

微软发布首款AI PC ，产业链有望迎来新一轮量价齐升

3月21日晚&#xff0c;微软举办主题为“办公新时代”的线上新品发布会&#xff0c;发布Surface Pro 10和Surface Laptop 6&#xff0c;新品将搭载基于英特尔酷睿Ultra或高通骁龙X Elite的处理器&#xff0c;配备新一代NPU&#xff0c;以增强AI性能。 这两款AI PC将支持“AI Exp…
阅读更多...
土地利用的时序建模

土地利用的时序建模

1、LULC 模型的现状 最近的土地利用和土地覆盖 (LULC) 建模进展来自两种方法。 在一种方法中&#xff0c;现有模型适用于 LULC&#xff0c;而在另一种方法中&#xff0c;模型架构是针对 LULC 明确设计的。 随着大型基础模型的兴起&#xff0c;人工智能和深度学习取得了重大进…
阅读更多...
数据结构 二叉树 力扣例题AC——代码以及思路记录

数据结构 二叉树 力扣例题AC——代码以及思路记录

LCR 175. 计算二叉树的深 某公司架构以二叉树形式记录&#xff0c;请返回该公司的层级数。 AC int calculateDepth(struct TreeNode* root) {if (root NULL){return 0;}else{return 1 fmax(calculateDepth(root->left), calculateDepth(root->right));} } 代码思路 …
阅读更多...
【Linux C | 多线程编程】线程的创建、线程ID、线程属性

【Linux C | 多线程编程】线程的创建、线程ID、线程属性

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; ⏰发布时间⏰&#xff1a;2024-03-22 0…
阅读更多...
SSC9211_USB-CAM解决方案

SSC9211_USB-CAM解决方案

一、方案描述 SSC9211是一种用于USB-CAM应用程序跟场景的高度集成的SOC产品。平台本身基于ARM层-A7双核&#xff0c;内置16位&#xff0c;64M的DDR2&#xff0c;集成了图像传感器接口、高级ISP、高性能JPEG编码器和其他丰富的外设接口。支持单&#xff0c;双 MIPI sensor方案&…
阅读更多...
H3C--堆叠（IRF）

H3C--堆叠（IRF）

拓扑图 配置流程 配置SW1与SW2堆叠 一、SW1&#xff1a; shutdown 物理端口配置堆叠优先级&#xff0c;优先级高的成为主设备创建堆叠逻辑接口&#xff0c;将物理接口加入到堆叠逻辑接口中 二、SW1&#xff1a; sysname SW1 # irf member 1 priority 6 # irf-port 1/1port…
阅读更多...
基于时空上下文（STC）的运动目标跟踪算法，Matlab实现

基于时空上下文（STC）的运动目标跟踪算法，Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…
阅读更多...
windowsVMware虚拟机中扩展linux磁盘空间

windowsVMware虚拟机中扩展linux磁盘空间

1.虚拟磁盘扩容 VM中&#xff0c;关闭linux虚拟机&#xff0c;直接编辑虚拟机-硬盘-扩展磁盘容量 2.通过Gparted工具进行LINUX系统磁盘分区 未分区挂载前可以看到/挂载点下空间为20G&#xff1a; 通过虚拟机-快照-拍摄快照&#xff0c;操作前可拍摄快照&#xff08;便于恢复之前…
阅读更多...
最新文章

Copyright @ 2022~2023