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

2022-08-03 18:04:10

一、迭代器失效

主要作用就是讓演演算法能夠不用關心底層資料結構，其底層實際就是一個指標，或者是對指標進行了封裝。比如：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++ Vector迭代器失效問題的解決方法

目錄

一、迭代器失效

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

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

2.2、迭代器指向的位置意義改變

熱門文章