C++迭代器失效問題及解決

2023-02-12 06:00:28

什麼是迭代器

迭代器不是指標，是類別範本，表現的像指標。他只是模擬了指標的一些功能，通過過載了指標的一些操作符，->,*,++ --等封裝了指標，是一個“可遍歷STL（ Standard Template Library）容器內全部或部分元素”的物件，本質是封裝了原生指標，他可以根據不同型別的資料結構來實現不同的++，–，*等操作；

迭代器只能指向容器,而指標還可以指向函數，

迭代器返回的是物件參照而不是物件的值，所以cout只能輸出迭代器使用*取值後的值而不能直接輸出其自身。

迭代器失效

迭代器失效就是迭代器底層對應指標所指向的空間倍銷燬了，導致使用了一塊已經被釋放了的空間。

容器操作可能使迭代器失效，一個失效的迭代器將不再表示任何元素。使用失效的迭代器是一個嚴重的程式設計錯誤，很可能產生與使用未初始化化指標一樣的問題。

順序容器迭代器失效

新增操作

容器是vector或者string的情況下，在向容器新增元素後，如果容器擴容，即容器的儲存空間重新分配，則指向容器的迭代器失效。

以vector為例，當我們插入一個元素時它的預分配空間不夠時，它會重新申請一段新空間，將原空間上的元素複製到新的空間上去，以滿足vector元素要求連續儲存的目的，而原空間會被系統復原或徵做他用，於是指向原空間的迭代器就成了類似於“空懸指標”一樣的東西，指向了一片非法區域，從而使得指向原空間的迭代器失效。

int main()
{
	vector<int>v1;
	vector<int>::iterator it1 = v1.begin();
	for (int i = 0;i < 10;i++) {
		v1.push_back(i);
		cout << "Size:" << v1.size() << "  Capacity:" << v1.capacity() << "  address:" << &v1[0] << endl;
	}
	return 0;
}

容器是vector或者string的情況下，在向容器新增元素後，如果容器未擴容，則指向插入位置之前的元素的迭代器有效，但指向插入位置之後元素的迭代器將會失效，這是因為插入位置後的元素次序發生變化使得原本指向某元素的迭代器不再指向希望指向的元素。

對於push_back()操作，end操作返回的迭代器肯定失效

int main()
{
	vector<int>v1 = { 0,1,2,3 };
	v1.reserve(10);//分配至少能容納10個元素的記憶體空間
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v1.begin() + 1;
	vector<int>::iterator it3 = v1.begin() + 2;
	v1.insert(v1.begin() + 2, 4);
	while (it1 <= it2) {	//輸出0 1
		cout << *it1 << endl;
		it1++;
	}
	cout << *it3 << endl; //此時該迭代器已失效，指向非法的區域
	return 0;
}

容器是deque的情況下，插入到任何位置都會導致迭代器。

插入前迭代器處於正常狀態

插入後所有迭代器失效

容器是list和forward_list的情況下，插入到任何位置，指向容器的迭代器仍然有效，

刪除操作

刪除操作會導致元素次序傳送改變而導致迭代器失效

容器是vector或者string的情況下，在刪除容器元素後，指向被刪元素之前元素的迭代器有效，被刪元素之後的迭代器失效

注意：當我們刪除元素時，尾後迭代器總是會失效

容器是deque的情況下，如果刪除的是首尾元素，則只有首尾迭代器失效，如果刪除的是其他元素，則所有迭代器失效。

容器是list和forward_list的情況下，刪除任何元素，僅僅會使被刪除元素的迭代器失效，這是因為 list 之類的容器，使用了連結串列來實現，插入、刪除一個結點不會對其他結點造成影響。

關聯容器迭代器失效

對於關聯容器map、multimap、set、multiset，底層是使用紅黑樹實現的，所以刪除某個元素，僅僅會刪除元素的迭代器失效。

插入、刪除一個結點不會對其他結點造成影響。

swap()操作迭代器為什麼不失效

因為swap操作不會對容器的任何元素進行拷貝、刪除或插入操作，也意味著元素不會被移動，這也就是迭代器為什麼不失效的原因，因為指向容器的迭代器swap操作之後，仍指向swap操作之前所指向的那些元素，只不過這些元素已經屬於不同的容器了

注意：對於string容器呼叫swap操作會導致迭代器失效，而swap兩個array會真正交換它門的元素

int main()
{
	vector<int>v1 = { 0,1,2,3 };
	vector<int>v2 = { 4,5,6,7};
	vector<int>::iterator it1 = v1.begin();
	vector<int>::iterator it2 = v2.begin();
	vector<int>::iterator tmp1 = v1.begin();
	vector<int>::iterator tmp2 = v2.begin();
	cout << "v1: ";
	for (const auto&n : v1) {
		cout << n << " ";
	}
	cout << endl;
	cout << "v2: ";
	for (const auto&n : v2) {
		cout << n << " ";
	}
	cout << endl;
	while (it1 != v1.end()) {
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
	while (it2 != v2.end()) {
		cout << *it2 << " ";
		it2++;
	}
	cout << endl;
	swap(v1, v2); //交換容器v1,v2;
	it1 = tmp1;
	it2 = tmp2;
	cout << "v1: ";
	for (const auto&n : v1) {
		cout << n << " ";
	}
	cout << endl;
	cout << "v2: ";
	for (const auto&n : v2) {
		cout << n << " ";
	}
	cout << endl;
	while (it1 != v2.end()) {
		cout << *it1 << " ";
		it1++;
	}
	cout << endl;
	while (it2 != v1.end()) {
		cout << *it2 << " ";
		it2++;
	}

	cout << endl;
	return 0;
}

輸出：