ホーム < ゲームつくろー！ < Programming TIPs編
その12 イテレート中のSTLのlistから要素を安全に削除する方法
STLのコンテナは「イテレータ」によって要素を取り出します。この時良くあるのが「ある要素をチェックして、必要が無くなった場合はリストから削除する」という作業です。例えば描画オブジェクトのリストからもういらなくなったオブジェクトを除く時などこの作業が必要になります。
イテレート中のリストから要素を除く場合、ちょっと注意しないと思わぬバグが誘発します。この章ではイテレート中のリストから要素を除く方法をまとめます。まさにTIPsです(^-^;。
① まともにやるとあっさりバグ
例として、int型のリストに0～9までの要素がこの順番で登録されているとしましょう。このリストをイテレートして「5」を取り除きたいとして、次のようなコードを書きました：
バグのあるイテレート内削除コード list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); it++ ) {
if( (*it) == 5 )
MyList.erase( it );
}
イテレート中に5があったらリストから削除という至って普通のコードですが、これを実行するとメモリ保護違反で止まってしまいます。なぜでしょうか？上のコードを慎重にステップ実行し、eraseメソッドが呼ばれる前と後でitの中身を見てみましょう。呼ばれる直後デバッグウィンドウには、
eraseが呼ばれる直後 it 5 MyList [10](0,1,2,3,4,5,6,7,8,9)
と削除対象の「5」を正しく指していますが、呼んでメソッドから戻ってきた瞬間は、
eraseが呼ばた後 it -17891602 MyList [9](0,1,2,3,4,6,7,8,9)
となります。呼ばれた後、MyList自体は正しく削除されていますが、イテレータが全くおかしな値を指しています。実はこの時点でイテレータは不正な場所に飛んでおり、次のforループでこの不正なイテレーションの次へ行こうとしたため、メモリ保護違反で止まってしまったというわけです。
② eraseメソッドの戻り値で削除後の次のイテレータをゲット！
上のソースだと、削除自体は正常に行われますが、イテレータがどこかに行ってしまいます。これを正しく動かすにはeraseメソッドの戻り値のイテレータを捕まえます：
eraseメソッドの戻り値は次のイテレータ list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); it++ ) {
if( (*it) == 5 )
it = MyList.erase( it );
}
こうすると、eraseメソッドが呼ばれた直後、イテレーションは次のようになります：
eraseが呼ばた後 it 6 MyList [9](0,1,2,3,4,6,7,8,9)
削除された「5」の次である6を正しく指すイテレータを捕まえています。これで5を消すプログラムはうまくいきます。しかし、実は上のプログラムもバグ持ちなんです。
③ 5と6を消したらうまく行かない･･･
次は、5と6を消してみましょう。上のソースを少し改良します：
eraseメソッドの戻り値は次のイテレータ list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); it++ ) {
if( (*it) == 5 || (*it) == 6 )
it = MyList.erase( it );
}
イテレータが5ないしは6だった場合は削除するという意図になっています。このプログラム自体は止まらずに動きます。しかし、リストの出力結果はこうなります：
リスト出力 MyList [9](0,1,2,3,4,6,7,8,9)
6が消えていません。これは、上のソースで5を消した直後の動作に原因があります。5を消した直後eraseメソッドは次のイテレータである6を返してくれます。ここまでは良好なのですが、次にforループがご丁寧にもイテレーションを次に進めてしまいます。さっきは6を指していたので、次は7。つまり「6がスキップされてしまっている」んです。潜在的なバグが上のソースにはあるわけです。
④ イテレーションを戻すのはだめ
単純に次のイテレータを捕まえると、forループが悪さしてしまう。では、捕まえた後に一つ戻してみてはどうでしょう：
eraseメソッドの後にイテレータを戻してみる list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); it++ ) {
if( (*it) == 5 || (*it) == 6 ) {
it = MyList.erase( it );
it--;
}
}
これ、うまくいきます。リストからは5と6が綺麗に消えます。「ならOK！」と言いたいのですが、残念ながらこれにも潜在的なバグが潜んでいます。削除する対象を0にしてみます：
リストの先頭を削除するとイテレーションのバグ！ list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); it++ ) {
if( (*it) == 0 ) {
it = MyList.erase( it );
it--;
}
}
こうすると、一番最初に削除作業が入ります。eraseメソッドの後は0が消えて、itには「1」を指すイテレータが戻ります。今0が無いので1はリストの先頭にあります。それを一つ戻すとどうなるのか？残念ながらメモリ保護違反でハングアップしてしまいます。先頭リストの1つ前に戻してはいけないんです。
⑤ イテレーション増加をループ内で操作すると良し！
おしいのですがうまく行かないイテレーション中の要素消去。うまく行かない原因はforループが問答無用に「it++」してしまう所にあります。そこで、これをやめてしまいましょう：
forループ先頭でのイテレータ増加をやめる list<int>::iterator it;
for ( it=MyList.begin(); it!=MyList.end(); ) { // <-「it++」を削除
if( (*it) == 0 ) {
it = MyList.erase( it );
continue;
}
it++; // ここで次のイテレートに
}
forループの最後にお決まりのように付けていた「it++」をまずはやめます。そして、forループの最後でイテレートするように変更します。削除対象の「0」が来たらeraseメソッドで削除します。itには次のイテレータが入りますので「何もせずに」continueでループの頭に戻ります。こうすると、何事も無かったようにイテレーションが実行できます。これが決定版です(^-^)b
この方法は順方向のイテレータだけでなくて逆方向のイテレータでもオリジナルなイテレータでも正しく動作します。ちょっと心配なのが最後の要素を削除した時です。上の場合だと「9」を削除した後にeraseメソッドは何を返すのか？これは「終端イテレータ」を返します。STLのコンテナは最後の要素の次に必ず終端イテレータをくっつけています。これはendメソッドが返すイテレータと同じです。ですから、上のコードは正しく動きます。
(2007. 12. 8追加)
⑥ remove_ifテンプレート関数による削除方法
これはてぃあのさんから教えて頂いた方法です。リストからの削除についてSTLの作法をより意識した方法にremove_ifテンプレート関数を使用するという手もあります。まずremove_if関数の定義を見てみましょう：
remove_ifテンプレート関数 template<class FwdIt, class Pred>
FwdIt remove_if(FwdIt first, FwdIt last, Pred pr);
STLのマニュアルに苦手意識がある方もいらっしゃると思います。私もちょっと苦手です(^-^;。
このテンプレート関数はalgorithmヘッダー内で定義されています。
firstとlastには削除したい範囲のイテレータを指定します。面倒ならばSTLコンテナのbegin()とend()にしても構いません。その場合は全範囲検索となります。
第3引数のprは叙述関数（プレディケータ）へのポインタです。これは削除対象か否かを判定する関数を渡します。
叙述関数は次のような定義にする必要があります：
叙述関数 bool Pred_Func( ClassType obj ) {
// 削除判定
if( 削除条件 )
return true;
return false;
}
ClassTypeはコンテナに渡した型です。ここにfirstとlastの間にある値が一つずつ渡されます。叙述関数の内部ではそのオブジェクトを見て削除対象であるかどうかをチェックします。削除対象ならばtrue、そうでなければfalseを返すようにします。
さて、この叙述関数を使って、
削除しない･･･ bool Pred_Func( int value ) {
if( value == 5 )
return true;
return false;
}
main(){
list<int> MyList;
MyList.push_back(0);
MyList.push_back(1);
...
MyList.push_back(9);
remove_if( MyList.begin(), MyList.end(), Pred_Func );
}
とすると「5」が消えそうな気がしますが、実は完全には消えません。remove_if関数は対象イテレータを消してくれるのですが、実際にはイテレータを詰めるだけなんです。ですから、実はこの作業の後にMyList.size()でサイズを調べると「10」と出てきてしまいます。もちろん、イテレートすると10回イテレーションされます。
remove_if関数を正しく使うには上の太文字部分を次のように変更します：
削除しない･･･ MyList.erase( remove_if( MyList.begin(), MyList.end(), Pred_Func ), MyList.end() );
remove_if関数は削除対象のイテレータを除いた後「消すべき末尾のゴミリストの先頭イテレータ」を返してくれます。これにeraseメソッドを組み合わせます。ゴミの先頭から最後まで消すように指示するわけです。これで綺麗に消えてくれます。
使い方にちょっとコツがいりますが、この方法は先に紹介した方法よりもすっきりとした削除コードを書くことができます。パフォーマンステストをしてみると先の方法の方が若干早い（多分関数呼び出しのオーバーヘッドなどが絡んでいるのかもしれません）のですが、気になる違いではありません。
これら操作は割とあちこちに出てきて、私も一瞬「どうだっけ？」と忘れがちになるもんでして、今回備忘録としてまとめておきました。知らなかった方は是非ご活用下さい(^-^)
⑦ 謝辞
remove_if関数の使用についてご助言頂きましたてぃあのさんに感謝申し上げます。