你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

【C++初阶】vector(中)

2021/11/21 0:52:28

目录

vector模拟实现

reserve 

resize 

迭代器失效

insert

erase


vector模拟实现

vector模拟实现:Gitee

reserve 

//开空间
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				//动态申请n个T类型的空间
				T*tmp = new T[n];
				//从_start位置开始向后复制sizeof(T)*size()字节的数据到tmp的内存位置
				memcpy(tmp, _start, sizeof(T)*size());
				_start = tmp;
				_finish = _start + size();
				_endofstorage = _start + n;
			}
		}

运行上面的代码,会发现挂了——why?

size()算原来旧空间的数据,旧空间的话——_finish和_start都是0,零减零应该还是0

 调试显示_finish是0,而_start是已经指向新空间了,所以相减为负了

改造:把size()提前存好

//开空间
		void reserve(size_t n)
		{
			if (n > capacity())
			{
				size_t sz = size();
				//动态申请n个T类型的空间
				T*tmp = new T[n];
				//从_start位置开始向后复制sizeof(T)*size()字节的数据到tmp的内存位置
				memcpy(tmp, _start, sizeof(T)*size());
				_start = tmp;
				_finish = _start + sz;
				_endofstorage = _start + n;
			}
		}

resize 

//开空间+初始化
		void resize(size_t n, const T& val = T())
		{
			if (n <= size())
			{
				_finish = _start + n;
			}
			else//n>size()
			{
				//空间容量不够
				if (n > capacity())
				{
					reserve(n);
				}
				//size()<n<capacity()
				while (_finish < _start + n)//指针
				{
					*_finish = val;
					_finish++;
				}
			}
		}

迭代器失效

insert

namespace std
{
	void test_vector1()
	{
		vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.insert(pos, 20);//2的前面插入20
		}
		//在insert以后pos就失效了
		cout << *pos << endl;//访问
		*pos = 100;//修改
	}
}

调试出现报错:

在insert以后pos就失效了——增容导致的(扩容之后pos还指向旧空间) 

反观下面这段代码,先增容后,没有报错:

namespace std
{
	void test_vector1()
	{
		std::vector<int>v;

		v.reserve(8);//先增容

		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		std::vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.insert(pos, 20);//2的前面插入20
		}
		cout << *pos << endl;//访问
		*pos = 100;//修改
		pos++;
	}
}

在insert过程空间足够,没有增容,pos还是指向原来的位置

访问不会报错,那么我们依旧认为pos失效了

这里的失效指的是pos的意义变了,pos不再指向原来的值!

总结insert的失效2中情况:

第一种:由于insert扩容,导致pos失效,pos指向的空间释放,pos本质上是一个野指针

第二种:insert插入数据,没有扩容,我们也认为pos失效了,因为pos的意义变了,不再指向原来的数据

erase

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		std::vector<int>::iterator pos = find(v.begin(), v.end(), 2);
		if (pos != v.end())
		{
			v.erase(pos);
		}
		cout << *pos << endl;
		*pos = 100;
	}
}

调试出现报错: 不能解引用!

erase导致pos失效了,pos没有野指针,只是意义变了,但是vs版本下进行了强制检查,都不能访问

下面这段代码同样会报错:

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//要求删除v中所有偶数
		std::vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				v.erase(it);
			}
			it++;
		}
	}
}

 正确的写法:erase返回删除数据的下一个数据的位置

namespace std
{
	void test_vector2()
	{
		std::vector<int>v;
		v.push_back(1);
		v.push_back(2);
		v.push_back(3);
		v.push_back(4);
		//要求删除v中所有偶数
		std::vector<int>::iterator it = v.begin();
		while (it != v.end())
		{
			if (*it % 2 == 0)
			{
				//erase返回删除数据的下一个数据的位置
				it = v.erase(it);
			}
			else
			{
				it++;
			}
		}
		for (auto e : v)
		{
			cout << e << " ";
		}
		cout << endl;
	}
}

总结:insert和erase以后的迭代器都失效了,一定不要直接去访问或解引用insert或erase后的迭代器