（C++）錯誤的map刪除操作和STL中容器的迭代器的底層實作機制

1.錯誤的map刪除操作

假設有個map容器，用於儲存大學班級中各個家鄉省份對應的學生數，key為省份中文全拼，value為學生數。現需要刪除人數為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）對於節點式容器(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;
    }
}

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

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

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

如何更簡潔的實作該方法呢？以下給出該方法的《Effective STL》一書的具體實作：

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

該實作方式利用了後置 操作符的特性，在erase操作之前，迭代器已經指向了下一個元素。

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

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方法。先透過函數模板remove_copy_if 依照條件拷貝（copy）所需的元素到臨時容器中，剩下未被拷貝的元素就相當於被「刪除（remove）」了，然後將兩個容器中的元素交換（swap ）即可，可以直接呼叫map的成員函數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函数模板是因为通过调用insert()成员函数来插入元素，并由用户指定插入位置
    remove_copy_if(mapCount.begin(),mapCount.end(),inserter(mapCountTemp,mapCountTemp.begin()),notCopy);

    mapCount.swap(mapCountTemp);//实现两个容器的交换

    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

這個方法的缺點：雖然實作兩個map的交換的時間複雜度是常數級，一般情況下，拷貝帶來的時間開銷會大於刪除指定元素的時間開銷，且臨時map容器也增加了空間的開銷。

2.STL中容器的迭代器的底層實作機制

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

STL中容器迭代器的本質是類別對象，其作用類似於資料庫中的遊標（cursor），除此之外迭代器也是一種設計模式。我們可以對它進行遞增（或選擇下一個）來存取容器中的元素，而無需知道它內部是如何實現的。其行為很像指針，都可以用來存取指定的元素。但是二者是完全不同的東西，指標代表元素的記憶體位址，也就是物件在記憶體中的儲存位置，而迭代器則代表元素在容器中的相對位置。

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

for(auto __begin = collection.begin(),auto __end = collection.end();__begin!=__end;++__begin)
{ 
    i = *__begin;    ...//循环体
}

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

下面給出最簡單的實作程式碼。我們定義一個CPPCollection類，裡面有一個字串數組，我們讓它能夠透過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 中的內部嵌套類別與外圍的類別沒有聯繫，為了存取外部類別物件的值，我們必須傳入一個引用（或指針，本例中傳入引用）。 Iterator的自增方法其實就是增加內部的一個索引值。判斷！ =的方法是和另一個迭代器做比較，這個迭代器一般是集合的末尾，當我們的索引值等於末尾的索引值end時，認為迭代器已經達到了末尾。在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(),…），这种泛型算法其实就是在迭代器的首位反复迭代，然后运行相应的行为。

---

参考文献

[1]编写高质量代码：改善C++程序的150个建议.李健.机械工业出版社.

相关文章：

C# 2.0 Specification(迭代器)（二）

C#中使用迭代器处理等待任务_基础知识

C# 2.0 Specification(迭代器)（一）

以上是（C++）錯誤的map刪除操作和STL中容器的迭代器的底層實作機制的詳細內容。更多資訊請關注PHP中文網其他相關文章！