2015-10-23-01-STL書籍の掲載コードをCL-STLで書いてみよう-12 - project-enigma

2015-10-23-01-STL書籍の掲載コードをCL-STLで書いてみよう-12

>> Site top >> weblog >> 月別アーカイブ >> 2015年10月のlog >> 2015-10-23-01-STL書籍の掲載コードをCL-STLで書いてみよう-12

最終更新日付:2015/10/24 00:02:30


STL書籍の掲載コードをCL-STLで書いてみよう-12

2015 年 10 月 23 日

連想コンテナの全面刷新が佳境に入っているため、しばらくの御無沙汰となった。今回は Effective STL の第32項、「本当に削除したい場合は、remove風アルゴリズムの後にeraseを使おう」をやってみよう。

この項は、まず remove アルゴリズムの宣言の確認から始まる。同じようにしよう。以下のようなものだ。

template<class ForwardIterator, class T>
FowardIterator remove( FowardIterator first, FowardIterator last, const T& value );

 

このアルゴリズムは、(というかアルゴリズムは皆そうなのだが)反復子の指すシーケンスを保有しているコンテナには関知しない。そこがポイントだ。だから、このアルゴリズムは remove といいつつも実際にコンテナから要素を削除することはない。実際には、シーケンスの中で『削除されない』要素を前方に詰めるだけなのだ。そして、削除されなかった最後の要素の次を指す反復子を返す。ここで、CL-STL における remove アルゴリズムを見ておこう。

(defmethod-overload remove ((first forward-iterator) (last forward-iterator) value))

#+cl-stl-extra
(defmethod-overload remove ((first forward-iterator) (last forward-iterator) value eql-bf))

 

STL の remove は常に operator== で要素を比較する。これに対し、CL-STL では2番目の定義により、operator_== 以外の等値検査を使うことができる。これには、*features*:cl-stl-extra を入れた状態でロードする必要がある。ところで、STL にこれがないのは何故だろう? おそらく、remove-if を使えば? ということなのだろう。多分だけど。

さて、最初に提示されるコードは以下のようなものだ。これじゃ v の要素数は変わりませんよ、というサンプルだな。

vector<int> v;
v.reserve( 10 );
for( int i = 1; i <= 10; ++i )
    v.push_back( i );

cout << v.size();                  // 10
v[3] = v[5] = v[9] = 99;
remove( v.begin(), v.end(), 99 );
cout << v.size();                  // still 10 !

 

一応 CL-STL での対応するコードを示しておこう。ついでに、結果としてシーケンスがどのような状態になっているかの実際も表示させてある。

* (let ((v (new stl:vector)))
    (stl:reserve v 10)
    (stl:for (((i 1)) (<= i 10) (incf i))
      (stl:push-back v i))
    (print (stl:size v))            ; 10
    (with-operators
        (_= v[3] (_= v[5] (_= v[9] 99))))
    (stl:remove (stl:begin v) (stl:end v) 99)
    (print (stl:size v))            ; still 10 !
    v)

;=> 10
;   10
;   #<CL-STL:VECTOR {10087ADC53}>


* (stl:for (v *)
    (format t " ~A" v))

;=> 1 2 3 5 7 8 9 NIL NIL 99
;   NIL

 

ここで注意書き。書籍では、remove 実行後のシーケンスは 1 2 3 5 7 8 9 8 9 99 になると言っているが、上記の結果は違うようだ。これには理由があって、Effective STL は C++98 の時代に書かれており、一方で CL-STL は C++11 以降の実装をベースに作成されている。結果、remove アルゴリズムは要素の移動に move を使用するようになっているため、このようになっているわけだ。ちなみに、*features*:cl-stl-0x98 を入れた状態でロードすれば、書籍と同じ結果になるはずだ(試してないけど)。

では本題に入ろう。コンテナから要素を実際に削除するには、remove が返す反復子からシーケンス末尾までの要素を erase すれば良い。書籍には以下のコードが掲載されている。

vector<int> v;
// ...
v.erase( remove( v.begin(), v.end(), 99 ), v.end() );
cout << v.size();

 

同じことをする CL-STL のコードは以下の通りだ。先程と同様、最終的なシーケンスの内容を確認している。お望み通りだ。

* (let ((v (new stl:vector 10)))
    (stl:iota (stl:begin v) (stl:end v) 1)
    (with-operators
        (_= v[3] (_= v[5] (_= v[9] 99))))
    (stl:erase v (stl:remove (stl:begin v) (stl:end v) 99) (stl:end v))
    (print (stl:size v))
    v)

;=> 7
;   #<CL-STL:VECTOR {100C711FE3}>


* (stl:for (v *)
    (format t " ~A" v))

;=> 1 2 3 5 7 8 9
;   NIL

 

ここからは、話題はコンテナに特有の削除メソッドに移る。まずは list だ。こいつは紛らわしいことに remove というメソッドでもって削除を行なう。書籍のコードは以下のようなものだった。

list<int> li;
// ...
li.remove( 99 );

 

これも CL-STL の実際に動作するコードで確認しよう。こんな感じ。

* (let ((li (new stl:list #{1 2 3 99 5 99 7 8 9 99})))
   (stl:remove li 99)
   (stl:for (v li)
     (format t " ~A" v)))

; =>  1 2 3 5 7 8 9
;    NIL

 

コードは以上かな。Effective STL でも、連想コンテナの要素削除メソッドが erase であるのに対して listremove だという点が STL の不整合だと嘆いている。CL-STL は可能な限り STL と同じように作る、というお題目を掲げているので、こういうイマイチな部分もきっちりと再現している。

それではまた次回。

 

このシリーズのこれまでのエントリ

 

コメント

このページにコメントする

 

このページのタグ

Page tag : STLとその移植

Page tag : Common Lisp

 

 


Copyright(C) 2005-2017 project-enigma.
Generated by CL-PREFAB.