C++ Iterator Invalidation

　以下のようなコードをサーバー上で実行すると、Runtime Errorになった。
ローカルだと正常に終了するけど何だろうなと思って調べていたらIterator Invalidationという現象が起こっていたことが分かった。

#include <set>
#include <iostream>

using namespace std;

int main() {
    int nums[] = {0,1,2,3,4,5,6,7,8,9};
    set<int> st(nums, nums+10);

    for (set<int>::iterator itr = st.begin(); itr != st.end(); itr++)
        if (*itr % 2)
            st.erase(itr);

    for (set<int>::iterator itr = st.begin(); itr != st.end(); itr++)
        cout << *itr << " ";

    cout << endl;
}

Iterator Invalidationとは、

Iterators are glorified pointers. Iterator invalidation is a lot like pointer invalidation; it means it suddenly points to junk data.
The problem occurs when a container that is being processed using an iterator has its shape changed during the process.

ということらしい[1]。

下のように書き直すと、Iterator Invalidationは起こらない[2]。itr++で現在のiteratorのコピーを返した後に、itrをインクリメントしているのがポイント。

#include <set>
#include <iostream>

using namespace std;

int main() {
    int nums[] = {0,1,2,3,4,5,6,7,8,9};
    set<int> st(nums, nums+10);

    for (set<int>::iterator itr = st.begin(); itr != st.end(); ) {
        if (*itr % 2)
            st.erase(itr++);
        else
            ++itr;
    }

    for (set<int>::iterator itr = st.begin(); itr != st.end(); itr++)
        cout << *itr << " ";

    cout << endl;
}

まー、実は上の例だと、remove_ifとerase使えば一発なんだけど。
実際サーバー上で走らせたコードはもう少し複雑で、フィルタリングに使う関数がシンプルな冪等関数じゃなかったので、functor使って簡単には書けなそうな感じだった。

他のSTLコンテナについても、Iterator Invalidationが起こる場合がある。どのような場合に気をつけないといけないかまとめてくれているサイトがあったのでリンクしておく。

• Iterator Invalidation Rules (C++03)
• Iterator Invalidation Rules (C++0x)

References

[1] c++ - What is iterator invalidation? - Stack Overflow
[2] c++ - Deleting elements from STL set while iterating - Stack Overflow