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とか書いてしまうと、ListSkipListに変えたときの変更範囲が大きくなってしまう
    • これを避けるために、ListSkipListCreataIterator()メソッドを持たせ、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
  • 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を複製する

      • 高コスト
    • aggregateiteratorを修正させる

      • 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 でも大丈夫

IteratorAggregateに特権アクセスをもちうる

  • ConcreteIteratorConcreteAggregateとは密結合
  • ConcreteIteratorの実装をシンプルにするために、
    ConcreteAggregateにヘルパメソッドを持たせたいことがある
  • しかし、そのためだけにConcreteAggregateの公開インターフェースを太らせるのは嫌
  • C++ならfriendで解決可能

    • 前述のヘルパメソッドはprotectedにしておく
    • friendからは見える

Compositeの走査

  • 再帰呼び出しのコールスタックを上手に使うとよい
  • 木構造では、さまざまな走査方法がある

    • 先行順
    • 後行順
    • 中間順
    • 幅優先

      • 【所感】こいつだけコールスタックじゃ対応できなそう

NullIterator — 番兵

  • IsDone()が常にtrueになるようなIterator
  • 例えばCompositeの葉ノードのCreateIterator()nullIteratorオブジェクトを返すようにするとコードがシンプルになる

関連するパターン

  • Composite

    • 木の走査
  • FactoryMethod

    • Polymorphic Iteratorを実現するうえで利用
  • Memento

    • Iteratorに「現在の要素」状態を持たせる際に利用

英語

  • obviate

    • 困難などを除去する
  • mitigate

    • 苦痛などをやわらげる