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 )

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