C++錯誤的map刪除操作和STL中容器的迭代器的底層實現(xiàn)機制

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

1.錯誤的map刪除操作

假設有個map容器，用于存儲大學班級中各個家鄉(xiāng)省份對應的學生數(shù)，key為省份中文全拼，value為學生數(shù)?，F(xiàn)需要刪除人數(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);
    }
}

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

所以，在刪除一個元素的時候，是沒有什么問題的。即：

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

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

方法一：當刪除特定值的元素時，刪除元素前保存當前被刪除元素的下一個元素的迭代器。

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;
}

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

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

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

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

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

方法二：當刪除滿足某些條件的元素，可以使用remove_copy_if & swap方法。先通過函數(shù)模板remove_copy_if 按照條件拷貝（copy）需要的元素到臨時容器中，剩下未被拷貝的元素就相當于被“刪除（remove）”了，然后在將兩個容器中的元素交換（swap）即可，可以直接調用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;//臨時map容器
    //之所以要用迭代器適配器inserter函數(shù)模板是因為通過調用insert()成員函數(shù)來插入元素，并由用戶指定插入位置
    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notCopy);

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

    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;
    }
}

程序輸出結果：

2
4
anhui 1
shandong 1

這種方法的缺點：雖然實現(xiàn)兩個map的交換的時間復雜度是常量級，一般情況下，拷貝帶來的時間開銷會大于刪除指定元素的時間開銷，并且臨時map容器也增加了空間的開銷。

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

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

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

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

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

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

下面給出最簡單的實現(xiàn)代碼。我們定義一個CPPCollection類，里面有個字符串數(shù)組，我們讓它能夠通過range for將每個字符串輸出來。

class CPPCollection 
{public:
    //迭代器類    class Iterator
    {    public:        int index;//元素下標
        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];
};

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

　　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;
   }

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

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

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