1、前言

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

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

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

產(chǎn)生的原因：

這幾個(gè)接口都存在擴(kuò)容的問題，擴(kuò)容的時(shí)候存在異地?cái)U(kuò)容，當(dāng)異地?cái)U(kuò)容后，原本的空間被釋放，但是迭代器指的是被釋放空間，這就會(huì)導(dǎo)致迭代器的失效問題，會(huì)引發(fā)程序崩潰的問題。

解決方法：

一旦存在擴(kuò)容，擴(kuò)容后對(duì)迭代器更新一次，重新給迭代器賦值即可。

舉例：

我們看一下insert接口。

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

代碼實(shí)現(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位置的距離，因?yàn)閿U(kuò)容后迭代器pos就會(huì)失效
        reserve(capacity() == 0 ? 4 : 2 * capacity());
        pos = _start + len;//新的空間需要更新迭代器pos
    }
    iterator end = _finish - 1;
    //挪動(dòng)數(shù)據(jù)
    while (end >= pos)
    {
        *(end + 1) = *end;
        --end;
    }
    *pos = x;
    ++_finish;
    return pos;
}

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

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

產(chǎn)生原因：

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

#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ù)，導(dǎo)致pos迭代器失效。
    v.erase(pos);
    cout << *pos << endl; // 此處會(huì)導(dǎo)致非法訪問
    return 0;
}

解決方法：

本質(zhì)是因?yàn)槲矂h導(dǎo)致的迭代器失效問題，因此我們?cè)谖矂h完后，返回it的下一個(gè)位置，我們的模擬實(shí)現(xiàn)是數(shù)據(jù)覆蓋（it+1覆蓋it），因此返回的還是it，一刪之后 --_finish，當(dāng) it指的位置就是_finish 的時(shí)候正好也就停止了，因此也就解決了迭代器失效的問題。

代碼實(shí)現(xiàn)：

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

4、g++編譯器對(duì)迭代器失效檢測(cè)

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

4.1 擴(kuò)容

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 << "擴(kuò)容之前，vector的容量為: " << v.capacity() << endl;
    v.reserve(100);
    cout << "擴(kuò)容之后，vector的容量為: " << v.capacity() << endl;
    while(it != v.end())
    {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
    return 0;
}

g++下運(yùn)行結(jié)果：

vs2019下運(yùn)行結(jié)果：

vs2019下程序崩潰了。
結(jié)論：當(dāng)擴(kuò)容后迭代器就是失效的，g++下雖然能運(yùn)行，但是結(jié)果出錯(cuò)了，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++下運(yùn)行結(jié)果：

vs2019下運(yùn)行結(jié)果：

結(jié)論：在非尾刪的刪除中，空間是沒有變的，迭代器指的是還是那塊空間，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++下運(yùn)行結(jié)果：

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

5、總結(jié)

本篇主要講了擴(kuò)容、插入、刪除造成的迭代器失效，g++對(duì)迭代器失效檢測(cè)的不嚴(yán)格，而vs對(duì)迭代器失效檢測(cè)很嚴(yán)格，直接崩潰。

1、擴(kuò)容一般都要更新迭代器，我們不知道哪一次的擴(kuò)容是異地?cái)U(kuò)。

2、插入任意位置時(shí)，一旦存在擴(kuò)容就要更新迭代器，本質(zhì)就是擴(kuò)容要更新迭代器。

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

以上就是C++ STL_vector 迭代器失效問題的解決方法的詳細(xì)內(nèi)容，更多關(guān)于C++ STL_vector 迭代器失效的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論