如何在遍歷中使用 iterator/reverse_iterator 刪除元素

眾所周知，在使用迭代器遍歷 STL 容器時(shí)，需要特別留意是否在循環(huán)中修改了迭代器而導(dǎo)致迭代器失效的情形。下面我來(lái)總結(jié)一下在對(duì)各種容器進(jìn)行正向和反向遍歷過程中刪除元素時(shí)，正確更新迭代器的用法。本文完整源碼：點(diǎn)此查看

首先，要明白使用正向迭代器（iterator）進(jìn)行反向遍歷是錯(cuò)誤的用法，要不干嘛要有反向迭代器呢（reverse_iterator）。其次，根據(jù)容器的特性，遍歷刪除操作的用法可以分為兩組，第一組是 list 和 vector，第二組是 map 和 set。

接下來(lái)，看看具體怎么個(gè)用法。

第一種情形：正向遍歷刪除元素

對(duì) list 和 vector 來(lái)說(shuō)，它們的 erase 函數(shù)會(huì)返回下一個(gè)迭代器，因此在遍歷時(shí)，只需要 it = c.erase(it); 即可。

對(duì) map 和 set 來(lái)說(shuō)，它們的 erase 函數(shù)返回的 void，而在進(jìn)行 erase 之后，當(dāng)前迭代器會(huì)失效，無(wú)法再用于獲取下一個(gè)迭代器。因此需要 erase 之前就獲取指向下一個(gè)元素的迭代器。如： 

tmpIt = it;
++it;
c.erase(tmpIt);

利用后綴++操作符的特性（先創(chuàng)建副本，然后再遞增迭代器，然后返回副本）上面的三行代碼可以簡(jiǎn)化為一行：

c.erase(it++);

下面來(lái)看實(shí)例：

list 正向遍歷刪除元素示例（vector 用法相同）：

    // erase with iterator
    list<int>::iterator it;
    for (it = l.begin(); it != l.end();)
    {
        if (0 == (*it) % 2) {
            it = l.erase(it);
        }
        else {
            ++it;
        }
    }

map 正向遍歷刪除元素示例（set 用法相同）：

    // erase with iterator
    map<int, int>::iterator mit;
    for (mit = m.begin(); mit != m.end();)
    {
        if (0 == mit->first % 2) {
            m.erase(mit++);
        }
        else {
            ++mit;
        }
    }

第二種情形，反向遍歷刪除元素

關(guān)于正向/反向迭代器的關(guān)系，請(qǐng)參考《Effective STL》，在這里我只說(shuō)明一點(diǎn)，兩者相差一個(gè)元素，從一個(gè)反向迭代器獲得對(duì)應(yīng)的正向迭代器需要使用 base() 方法。如下圖所示：ri 是指向元素3的反向迭代器，而 i 是 ri.base() 所得到的正想迭代器。

由于所有的 erase 函數(shù)都只接受正向迭代器 iterator，所以在進(jìn)行反向遍歷刪除元素時(shí)，首先需要將 reverse_iterator 轉(zhuǎn)換為 iterator，然后再考慮更新迭代器的問題。

先來(lái)分析如何將 reverse_iterator 轉(zhuǎn)換為 iterator。如上圖所示，我們想要?jiǎng)h除元素3，而 ri.base() 所得到的正向迭代器 i 指向的其實(shí) 4 了，因而為了正確地刪除元素 3，需要將ri往前（反向的）挪一個(gè)位置。也就是說(shuō)，這一步的刪除用法應(yīng)為：

c.erase((++rit).base()); 

或：(想想為什么？，但這個(gè)用法不具備可移植性，因?yàn)橛行?STL 實(shí)現(xiàn)不允許修改函數(shù)返回的指針)

c.erase(--(rit.base();

然后，我們來(lái)分析迭代器更新的問題。
對(duì) list/vector 來(lái)說(shuō)，由于的 erase 能夠返回一個(gè)有效的正向迭代器，因而只需要將返回的正向迭代器轉(zhuǎn)換為反向迭代器即可。

對(duì) map/set 來(lái)說(shuō)，因?yàn)樵谶M(jìn)行刪除操作 l.erase((++rit).base()) 時(shí)，迭代器已經(jīng)更新過了，真是一舉兩得啊。從這里也可以看出，使用這種先遞增后 base() 的轉(zhuǎn)換刪除法，代碼更清晰。

至此，理論分析完畢，下面我們來(lái)看具體的實(shí)例。

list 反向遍歷刪除元素示例（vector 用法相同）：

    // erase with reverse_iterator
    list<int>::reverse_iterator rit;
    for (rit = l.rbegin(); rit != l.rend();)
    {
        if (0 == (*rit) % 2) {
            rit = list<int>::reverse_iterator(l.erase((++rit).base()));
            //rit = list<int>::reverse_iterator(l.erase(--(rit.base()));
        }
        else {
            ++rit;
        }
    }

map 反向遍歷刪除元素示例（set 用法相同）：

    // erase with reverse_iterator
    map<int, int>::reverse_iterator rit;
    for (rit = m.rbegin(); rit != m.rend();)
    {
        if (0 == rit->first % 2) {
            m.erase((++rit).base());
        }
        else {
            ++rit;
        }
    }

OK，刪除用法相信大家都明白了，但是，但是，引起迭代器失效的操作還有插入操作呀，相信聰明的你一定能夠舉一反三正確更新迭代器～～