Standard いくつかの項目を保持していた。 要素 N へのアクセスに際し , 式 : ストでできる。インクリメント / デクリメ Map[N/ B][N % B] ・その要素を保持するプロックを指すポ ントはもっとたいへんである。ふたつの反 インタを格納する Map の要素へのポイ 復子の差をとることはめんどうである。反 でアクセスすることができる。 復子に任意の整数を足すことは大混乱以外 実際には , コンテナは両方の端で伸びる ンタ ・そのプロックの先頭へのポインタ ようになっていなければならない。それで , のなにものでもない。 ・プロック内部でその要素を指すポイン コンテナはあるオフセット Offl こある有効な しかし , それが最悪のケースではない。 内容から始まり , 有効な要素の数例の長 タ この表現方法にはいくつかの問題がある。 ・プロック末尾 ( 最後の要素のすぐ次 ) を さ ) を別の整数 Size に格納する。上の式の N ( 1 ) インクリメント / デクリメントにより を N + O Ⅱで置き換えると , 要素 N を見つける 指すポインタ 反復子が有効な map の端から外れるか ためのより現実的な解を得ることになる。 List1 に , この実装の私のバージョンを示 どうかを知る方法がない ところが , 現実はそれほど単純ではない。 す。これはテンプレートクラス deque の先 ( 2 ) 有効な map の配列に連続した要素を格 STL の deque では , さらに次のことを保証せ 頭を示しており , そこには入れ子クラス iter 納しなくてはならない ねばならない。 ator の定義も含まれている。 ( 3 ) 端から外に出た反復子には 2 種類の表 こで , iterato 現がある。最終の有効プロックから外 ( 3 ) 列の内部に対し挿入 / 削除しないかぎ r の前で typedef 型を押さえておき , iterator れたか , 次の有効なプロック ( 通常ま り , いずれかの端に push / pop したとし の内側で意味を持つ型のいくつかについて , より便利な表記ができるようにする。 だ存在しない ) の先頭に位置するかで ても , 反復子は同じ要素を指し続ける おわかりのように , 反復子のようなもの この挙動をうまくこなすために , もとも ある で要素にアクセスすることはきわめて低コ 問題 ( 1 ) は , デノヾッグの間中どれほど困 との Hewlett-Packard の実装では , 反復子が 1997 年ころの deque::ite 「 atö「 List return (*this); } iterator operator-— ( int ) {iterator Tmp = *this; --*this; return (Tmp); ) 土セ e て a に or & operator 十 = ( difference—type N) (Add(N); return ( *this ) iterator& N) (return ( *this 十 = -N } iterator operator 十 (difference—type N) const {iterator Tmp = *this; return (Tmp 十 = N); ) iterator operator- ( N ) const { iterator Tmp = * this; return (Tmp - = N); ) difference—type operator- ( const iterator& X ) const {return (Map = = X. Map ? Next - X. Next : DEQUESIZ * (Map - X. Map - 1 ) 十 (Next - First) 十 (). Last - X. Next)); ) reference operator [ ] ( difference—type N ) const {return (*(*this 十 N) b00 ー ( const iterator& X ) const (return (Next = = X. Next); ) b00 ー i に e て a に 0 て & X) const {return ( ! (*this = x) ) b00 ーて atO てく ( const iterator& X) const 仕 e 加て n (Map く x ・ Map Ⅱ yap = x ・ Map & & Next く x. Next); ) 引 ope 【 atO て← ( const iterator& X ) const {return い (x く *this) ) 20 ー operator>(const iterator& X) const { re 加てれ (X く *this); ) 20 ー ( cons に iterator& X ) const {return ( ! (*this く x) ) protected : void Add(difference—tm N) Off = N 十 Next - First; difference—type Moff = ( 0 く = Off) ? Off / DEQUESIZ - ( (DEQUESIZ - 1 - Off) / DEQUESIZ); if (Moff = Next 十 = N ー e lse {Map 十 = Moff; First = *Map ・ Last = First 十 DQUESIZ; Next = Pirst 十 (Off - MOff * DEQUESIZ); ) ) つに r Pirst , Last , Next ー Mapptr 齟店 #define DEQUEMAPSIZ 2 #define DEQUESIZ ( 4096 く sizeof ( ) ? 1 : 4096 / sizeof ( ) ) / / テンプレートクラス deque template«class 町 % class A = allocator く TY> ・ > class ( public: typedef deque く町% わ MYt; typedef A a Ⅱ ocator—type; typedef typename A : : difference—type difference—type; typedef typename A: :pointer Tptr; typedef tmname A : : const—pointer Ctptr; typedef A: :rebind<Tptp: :other: :pointer Mapptr; typename A: :reference reference; typename A : : const—reference const—reference ー typedef typename A: / / クラス iterator C ー ass const—iterator ー class iterator : public Ranit<Ty, difference—type' Tptr, reference> { public: friend class deque く町% A>; friend c lass const—iterator; iterator( ) : Fi て北 ( 0 ) , い北 ( 0 ) , Next(O), p ( 0 ) ( ) iterator(Tptr 2 , Mapptr M) : First(*M) , Last()M 十 DEQUESIZ) , Next(P), 齟 p ( 幻 { ) reference て atO て * ( ) const 仕 e にリ rn ( * N に ) Tptr OEE て a に 0 て - > ( ) const 仕 e セ n (&**this); ) iterator& operator 十十 ( ) {if ( 十十 Next = = Last) (First = * 十十 Map; Last = First 十 DQUESIZ; Next = First; ) return ( *this ) iterator 十十 ( int ) {iterator Tmp = *this; 十十 *this; return ( p ) iterator& 0 ra セ or -- ( ) {if (Next = First) {First = *--Map; Last = First 十 DEQUESIZ; Next = Last; ) ——Next; 105 Standard C ℃ + +

Standard List 1999 年ころの deque::iterator #define -DEQUEMAPSIZ 8 / * 少なくとも 1 以上 * / #define —DEQUESIZ ( 4096 く sizeof (—TY) ? : 4096 / sizeof ( ー町 ) ) 1 / / deque 基底クラスのコードは省略 / / テンプレートクラス deque template«class -Ty, class —AX = allocator く—TY> 〉 cl ass deque public -Deque-val<-Ty, -AX>{ public: / / typedef は省略 / / クラス iterator C ー ass const—iterator ー class iterator ・ public —Ranit くー町,, —Dift, —Tptr' —Reft> { public: —Ranit くー町′, —Dift, —TPtr, —Reft> —Mybase; tY*ief typename —Mybase : : iterator—category iterator—category ー typedef typename —Mybase: :value—type value—type; typedef typename —Mybase: difference-tYEE; typedef typename —Mybase: :pointer pointer; typedef typename —Mybase: :reference reference; iterator& opera し 0 て十十 ( ) {return (&**this); —Tptr operator—> ( ) const return ( (-Deque → -Map) に引 ock Ⅱー I ] ) —B lock ー = —Deque->—Mapsize; if ( ー田 OCk く = —Deque->—Mapsize ) —ldx - = —Block * —DEQUESIZ; —BIock = —ldx / —DQUESIZ; reference ( ) const -ldx(-l) , —Deque(-P) iterator(difference-type —I , deque くー町,, —A> *—p) ー 1 ( 0 ) , -Deque(0) iterator ( ) friend c lass const—iterator ー friend class deque くー町,, —A>; 叩をあちこち動かすために , 1 年以上にわ 別の改善方法に気づいたからだ。有効な m はしない。というのは , 数日のうちにまた いくものだった。ここではそれを示すこと えの結果得られたコードの単純化は満足の 得ることがあることに気がついた。書き換 私は , すぐに L の実装もこの表現から ものになった。 により , C + + の同等品よりはるかに丈夫な M 叩と 0 Ⅱの現在の値にアクセスする。それ 反復子は deque オプジェクトに格納された 格納するという考えに傾いていった。この ンタと , 前述の N に似た絶対オフセットを deque の反復子には , その deque を指すポイ を大々的に考え直すことになった。即座に は , Java で反復子をどのように表現するか これらとそれに関連する理由により , 私 信頼を置いている。 なった記憶領域をときおり回収することに ログラム (garbagecollector) 」が使われなく 示的に斤 ee されない。 Java では「ゴミ集めプ { 十十一 ld return (*this); } iterator operator 十十 ( int ) {iterator —Tmp = *this; 十十 *this; return (-Tmp); ) iterator& operator-- ( ) return ( *this ) iterator operator-- ( int) {iterator —Tmp = *this; —-*this ー return (-Tmp); } iterator& て a に 0 て十 = ( difference—type —N ) {—ldx 十 = —N; return (*this); iterator& operator-= ( difference—type —N ) 仕 e 加て n ( *this + = --N } iterator operator 十 ( —N ) const {iterator —Tmp = *this; return (-Tmp 十 = (N); } iterator operator- ( difference—type —N ) const {iterator —Tmp = *this; て e 加て n (-Tmp - = (N); } difference—type operator- ( const iterator& —X ) const {return (-ldx - ー x. ー I } reference ope て atO て冂ユ ) const 仕 e 加て n (*(*this 十 (N)); } b00 ー ope て a セ 0 て = = ( const iterator& —X ) const { て e 加て n (—Deque = = -x ・ -Deque & & -ldx = ー x. ー I } b00 ー operator!=(const iterator& (X) const { て e 加て n い (*this = = (x) } b00 ー operator< ( const iterator& —X ) const 仕 e 加て n (—ldx くュ . ー I } b00 ー operator<= ( const iterator& —X ) const 仕 e 加て n ( ! ()x く *this) ) b00 ー operator> ( const iterator& —X ) const {return ()x く *this); } 引 operatop= ( const iterator& —X ) const {return い (*this く (x) } deque<—Ty, —A> *—Deque; difference—type —ldx; protected : たりバグを取り除いてきたコードのすべて を書き直すという考えにたじろいだ。 有効な m 叩を動かすことを避けるために m 叩配列を循環バッフアとみなすように考 え直した。有効な m 叩が成長しどちらかの 端からはみ出すと , 他方の端につなげるだ けだ。 m 叩を伸ばす必要があるのは , 先頭 の要素と末尾の要素が同じプロックを共有 する脅威がきたときだけだ。 List3 に , この 考え方の変更に基づく deque 反復子を示す。 叩 erator * ( ) はこれまでより込み入ったも のになった。これは , プロック番号が m 叩 配列内で丸められる可能性があるからであ る。しかし , それ以外はかなり単純になっ た。私はこのトレードオフでは十分元を取 ったと思う。 m 叩管理のややこしいソフト ウェアのすべては , 多くのバグの元であっ たが , これがどこかに飛んでいってしまっ た。その代わりに , m 叩を伸ばすための比 較的単純な関数が出てきた。 しかし , 関数ー Growm 叩を示すよりも , それをどのように使うかを示すほうがはっ きりすることに私は気づいた。要素を列の 端から push/p 叩するメンバ関数を付録 CD-R OM に収録しておく ( LI 4 ) 。私にとって , これらは満足のいくだけの単純なものにな った。 今回の記事を終わるにあたり , いつもの 注意で締めることにする。最後に示したコ ードは , 製図板から出たばかりのほやほや である。私は徹底的なテストは行っていな いので , このコードについて保証はしない。 ここで示す準備の間に , ソースの書き換え 工ラーが入り込んでいるかもしれない。私 の目標は , 訂 L や標準 C + + ライプラリと同 程度の複雑さを持っライプラリを保守拡張 するためのプロセスのうちいくつかを伝え ることである。競争により私たちは少しば かりバランスを崩している。しかし , 競争 により , 私たちみんなが使うソフトウェア を開発するために使用するツールを改善し 続けることにもなる。 Standard C ℃ + + 107

standard 問題 ( 3 ) は , deque の実装に大量のバグを を直ちに伸ばさなくてはならない。 なかで上 , もしくは下に移動させるか , map を使い犀くすと , 有効な領域を m 叩配列の しくする。 m 叩のどちらかの端の空き領域 問題②は , m 叩の管理をはるかにややこ かれ少なかれ存在する問題である。 惑するにしても , 訂 L のほかの部分にも多 バグと改良 生み出す元になる。 Bugs and Betters ふたを開けてみると , Hewlett-Packard の もともとの実装は , バグの数は実際のとこ ろひとつでは収まっていなかった。最初の 時点でほとんど理解できていなかったアプ ローチを , 盲目的にまねするところから始 めていた私も同じ目にあった。 SGI は , 端から外れた反復子に対して , よ 1988 年ころの deque : : ite 「 ato 「 List #define -DEQUEMAPSIZ 8 / * 最低でも 5 以上 * / #define —DEQUESIZ ( 4096 く sizeof ( ー町′ ) ? 1 : 4096 / sizeof ( 一時′ ) ) ぶんな要素を常に脇に取り分けておくこと で , このあいまいな問題を解決したと思っ ている。私がこれらの問題のいくつかをど のように扱ったかを , Ⅱ st2 に示す。これは 私の会社の Web サイトにあるコード : http://www.dinkumware.com/vc fixes から取ってきたものだ。 この Web サイトには , Microsoft Visual C + + 5.0 , 6.0 とともに出荷されたファイル に対するいくつかの修正がある。 List2 の元 になったく deque > の改良版もここに含まれ ている。 これは , ヌルポインタを有効な m 叩の両 端の番兵として置くことで , 問題 ( 1 ) を解 決している。こうすることで , 少なくとも インクリメント / デクリメントでは , 端か ら転がり落ちないようにするやり方のメド がついた ( 任意の整数を足す場合は , 依然 としてこの番兵を飛び越してしまうことが あるのは当然である ) 。端から外れた反復 子を正規の表現に保ち続け , あいまいな状 態を回避することで , 問題②を解決して いる。そして , m 叩の成長とかき混ぜを , 少なくともほとんどの箇所で , いままで以 上に注意して行うことで , 問題 ( 3 ) に起因 するバグを解決しているにの部分のコー ドは List2 では示していない ) 。 私は , つい最近まではいくつかの小さな 部分を除けば , このバージョンにけっこう 満足していた。で , STL を Java で書き直し た ( そう , Java にテンプレートはないが , そ れでも可能なのだ ) 。 Java は , C や C + + の意 味でのポインタを持たない。非スカラオプ ジェクトに対し , C や C + + の意味での値のセ マンティックスもない。ヒープに割り付け られたオプジェクトを指す参照 ( 実際には ポインタ ) を用いてすべてが行われる。そ のうえ , これらのオプジェクトは決して明 〃テンプレートクラス deque template く class 一時 % class —A = allocator く—TY> > c lass deque { public: / / typedef は省略 / / クラス iterator c lass iterator : pub lic —Ranit くー町, , difference—type> public: friend class deque く—Ty, —A>; iterator ( ) : -First(0), -Last(0), -Next(0), -Map(0) { } iterator(—Tptr —p, —Mapptr —M) : —First(*—M) , ーも ast ( * ユ十—DEQUESIZ), reference 0EErator* ( ) const {return (*—Next); } —Tptr operator-> ( ) const {return ( &**this ) , iterator& operator 十十 ( ) {if (—Next ! = —Last & & 十十—Next = = —Last (—First = * 十十一 Ma 店 —Last = —First 十—DEQUESIZ; —Next = —First; } return (*this) , iterator operator 十十 ( int ) {iterator —Tmp = *this; 十十 *this; て e 加て n (-Tmp); } 土に e て a に or & operator—— ( ) {if (—Next ! = —First) --—Next; elSe if (—Map[-11 ! = 0 ) {—First = *--—Map; —Last = —First 十—DEQUESIZ; —Next = —Last - } return ( *this ) iterator operator—- ( int ) {iterator —Tmp = *this; -—*this; return (—Tmp); ) iterator& operator 十 =(difference—type —N) 106 C MAGAZINE 2000 9 return ( *this ) —Mapptr —Map; -Tptr —First , —Last, —Next; —Next = —First 十 (—Off - —Moff * —DEQUESIZ); —Last = —First 十—DEQUESIZ; —First = *—Map ー {—Map 十 = —MOff; e ー se if (—Moff = - ( (-DEQUESIZ - 1 - -Off) / -DEQUESIZ); ? —Off / —DEQUESIZ difference—type —Moff = ( 0 く = —Off) {difference-type -Off = —N 十—Next - —First; void —Add(difference—type —N) protected : {return い (*this く (x) ) bO 引 operator>= ( const iterator& —X ) const {return ()x く *this); } b00 ー operator> ( cons し iterator& —X ) const {return い ()x く *this) ); ) b00 ーて atO てく = ( const iterator& —X ) const Ⅱ—Map = = —X ・—Map & & —Next く—X. —Next); } {return (—Map く—X ・—Map b00 ー ope て atO てく ( const iterator& —X ) const {return い (*this = = (x) } b00 ー operator ! = ( const iterator& —X ) const {return (—Next = = —X. —Next); } b00 ー operator== ( const iterator& —X ) const {return (*(*this 十 (N)); } reference oper 0 て [ ] ( difference—type (N) const 十 (-Next - ー F 辷 ) 十 (-x. ユ ast - -x. —Next)); } : -DEQUESIZ * (—Map - —x ・—Map - 1 ) {return (—Map = = —X. —Map ? —Next - —X. —Next difference—type operator-(const iterator& (X) const return (-Tmp - = (N); ) {iterator —Tmp = *this; iterator operator-(difference—type (N) const return (-Tmp + = (N); ) {iterator —Tmp = *this; iterator 十 ( difference—type —N ) const {return ( 社 h + = --N); } iterator& operator-= ( difference—type —N )

plusl = 1. method(: + ) p plusl .type # = > M eth od p plusl. c 訓 ( 3 ) # = > 4 Method オプジェクトは Proc と同じよう に ca Ⅱで使うことができます。ただし , のオプジェクトは生成したときのレシーバ がずっと結び付いています。あまり使うこ とはありませんが , Ruby でメソッドをオプ ジェクトにする唯一の方法なので知ってお いて損はないでしよう。 プロックの使いみち Ruby1.4. x まではプロック付きで呼ばれ たかどうかを調べる関数として iterator ? だ けが提供されてきましたが , iterate しない のに iterator ? で検査するのは気持ち悪いと いう理由から , Ruby 1.5 以降では block ー given ? という関数も提供されるようになり ました。 よく見られる使いみち このようにプロックの使いみちはイテレ ータにかぎられるわけではありません。た のプロック引数にはレシーバ自身が渡され の要領で書きます。 とえば前述の List 11 で出てきた instance_e ます。 val などは繰り返さないわけです。大まか なお , Proc オプジェクトはアンパサンド 「 & 」を頭に付けて最後の引数に指定すれば にいって , 次のような用途に使われている [ 注 5 ] プロックとして渡ります。 ようです。 プライベートにせず , また instance eval で なく y 回 d を使い , プロック内で n. PRE と書 また , もっと詳しい分類があおきさん [ A 。 ] def f00 ; yield; end けば同等のことができます one = Proc. new{l} によって与えられているので , 興味のある p foo(&one) # = > 1 方はそちらもご覧ください。 与えられたプロックをそのまま渡す Method オブジェク ・繰り返し 与えられたプロックをそのまま別のメソ ッドに渡すには , List11 でやっているよう 本題とはズレますが , Proc が出てきたっ 各種 each や String#each—byte などです。 いでに Me 市面オプジェクトを紹介します。 おのおのの要素について行う処理をプロッ def methodl (argl , , argn, &block) クで渡すのが目的です。イテレータと呼ば Object#method というメソッドがあり , れは引数で指定されたシンポルに対応する れるのがこれです。 メソッドをオプジェクトとして返します。 ・手続きをバラメータとして渡す Object のメソッドなので , すべてのオプジ ェクトで使えます。 この分類に含まれるものとしては , Arra # ! /usr/bin/env ruby c ー ass Tree def initialize(val, *children) children = children. collect{lcl if c.is—a? Tree then 0 else Tree. new(c) end # 第 2 引数以降が子として登録される @val, @children = val, children end attr—reader :val def traverse(&block) instance-eval(&block) # @pre と @post を設定 @pre.call if @pre @children.each{lcl 0. traverse(&block) } @pos し ca Ⅱ if @post end private def PRE(&block); @pre = block; end def POST(&block); ② pos セ = oc 塒 end end # 例 : 木をインデントして表示 ” a21 % t = T て ee. れ ew に 4 ” , al"j Tree. new( ″ a2 ″ a22 # インデントのための深さ depth = 0 t.traverse dO ー司 PRE do ” *depth 響インデント print puts n. val # 子に行く前に depth を増やす depth 十 = 1 end POST do depth ー = 1 end end ふたつのプロックを渡す ( t 「 ee. 「 b ) # 子から戻ったら depth も元に meth0d2 (&block) end 112 C MAGAZINE 20 9

味深い間違いを見たことがあります。 List 9 がその抜粋で , プログラマの意図と異な る方法で意図した結果を出力していまし た。このプログラムは "b" を出力するもの ですが , 問題は each のプロックが何回実行 されるかです。 a の要素数が 3 だから 3 回と 思わせて , 0..3 は終端の 3 も含むから 0 , 1 , 2 , 3 で合計 4 回というのが答えかというと , それも違って , 驚くなかれ正解は 1 回です。 理解できない人は , each プロックのなかに 「 p i 」という 1 行を追加して , i に渡されるも のを確認してください。またわかった人は , List9 の # 1 から # 2 までをひとつのメソッドで れないのが不便に思うこともたまにありま めというわけではありません。 す。たとえば木を根からなぞる (traverse) 書く方法を考えてください。一方この回数 f00 bar { … } d0 … end これと関係してハッシュのリテラル引数 ときは , 子にいく前にする処理と , 子から が 1 回であることがわかったとたんに今度 はなぜ " b " を出力するのかわからなくなっ として渡す場合は引数を囲むカッコを省略 返ったときにする処理の両方を指定したい のが人情でしよう。 た人は Array クラスのマニュアルをじっく することはできません。 p { 1 = > 2 } # { 1 = > 2 } はプロックと こんな場合は , あきらめてふたつの Proc り読んでみましよう [ 注 4 ] 。 オプジェクトを渡すという方法も手です # 解釈されてエラー [ 注 4 ] こではややトリッキーな方法を紹介 そこで問題 , デバッグプリンタ p を使った が それでもわからない場合は , メーリングリ ストでの解題 [ 両 131 があります 次の # 1 と # 2 は何を出力するでしよう ? 答 します。 えは各自確かめてみてください。 やり方としては , イテレータに渡すプロ def f00 ( * x) ;[x, iterator?]; end ックのなかだけで使える特別なメソッド P プロック RE と POST を用意し , これらのメソッドで p f00 d0 1 end # 1 子にいく前の処理 (@pre ) と子から戻ったと pfoo { 1 } # 2 きの処理 ()p 。 st ) を登録します。このよう each と fo 「の違い do … end とに . } の違い なことを実現するひとつの方法はⅲ s ね nce ー プロックは do... end もしくは {. 」のいずれ eval の利用です。 Ruby にも for 文がありますが , これは eac List 11 では instance_eval を使ってプライ かで与えますが , 結合強度が異なります。 h を呼び出します。すなわち , 次のふたっ べートメソッド PRE POST を traverse のユ 次のふたつは互いに等価です。 はほば等価です。 ーザに , 事実上公開しています。あまりよく f00 bar do … end 0bj. each d0 川… end ないことかもしれませんが , イテレータ変 foo(bar)do … end fO 「 i in Obj; . end また次のふたつも互いに等価です。 異なるのは , スコープに関する点です。 数を何度も登場させるのがイヤなので [ 注 5 ] f00 bar {... } プロック変数やプロック内で初めて出てき ばくはときどきこうします。 PRE と POST たローカル変数は , プロックの外側では無 は与えられたプロックをそれぞれ @pre と f00 (bar{ … }) @post に代入するだけのメソッドとなって 一方 , 両方にプロックを渡す場合 , 効です。そのため , List 10 は # ! のところで います。利用例として木をインデントして NameError を起こします。 表示するためのコードを付けているのでお を次のように書くことはできません。 複数のプロックを渡せるか 試しください。 f00 bar { … } { … } # ! 工ラー なお , instance_eval に渡されるプロック ところで , プロックはひとっしか与えら ただし次の書き方は許されますが , お薦 プロックとスコープ ( fo ト each. 「 b ) # ! /usr/bin/env ruby a = [ 1 , 2 , 3 ] # 土は初出 fO て土 a # k も初出 end # ここで , i は有効 # k もまた有効 団 # j は初出 a. each do # m も初出 9 each のプロックは何回まわるか ? (howmany. 「 b) # ! /usr/bin/env ruby column = [ ] [0.. a. size] . each do c 引 n [ 幻 a[i] end p column[ll # 1 # ! j は無効なので例外 # ! これも例外 極めよ Ruby 道 111 伝授 !

血 I ・ d P. J. Plauger 熊谷典大訳 q の 質のいいライブラリは , 一度書くだけでで きるものではない。顧客から , 競合相手か ら , 場合によってはほかのプログラミング 言語から優れた技術を学ぶたびに書き換え 続けてゆかねばらならない。 はじめに lntro ducti on 私が Standard TempIate Library を本格的 に知ったのは 1994 年であった。 1993 年の暮 れに知ることができたかもしれないが , 19 93 年 11 月の C + + 標準化委員会で行われた川 ex Stepanov の発表を聞き逃した。 C + + 標準 仕様案に追加する新規機能については , 夜 間セミナーを開催していたが , 標準化を 19 年中に完了させるという計画にのっとり , 1993 年の初めの時点で , セミナーをやめる ことに全員が同意していた。しかし , どう いうわけだか訂 L の発表が行われた。私は 疲労半分怒り半分の状態で , Stepanov の講 演に出なかった ( その 4 年後に C + + の標準化 が完了したときには , 訂 L は重要な追加機 能となっていた ) 。 というわけで , 私が訂 L の本格的な勉強 を始めたのは , それが C + + 標準化仕様案に 強引に吸収されることが明らかになった 199 4 年の中ごろであった。私のテンプレートに 関する知識はそれまではほとんどなかった。 1993 年の初めに書き上げ , 以後 , 仕様案の 進展に合わせて改定していたライプラリで は , テンプレートの使用はその時点のコン パイラの状況に合わせてきわめて単純なレ ベルにとどめていた。そんな私に (Stepanov, Meng Lee , David Musser が Ada から C + + に L を変換する際に開発した ) とても単純と はいえないテンプレート技法に対する備え ができていなかったことは間違いない。単 純にいえば , 私は深みにはまってしまい , 急速な自習を何週間も続けることになって しまった。 ここで , L とは何であるかをもう一度 簡単に確認しておきたい。 STL は , Hewlet t-Packard Labs で Stepanov とレ e によって最 初に開発され , テンプレートクラスとテン プレート関数の包括的な集合として出発し た。それは , Stepanov( 現在は SGI に在籍 ) と Musser( いまも Rensslaer Polytechnic に 在籍 ) が初期の言語のうえで何年ものあい だ繰り返し作業を続けた成果であった。 訂 L の一部は汎用のコンテナの集合であ る。これは拡張可能なべクタ , リスト , 順 序木などの共通データ構造を実装したテン プレートクラスである。テンプレートによ り , これらのクラスは , ユーザが指定する どのような型でも , 列の要素として格納で きるように特殊化できる。十分な配慮で設 計され記述されていて , STL コンテナクラ スのカスタム版を自分で書くとしても , お そらくこれ以上のことはできないだろう。 訂 L のもうひとつの部分は , 整列 , 検索 , 並べ替えなど , 列の要素に対する共通の操 作を実装したアルゴリズムとテンプレート 関数の膨大な集合である。テンプレートに より , ユーザが指定するどのような要素型 に対してもコードを改変し適合できる。ア ルゴリズムはもっともよく知られたアプロ ーチをカプセル化する。これらの関数のひ とつのカスタム版を自分で書くとしても , おそらくこれ以上のことはできないだろう。 STL をひとつにまとめている糊が , 反復 子 (iterator) の概念である。これは , C 言語 や C + + 言語のオプジェクトボインタを一般 化したものである。反復子はコンテナから アルゴリズムを切り離す。反復子を使う関 数は , 自分がコンテナに格納された列上で 動作しているのか , 配列に格納された列上 で動作しているのか , それともファイルを 読み込んでその場で形成された列上で動作 しているのかを知る必要はない。反復子は 半ダースのカテゴリに分類される。これら のカテゴリの柔軟性は幅広い。アルゴリズ ムによっては , 一緒に指定された反復子の カテゴリにもっとも合うように挙動を適合 させるものがある。 コンテナ , アルゴリズム , 反復子が SPL のほとんどすべてを形成している。その結 果が , 一貫性と拡張性を兼ね備えたライプ ラリである。しかし , STL がどれほど目立 っとしても , STL は標準 C + + ライプラリ全体 のある一部分にすぎない ( 最近よく見るが , 標準ライプラリ全体を指すのに L を使う のは誤りである ) 。ライプラリの大部分が オプジェクト指向であるとしても , 、 L は オプジェクト指向ライプラリではないこと に注意してほしい。というよりは , ST L は一般化プログラミング (generic progra mming) の例であり , それ自体が十分強力 な , 再利用性に対する異なるアプローチで ある。 S 比は簡潔に使うこともできる。 Bjarne S ous 叩の記事にあるプログラム の例を示す (Bjarne Stroustrup, "Learning Standard C/C + + 103