1、前言

**迭代器的主要作用就是讓算法能夠不用關心底層數(shù)據(jù)結構，其底層實際就是一個指針，或者是對指針進行了封裝，比如：string的迭代器就是原生指針char，vector的迭代器就是原生態(tài)指針T 。因此迭代器失效，實際就是迭代器底層對應指針所指向的空間被銷毀了，而使用一塊已經(jīng)被釋放的空間，造成的后果是程序崩潰(即如果繼續(xù)使用已經(jīng)失效的迭代器，程序可能會崩潰)。
對迭代器失效我們了解了，那么現(xiàn)在我們就分析，在vector中哪些操作會導致迭代器失效。

2、情況一：底層空間改變的操作

存在底層空間改變的函數(shù)接口有：resize、reserve、insert、assign、push_back等。

產(chǎn)生的原因：

這幾個接口都存在擴容的問題，擴容的時候存在異地擴容，當異地擴容后，原本的空間被釋放，但是迭代器指的是被釋放空間，這就會導致迭代器的失效問題，會引發(fā)程序崩潰的問題。

解決方法：

一旦存在擴容，擴容后對迭代器更新一次，重新給迭代器賦值即可。

舉例：

我們看一下insert接口。

我們由圖中可以看到，當我們需要在3之前插入數(shù)據(jù)30，但是空間已經(jīng)滿了，因此我們需要進行擴容，擴容是異地開空間，開好空間將舊空間的數(shù)據(jù)拷貝回來，并將舊空間釋放掉，_start指向新的空間頭部，但是it指的是舊空間的位置，這就是迭代器失效。我們記住it相對于_start的相對位置，在新空間開好后，更新it，讓其指向新空間的相對位置。（方式：計算出it到_start的距離len，開好新空間后，更新it為新的_start+len）。

代碼實現(xiàn)：

iterator insert(iterator pos, const T& x)
{
    assert(pos >= _start);
    assert(pos <= _finish);
    if (_finish == _endOfStorage)
    {
        size_t len = pos - _start;//先記下_start到pos位置的距離，因為擴容后迭代器pos就會失效
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;//新的空間需要更新迭代器pos
    }
    iterator end = _finish - 1;
    //挪動數(shù)據(jù)
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

3、情況二：指定位置元素的刪除操作

對于erase接口也會導致迭代器失效問題。那它是怎么導致的呢，我們來分析一下。

產(chǎn)生原因：

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

#include <iostream>
using namespace std;
#include <vector>
int main()
{
    int a[] = { 1, 2, 3, 4 };
    vector<int> v(a, a + sizeof(a) / sizeof(int));
    // 使用find查找3所在位置的iterator
    vector<int>::iterator pos = find(v.begin(), v.end(), 3);
    // 刪除pos位置的數(shù)據(jù)，導致pos迭代器失效。
    v.erase(pos);
    cout << *pos << endl; // 此處會導致非法訪問
    return 0;
}

解決方法：

本質是因為尾刪導致的迭代器失效問題，因此我們在尾刪完后，返回it的下一個位置，我們的模擬實現(xiàn)是數(shù)據(jù)覆蓋（it+1覆蓋it），因此返回的還是it，一刪之后 --_finish，當 it指的位置就是_finish 的時候正好也就停止了，因此也就解決了迭代器失效的問題。

代碼實現(xiàn)：

iterator erase(iterator pos)
{
    assert(pos >= _start);
    assert(pos < _finish);
    iterator it = pos + 1;
    //挪動數(shù)據(jù)
    while (it < _endOfStorage)
    {
        *(it - 1) = *it;
        ++it;
    }
    --_finish;
    return pos;
}

4、g++編譯器對迭代器失效檢測

Linux下，g++編譯器對迭代器失效的檢測并不是非常嚴格，處理也沒有vs2019下極端。
我們來看下面這幾種情況下，代碼在vs2019和g++下不同的表現(xiàn)。

4.1 擴容

int main()
{
    vector<int> v{1,2,3,4,5};
    for(size_t i = 0; i < v.size(); ++i)
    	cout << v[i] << " ";
    cout << endl;
    auto it = v.begin();
    cout << "擴容之前，vector的容量為: " << v.capacity() << endl;
    v.reserve(100);
    cout << "擴容之后，vector的容量為: " << v.capacity() << endl;
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

g++下運行結果：

vs2019下運行結果：

vs2019下程序崩潰了。
結論：當擴容后迭代器就是失效的，g++下雖然能運行，但是結果出錯了，vs下直接程序崩潰。

4.2 erase刪除任意位置（非尾刪）

#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> v{1,2,3,4,5};
    vector<int>::iterator it = find(v.begin(), v.end(), 3);
    v.erase(it);
    cout << *it << endl;
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

g++下運行結果：

vs2019下運行結果：

結論：在非尾刪的刪除中，空間是沒有變的，迭代器指的是還是那塊空間，g++下迭代器沒有失效，刪除后后面的數(shù)據(jù)前移，it位置沒失效，vs下只要是erase，就判斷為迭代器失效了。

4.3 erase尾刪

int main()
{
	vector<int> v{1,2,3,4,5,6};
	auto it = v.begin();
	while (it != v.end())
	{
		if (*it % 2 == 0)
			v.erase(it);
		++it;
	}
	for (auto e : v)
		cout << e << " ";
	cout << endl;
	return 0;
}

g++下運行結果：

vs2019下不用看，直接崩潰。
結論：當在尾刪的時候，刪除之后存在數(shù)據(jù)挪動，一挪動_finish與it是一個位置了，erase本就返回被刪除位置的下一個位置，此時迭代器失效，再++it程序直接崩潰。

5、總結

本篇主要講了擴容、插入、刪除造成的迭代器失效，g++對迭代器失效檢測的不嚴格，而vs對迭代器失效檢測很嚴格，直接崩潰。

1、擴容一般都要更新迭代器，我們不知道哪一次的擴容是異地擴。

2、插入任意位置時，一旦存在擴容就要更新迭代器，本質就是擴容要更新迭代器。

3、刪除任意位置時，g++下非尾刪不考慮迭代器失效問題，尾刪一定要注意迭代器失效問題；vs2019中刪除就認定為迭代器失效，直接崩潰。

以上就是C++ STL_vector 迭代器失效問題的解決方法的詳細內容，更多關于C++ STL_vector 迭代器失效的資料請關注腳本之家其它相關文章！

最新評論