快捷導(dǎo)航

C++ Vector迭代器失效問題的解決方法

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

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

一、迭代器失效

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

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

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

凡是涉及到擴容操作，都有可能引起迭代器失效，因為vector擴容是分配一個新的數(shù)組，然后全部元素移到新的數(shù)組中。

下面我們就以Insert函數(shù)來舉例說明！

示例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;
}

程序崩潰！

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

示例2：

如果我們用返回值來接受新的迭代器，則不會崩潰！

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ā)生了擴容是實現(xiàn)了對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
請按任意鍵繼續(xù). . .

代碼解釋：

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

示例3：

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

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時，可以考慮開一個size()大小的空間，拷貝數(shù)據(jù)，釋放舊空間。縮容方案本質(zhì)是時間換空間。一般設(shè)計都不會考慮縮容，因為實際比較關(guān)注時間效率，不關(guān)注空間效率，因為現(xiàn)在硬件設(shè)備空間都比較大，空間存儲也比較便宜。

示例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; //只要一訪問 系統(tǒng)強制檢查(怎么檢查的不知道！)， 就報錯（Linux沒報錯）
	*pos = 10;
	cout << *pos << endl << endl;
}

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

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

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

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

下面我們舉個實例：

要我們刪除容器中所有偶數(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);//刪除了就不移動
		}
		else
		{
			++it;
		}
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

代碼解釋：毫無疑問上訴代碼會崩潰，因為erase后迭代器it所指向的位置失效，（雖然感覺是可以繼續(xù)使用的，但在vs下就是不可以使用，在Linux下就可以對這個位置進行訪問），所以下面我們用返回值來更新迭代器。

示例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);//刪除了就不移動
		}
		else
		{
			++it;
		}
	}
	for (auto e : v)
	{
		cout << e << " ";
	}
	cout << endl;
}

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

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

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

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

示例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

代碼解釋：同樣地，不是因為擴容而引起的意義失效，這個時候我們訪問了pos指向的位置，編譯器卻不報錯，但此時并不意味著一定對，后續(xù)如果進一步操作，還是會發(fā)生各種各樣的錯誤！

2.3、總結(jié)

總結(jié):

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

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

您可能感興趣的文章: