這篇文章將為大家詳細(xì)講解有關(guān)C++錯(cuò)誤的map刪除操作和STL中容器的迭代器的底層實(shí)現(xiàn)機(jī)制，小編覺(jué)得挺實(shí)用的，因此分享給大家做個(gè)參考，希望大家閱讀完這篇文章后可以有所收獲。

成都創(chuàng)新互聯(lián)公司始終堅(jiān)持【策劃先行，效果至上】的經(jīng)營(yíng)理念，通過(guò)多達(dá)10多年累計(jì)超上千家客戶(hù)的網(wǎng)站建設(shè)總結(jié)了一套系統(tǒng)有效的全網(wǎng)整合營(yíng)銷(xiāo)推廣解決方案，現(xiàn)已廣泛運(yùn)用于各行各業(yè)的客戶(hù)，其中包括：白烏魚(yú)等企業(yè)，備受客戶(hù)表?yè)P(yáng)。

1.錯(cuò)誤的map刪除操作

假設(shè)有個(gè)map容器，用于存儲(chǔ)大學(xué)班級(jí)中各個(gè)家鄉(xiāng)省份對(duì)應(yīng)的學(xué)生數(shù)，key為省份中文全拼，value為學(xué)生數(shù)。現(xiàn)需要?jiǎng)h除人數(shù)為0的記錄，刪除代碼如下：

map<string,int > countMap;for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it)
{if(it->second==0)
{
        countMap.erase(it);
    }
}

猛一看，沒(méi)問(wèn)題，仔細(xì)一看，有巨坑，STL容器的刪除和插入操作隱藏的陷阱主要有如下兩條。
（1）對(duì)于節(jié)點(diǎn)式容器(map, list, set)元素的刪除，插入操作會(huì)導(dǎo)致指向該元素的迭代器失效，其他元素迭代器不受影響；
（2）對(duì)于順序式容器(vector，string，deque)元素的刪除、插入操作會(huì)導(dǎo)致指向該元素以及后面的元素的迭代器失效。

所以，在刪除一個(gè)元素的時(shí)候，是沒(méi)有什么問(wèn)題的。即：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();++it)
{    if(it->second==0)
    {
        countMap.erase(it);        break;
    }
}

但是，當(dāng)刪除多個(gè)元素時(shí)，程序會(huì)出現(xiàn)崩潰。原因是通過(guò)迭代器刪除指定的元素時(shí)，指向那個(gè)元素的迭代器將失效，如果再次對(duì)失效的迭代器進(jìn)行++操作，則會(huì)帶來(lái)未定義行為，程序崩潰。解決方法有二，還是以上面的map容器為例，示例刪除操作的正確實(shí)現(xiàn)：

方法一：當(dāng)刪除特定值的元素時(shí)，刪除元素前保存當(dāng)前被刪除元素的下一個(gè)元素的迭代器。

map<string,int >::iterator nextIt=countMap.begin();for(map<string,int>::iterator it=countMap.begin();;)
{    if(nextIt!=countMap.end())
    {
        ++nextIt;
    }    else
    { 
        break;
    }    if(it->second==0)
    {
        countMap.erase(it);
    }
    it=nextIt;
}

如何更加簡(jiǎn)潔的實(shí)現(xiàn)該方法呢？下面給出該方法的《Effective STL》一書(shū)的具體實(shí)現(xiàn)：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();)
{    if(it->second==0)
    {
        countMap.erase(it++);
    }    else
    {
        ++it;
    }
}

該實(shí)現(xiàn)方式利用了后置++操作符的特性，在erase操作之前，迭代器已經(jīng)指向了下一個(gè)元素。

再者map.erase()返回指向緊接著被刪除元素的下一個(gè)元素的迭代器，所以可以實(shí)現(xiàn)如下：

for(map<string,int>::iterator it=countMap.begin();it!=countMap.end();)
{    if(it->second==0)
    {
        it=countMap.erase(it);
    }   
    else
    {
        ++it;
    }
}

方法二：當(dāng)刪除滿(mǎn)足某些條件的元素，可以使用remove_copy_if & swap方法。先通過(guò)函數(shù)模板remove_copy_if 按照條件拷貝（copy）需要的元素到臨時(shí)容器中，剩下未被拷貝的元素就相當(dāng)于被“刪除（remove）”了，然后在將兩個(gè)容器中的元素交換（swap）即可，可以直接調(diào)用map的成員函數(shù)swap。參考代碼：

#include <iostream>#include <string>#include <map>#include <algorithm>#include <iterator>  using namespace std;map<string,int> mapCount;//不拷貝的條件bool notCopy(pair<string,int> key_value)
{    return key_value.second==0;
}int main()
{
    mapCount.insert(make_pair("tanwan",0));
    mapCount.insert(make_pair("anhui",1));
    mapCount.insert(make_pair("shanghai",0));
    mapCount.insert(make_pair("shandong",1));    map<string,int> mapCountTemp;//臨時(shí)map容器
    //之所以要用迭代器適配器inserter函數(shù)模板是因?yàn)橥ㄟ^(guò)調(diào)用insert()成員函數(shù)來(lái)插入元素，并由用戶(hù)指定插入位置
    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notCopy);

    mapCount.swap(mapCountTemp);//實(shí)現(xiàn)兩個(gè)容器的交換

    cout<<mapCount.size()<<endl;     //輸出2
    cout<<mapCountTemp.size()<<endl; //輸出4

    for(map<string,int>::iterator it=mapCount.begin();it!=mapCount.end();++it)
    {        cout<<it->first<<" "<<it->second<<endl;
    }
}

程序輸出結(jié)果：

2
4
anhui 1
shandong 1

這種方法的缺點(diǎn)：雖然實(shí)現(xiàn)兩個(gè)map的交換的時(shí)間復(fù)雜度是常量級(jí)，一般情況下，拷貝帶來(lái)的時(shí)間開(kāi)銷(xiāo)會(huì)大于刪除指定元素的時(shí)間開(kāi)銷(xiāo)，并且臨時(shí)map容器也增加了空間的開(kāi)銷(xiāo)。

2.STL中容器的迭代器的底層實(shí)現(xiàn)機(jī)制

提到STL，必須要馬上想到其主要的6個(gè)組成部件，分別是：容器、迭代器、算法、仿函數(shù)、適配器和空間分配器，迭代器是連接容器和算法的一種重要橋梁。

STL中容器迭代器的本質(zhì)是類(lèi)對(duì)象，其作用類(lèi)似于數(shù)據(jù)庫(kù)中的游標(biāo)（cursor），除此之外迭代器也是一種設(shè)計(jì)模式。我們可以對(duì)它進(jìn)行遞增（或選擇下一個(gè)）來(lái)訪問(wèn)容器中的元素，而無(wú)需知道它內(nèi)部是如何實(shí)現(xiàn)的。其行為很像指針，都可以用來(lái)訪問(wèn)指定的元素。但是二者是完全不同的東西，指針代表元素的內(nèi)存地址，即對(duì)象在內(nèi)存中的存儲(chǔ)位置，而迭代器則代表元素在容器中的相對(duì)位置。

要自定義一個(gè)迭代器，就要重載迭代器一些基本操作符：*（解引用）、++（自增）、==（等于）、!=（不等于）、=（賦值），以便它在range for語(yǔ)句中使用。range for是C++11中新增的語(yǔ)句，如我們對(duì)一個(gè)集合使用語(yǔ)句for （auto i : collection ） 時(shí)，它的含義其實(shí)為：

for(auto __begin = collection.begin(),auto __end = collection.end();__begin!=__end;++__begin)
{ 
    i = *__begin;    ...//循環(huán)體
}

begin和end是集合的成員函數(shù)，它返回一個(gè)迭代器。如果讓一個(gè)類(lèi)可以有range for的操作，它必須滿(mǎn)足以下幾條：
（1）擁有begin和end函數(shù)，它們均返回迭代器 ，其中end函數(shù)返回一個(gè)指向集合末尾，但是不包含末尾元素的值，即用集合范圍來(lái)表示，一個(gè)迭代器的范圍是 [ begin, end ） 一個(gè)左閉右開(kāi)區(qū)間。
（2）必須重載++、！=和解引用（*）運(yùn)算符。迭代器看起來(lái)會(huì)像一個(gè)指針，但是不是指針。迭代器必須可以通過(guò)++最后滿(mǎn)足！=條件，這樣才能夠終止循環(huán)。

下面給出最簡(jiǎn)單的實(shí)現(xiàn)代碼。我們定義一個(gè)CPPCollection類(lèi)，里面有個(gè)字符串?dāng)?shù)組，我們讓它能夠通過(guò)range for將每個(gè)字符串輸出來(lái)。

class CPPCollection 
{public:
    //迭代器類(lèi)    class Iterator
    {    public:        int index;//元素下標(biāo)
        CPPCollection& outer;
        Iterator(CPPCollection &o, int i):outer(o), index(i){}        void operator++()
        {
            index++;
        }
        std::string operator*() const
        {            return outer.str[index];
        }        bool operator!=(Iterator i)
        {            return i.index!=index;
        }
    };public:    CPPCollection()
    {        string strTemp[10]={"a", "b", "c", "d", "e", "f", "g", "h", "i", "j"};        int i=0;        for(auto strIt:strTemp)
        {
            str[i++]=strIt;
        }
    }

    Iterator begin()
    {        return Iterator(*this,0);
    }
    Iterator end()
    {        return Iterator(*this, 10);
    }private:
    std::string str[10];
};

我們定義了個(gè)內(nèi)部的嵌套類(lèi)Iterator,并為它重載了++、*、！=運(yùn)算符。由于C++中的內(nèi)部嵌套類(lèi)與外圍的類(lèi)沒(méi)有聯(lián)系，為了訪問(wèn)外部類(lèi)對(duì)象的值，我們必須要傳入一個(gè)引用（或指針，本例中傳入引用）。Iterator的自增方法其實(shí)就是增加內(nèi)部的一個(gè)索引值。判斷！=的方法是和另外一個(gè)迭代器做比較，這個(gè)迭代器一般是集合的末尾，當(dāng)我們的索引值等于末尾的索引值end時(shí)，認(rèn)為迭代器已經(jīng)達(dá)到了末尾。 在CPPCollection類(lèi)中，定義了begin（）、end（）分別返回開(kāi)頭、結(jié)束迭代器，調(diào)用如下代碼：

　　CPPCollection cpc;
　　for (auto i : cpc)
　　{
    　　std::cout <<i<<std::endl;
　　}
　　//或者　　CPPCollection cpc;
　　for(CPPCollection::Iterator i= cpc.begin();i!=cpc.end();++i)
　　{        std::cout<<*i<<std::endl;
   }

即可遍歷集合中的所有元素了。

在泛型算法中，為了對(duì)集合中的每一個(gè)元素進(jìn)行操作，我們通常要傳入集合的迭代器頭、迭代器尾，以及謂詞，例如std::find_if（vec.begin(),vec.end(),…），這種泛型算法其實(shí)就是在迭代器的首位反復(fù)迭代，然后運(yùn)行相應(yīng)的行為。

---

關(guān)于C++錯(cuò)誤的map刪除操作和STL中容器的迭代器的底層實(shí)現(xiàn)機(jī)制就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。

當(dāng)前文章：C++錯(cuò)誤的map刪除操作和STL中容器的迭代器的底層實(shí)現(xiàn)機(jī)制
文章鏈接：http://chinadenli.net/article8/ipcgop.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站設(shè)計(jì)、虛擬主機(jī)、動(dòng)態(tài)網(wǎng)站、企業(yè)網(wǎng)站制作、網(wǎng)站制作、搜索引擎優(yōu)化

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)