【C++/STL】vector(常见接口、模拟实现、迭代器失效)

慈云数据 2024-05-30 技术支持 42 0

 🌈个人主页:秦jh_-CSDN博客
🔥 系列专栏: https://blog.csdn.net/qinjh_/category_12575764.html?spm=1001.2014.3001.5482

9efbcbc3d25747719da38c01b3fa9b4f.gif

目录

 简单使用

常见接口

find 

 insert

 vector模板

模拟实现

尾插

构造

 迭代器失效

使用memcpy拷贝问题

 花括号列表初始化

完整代码


前言

    💬 hello! 各位铁子们大家好哇。

             今日更新了vector的相关内容

    🎉 欢迎大家关注🔍点赞👍收藏⭐️留言📝

 vector是表示可变大小数组的序列容器

 简单使用

38922f8024854c359c48b0c7122893e8.pnga3512176ae1649e6890fd63409b7b88e.png

abaa98010bdf4528a26fd2285c500e42.png

vector接口的使用跟string差不多,功能很多都类似。 

常见接口

153041c951a240e3b756bae497424730.png0690a43622c34c3895ab73c4e3af01da.png

注意end是指向最后一个数据的下一个位置。b814ef2c19be4767a17cf1b614786138.png

c36e3fca1c334d4ea9d9391dc3d5f866.png32ab8c6d71904b5aad7d5b9fb3fca785.png

find 

find的使用需要包  头文件fdbf7ef087dc40fe9fe6eb57012ee573.png

7d67ba94dea94130a6760dba4f667c0e.png

48d9070a24b74e9c96167970c3ebe366.png

注意上面if语句的判断条件,找不到时,返回值是自己给的last,即上面的v.end()。

 insert

a086a69d1c544f43bc8e9ad7cbaae85c.png

e45b8fa595fc42b893fe999d155f69bc.png

insert还可以插入一段迭代区间 

 vector模板

38922f8024854c359c48b0c7122893e8.png

f4fa8126349a47298d6ff64e063b7ece.png

vector 括号里可以是不同的类型,如上面的string,还可以是list,vector等。 如下图:7e031985314c42358dbbd5724f5b18b6.pngf94db551939e4f52b2cc94f8823de209.png

模拟实现

尾插

69143aaf459446e1b187463db5337c34.pnga5085085b4214cb993e66b6f19fc10a8.pngd19586e2eeef4e84927c0fdadb89e395.png

上方是错误的模拟。因为_start已经改变了,_finish-_start就不是原本的空间大小了。正确代码如下:

size_t size()
{
	return _finish - _start;
}
T& operator[](size_t pos)
{
	assert(pos  

构造

16620059a92b490da6e3a44a219ab7b9.png

17d7fab585cb4f4da217ffc81c701998.png

在不写第三个函数的情况下,当我们想插入10个1构造时,会优先跟函数1匹配,因为他是模板, 而函数2的形参类型有size_t ,因此匹配度没模板的好。为了能够插入10个1进行构造,就需要函数3来进行匹配。没有函数3的情况下,(10u,1)和(10,'a')都会跟函数2匹配。

 迭代器失效

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

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

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

dd26f7e657464a2b96f6b03b96b640db.pngced4c486d7ac4ef698f0505e58389e6e.png

插入发生错误的本质是迭代器失效,因为此时pos还指向旧空间,而旧空间已经被释放了。正确代码如下:153aa498faab42d8a3a99fecd57a0ccd.png

	void insert(iterator pos, const T& val)
	{
		assert(pos >= _start);
		assert(pos = pos)
		{
			*(it + 1) = *it;
			--it;
		}
		*pos = val;
		++_finish;
	}

 另一个问题:

519aaf8afcab456a8a7319d026f62149.png

 因为要扩容,此时it就是野指针了,要继续使用就得在外面重新更新。要解决这个问题就得在insert形参里面传引用,但是这会引发别的问题,库里面没有去解决这个问题,所以不要使用。 

af00b43d5bfc4c7a851cb8dbf9ed28b0.png

 上方删除偶数的操作也是导致迭代器失效。erase删除pos位置元素后,pos位置之后的元素会往前搬移,如果pos刚好是最后一个元素,删完之后pos刚好是end的位置,而end位置是 没有元素的,那么pos就失效了。

52f346d7315649b6b13f68869373c95f.png

 库里面的解决方案如上图,erase删除后会返回删除元素的下一个位置,进行更新即可。

eba2c0a621444e37a2c48a6e0c613424.png

上图是修改后的代码。模拟实现的erase也要跟着修改 ,要有返回值,如下图:

76389412e5134658b7b64616a81fa825.png

使用memcpy拷贝问题

a4c6a447cbba4cb197a8f268f6257bad.png

当不需要扩容时,可以正常运行。 

1b13802d1ee74c95b59e25502d9dcfe0.pngdcdf374d59c349aeaaa18ad917b79fa2.png

 如果扩容了,程序就崩了。问题出在memcpy上。

f25603213aa64f57bedf102f664417ba.png

memcpy是按字节一个一个拷贝的。扩容时,开辟了新空间, 然后memcpy就把string拷贝到tmp上。接着delete时,会调用析构函数,此时string就没了,start指向的空间也被销毁了。再让start指向tmp的空间,而tmp空间里的string是浅拷贝,在刚才就没了。即memcpy使vector是深拷贝,但vector的对象string却是浅拷贝。 

 正确代码:

fdda6410b3ac420a938f1e39e46224c0.png

我们用循环进行赋值即可,赋值时每次都是深拷贝。 

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

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

 花括号列表初始化

e319fb4fb8a9410687062b665c9353f9.png

7321d2a5cdfd4ba18f54b0dda96be332.png

库里面的vector支持用花括号初始化,其原理如下图:

c7a69b0ac3304cb7a1a627bdd1219f87.png

即隐式类型转换,传引用时,注意临时对象具有常性,需要用const对象。

自己实现: 

f6b269ae7fbd45c89a1518c820f6f331.png

完整代码

#pragma once
#include
namespace qjh
{
	template
	class vector
	{
	public:
		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()
		{}
		//v2(v1)
		vector(const vector& v)
		{
			reserve(v.capacity());
			for (auto& e : v)
			{
				push_back(e);
			}
		}
		//vector v1 ={1,2,3,4,5};
		vector(initializer_list il)
		{
			reserve(il.size()); 
			for (auto& e : il)
			{
				push_back(e);
			}
		}
		//类模板的成员函数可以是函数模板
		//迭代器区间构造,可以是vector的迭代器,也可以是其他容器
		template 
		vector(InputIterator first, InputIterator last)
		{ 
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		vector(size_t n, const T& val = T())
		{
			reserve(n);
			for (size_t i = 0; i  capacity())
			{
				T* tmp = new T[n];
				size_t old_size = size();
				//memcpy(tmp, _start, size() * sizeof(T));
				for (size_t i = 0; i  size())
			{
				reserve(n);
				while (_finish = _start);
			assert(pos = pos)
			{
				*(it + 1) = *it;
				--it;
			}
			*pos = val;
			++_finish;
		}
		iterator erase(iterator pos)
		{
			assert(pos >= _start);
			assert(pos 
微信扫一扫加客服

微信扫一扫加客服

点击启动AI问答
Draggable Icon