C++STL的vector模拟实现

文章目录

  • 前言
  • 成员变量
  • 成员函数
    • 构造函数
    • push_back
    • pop_back
    • insert
    • erase
    • 析构函数
    • 拷贝构造

前言

成员变量

namespace but
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
	private:
		iterator _start;
		iterator _finish;
		iterator _end_of_storage;
	};
}

我们之前实现顺序表是用指向数组的的指针和数组个数和容量来维护顺序表的，这里用三个指针来实现其实大差不差。
在这里插入图片描述

成员函数

构造函数

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

push_back

void push_back(const T& x)
{
	if (_finish == _end_of_storage)
	{
		reserve(capacity() == 0 ? 4 : capacity() * 2);//避免容量为0扩容还是0的情况
	}
	*_finish = x;
	++_finish;
}

首先放数据怎么放呢？
直接赋值。

为什么可以直接赋值？
因为空间是new出来的，如果是内置类型，有没有初始化都可以直接赋值。
但是自定义类型没有初始化不能直接赋值。

扩容

void reserve(size_t n)
{
	//避免缩容
	//1.缩容的代价太大
	//2.反复缩容与扩容，降低了性能。
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		//如果旧空间没有数据就不用拷贝了
		if (_start)
		{
			//因为是类型不一定是字符串，所以得使用memcpy
			memcpy(tmp, _start, sizeof(T)*size());
			delete[] _start;
		}
		_start = tmp;
		//这里有个小坑
		//_finish=_start + size();
		
		//提前把size()记录下来，防止这里出错
		//改成tmp也可以，但是有点影响我们原本的理解，不利于维护。
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

我们把其他一些需要用到的代码补上，然后测试一下。

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

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

迭代器

//这个普通迭代器实现起来也相当简单
iterator begin()
{
	return _start;
}

iterator end()
{
	return _finish;
}

pop_back

删除数据好像也很简单，直接finish- -就可以，但是也有一些问题，那具体有什么问题呢？我们来看一下。
在这里插入图片描述
我们简单测试一下。
我们一直pop,就出问题了。
在这里插入图片描述
_finish一直减就走到前面去了，这样我们使用迭代器就出问题了。

我们简单改一下。

void pop_back()
{
	assert(!empty());
	--_finish;
}
bool empty()
{
	return _start == _finish;
}

针对const对象的访问
在这里插入图片描述
本质还是涉及到权限的放大，我们把成员函数都改为const就可以了。

resize()

void resize(size_t n, T val = T())//T()默认构造，是匿名对象，具体解释看下面
{
	if (n < size())
	{
		// 删除数据
		_finish = _start + n;
	}
	else
	{
		if (n > capacity())
			reserve(n);
			
		while (_finish != _start+n)
		{
			*_finish = val;
			++_finish;
		}
	}
}

上面resize的缺省值能不能给0？
其实答案很明显， 显然不行，因为T是泛型编程，类型不一定是int,如果是double或者指针，对象都不行。

那问题又来了，int有默认构造函数吗？
我们在之前学习类和对象的时候知道，内置类型是没有构造函数的，但是有了模板之后它需要有。

在这里插入图片描述

insert

在这里插入图片描述
下面这段代码有什么问题？
在这里插入图片描述
如果容量不够，挪动数据就越界了。
在这里插入图片描述
除了容量不够还有没有其他什么问题？
提示一下pos==0; 好吧，其实不会发生之前模拟实现string的时候发生的无符号整型最大值的问题。

在这里插入图片描述
大家看这样子去测试就出问题了
在这里插入图片描述
注意，func(v1)是两次读取
程序运行时崩了。
在这里插入图片描述

先简单分析一下，这可能时内存问题，可能时数组越界。
为什么push_back 5次的时候没问题，push_back 4次就出问题了？
5个和4个的区别是什么？

insert的时候扩容出问题了。

注意看
在这里插入图片描述
在这里插入图片描述
发生了什么，扩容之后，start和finish变了，start 和finish为什么会变？
这是我们遇见的最经典的迭代器失效的问题。

pos变成野指针了。
这也就导致一直在循环的问题。
在这里插入图片描述
那这个怎么解决呢？
更新一下pos.

//void insert(iterator pos, const T& val)
iterator insert(iterator pos, const T& val)
{
	assert(pos >= _start);
	assert(pos <= _finish);

	if (_finish == _end_of_storage)
	{
		size_t len = pos - _start;
		reserve(capacity() == 0 ? 4 : capacity() * 2);

		// 扩容后更新pos，解决pos失效的问题
		pos = _start + len;
	}

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

	*pos = val;
	++_finish;

	return pos;
}

接下来，继续问一个问题，看前面的测试图片，insert之后能不能修改迭代器的位置。

(*pos)++;//我想修改这个3的位置。
func(v1);

在这里插入图片描述
程序没有报错，但是很明显不符合我们的预期。为什么？
不是已经把pos更新了吗，为什么外面还是不行呢？怎么不起作用。
因为自己写的insert是传值形参，形参的改变 不会影响实参的改变 。

怎么解决？

能不能用引用传参解决，看起来不错，实际不好。用引用传参会报错，为什么？
在这里插入图片描述

insert 引起迭代器失效的两种情况：
1.野指针问题
2.意义已经变了

通过返回值去解决
但是最好别用，你也不知道是什么时候失效。
insert以后我们认为pos失效了，不能再使用。

erase

在这里插入图片描述
现在又有一个问题，erase以后pos会不会失效？
不会，但是库里面的失效了，并且vs报错非常强烈，看下面。
在这里插入图片描述
报了一个断言错误。

再看一下g++下的运行。
在这里插入图片描述

那到底erase以后pos失效还是不失效？vs比较合理还是g++合理？
如果pos位置是4呢，那这个位置就很不合理了。

所以我们认为失效，不要访问，行为结果未定义，跟具体的编译器有关。
一定要注意，不然会被坑的很惨。

要想解决一下这种情况，我们都是用返回值来处理一下，其实本质就是不要pos跳过。

iterator erase(iterator pos)
{
	assert(pos >= _start);
	assert(pos < _finish);

	iterator start = pos + 1;
	while (start != _finish)
	{
		*(start - 1) = *start;
		++start;
	}

	--_finish;

	return pos;
}

下面这个测试，连续的偶数和最后一个是偶数都能解决，就没什么大问题了。
在这里插入图片描述

1. vs进行强制检查，erase以后，迭代器不能访问。
2.g++没有强制检查，具体问题具体分析，结果未定义。

string有没有迭代器失效？
有，但是string不容易发生迭代器失效问题。
insert和erase不喜欢用迭代器，用的都是下标。

析构函数

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

下面的构造函数。
在这里插入图片描述

给大家看一个大坑。
先看下面的代码，这样写有没有什么问题？
在这里插入图片描述
程序崩了

不初始化会出各种问题。
一调试很容易看到会出现哪些问题。

加上初始化列表

vector(size_t n, const T& val = T())//T()是什么前面已经讲得很清楚了
	: _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	reserve(n);
	for (size_t i = 0; i < n; ++i)
	{
		push_back(val);
	}
}

看一下这个构造函数。
在这里插入图片描述
在这里插入图片描述
如果是用iterator就写死了，你必须用vector的迭代器来进行初始化。

迭代器区间初始化，是必须用vectro的迭代器初始化吗？
一个容器用迭代器区间初始化，需要时任意类型的迭代器。

这里引出了另一个语法，允许一个类的成员函数再是函数模板。

// [first, last)
template <class InputIterator>
vector(InputIterator first, InputIterator last)
	: _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	while (first != last) //不能用 <=,如果是链表肯定就不行
	{
		push_back(*first);
		++first;
	}
}

如果我们不写初始化列表，可用c++11的语法，成员变量声明的时候给个缺省值
缺省值是给构造函数的初始化列表用的。
在这里插入图片描述

在这里插入图片描述

奇怪的事情发生了，编译的时候报了一个这样的错误
在这里插入图片描述

为什么匹配错了，匹配到上面写的那个迭代区间初始化那个？
在这里插入图片描述

我们知道编译器会调用最匹配的那个，仔细分析一下其实可以发现，如果推演一下的话，如果要匹配 vector(size_ t n, const T& val =T()); 的话，就会发生类型转换，而调用迭代器区间初始化的话，进行推演，如果类型是int 直接就匹配上了。

然后看迭代器区间初始化的代码，int不能解引用，就直接报错了。

怎么解决？
1.加个u, 代表我这个变量是无符号。
在这里插入图片描述

2…看STL的源码，看源码是怎么解决这个问题的。
我们这里可以用一个很简单的方式去就解决，提供一个重载的版本。

引用返回时有风险的，要谨慎使用，除非你想想operator【】那样，可以去修改。

给大家看一下神奇的东西。
在这里插入图片描述
只要类型能匹配，char可以发生转换。

最神奇的还是可以这么玩。
在这里插入图片描述

甚至可以是数组，为什么可以是数组？
原生指针可以是天然的迭代器，有个前提，这个原生指针是指向数组。
其实vector的迭代器，string的迭代器也可以是原生指针。

接着扩展一下。
sort

默认是升序
在这里插入图片描述
这是一个函数模板，它的名字叫随机访问迭代器，那随机访问是什么呢？一般底层是数组。
在这里插入图片描述
它可以帮我们排序，并且用起来很爽。

如果是降序，我们就这么用。
1.
在这里插入图片描述
2.
在这里插入图片描述
这两个其实是等价了。

拷贝构造

我们还涉及深浅拷贝的问题。
在这里插入图片描述
首先这样写，是我们经典的浅拷贝的问题。

我们先写一个传统写法的深拷贝。
在这里插入图片描述

vector(const vector<T>& v)
	: _start(nullptr)
	, _finish(nullptr)
	, _end_of_storage(nullptr)
{
	_start = new T[v.capacity()];
	memcpy(_start, v._start, sizeof(T) * v.size());
	_finish = _start + v.size();
	_end_of_storage = _start + v.capacity();
}

看下面的代码，崩了，为什么？
在这里插入图片描述

在这里插入图片描述
也就是说当我们数据是int的时候程序能正常运行，当我们的数据是string的时候就崩的。

因为memcpy也是一种浅拷贝。调用拷贝构造的时候，memcpy干了什么事情。
从起始位置开始依次把所有值拷贝下来。

在这里插入图片描述
这里面还有一层是我们没有考虑的，这是深拷贝里面又套了一层深拷贝。memcpy就是深层次的浅拷贝。
调用析构的时候会崩。

怎么解决呢？
我们肯定是要解决三个问题，数据是int类型，或者string类型，或者vector的vector类型。

怎样完成深拷贝呢？难道是我们自己写吗？
我们不能自己解决，因为T是模板，我们也不知道它具体是什么类型。
不能自己给它写一个深拷贝，因为它们是私有的，动不了里面的。

所以我们这里面调一个深拷贝的函数来完成。
赋值就是深拷贝。
在这里插入图片描述

其实我们还没有完全解决所有的问题 ，除了拷贝构造用了memcpy，扩容也用了memcpy。

修改扩容的代码。

void reserve(size_t n)
{
	if (n > capacity())
	{
		size_t sz = size();
		T* tmp = new T[n];
		if (_start)
		{
			//memcpy(tmp, _start, sizeof(T)*size());
			for (size_t i = 0; i < sz; ++i)
			{
				tmp[i] = _start[i];
			}
			delete[] _start;
		}

		_start = tmp;
		_finish = _start + sz;
		_end_of_storage = _start + n;
	}
}

那接着，哪里还有问题呢？vector里面的数据比如说是vector对象呢，比如vectro<vector >,给大家看一下，一个杨辉三角的例子。
在这里插入图片描述
测试
在这里插入图片描述

在这里插入图片描述
出错了，为什么？还有什么问题没有解决。
外面的vector是深拷贝，里面的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(const vector<T>& v)
{
	vector<T> tmp(v.begin, v.end());
	swap(tmp);
}

最后一个小问题，不加模板参数语法上也允许，但是不推荐这样写。
在这里插入图片描述

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

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

相关文章

c/c++ malloc、calloc、realloc and free

c/c++ malloc、calloc、realloc and free

malloc 需要头文件 #include<stdlib.h> void *malloc( size_t size ); malloc returns a void pointer to the allocated space, or NULL if there is insufficient memory available. To return a pointer to a type other than void, use a type cast on the return …
阅读更多...
【算法题】单词接龙(js)

【算法题】单词接龙(js)

![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/7fcc5df3354742bd88dad28219f82bf8.png 用例&#xff1a; 输入&#xff1a; 0 6 word dd da dc dword d 输出&#xff1a; worddwordda 说明&#xff1a; 先确定起始单词word&#xff0c;再接以d开有的且长度最长…
阅读更多...
Canal实时同步MySQL数据到ES

Canal实时同步MySQL数据到ES

一、canal简介 canal主要用途是对MySQL数据库增量日志进行解析&#xff0c;提供增量数据的订阅和消费&#xff0c;简单说就是可以对MySQL的增量数据进行实时同步&#xff0c;支持同步到MySQL、Elasticsearch、HBase等数据存储中去。 早期阿里巴巴因为杭州和美国双机房部署&…
阅读更多...
MATLAB运动学之蒙特卡罗法求积分与机器人工作域分析

MATLAB运动学之蒙特卡罗法求积分与机器人工作域分析

蒙特卡罗法又叫做统计模拟法、随机抽样技术&#xff0c;是一种随机模拟方法以概率和统计理论方法为基础的一种计算方法&#xff0c;通俗来说是可以使用随机数来解决很多计算问题的一种方法&#xff0c;很直观简单&#xff0c;尤其对于一些求解积分无解的情况&#xff0c;非常好…
阅读更多...
《Easy3d+Qt+VTK》学习

《Easy3d+Qt+VTK》学习

《Easy3dQtVTK》学习-1、编译与配置 一、编译二、配置注 一、编译 1、 资源下载&#xff1a;easy3d giuhub 2、解压缩 3、用qt打开CMakeLists.txt即可 4、点击项目&#xff0c;选择debug或者release&#xff0c;图中3处可自行选择&#xff0c;因为我的qt版本是6&#xff0c…
阅读更多...
Linux上使用Python的requests库进行HTTP请求

Linux上使用Python的requests库进行HTTP请求

在Linux上使用Python的requests库进行HTTP请求是一种非常方便和高效的方式。requests库是一个第三方库&#xff0c;用于发送HTTP请求并获取响应。下面是一个简单的示例&#xff0c;演示如何使用requests库发送GET请求并获取响应。 首先&#xff0c;你需要安装requests库。你可…
阅读更多...
玩转大数据15：常用的分类算法和聚类算法

玩转大数据15：常用的分类算法和聚类算法

前言 分类算法和聚类算法是数据挖掘和机器学习中的两种常见方法。它们的主要区别在于处理数据的方式和目标。 分类算法是在已知类别标签的数据集上训练的&#xff0c;用于预测新的数据点的类别。聚类算法则是在没有任何类别标签的情况下&#xff0c;通过分析数据点之间的相似性…
阅读更多...
MATLAB代码：含电热联合系统的微电网运行优化

MATLAB代码：含电热联合系统的微电网运行优化

微♥关注“电击小子程高兴的MATLAB小屋”获取专属优惠 说明书 MATLAB代码&#xff1a;含电热联合系统的微电网运行优化 关键词&#xff1a;微网 电热联合系统 优化调度 参考文档&#xff1a;《含电热联合系统的微电网运行优化》完全复现 仿真平台&#xff1a;MATLAB yalmi…
阅读更多...
vue的小练习-翻转单词

vue的小练习-翻转单词

先将字符串转成数组&#xff0c;用reverse&#xff08;&#xff09;翻转数组&#xff0c;再转成字符串 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevic…
阅读更多...
路由器的转换原理--ENSP实验

路由器的转换原理--ENSP实验

目录 一、路由器的工作原理 二、路由表的形成 1、直连路由 2、非直连路由 2.1静态路由 2.2动态路由 三、静态路由和默认路由 1、静态路由 1.1静态路由的缺点 1.2路由的配置--结合ensp实验 2、默认路由--特殊的静态路由 2.1概念 2.2格式 2.3默认路由的配置--ens…
阅读更多...
MySQL中的回表

MySQL中的回表

目录 1、表扫描和索引&#xff1a; 表扫描&#xff08;Table Scan&#xff09;&#xff1a; 索引&#xff1a; 2、聚簇索引 vs. 非聚簇索引&#xff1a; 聚簇索引&#xff08;Clustered Index&#xff09;&#xff1a; 非聚簇索引&#xff08;Non-clustered Index&#x…
阅读更多...
mybatis多表映射-分步查询

mybatis多表映射-分步查询

1、建库建表 create database mybatis-example; use mybatis-example; create table t_book (bid varchar(20) primary key,bname varchar(20),stuid varchar(20) ); insert into t_book values(b001,Java,s001); insert into t_book values(b002,Python,s002); insert into …
阅读更多...
焦炭冶金工艺3D可视化仿真展示更直观、形象

焦炭冶金工艺3D可视化仿真展示更直观、形象

冶金行业作为重要的工业领域&#xff0c;其岗位实践培训一直面临着诸多挑战&#xff0c;随着web3d开发和VR虚拟仿真技术的不断创新和应用&#xff0c;冶金3D虚拟仿真实践教学平台应运而生&#xff0c;为钢铁生产培训带来了崭新的变革。 冶金3D虚拟仿真实践教学平台采用了先进的…
阅读更多...
节日问候：在 Metaverse 中一起庆祝节日！

节日问候：在 Metaverse 中一起庆祝节日！

冬季即将来临&#xff0c;节日的脚步也越来越近&#xff0c;是时候通过 The Sandbox 中的最新活动——“节日问候”来迎接节日气氛了&#xff01;为期 43 天的庆祝活动从 12 月 11 日开始&#xff0c;到 1 月 22 日结束&#xff0c;将带领玩家穿越一个充满 60 种体验的冬季仙境…
阅读更多...
QT中时间时区处理总结

QT中时间时区处理总结

最近项目中要做跨国设备时间校正功能&#xff0c;用到了时区时间&#xff0c;在此做一下记录。 目录 1.常见时区名 2.测试代码 3.运行效果 1.常见时区名 "Pacific/Midway": "中途岛 (UTC-11:00)", …
阅读更多...
【NSX-T】搭建NSX-T环境 —— Lab 说明和准备工作

【NSX-T】搭建NSX-T环境 —— Lab 说明和准备工作

目录 Lab 说明VM列表IP地址规划使用192.168.1.0/24作为实验环境主IP网段使用192.168.2.0/24网段作为freenas存储网段NSX 网段 拓扑汇总vSphere 7vSphere 8 虚拟机部署顺序 准备工作 Lab 说明 VM列表 Y&#xff1a;表示已部署N&#xff1a;表示未部署 HostIPDomain NameOSServ…
阅读更多...
清雪除冰，扫出“平安路” 开封市鼓楼区民政局社工组织开展除雪破冰志愿行动

清雪除冰，扫出“平安路” 开封市鼓楼区民政局社工组织开展除雪破冰志愿行动

近日&#xff0c;我市迎来大范围降雪天气&#xff0c;积雪融化、道路结冰、湿滑难行&#xff0c;造成居民群众出行不便和较大的交通安全隐患。为迅速清除积雪和道路结冰积水&#xff0c;保障辖区居民尤其是困境群体的出行安全&#xff0c;2023年12月11日下午&#xff0c;鼓楼区…
阅读更多...
Kafka系列之：统计kafka集群Topic的分区数和副本数，批量增加topic副本数

Kafka系列之：统计kafka集群Topic的分区数和副本数，批量增加topic副本数

Kafka系列之：统计kafka集群Topic的分区数和副本数，批量增加topic副本数 一、创建KafkaAdminClient二、获取kafka集群topic元信息三、获取每个topic的名称、分区数、副本数四、生成增加topic副本的json文件五、执行增加topic副本的命令六、确认topic增加副本是否成功一、创建K…
阅读更多...
系列二十七、Apache Jmeter使用

系列二十七、Apache Jmeter使用

一、安装 下载安装包>解压到指定目录>双击打开D:\Programs\apache-jmeter-5.5\bin\ApacheJmeter.jar即可。我分享的ApacheJmeter链接&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/1VI7f3buIWZbQEeq2CRbwlg?pwdyyds 提取码&#xff1a;yyds 二、使用 2.1、添…
阅读更多...
@CrossOrigin解决跨域不生效问题

@CrossOrigin解决跨域不生效问题

参考文献 CrossOrigin注解没有生效&#xff0c;解决方案集合_crossorigin注解不起作用-CSDN博客
阅读更多...
最新文章

Copyright @ 2022~2023