快捷導(dǎo)航

C++ Vector迭代器失效問(wèn)題的解決方法

更新時(shí)間：2022年08月03日 15:28:01 作者：Rookiep

最近我學(xué)習(xí)了C++中的迭代器失效問(wèn)題，迭代器失效問(wèn)題是非常非常重要的，所以特意整理出來(lái)一篇文章供我們一起復(fù)習(xí)和學(xué)習(xí)

一、迭代器失效

主要作用就是讓算法能夠不用關(guān)心底層數(shù)據(jù)結(jié)構(gòu)，其底層實(shí)際就是一個(gè)指針，或者是對(duì)指針進(jìn)行了封裝。比如：vector的迭代器就是原生態(tài)指針T*。因此迭代器失效，實(shí)際就是迭代器底層對(duì)應(yīng)指針?biāo)赶虻目臻g被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰（即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會(huì)崩潰）。

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

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

凡是涉及到擴(kuò)容操作，都有可能引起迭代器失效，因?yàn)関ector擴(kuò)容是分配一個(gè)新的數(shù)組，然后全部元素移到新的數(shù)組中。

下面我們就以Insert函數(shù)來(lái)舉例說(shuō)明！

示例1：

void test02()
{
	// 在所有的偶數(shù)的前面插入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;
}

程序崩潰！

代碼解釋：如果我們沒(méi)有預(yù)先分配空間，那么在insert的時(shí)候會(huì)發(fā)生擴(kuò)容，根據(jù)我們模擬實(shí)現(xiàn)vector可知，STL標(biāo)準(zhǔn)庫(kù)的vector中insert函數(shù)是實(shí)現(xiàn)了對(duì)迭代器的更新，但是形參列表沒(méi)有使用輸出型參數(shù)，所以我們只有通過(guò)返回值來(lái)接收新的迭代器！

示例2：

如果我們用返回值來(lái)接受新的迭代器，則不會(huì)崩潰！

void test02()
{
	// 在所有的偶數(shù)的前面插入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如果發(fā)生了擴(kuò)容是實(shí)現(xiàn)了對(duì)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
請(qǐng)按任意鍵繼續(xù). . .

代碼解釋：

STL中的insert如果發(fā)生了擴(kuò)容是實(shí)現(xiàn)了對(duì)it位置的更新,并用返回值輸出了形參的改變。

示例3：

如果我們預(yù)先預(yù)留（reserve）了空間，再插入過(guò)程中沒(méi)發(fā)生擴(kuò)容，那么自然也不會(huì)失效了。

void test02()
{
	// 在所有的偶數(shù)的前面插入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刪除數(shù)據(jù)，都不考慮縮容的方案?？s容方案: size() < capacity()/2時(shí)，可以考慮開(kāi)一個(gè)size()大小的空間，拷貝數(shù)據(jù)，釋放舊空間?？s容方案本質(zhì)是時(shí)間換空間。一般設(shè)計(jì)都不會(huì)考慮縮容，因?yàn)閷?shí)際比較關(guān)注時(shí)間效率，不關(guān)注空間效率，因?yàn)楝F(xiàn)在硬件設(shè)備空間都比較大，空間存儲(chǔ)也比較便宜。

示例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; //只要一訪問(wèn) 系統(tǒng)強(qiáng)制檢查(怎么檢查的不知道！)， 就報(bào)錯(cuò)（Linux沒(méi)報(bào)錯(cuò)）
	*pos = 10;
	cout << *pos << endl << endl;
}

代碼解釋：可見(jiàn)代碼確實(shí)是實(shí)現(xiàn)了刪除，但是程序卻崩了，原因就是erase后pos失效了，pos的意義變了，（但是在不同平臺(tái)下對(duì)于訪問(wèn)pos的反應(yīng)是不一樣的，因此我們使用的時(shí)候要特別小心，統(tǒng)一以失效的角度去看待）。但如果不訪問(wèn)pos指向的內(nèi)容就不會(huì)崩潰！

erase導(dǎo)致的失效：

erase失效都是意義變了。
一般不會(huì)有縮容方案，那么erase的失效，一般也不存在野指針的失效。

??????????????????????????

下面我們舉個(gè)實(shí)例：

要我們刪除容器中所有偶數(shù)：

示例5：

void test05()
{
	std::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			v.erase(it);//刪除了就不移動(dòng)
		}
		else
		{
			++it;
		}
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

代碼解釋：毫無(wú)疑問(wèn)上訴代碼會(huì)崩潰，因?yàn)閑rase后迭代器it所指向的位置失效，（雖然感覺(jué)是可以繼續(xù)使用的，但在vs下就是不可以使用，在Linux下就可以對(duì)這個(gè)位置進(jìn)行訪問(wèn)），所以下面我們用返回值來(lái)更新迭代器。

示例6：

void test05()
{
	std::vector<int> v;
	v.push_back(1);
	v.push_back(2);
	v.push_back(2);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);
	v.push_back(4);
	v.push_back(4);
	v.push_back(5);
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
		{
			it = v.erase(it);//刪除了就不移動(dòng)
		}
		else
		{
			++it;
		}
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

1 3 5
請(qǐng)按任意鍵繼續(xù). . .

代碼解釋：可見(jiàn)成功的刪除了其中的偶數(shù)！

其中緣由：erase刪除pos位置元素后，pos位置之后的元素會(huì)往前移動(dòng)，沒(méi)有導(dǎo)致底層空間的改變，理論上講迭代器不會(huì)失效，但是如果pos位置剛好是最后一個(gè)元素，刪完之后pos剛好是end的位置，而end的位置是沒(méi)有有效元素的，那么pos就失效了。因此刪除vector中任意位置元素時(shí)，vs均認(rèn)為該位置上迭代器失效了！

除erase導(dǎo)致意義失效外，insert也可能導(dǎo)致意義失效，但是編譯器卻檢查不出來(lái)?。?！

示例7：

void test01(){
	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.insert(pos, 20);
	}
	cout << v.size() << ":" << v.capacity() << endl;
	cout << *pos << endl;
	*pos = 10;
	cout << *pos << endl << endl;
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

0:0
4:10
5:10
20
10

1 10 2 3 4

代碼解釋：同樣地，不是因?yàn)閿U(kuò)容而引起的意義失效，這個(gè)時(shí)候我們?cè)L問(wèn)了pos指向的位置，編譯器卻不報(bào)錯(cuò)，但此時(shí)并不意味著一定對(duì)，后續(xù)如果進(jìn)一步操作，還是會(huì)發(fā)生各種各樣的錯(cuò)誤！

2.3、總結(jié)

總結(jié):

對(duì)于insert和erase造成迭代器失效問(wèn)題，linux g++平臺(tái)檢查很佛系，基本依靠操作系統(tǒng)自身野指針越界檢查機(jī)制，windows下vs系列檢查更嚴(yán)格，使用一些強(qiáng)制檢查機(jī)制，意義變了也可能會(huì)檢查出來(lái)。
雖然g+＋對(duì)于erase迭代器失效檢查時(shí)非常佛系的，但是套在實(shí)際場(chǎng)景中，迭代器意義變了，也會(huì)出現(xiàn)各種問(wèn)題，所以我們要有正確處理迭代器失效的方式,比如用函數(shù)返回值來(lái)更新迭代器。
windows下vs系列對(duì)意義失效的檢查很雙標(biāo)，由insert函數(shù)引起的意義失效檢查不出來(lái)，而且可以訪問(wèn)pos位置，但是由erase函數(shù)引起的意義失效卻檢查很嚴(yán)格，絲毫不準(zhǔn)訪問(wèn)pos位置。（Linux卻可以）

到此這篇關(guān)于C++ Vector迭代器失效問(wèn)題的解決方法的文章就介紹到這了,更多相關(guān)C++ Vector迭代器失效內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: