ねらい
- 要素の集合体(以下
Aggregate
とする。配列、線形リスト、木など)について、内部表現を意識せずに要素を走査したい
AKA
Cursor
モチベーション
Aggregate
の内部表現を意識せずに要素を走査したい-
走査の方法はいろいろある
- 順方向
- 逆方向
- etc.
- 走査の方法を増やすたびに
Aggregate
クラスのインターフェースが肥大化するのはよくない -
走査に関する責務を分離 —
Iterator
クラス- 現在どの要素まで走査したか、という状態を保持する
-
下記のようなメソッドを提供する
First()
走査の初期化処理。
「最初の」要素にカーソルを当てるCurrentItem()
現在カーソルが指している要素を返すNext()
カーソルを進める-
IsDone()
- 全部走査したか否かを返す
- 「現在の要素」という状態が
iterator
オブジェクトに外出しされるため、
同一のaggregate
について1つの走査を保留して別の走査を始めることもできる
-
走査の種類を増やすには、
Iterator
クラスを派生して実現するAggregate
クラスのインターフェースが太らない- 「順方向」「逆方向」といった種類を問わず、「走査」として一様に扱える
-
Polymorphic Iteration
Aggregate
クラスと、対応するIterator
クラスとは密結合する- 例えば
List
にはListIterator
SkipList
にはSkipListIterator
が対応する - クライアントコードに
ListIterator
とか書いてしまうと、List
をSkipList
に変えたときの変更範囲が大きくなってしまう -
これを避けるために、
List
やSkipList
にCreataIterator()
メソッドを持たせ、Iterator
の生成の責務を負わせるとよい- Factory Method Pattern
つかいどころ
- 要素の集合体(配列、線形リスト、木など)について、内部表現を意識せずに要素を走査したい
- 複数の種類の走査をサポートしたい
- Polymorphic Iterationをサポートしたい
構造
あとでかくかも
登場人物
-
Iterator
-
要素アクセス・走査のメソッドを定義するインターフェース
First()
CurrentItem()
Next()
IsDone()
-
-
ConcreteIterator
Iterator
の実装クラス- 「現在の要素」という状態を保持
-
Aggregate
-
Iterator
の生成メソッドを定義するインターフェースIterator* CreateIterator()
-
-
ConcreteAggregate
-
Aggregate
の実装クラスArray
List
BinaryTree
- …
CreateIterator()
をoverrideし、対応するConcreteIterator
を生成する
-
クライアントコードからの利用
aggregate
オブジェクトにiterator
オブジェクトを作らせる-
iterator
オブジェクトを利用し、要素アクセス・走査を行う-
external iteratorの場合、走査の制御はクライアントコードが行う
for (iterator->First(); !iterator->IsDone(); iterator->Next()) { /* ... */ }
とか書くのはクライアントコード側、ということ
-
実装にあたり考えるべきこと
いっぱいある
Iteratorの分類 — External/Internal
分類 | external iterator | internal iterator |
---|---|---|
走査の制御 | クライアントコード | Iterator自身 |
要素を処理する手続き | for文の中に記述 | 高階メソッドに関数を渡す等 |
柔軟性 | 高い | 低い 例) 2つのaggregateの相等性チェックが困難 |
簡便性 | 低い 似たようなfor制御文を毎回書かされる |
高い |
-
Internal IteratorでExternal Iteratorを包む実装が紹介されていた
- External Iterator:
Iterator
- Internal Iterator:
Traverser
- External Iterator:
-
C++など、関数が第一級オブジェクトでない言語では、
Traverser
の高階メソッド(ForEach
とか)に関数を渡す方法は不便-
関数に副作用を持たせる場合、状態を保持する方法としてstatic変数くらいしか実現方法がない
- 同時に2つの走査で使えなくなってしまう
-
-
そういう場合は、
Traverser
に要素を処理するメソッドvirtual ProcessItem(const Item&)
をもたせ、派生クラスでoverrideするとよいtraverser
オブジェクトが、インスタンス変数として状態を保持する- Template Method pattern
- 【所感】
ProcessItem()
の実装ごとにTraverser
クラスを派生するのはやめたほうがいい。
Command Patternを適用して「実行可能な第一級オブジェクト」を作り、高階メソッドの方法をとるべきだろう
TODO
気が向いたらクラス図書く
走査アルゴリズムをどのクラスに定義するか
-
ConcreteAggregate
-
この場合、
Iterator
は単に「現在の要素」状態を保持するだけとなるCursor
と呼ばれることがある
- クライアントコードは、
aggregate->Next(cursor);
という具合に走査を制御する
-
-
ConcreteIterator
- 同一の
ConcreteAggregate
に対して、異なる走査アルゴリズムを実装するのが容易になる - 同一の走査アルゴリズムを、異なる
ConcreteAggregate
に対して実装するのが容易になる ConcreteAggregate
のカプセル化を壊してしまいがち
- 同一の
どれだけ堅牢にするか
-
iterator
での走査中にaggregate
の要素の追加削除を行うのは危険- 2重走査、要素のスキップ、out of bounds等を誘起する
-
解決策
-
aggregate
を複製する- 高コスト
-
aggregate
にiterator
を修正させるaggegate
は、生成したiterator
を覚えておくaggerate
は要素の追加・削除の折に、iterator
をいい感じに修正する
-
走査のメソッドの追加
-
あると便利そうなやつ
Prev()
SkipTo()
-
【所感】Aggegateの実装によってはコスト高い or 不可能
- 単方向線形リストとか
Iteratorの後始末
- C++でPolymorphic Iteratorを実現するには、
iterator
オブジェクトをIterator*
に受ける必要がある iterator
オブジェクトはnewしてヒープ上に積む必要がある-
すると、delete漏れが起こりがち
- 忘れる
- deleteを通らないコードパスができる
- 例外でstack unwindしちゃう
-
Proxy Patternを適用し、スマートポインタで包むことでこれを防ぐ
-
いわゆる RAII: Resource Acquisizion Is Initialization というやつ
- GoF本執筆当時は Resource Allocation Is Ininialization と言った模様
-
スマートポインタ自体は必ずstack上に積むようにする
- new, deleteをprivateにすればよい
- スマートポインタのコンストラクタ内で
iterator
をnew -
スマートポインタのデストラクタ内で
iterator
をdelete- 2重deleteされないように、コピーコンストラクタやコピー代入をprivateにすること
-
スタック上のオブジェクトは、スコープを抜ける際に必ずデストラクタで解体される
- 例外による stack unwinding でも大丈夫
-
Iterator
はAggregate
に特権アクセスをもちうる
ConcreteIterator
とConcreteAggregate
とは密結合ConcreteIterator
の実装をシンプルにするために、
ConcreteAggregate
にヘルパメソッドを持たせたいことがある- しかし、そのためだけに
ConcreteAggregate
の公開インターフェースを太らせるのは嫌 -
C++ならfriendで解決可能
- 前述のヘルパメソッドはprotectedにしておく
- friendからは見える
Compositeの走査
- 再帰呼び出しのコールスタックを上手に使うとよい
-
木構造では、さまざまな走査方法がある
- 先行順
- 後行順
- 中間順
-
幅優先
- 【所感】こいつだけコールスタックじゃ対応できなそう
NullIterator — 番兵
IsDone()
が常にtrue
になるようなIterator
- 例えばCompositeの葉ノードの
CreateIterator()
はnullIterator
オブジェクトを返すようにするとコードがシンプルになる
関連するパターン
-
Composite
- 木の走査
-
FactoryMethod
- Polymorphic Iteratorを実現するうえで利用
-
Memento
- Iteratorに「現在の要素」状態を持たせる際に利用
英語
-
obviate
- 困難などを除去する
-
mitigate
- 苦痛などをやわらげる