【C++】STL--vector

目录

vector的使用

vector的定义

vector iterator的使用

vector空间增长问题

vector增删查改

vector深度剖析及模拟实现

vector核心接口模拟实现

使用memcpy拷贝问题

迭代器失效问题


vector的使用

vector的定义

 C++中,vector是一个模版,第一个参数是类型T,第二个参数暂且不考虑。

vector<int> v; 

我们可以通过上面这句代码将参数T给成int,那么vector中所包含的元素就是int。 

(重点)1.vector()

无参构造

(重点)2.vector (const vector& x)

拷贝构造

3.vector(size_type n, const value_type& val = value_type())

构造并初始化n个val

4.vector(size_type n, const value_type& val = value_type()

使用迭代器进行初始化构造

vector iterator的使用

(重点)1.begin+end

获取第一个数据位置的iterator/const_iterator,获取最后一个数据的下一个位置的iterator/const_iterator

2.rbegin+rend

获取最后一个数据位置的reverse_iterator,获取第一个数据前一个位置的reverse_iterator

vector空间增长问题

1.size和capacity

size用来获取数据个数,capacity获取容量大小

2.empty

判断是否为空

(重点)3.resize

改变vector的size

(重点)4.reserve

改变vector的capacity

关于空间增长问题,有几个点需要注意:

1.capacity的代码在vs和g++下分别运行会发现,vs下capacity是按1.5倍增长的,g++是按2倍增长的。这个问题经常会考察,不要固化的认为,vector增容都是2倍,具体增长多少是根据具体的需求定义的。vs是PJ版本STL,g++是SGI版本STL。

2.reserve只负责开辟空间,如果确定知道需要用多少空间,reserve可以缓解vector增容的代价缺陷问题。

3.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';
		}
	}
}

在vs2019下的运行结果:

结论:vs下使用的STL基本是按照1.5倍方式扩容!

在g++下的运行结果:

结论:linux下使用的STL基本是按照2倍方式扩容!

//如果已经确定vector中要存储元素大概个数,可以提前将空间设置足够
//就可以避免边插入边扩容导致效率低下的问题了
void TestVectorExpandOP()
{
    vector<int>v;
    size_tsz=v.capacity();
    v.reserve(100);//提前将容量设置好,可以避免一遍插入一遍扩容
    cout<<"making bar grow:\n";
    for(inti=0;i<100;++i)
    {
        v.push_back(i);
        if(sz!=v.capacity())
        {
            sz=v.capacity();
            cout<<"capacity changed: "<<sz<<'\n';
        }
    }
}

vector增删查改

(重点)1.push_back

尾插

(重点)2.pop_back

尾删

 注意,vector未提供头插头删,因为那样效率很低!  

3.find

查找。(注意这个是算法模块实现,不是vector的成员接口)

4.insert

在position之前插入val

5.erase

删除position位置的数据

6.swap

交换两个vector的数据空间

7.operator[ ]

像数组一样访问。越界时会发生assert报错!

更进一步

除了将vector中的参数T初始化为int、double等内置类型外,还可以将其初始化为string、vector<int>等。

void test_vector()
{
	vector<string> v;
	string s1("苹果");
	v.push_back(s1);
	v.push_back(string("香蕉"));
	v.push_back("草莓");
}
vector<vector<int>> v;

下面画出这个的示意图,以便理解:

对于vector<vector<int>> v这种,我们可以把它看成一个二维数组,可以通过v[i][j]的形式去访问其成员,那么我们难免会联想到二维数组的访问也是v[i][j]这种形式,那它们有区别吗?其实,它们的区别很大

对于静态的二维数组,v[i][j]其底层是一个一维数组,数组名v表示第一行的地址,v+i表示第i行地址(从0行开始),*(v+i)表示第i行第一个元素的地址,*(*(v+i)+j)表示第i行第j个元素,即v[i][j]。

对于vector<vector<int>> v,v[i][j]可以看成两次函数调用,第一次调用相当于vv.operator[](i),其返回值为vector<int>对象,第二次调用相当于vv.operator[](i).operator[](j)。

vector深度剖析及模拟实现

如果按照之前string的习惯,start就是a,finish就是a+size,end_of_storage就是a+capacity。

vector核心接口模拟实现

#include <assert.h>

namespace ghs
{
	template<class T>
	class vector
	{
	public:
		typedef T* iterator;
		typedef const T* const_iterator;
		const_iterator begin()const
		{
			return _start;
		}
		const_iterator end()const
		{
			return _finish;
		}
		iterator begin()
		{
			return _start; 
		}
		iterator end()
		{
			return _finish;
		}
		vector()
		{}
		//v2(v1)
		vector(const vector<T>& v)
		{
			reserve(v.capacity());
			//引用,防止深拷贝
			for (auto& ch : v)
			{
				push_back(ch);
			}
		}
		//vector<int> v = { 1,2,3,4,5,6,7,8,9 };
		vector(initializer_list<T> il)
		{
			reserve(il.size());
			for (auto e : il)
			{
				push_back(e);
			}
		}
		//类模板的成员函数可以是函数模版
		template <class InputIterator>
		vector(InputIterator first, InputIterator last)
		{
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//const T& val = T() 构造匿名对象
		vector(size_t n, const T& val = T())
		{
			reserve(n);
			for (size_t i = 0; i < n; i++)
			{
				push_back(val);
			}
		}
		//和上面的构成重载
		vector(int n, const T& val = T())
		{
			reserve(n);
			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		void swap(vector<T>& v)
		{
			std::swap(_start, v._start);
			std::swap(_finish, v._finish);
			std::swap(_endofstorage, v._endofstorage);
		}
		//v1 = v3,v是v3的拷贝
		vector<T>& operator=(vector<T> v)
		{
			swap(v);
			return *this;
		}
		size_t capacity()const
		{
			return _endofstorage - _start;
		}
		size_t size()const
		{
			return _finish - _start;
		}
		~vector()
		{
			delete[] _start;
			_start = _finish = _endofstorage = nullptr;
		}
		T& operator[](size_t pos)
		{
			assert(pos < size());
			return _start[pos];
		}
		const T& operator[](size_t pos)const
		{
			assert(pos < size());
			return _start[pos];
		}

		void reserve(size_t n)
		{
			if (n > capacity())
			{
				T* tmp  = new T[n];
				size_t old_size = size();
				//memcpy(tmp, _start, old_size * sizeof(T));
				for (size_t i = 0; i < old_size; i++)
				{
					tmp[i] = _start[i];//这样如果T是string,走的深拷贝
				}
				delete[] _start;
				_start = tmp;
				_finish = _start + old_size;
				_endofstorage = _start + n;
			}
		}
		void resize(size_t n, const T& val = T())
		{
			if (n > size())
			{
				reserve(n);
				//插入
				while (_finish < _start + n)
				{
					*_finish = val;
					_finish++;
				}
			}
			else
			{
				//删除
				_finish = _start + n;
			}
		}
		void push_back(const T& val)
		{
			if (_finish == _endofstorage)
			{
				reserve(capacity() == 0 ? 4 : 2 * capacity());
			}

			*_finish = val;
			_finish++;
		}

		void pop_back()
		{
			/*assert(!empty());
			--_finish;*/
			erase(--end());
		}
		bool empty()
		{
			return _start == _finish;
		}
		void insert(iterator pos, const T& val)
		{
			assert(pos >= _start);
			assert(pos <= _finish);
			if (_finish == _endofstorage)
			{
				size_t len = pos - _start;
				reserve(capacity() == 0 ? 4 : 2 * capacity());
				//如果扩容了,要更新pos
				pos = _start + len;
			}
			iterator end = _finish - 1;
			while (end >= pos)
			{
				*(end + 1) = *end;
				end--;
			}
			*pos = val;
			_finish++;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos <= _finish);

			iterator it = pos + 1;
			while (it < _finish)
			{
				*(it - 1) = *it;
				++it;
			}
			--_finish;
			//返回pos,用于迭代器更新
			return pos;
		}
		  
	private:
		iterator _start = nullptr;
		iterator _finish = nullptr;
		iterator _endofstorage = nullptr;
	};
	template<class T>
	void print_vector(const vector<T>& v) 
	{
		for (size_t i = 0; i < v.size(); i++)
		{
			cout << v[i] << " ";
		}
		cout << endl;

		//加一个typename,告诉编译器后边那个是一个类型,否则报错
		//typename vector<T>::const_iterator it = v.begin();
		/*auto it = v.begin();
		while (it != v.end())
		{
			cout << *it << " ";
			++it;
		}
		cout << endl;
		for (auto c : v)
		{
			cout << c << " ";
		}
		cout << endl;*/
	}
}

使用memcpy拷贝问题

假设模拟实现的vector中的reserve接口中,使用memcpy进行的拷贝,以下代码会发生什么问题?

void testvector()
{
	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);
	v1.push_back(7);
	v1.push_back(8);
}

1. memcpy是内存的二进制格式拷贝,将一段内存空间中内容原封不动的拷贝到另外一段内存空间中。

2. 如果拷贝的是自定义类型的元素,memcpy既高效又不会出错,但如果拷贝的是自定义类型元素,并且 自定义类型元素中涉及到资源管理时,就会出错,因为memcpy的拷贝实际是浅拷贝。

结论:如果对象中涉及到资源管理时,千万不能使用memcpy进行对象之间的拷贝,因为memcpy是浅拷贝,否则可能会引起内存泄漏甚至程序崩溃

在上面我们自己模拟实现的扩容接口中:

void reserve(size_t n)
{
    if (n > capacity())
	{
		T* tmp  = new T[n];
		size_t old_size = size();
		//memcpy(tmp, _start, old_size * sizeof(T));
		for (size_t i = 0; i < old_size; i++)
		{
			tmp[i] = _start[i];//这样如果T是string,走的深拷贝
		}
			delete[] _start;
			_start = tmp;
			_finish = _start + old_size;
			_endofstorage = _start + n;
	}
}

我们使用for循环赋值的方式进行拷贝,这样即使T是自定义类型,比如是string,那么会去调string的赋值,string的赋值是深拷贝。

迭代器失效问题

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

对于vector可能会导致其迭代器失效的操作有:

1. 会引起其底层空间改变的操作,都有可能是迭代器失效,比如:resize、reserve、insert、assign、push_back等。

2. 指定位置元素的删除操作--erase

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

下面实现了删除vector中偶数的功能:

void testvector()
{
	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);
	v1.push_back(7);
	v1.push_back(8);
	print_vector(v1);

	//删除偶数
	vector<int>::iterator it = v1.begin();
	while (it != v1.end())
	{
		if (*it % 2 == 0)
		{
			it = v1.erase(it);
		}
		else
		{
			++it;
		}
	}
	print_vector(v1);
}

其中,我们每次使用了it = v1.erase(it);更新迭代器。

迭代器失效解决办法:在使用前,对迭代器重新赋值即可。

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

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

相关文章

PHP数据类型

华子目录 数据类型PHP的八种数据类型基本数据类型&#xff0c;4类复合数据类型&#xff0c;2类特殊数据类型&#xff0c;2类 类型转换在PHP中有两种类型转换方式其他类型转bool类型其他类型转数值类型实例 类型判断获取和设定变量类型获取gettype(变量名)设置settype(变量名,类…

蓝桥杯单片机第十四届省赛模拟考试一

一、基本要求 使用大赛组委会提供的国信长天单片机竞赛实训平台&#xff0c;完成本试题的程序设计与调试。程序编写、调试完成后&#xff0c;选手需通过考试系统提交以准考证号命名的hex文件。不符合以上文件提交要求的作品将被评为零分或者被酌情扣分。 硬件设置&#xff1a; …

数组-二维数组

本笔记为47 数组-二维数组定义方式_哔哩哔哩_bilibili的学习笔记 二维数组 定义方式 注&#xff1a; 常用第二种方式定义&#xff0c;原因&#xff1a;第二种方式更清晰列数可以省行数不可省 &#xff0c;详见上述第四种定义方式 示例&#xff1a; 二维数组 数组名 作用&am…

CSS层叠样式表学习(引入方式)

&#xff08;大家好&#xff0c;今天我们将继续来学习CSS引入方式的相关知识&#xff0c;大家可以在评论区进行互动答疑哦~加油&#xff01;&#x1f495;&#xff09; 五、CSS的三种样式表 5.1 CSS的三种样式表 按照CSS样式书写的位置(或者引入方式)&#xff0c;CSS样式表可…

笔记-Building Apps with the ABAP RESTful Application Programming Model-Week3

Week3 Unit 1: The Enhanced Business Scenario 本节介绍了将要练习的demo的业务场景,在前两周成果的基础上,也就是只读列表,也可以说是报表APP基础上启用了事务能力,也就是CURD以及自定义业务功能的能力,从创建基本的behavior definition,然后behavior definition proj…

基于GD32的简易数字示波器(2)- 原理图设计

这期记录的是项目实战&#xff0c;做一个简易的数字示波器。 教程来源于嘉立创&#xff0c;202&#xff1a;简易数字示波器项目文档 语雀 下图为示波器的指标 具有选择交流耦合还是直流耦合功能、输入信号不衰减或衰减50倍 输入频率理论最大800KHz输入幅值&#xff08;不衰…

2024HW-->Wireshark攻击流量分析

在HW中&#xff0c;最离不开的&#xff0c;肯定是看监控了&#xff0c;那么就要去了解一些wireshark的基础用法以及攻击的流量&#xff01;&#xff01;&#xff01;&#xff01; 1.Wireshark的基本用法 比如人家面试官给你一段流量包&#xff0c;你要会用 1.分组详情 对于我…

9_springboot_shiro_jwt_多端认证鉴权_整合jwt

1. Shiro框架回顾 到目前为之&#xff0c;Shiro框架本身的知识点已经介绍完了。web环境下&#xff0c;整个框架从使用的角度我们需要关注的几个点&#xff1a; 要使用Shiro框架&#xff0c;就要创建核心部件securityManager 对象。 SpringBoot项目中&#xff0c;引入shiro-spr…

蓝凌OA单点登录实现方案:以统一身份管理提升效率与安全新举措

蓝凌OA的优势与挑战 在数字化浪潮的推动下&#xff0c;企业对于高效、安全的身份管理需求愈发迫切。蓝凌OA系统&#xff0c;以其出色的流程管理和协同办公能力&#xff0c;已经成为众多企业实现数字化转型的重要工具。然而&#xff0c;随着企业信息化建设的不断深入&#xff0…

什么时候外部依赖接口慢拖死应用?

A应用调用B应用&#xff0c;当B应用的接口响应耗时平均都在3000ms的时&#xff0c;如果当前A调用B的请求数达300/s 那么在3s内A应用在途的请求数 300 * 3 900 &#xff0c;按照servlet原理一个http的请求需要一个线程提供服务&#xff0c;即需要900个线程提供服务&#xff0c…

CSS面试题常用知识总结day03

大家好我是没钱的君子下流坯&#xff0c;用自己的话解释自己的知识 前端行业下坡路&#xff0c;甚至可说前端已死&#xff0c;我还想在前段行业在干下去&#xff0c;所以从新开始储备自己的知识。 从CSS——>Javascript——>VUE2——>Vuex、VueRouter、webpack——>…

聚能共创下一代智能终端操作系统 软通动力荣膺“OpenHarmony优秀贡献单位”

近日&#xff0c;由开放原子开源基金会指导&#xff0c;以“开源共享未来”为主题的OpenHarmony社区年会在北京成功举办。本次活动汇集OpenHarmony项目群共建单位及生态伙伴等多方力量&#xff0c;旨在对2023年度OpenHarmony年度开源事业全面总结的同时&#xff0c;吸引更多伙伴…

【Java EE】SpringBoot的创建与简单使用

文章目录 &#x1f340;环境准备&#x1f333;Maven&#x1f332;SpringBoot是什么&#x1f384;Spring Boot 项目创建&#x1f338;使用Idea创建&#x1f338;创建SpringBoot项⽬&#x1f338;SpringBoot项目的运行 ⭕总结 &#x1f340;环境准备 如果你的IDEA是专业版&#…

STM32F103/F407/H743不同GPIO速度配置(HAL库)对应的最高速度

0 前言 如果我们只是使用MCU控制LED的亮灭&#xff0c;完全可以不关心GPIO的速度配置。但如果我们使用到了SPI、MII、RMII、FSMC等这些高速总线就必须要清楚每种GPIO速度配置对应的最高速度&#xff0c;避免因为GPIO速度配置过低导致总线速度提不上去。 既然如此&#xff0c;那…

Linux网络基础 (三) —— Socket

文章目录 Socket 编程基本概念Socket背景Socket 为了解决什么问题 socketsockaddr结构sockaddrsockaddr_insockaddr 和 sockaddr_in 的关系sockaddr_un 示例代码 &#x1f396; 博主的CSDN主页&#xff1a;Ryan.Alaskan Malamute &#x1f4dc; 博主的代码仓库主页 [ Gitee ]&…

OpenHarmony实战:Combo解决方案之ASR芯片移植案例

本方案基于 OpenHarmony LiteOS-M 内核&#xff0c;使用 ASR582X 芯片的 DEV.WIFI.A 开发板进行开发移植。作为典型的 IOT Combo&#xff08;Wi-FiBLE&#xff09;解决方案&#xff0c;本文章介绍 ASR582X 的适配过程。 编译移植 目录规划 本方案的目录结构使用 Board 和 So…

C和C++内存管理

目录&#xff1a; 一&#xff1a;C和C内存分布 二&#xff1a;C动态内存管理方式 三&#xff1a;C动态内存管理方式 四&#xff1a;operator new与operator delete函数 五&#xff1a;new和delete的实现原理 六&#xff1a;定位new表达式(placement-new) 七&#xff1…

如何利用Flutter将应用成功上架至iOS平台:详细指南

引言 &#x1f680; Flutter作为一种跨平台的移动应用程序开发框架&#xff0c;为开发者提供了便利&#xff0c;使他们能够通过单一的代码库构建出高性能、高保真度的应用程序&#xff0c;同时支持Android和iOS两个平台。然而&#xff0c;完成Flutter应用程序的开发只是第一步…

如何卸载干净 IDEA(图文讲解)

更新时间 2022-12-20 11:一则或许对你有用的小广告 星球 内第一个项目&#xff1a;全栈前后端分离博客项目&#xff0c;演示地址&#xff1a;Weblog 前后端分离博客, 1.0 版本已经更新完毕&#xff0c;正在更新 2.0 版本。采用技术栈 Spring Boot Mybatis Plus Vue 3.x Vit…

【Consul】基于Golang实现Consul服务的注册、注销、修改、监控注册的服务变化、实时同步服务信息机制

【Consul】基于Go实现Consul服务的注册、注销、修改、监控注册的服务变化、实时同步服务信息机制 大家好 我是寸铁&#x1f44a; 总结了一篇【Consul】基于Go实现Consul服务的注册、注销、修改、监控注册的服务变化、实时同步服务信息机制✨ 这应该是目前全网最全的使用golang手…