C++におけるイテレータの無効化――原因とコンテナ別のルールを解説

イテレータ無効化とは

C++には、vector、list、set、mapなど、用途に応じたさまざまなコンテナが標準ライブラリとして用意されています。これらのコンテナを走査する際にはイテレータを使用しますが、扱い方を誤ると予期しない動作を引き起こすことがあります。特に注意が必要なのが「イテレータの無効化（invalidation）」です。コンテナを反復処理している最中に要素の追加や削除などでコンテナの構造やサイズが変化すると、イテレータが無効化され、最悪の場合は未定義動作につながります。

以下のサンプルコードで、無効化が引き起こす問題を確認してみましょう。

問題を引き起こすサンプルコード

#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector <int> vec{11, 55, 110, 155, 220};
    for (auto it=vec.begin(); it!=vec.end(); it++)
        if ((*it) == 110)
            vec.push_back(89); // 反復処理中に新しい値を挿入
    for (auto it=vec.begin(); it!=vec.end(); it++)
        cout << (*it) << " ";
}

実行結果

11 55 110 155 220 89 89

なぜ無効化が発生するのか

このプログラムでは、実行環境によって異なる結果が得られる可能性があります。vectorのサイズは事前に確保されておらず、初期値から自動的に決定されます。反復処理中にpush_back()で新しい値を追加すると、vectorに十分な空き容量（capacity）がない場合、実行時に新たなメモリブロックが確保され、既存の全要素がその領域へコピーされます。しかし、それまで使用していたイテレータは旧メモリ領域のアドレスを指したままになるため、無効化された状態となります。無効化されたイテレータを使い続けると、プログラムは不正な動作をする恐れがあります。

コンテナ別のイテレータ無効化ルール

イテレータが無効化される条件は、コンテナの種類や操作内容によって異なります。主なルールを以下の表にまとめました。

無効化を防ぐためのポイント

• vectorでは、あらかじめreserve()で必要な容量を確保しておくと、再割り当てによる無効化を回避できます。
• 要素を削除する際は、erase()の戻り値（削除要素の次の要素を指す有効なイテレータ）を受け取ってイテレータを更新しましょう。
• 反復処理中のコンテナ変更は避け、変更処理と走査処理を分けるのが安全です。

イテレータの無効化は、コンパイルエラーにならず実行時に問題が顕在化するため発見が難しいバグの一つです。コンテナの特性を理解し、安全なコードを心がけましょう。