勉強日記

チラ裏

GoF本 Iterator

デザインパターン 勉強メモ GoF

ねらい

  • 要素の集合体(以下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を包む実装が紹介されていた
  • 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
    • 苦痛などをやわらげる