当前位置 : 主页 > 编程语言 > c语言 >

C++Vector迭代器失效问题的解决方法

来源:互联网 收集:自由互联 发布时间:2023-02-01
目录 一、迭代器失效 二、可能引起的迭代器失效的操作 2.1、野指针引起迭代器失效 2.2、迭代器指向的位置意义改变 2.3、总结 一、迭代器失效 主要作用就是让算法能够不用关心底层数
目录
  • 一、迭代器失效
  • 二、可能引起的迭代器失效的操作
    • 2.1、野指针引起迭代器失效
    • 2.2、迭代器指向的位置意义改变
    • 2.3、总结

一、迭代器失效

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

二、可能引起的迭代器失效的操作

2.1、野指针引起迭代器失效

凡是涉及到扩容操作,都有可能引起迭代器失效,因为vector扩容是分配一个新的数组,然后全部元素移到新的数组中。

下面我们就以Insert函数来举例说明!

示例1:

void test02()
{
	// 在所有的偶数的前面插入2
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	cout << v.size() << ":" << v.capacity() << endl;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.insert(it, 20);
			++it; //这里++是为了解决第二种迭代器失效,防止原地踏步
		}
		++it;
	}
	cout << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

程序崩溃!

代码解释:如果我们没有预先分配空间,那么在insert的时候会发生扩容,根据我们模拟实现vector可知,STL标准库的vector中insert函数是实现了对迭代器的更新,但是形参列表没有使用输出型参数,所以我们只有通过返回值来接收新的迭代器!

示例2:

如果我们用返回值来接受新的迭代器,则不会崩溃!

void test02()
{
	// 在所有的偶数的前面插入2
	vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	cout << v.size() << ":" << v.capacity() << endl;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.insert(it, 20);//stl中的insert如果发生了扩容是实现了对it位置的更新,并用返回值输出了形参的改变
			++it; //这里++是为了解决第二种迭代器失效,防止原地踏步
		}
		++it;
	}
	cout << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

6:6
9:9
1 20 2 3 20 4 5 20 6
请按任意键继续. . .

代码解释:

STL中的insert如果发生了扩容是实现了对it位置的更新,并用返回值输出了形参的改变。

示例3:

如果我们预先预留(reserve)了空间,再插入过程中没发生扩容,那么自然也不会失效了。

void test02()
{
	// 在所有的偶数的前面插入2
	vector<int> v;
	v.reserve(20);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(5);
	v.push_back(6);
	cout << v.size() << ":" << v.capacity() << endl;
	vector<int>::iterator it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			//it = v.insert(it, 20);
			v.insert(it, 20);
			++it; 
		++it;
	}
	cout << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

2.2、迭代器指向的位置意义改变

一般vector删除数据,都不考虑缩容的方案。缩容方案: size() < capacity()/2时,可以考虑开一个size()大小的空间,拷贝数据,释放旧空间。缩容方案本质是时间换空间。一般设计都不会考虑缩容,因为实际比较关注时间效率,不关注空间效率,因为现在硬件设备空间都比较大,空间存储也比较便宜。

示例4:

void test03(){
	vector<int> v;
	cout << v.size() << ":" << v.capacity() << endl;
	v.reserve(10);
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	cout << v.size() << ":" << v.capacity() << endl;
	auto pos = find(v.begin(), v.end(), 2);
	if (pos != v.end())
	{
		v.erase(pos);
	}
	cout << v.size() << ":" << v.capacity() << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
	cout << *pos << endl; //只要一访问 系统强制检查(怎么检查的不知道!), 就报错(Linux没报错)
	*pos = 10;
	cout << *pos << endl << endl;
}

代码解释:可见代码确实是实现了删除,但是程序却崩了,原因就是erase后pos失效了,pos的意义变了,(但是在不同平台下对于访问pos的反应是不一样的,因此我们使用的时候要特别小心,统一以失效的角度去看待)。但如果不访问pos指向的内容就不会崩溃!

erase导致的失效:

  • erase失效都是意义变了。
  • 一般不会有缩容方案,那么erase的失效,一般也不存在野指针的失效。

上一篇:C/C++中实现让控制台暂停的方法
下一篇:没有了
网友评论