【C++】vector模拟实现及其应用

文章目录

  • vector的介绍
  • vector的使用及其实现
      • vector的定义
      • vector iterator 的使用
      • vector空间增长问题
      • vector的增删查改

vector的介绍

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

vector的使用及其实现

vector的定义

(constructor)构造函数声明接口说明
vector()(重点)无参构造
vector(size_type n, const value_type& val = value_type())构造并初始化n个val
vector (const vector& x); (重点)拷贝构造
vector (InputIterator first, InputIterator last);使用迭代器进行初始化构造
int main()
{
	vector<int> v1;//无参构造
	vector<int> v2(5, 3);
	for (auto ch : v2)
	{
		cout << ch << " ";
	}
	cout << endl;
	vector<int> v3(v2);
	//拷贝构造是定义一个新的,赋值是已经定义好了一个了
	for (auto ch : v3)
	{
		cout << ch << " ";
	}
	cout << endl;
	vector<int> v4(v3.begin()+ 1, v3.end()- 1);
	for (auto ch : v4)
	{
		cout << ch << " ";
	}
	cout << endl;

	return 0;
}

在这里插入图片描述
模拟实现,需要注意的地方注释在代码中了

		vector()
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{}
		vector(size_t n,const T& val=T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
		vector(int n, const T& val = T())
			:_start(nullptr)
			, _finish(nullptr)
			, _end_of_storage(nullptr)
		{
			reserve(n);
			for (int i = 0; i < n; ++i)
			{
				push_back(val);
			}
		}
		//1.vector(size_t n,const T& val=T())
		//2.vector<int> v1(10, 5);
		//3.template <class InputIterator>
		//vector(InputIterator first, InputIterator last)
		//上面的三行注释的代码,1和2互相冲突,2会优先访问3,它们的类型更加匹配,
		//编译器会优先找与自己更加合适的人匹配
		//错误非法的间接寻址
		//解决办法可以在重载一个构造函数,将size_t改成int
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//vector(const vector<T>& v)
		//{
		//	_start = new T[v.capacity()];
		//	//memcpy(_start, v._start, sizeof(T)*v.size());
		//	//因为memcpy也是进行浅拷贝,vector<string>
		//	for (size_t i = 0; i < v.size(); ++i)
		//	{
		//		_start[i] = v._start[i];
		//		//
		//	}

		//	_finish = _start + v.size();
		//	_end_of_storage = _start + v.capacity();
		//}
		//这里使用上面被注释的代码,拷贝构造也是可以的,上面的更加规范
		//注意memcpy是不能随便用的,会造成浅拷贝
		vector(const vector<T>& v)
		{
			vector<T> tmp(v.begin(), v.end());
			swap(tmp);
		}
		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_end_of_storage, v._end_of_storage);
		}
		//注意下面是传值,临时拷贝,所以交换时将他修改也是无所谓的,
		//也并不会影响v2的结果!!!!!!!!!!!!!
		//v1=v2
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}

在这里插入图片描述
在这里插入图片描述
从上面的两张图片当中,在实现拷贝构造和赋值重载时是可以将vector<T>替换为vector

在这里介绍一个自己当时的疑问,为什么模板函数不能直接代替vector<int>
vector(const vector<T>& v)
vector(int n, const T& val = T())
问题也是从上面的两个函数参数得来的,在第二个当中就能代替vector<int>,而上面的却不能。
T是vector存储的数据类型,拷贝构造是要用已有的vector对象构造新的vector,所以类型应该是const vector<T>

vector iterator 的使用

iterator的使用接口说明
begin + end(重点)获取第一个数据位置的iterator/const_iterator, 获取最后一个数据的下一个位置的iterator/const_iterator
rbegin + rend获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

在这里插入图片描述

int main()
{
	vector<int> v1;
	v1.push_back(1);
	v1.push_back(2);
	v1.push_back(3);
	v1.push_back(4);
	v1.push_back(5);
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		cout << *it << " ";
		it++;
	}
	cout << endl;
	vector<int>::reverse_iterator rit = v1.rbegin();
	while (rit !=v1.rend())
	{
		cout << *rit << " ";
		rit++;
	}
	cout << endl;
}

在这里插入图片描述
相关模拟实现,反向迭代器会在后期实现的。

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

vector空间增长问题

容量空间接口说明
size获取数据个数
capacity获取容量大小
empty判断是否为空
resize(重点)改变vector的size
reserve (重点)改变vector的capacity
  • capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。
    这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义
    的。vs是PJ版本STL,g++是SGI版本STL。
  • reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问
    题。
  • resize在开空间的同时还会进行初始化,影响size。
// 测试vector的默认扩容机制
void TestVectorExpand()
{
	size_t sz;
	vector<int> v;
	sz = v.capacity();
	cout << "making v grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}
vs:运行结果:vs下使用的STL基本是按照1.5倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 3
capacity changed : 4
capacity changed : 6
capacity changed : 9
capacity changed : 13
capacity changed : 19
capacity changed : 28
capacity changed : 42
capacity changed : 63
capacity changed : 94
capacity changed : 141
g++运行结果:linux下使用的STL基本是按照2倍方式扩容
making foo grow :
capacity changed : 1
capacity changed : 2
capacity changed : 4
capacity changed : 8
capacity changed : 16
capacity changed : 32
capacity changed : 64
capacity changed : 128
// 如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够
// 就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
	vector<int> v;
	size_t sz = v.capacity();
	v.reserve(100); // 提前将容量设置好,可以避免一遍插入一遍扩容
	cout << "making bar grow:\n";
	for (int i = 0; i < 100; ++i)
	{
		v.push_back(i);
		if (sz != v.capacity())
		{
			sz = v.capacity();
			cout << "capacity changed: " << sz << '\n';
		}
	}
}

下面为相关操作

int main()
{
	vector<int> v1(5, 3);
	cout << v1.size() << endl;
	cout << v1.capacity() << endl;
	for (auto ch : v1)
	{
		cout << ch << " ";
	}
	cout << endl;

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

	v1.resize(20,1);
	cout << v1.size() << endl;
	cout << v1.capacity() << endl;
	for (auto ch : v1)
	{
		cout << ch << " ";
	}
	cout << endl;
	return 0;
}

在这里插入图片描述
模拟实现

		bool empty() const
		{
			return  _start == _finish;
		}
		size_t size() const
		{
			return _finish - _start;
		}
		size_t capacity() const
		{
			return _end_of_storage - _start;
		}
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp = new T[n];
				size_t sz = size();//提前做好记录,防止更改地址
				if (_start)//判断一下,如果为空,就可以省去这步
				{
					//memcpy(tmp, _start, sizeof(T) * n);
					//在扩容这里也是有问题的,因为需要将数据移过来
					//如果只是进行浅拷贝,在执行delete[] _start;时数据会销毁
					for (size_t i = 0; i < sz; ++i)
					{
						tmp[i] = _start[i];
					}
					delete[] _start;
				}
				//开新的空间地址会更改,_strat,_finsh,_end_of_storage都会改变,***
				_start = tmp;
				_finish = _start + sz;
				_end_of_storage = _start + n;
			}
		}
		void resize(size_t n, T val = T())
		{//这里的第二个参数是可以为任意类型
			if (n < size())
			{
				_finish = _start + n;
			}
			else
			{
				if (n > capacity())
				{
					reserve(n);
				}
				while (_finish != _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}
		}

vector的增删查改

vector增删查改接口说明
push_back(重点)尾插
pop_back (重点)尾删
find查找。(注意这个是算法模块实现,不是vector的成员接口)
insert在position之前插入val
erase删除position位置的数据
swap交换两个vector的数据空间
operator[] (重点)像数组一样访问

1.2.4 vector 迭代器失效问题。(重点)
迭代器的主要作用就是让算法能够不用关心底层数据结构,其底层实际就是一个指针,或者是对指针进行了
封装,比如:vector的迭代器就是原生态指针T* 。因此迭代器失效,实际就是迭代器底层对应指针所指向的
空间被销毁了,而使用一块已经被释放的空间,造成的后果是程序崩溃(即如果继续使用已经失效的迭代器,
程序可能会崩溃)。
对于vector可能会导致其迭代器失效的操作有:

  1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、
    push_back等。
#include <iostream>
using namespace std;
#include <vector>
int main()
{
	vector<int> v{ 1,2,3,4,5,6 };

	auto it = v.begin();

	// 将有效元素个数增加到100个,多出的位置使用8填充,操作期间底层会扩容
	// v.resize(100, 8);

	// reserve的作用就是改变扩容大小但不改变有效元素个数,操作期间可能会引起底层容量改变
	// v.reserve(100);

	// 插入元素期间,可能会引起扩容,而导致原空间被释放
	// v.insert(v.begin(), 0);
	// v.push_back(8);

	// 给vector重新赋值,可能会引起底层容量改变
	v.assign(100, 8);

	/*
	出错原因:以上操作,都有可能会导致vector扩容,也就是说vector底层原理旧空间被释放掉,
   而在打印时,it还使用的是释放之间的旧空间,在对it迭代器操作时,实际操作的是一块已经被释放的
   空间,而引起代码运行时崩溃。
	解决方式:在以上操作完成之后,如果想要继续通过迭代器操作vector中的元素,只需给it重新
   赋值即可。
	*/
	while (it != v.end())
	{
		cout << *it << " ";
		++it;
	}
	cout << endl;
	return 0;
}
  1. 指定位置元素的删除操作–erase
#include <iostream>
using namespace std;
#include <vector>
int main()
{
 int a[] = { 1, 2, 3, 4 };
 vector<int> v(a, a + sizeof(a) / sizeof(int));
 // 使用find查找3所在位置的iterator
 vector<int>::iterator pos = find(v.begin(), v.end(), 3);
 // 删除pos位置的数据,导致pos迭代器失效。
 v.erase(pos);
 cout << *pos << endl; // 此处会导致非法访问
 return 0;
}

erase删除pos位置元素后,pos位置之后的元素会往前搬移,没有导致底层空间的改变,理论上讲迭代
器不应该会失效,但是:如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是
没有元素的,那么pos就失效了。因此删除vector中任意位置上元素时,vs就认为该位置迭代器失效
了。
以下代码的功能是删除vector中所有的偶数,请问那个代码是正确的,为什么?

int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
	return 0;
}
//这段代码的问题出在了,当删除了,最后一个值,end和it正好错过
//因此it != v.end()也就无法达到
//下面的代码是解决方法,这也是erase为什么要有返回值的原因
int main()
{
	vector<int> v{ 1, 2, 3, 4 };
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			it = v.erase(it);
		else
			++it;
	}
	return 0;
}

迭代器失效解决办法:在使用前,对迭代器重新赋值即可
模拟实现
在这里要重点注意一下memcpy

    1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中
    1. 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且
      自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。
void push_back(const T& x)
		{
			if (_finish == _end_of_storage)
			{
				reserve(capacity() == 0 ? 4 : capacity() * 2);
			}
			*_finish = x;
			_finish++;
		}
		void pop_back()
		{
			assert(!empty());
			_finish--;

		}

		iterator insert(iterator pos, const T& val)
		{
			assert(pos <= _finish);
			assert(pos >= _start);
			if (_finish == _end_of_storage)
			{
				size_t len = pos - _start;//防止迭代器失效
				reserve(capacity() == 0 ? 4 : capacity() * 2);
				pos = _start + len;
				//迭代器失效!!!!!
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = val;
			_finish++;
			return pos;
		}
		iterator erase(iterator pos)
		{
			assert(pos < _finish);
			assert(pos >= _start);
			iterator start = pos + 1;
			while (start != _finish)
			{
				*(start - 1) = *(start);
				start++;
			}
			_finish--;
			return pos;
		}


		T& operator[](size_t n)
		{
			assert(n < size());
			return _start[n];
		}
		const T& operator[](size_t n) const
		{
			assert(n < size());
			return _start[n];
		}
最后:文章有什么不对的地方或者有什么更好的写法欢迎大家在评论区指出

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

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

相关文章

开源 Swallow 代码审计系统体验

最近在哔哩哔哩看 到Swallow 代码审计系统的宣传,发现功能比较适合我目前的工作需要,安装使用了一下,简单做了一个笔记,分享给有需要的朋友. 底层架构为蜻蜓编排系统,墨菲SCA,fortify,SemGrep,hema 项目地址:https://github.com/StarCrossPortal/swallow 安装与使用视频教程:ht…

hexo 搭建个人博客记录

看B站的程序羊的关于搭建hexo博客的方法自己搭了一个博客&#xff0c;链接是 手把手教你从0开始搭建自己的个人博客 |无坑版视频教程| hexo 下面就视频所讲做做笔记&#xff0c;以后可以回来查看&#xff0c;推荐小伙伴想搭建hexo博客的可以去看看这个视频。 1. 安装Node.js…

react项目路由组件懒加载和路由传值方式

项目实战 使用useRoutes配置路由&#xff0c;结合插槽配置用户登录检测。 用户登录成功进入login 直接系统主界面 路由模块抽离 整体代码外移 { path: "/admin", element: ( <Author name"admin"> <Index /> </Author> ), }, { path:…

「SAP ABAP」OPEN SQL(七)【GROUP BY | HAVING | ORDER BY】

&#x1f482;作者简介&#xff1a; THUNDER王&#xff0c;一名热爱财税和SAP ABAP编程以及热爱分享的博主。目前于江西师范大学本科在读&#xff0c;同时任汉硕云&#xff08;广东&#xff09;科技有限公司ABAP开发顾问。在学习工作中&#xff0c;我通常使用偏后端的开发语言A…

基于matlab已知地球两点坐标求取距离和方位角函数distance

一、语法1.语法1[arclen,az] distance(lat1,lon1,lat2,lon2)&#xff1b;R6371.393; % 地球半径&#xff0c;单位&#xff1a;km地点1&#xff08;维度lat1&#xff0c;经度lon1&#xff09;&#xff0c;地点2&#xff08;维度lat2&#xff0c;经度lon2&#xff09;假设地点1和…

001 鸿蒙系统环境搭建及运行hello world

1 下载与安装DevEco Studio 在HarmonyOS应用开发学习之前&#xff0c;需要进行一些准备工作&#xff0c;首先需要完成开发工具DevEco Studio的下载与安装以及环境配置。 进入DevEco Studio下载官网&#xff0c;单击“立即下载”进入下载页面。 DevEco Studio提供了Windows版本…

PCIe基础

PCIe基础 PCI Express&#xff0c;简称PCI-E&#xff0c;官方简称PCIe&#xff0c;是计算机总线的一个重要分支&#xff0c;它沿用既有的PCI编程概念及信号标准&#xff0c;并且构建了更加高速的串行通信系统标准。目前这一标准由PCI-SIG组织制定和维护。 拓扑 配置空间 在 P…

【Python】plt.title()函数

plt.title() 是 matplotlib 库中用于设置图形标题的函数。 一、基本语法如下 plt.title(label, fontdictNone, locNone, padNone, **kwargs)其中&#xff1a; label 是要设置的标题文本&#xff0c;可以是字符串类型或者是数学表达式。fontdict 是一个可选的参数&#xff0c…

QT 基于AES加解密的使用,解析java端发来的密文

背景 java端往ukey中写授权信息&#xff0c;C端从ukey中读取授权信息。 java端写入的授权信息是加密的&#xff0c;并且要可逆。 因为java端采用的是AES加密的&#xff0c;所以我(C端)也只好采用对等形式搞定了。 使用的库 开发环境&#xff1a;Win10 Qt5.13 QT中AES加解密…

uniapp项目打包apk相关(androidStudio,Hbuildx,dCloud)

1、先注册和登陆dCloud平台&#xff0c;管理应用信息。 需要准备的参数(3个) APP_ID&#xff08;如&#xff1a;__UNI__123ABCD&#xff09; 包名&#xff08;如&#xff1a;com.hx.mhoa&#xff09; 应用签名&#xff08;应用sha1&#xff0c;应用md5&#xff0c;应用sha256&…

HLS协议格式

HLS协议格式 ES流&#xff08;Elementary Stream&#xff09;&#xff1a;基本码流&#xff0c;不分段的音频、视频或者其他信息的连续码流PES流&#xff0c;把基本码流ES分割成段&#xff0c;并加上相应头文件打包成形的打包基本码流PS流&#xff08;Program Stream&#xff…

一文解析RISC-V SiFive U54内核——中断和异常

中断 U54内核支持M模式和S模式中断。默认情况下&#xff0c;所有中断都在M模式下处理 。对于支持S模式的 hart&#xff0c;可以有选择地将中断委托给S模式。 U54中断架构如下&#xff1a; U54内核还支持两种类型的 RISC-V 中断&#xff1a;本地 和全局 。 本地中断 &#xf…

目标检测算法之Fast R-CNN和Faster R-CNN原理

一、Fast R-CNN原理 在SPPNet中&#xff0c;实际上特征提取和区域分类两个步骤还是分离的。只是使用ROI池化层提取了每个区域的特征&#xff0c;在对这些区域分类时&#xff0c;还是使用传统的SVM作为分类器。Fast R-CNN相比SPPNet更进一步&#xff0c;不再使用SVM作为分类器&a…

议程更新 | Occlum Meetup 北京站--一起来聊机密计算 TEE

首届 Occlum Meetup 还有 3 天就要和大家见面啦&#xff01;北京的小伙伴们&#xff0c;我们来喽&#xff01;为了能和大家有更充足的时间交流沟通&#xff0c;我们小小的调整了一下议程&#xff5e;最新议程请见下方。本次 Meetup 是 Occlum 开源社区首次在北京线下开展&#…

yolo车牌识别、车辆识别、行人识别、车距识别源码(包含单目双目)

视频效果 车牌识别视频车辆识别视频yolov5车辆识别视频yolov5 yoloR对比行人车辆识别视频yolo车距1完整源码http://www.hedaoapp.com/goods/goodsDetails?pid4132 系统设计 车牌自动识别是以计算机视觉处理、数字图像处理、模式识别等技术为基础&#xff0c;对摄像机所拍摄的…

从零开始,简单几步教会你shopify店铺设计

在弄完shopify的基础配置之后&#xff0c;我们就开始可以设计一下我们的店铺。人都是视觉动物&#xff0c;很难不被好看的东西吸引&#xff0c;所以把店面弄得漂漂亮亮的就是我们赢得顾客信赖的第一步。接下来龙哥会详细地解析一下&#xff0c;shopify的店铺设计与配置要怎么展…

Elasticsearch 核心技术(八):常用 DSL 查询(全文搜索、精确匹配、布尔查询)

❤️ 博客主页&#xff1a;水滴技术 &#x1f680; 支持水滴&#xff1a;点赞&#x1f44d; 收藏⭐ 留言&#x1f4ac; &#x1f338; 订阅专栏&#xff1a;大数据核心技术从入门到精通 文章目录一、全文搜索1.1 查询所有&#xff08;match_all&#xff09;1.2 全文检索&…

CS-Stdio Display Builder

Display Builder 1) 操作界面编辑器和Runtime 2&#xff09;在EPICS edd/dm, medm, edm, ...想法上构建 3&#xff09;与CS-Studio BOY兼容性非常好 4&#xff09;大约2015年在CS-Stdio/Eclipse中开始&#xff0c;现在在CS-Studio/Phoebus中 5) 从209年以Web Runtime获取。…

logstash+elasticsearch+Kibana(ELK)日志收集

文章目录一.安装elasticsearch二. 安装kibana三.配置logstash四.springboot整合logstash五.spring整合Elastic Search不要一股脑执行以下语句,请观察修改要修改的地方 注意给logstash,elasticsearch,kibana释放端口,云服务器提供商和系统的端口 一.安装elasticsearch # 安装e…

【Linux】共享内存

1.共享内存的概念共享内存区是最快的IPC形式。一旦这样的内存映射到共享它的进程的地址空间&#xff0c;这些进程间数据传递不再涉及到内核&#xff0c;换句话说是进程不再通过执行进入内核的系统调用来传递彼此的数据。通信的前提是让两个进程看到同一份资源&#xff0c;信息的…