連想コンテナのerase



STLの連想コンテナ(map/multimap/set/multiset)のeraseの返し値は、C++標準ではvoidである。これは、削除した次の要素の先頭を返すiteratorを実装するとパフォーマンスに問題があるとしたC++標準の見解を示すものであるが、STL実装者の間では、それはないだろうという意見が大半を占めている(⇒EffectiveSTL.第5項。やねうらおもそう思う)ので、VC++6/VC++.NETの実装はiteratorを返す実装となっている。

※　ちなみに、シーケンス(deque/list/vector)では削除した要素の次の要素を指すイテレータを返す。

STLPortのような標準にきっちり準拠しているお利口ちゃんの実装系に移植するときに問題となる。iteratorを返してくれないので、削除した次の要素はどれだかわからない。仕方ないので、また先頭に戻って1から条件に見合うものを探す処理を書いている人もいるだろう。

順序だてて考えてみよう。

あるいは、コピーしながら条件に合致しないものはコピー“しない”ことで解決する。
たとえばintのsetから、条件に合致するものをeraseしたい場合、以下のようになる。

list-1 cppll-931
  set<int> ss;
  {
    set<int> temp;
    remove_copy_if(ss.begin(), ss.end(), inserter(temp,temp.begin()), 条件);
    ss.swap(temp);
  }

    要素のコピーが発生するのであんまりナイスじゃないんだなー


あるいは、削除しても他の要素を指すiteratorは有効なので、削除する要素のiteratorをどこかにためていき、それをまとめて消すことでも実現できる。

list-2 cppll-970
    要素を削除しても(他の)iteratorはvalidだろうから、

  set<T> source;
  stack<set<T>::iterator> removes;
  for ( set<T>::iterator iter = source.begin(); 
        iter != source.end(); ++iter ) {
    if ( これはいらない(*iter) )
      removes.push(iter);
  }
  while ( !removes.empty() ) {
    source.erase(removed.top());
    removes.pop();
  }


枠-1 cppll-1012
[ISO/IEC 14882:1998 23.1.2の8]
The insert members shall not affect the validity of iterators and
references to the container, and the erase members shall invalidate only
iterators and references to the erased elements.


eraseメンバ(関数)は削除される要素への参照と削除される要素を指すiterator 'だけ' を無効にする。よって、先に現在のiteratorを++したものをコピーしておき、eraseしたのちに、そのコピーしておいたiteratorを現在のiteratorに戻せば良い。

list-3
    iterator tmp = it;
    tmp++;
    s.erase(it);
    it = tmp;


である。これは、後置インクリメントを使って単に次のように書ける。

list-4
    s.erase(it++);


なぜなら、eraseに渡す値は、インクリメントする前のものだが、eraseを呼び出すより前に++が行なわれるためにitは次の要素を指すiteratorとなる。これこそ、求めていたものである。(EffectiveSTL.第9項)

全体のソースは以下のようになる。

list-5 cppll-1011
   set<T> source;
   set<T>::iterator iter = source.begin();
   while ( iter != source.end() ) {
     if ( これはいらない(*iter) ) {
       source.erase(iter++);
     } else {
       ++iter;
     }
   }