Iterator

別名：イテレーター

一言でいうと

Iterator （イテレーター、反復子）は、振る舞いに関するデザインパターンの一つで、リスト、スタック、ツリーなどの実際のデータ表現を表に出さずにコレクションの要素を探索することができます。

問題

コレクションは、プログラミングで最も使われるデータ型の一つです。とは言っても、コレクションは、オブジェクトのグループを含むコンテナにすぎません。

ほとんどのクレクションは、要素を単純なリストにしまいます。しかし、いくつかは、スタック、ツリー、グラフその他の複雑なデータ構造に準拠しています。

コレクションの構造にかかわらず、他のコードがコレクションの要素を使えるように、要素にアクセスする何らかの方法が必要となります。同じ要素に何回もアクセスすることなく、順番に見ていく方法が必要です。

リストに基づくコレクションであれば、これは簡単な仕事のように聞こえるかもしれません。全部の要素に対してループを回せばすむ話です。でも、ツリーのような複雑なデータ構造の場合はどうしますか？たとえば、あるツリーに対し、深さ優先探索で今日は十分だとします。翌日になると、幅優先探索が必要となるかもしれません。そして翌週には、ツリーの任意の要素への直接アクセスのような違う要件が出てくるかもしれません。

コレクションにいくつもの探索アルゴリズムを追加していくと、効率的なデータの貯蔵という本来の目的が次第にぼやけてきます。また、ある種のアルゴリズムは、特定の用途向けにできているため、そのようなアルゴリズムを一般的なコレクションに含めるというのは、ちょっと変な話です。

一方、多くのコレクションと共に動作することになっているクライアント・コードにとっては、要素がどう格納されているかということは、どうでもいい話です。しかし、コレクションによって要素へのアクセス方法が異なるため、特定のコレクションのクラスに結合したコードを書くしかありません。

解決策

Iterator パターンの基本的な考え方は、コレクションに対する探索の振る舞いをイテレーター （反復子とも）と呼ばれるオブジェクトへ抽出することです。

イテレーターは様々な探索アルゴリズムを実装する。複数のイテレーター・オブジェクトは、同じコレクションを同時に探索可能。

アルゴリズム自体を実装することに加えて、イテレーター・オブジェクトは、現在位置、残数など詳細を一箇所にまとめます。このため、同一コレクション上を複数のイテレーターが、同時に、お互いに独立して、作業することができます。

通常、イテレーターにはコレクションの要素を取得するための主要なメソッドが一つあります。クライアントは、このメソッドが何も返さなくなるまで、このメソッドを実行し続けることができます。何も返さないということは、イテレーターが全要素を探索し終えたということを意味します。

すべてのイテレーターは同じインターフェースを実装する必要があります。これにより、クライアント・コードは、イテレーターが適切である限り、いかなるコレクション型とも、つまりいかなる探索アルゴリズムとも、互換性を維持できます。コレクションを探索する特別な方法が必要な場合は、コレクションやクライアントには手を加えずに、新しいイテレーターのクラスを作成するだけですみます。

現実世界でのたとえ

あなたは、数日間ローマを訪問し、その主な観光スポットすべてを訪問する予定です。しかし、到着してからぐるぐると円を描いて歩き回ると、多くの時間を無駄にしてしまい、コロッセオすら見つけられないかもしれません。

一方、ナビゲーションのためにスマートフォンの仮想ガイド・アプリを購入することもできます。それは賢くてしかも安く、自分の興味のある場所に好きなだけ長時間留まることを許してくれます。

第三の選択肢としては、旅行予算のいくらかを使って、自宅の裏庭のように市内を熟知している地元のガイドを雇うことです。ガイドは、あなたの好みに合わせてツアーを調整して名所を案内し、歴史や逸話を話してくれます。旅をもっと楽しくしてくれますが、残念ながら値段が張ります。

これらのオプション、つまり、カンを頼りに適当な方向へ行く、スマホのアプリ、人間のガイド、は、ローマにある数多い観光名所のコレクションに対するイタレーターと言えます。

構造

イテレーター （Iterator）インターフェースは、コレクションを探索するために必要な操作、つまり、次要素の獲得、現在位置の取得、探索のリセットなどを宣言します。
具象イテレーター （Concrete Iterator）は、コレクションを探索するための特定のアルゴリズムを実装します。イテレーター・オブジェクトは、探索の進行状況を独自に把握する必要があります。これにより、複数のイテレーターが同じコレクションを互いに独立して探索することができます。
コレクション （Iterable Collection）インターフェースは、コレクションと互換なイテレーターを取得するための一つまたは複数のメソッドを宣言します。具象コレクションが様々な種類のイテレーターを返せられるように、メソッドの戻り値型はイテレーター・インターフェースとして宣言されなければいけないことに注意してください。
具象コレクション （Concrete Collection）は、クライアントから要求があるたびに、特定の具象イテレーター・クラスの新インスタンスを返します。コレクションの残りのコードはどこにあるのだろう、と思ってませんか？大丈夫、同じクラスにあるはずです。このような細いことは実際のパターンにとっては重要ではないので、省略しているだけです。
クライアント （Client）は、コレクションとイテレーターの両方と、それぞれのインターフェースを介してやりとりをします。これにより、クライアントは具体的なクラスに結合されることなく、同じクライアント・コードで様々なコレクションやイテレーターを使用することができます。

多くの場合、クライアントは自分でイテレーターを作成することはせず、コレクションから取得します。しかし特別な場合、クライアントはイテレーターを直接作成できます。クライアントが専用の特殊イテレーターを定義した場合などです。

擬似コード

この例では、 Iterator パターンを使って、 Facebook のソーシャル・グラフへのアクセスを内包した特殊なコレクションを探索します。コレクションは、様々な方法でプロフィールを探索するイテレーターをいくつか提供します。

Iterator パターン例の構造 — ソーシャル・プロフィールの反復をする例。

createFriendsIterator の返す「友達」イテレーター、は、特定のプロフィールにある友達を渡り歩くために使用できます。 createCoworkerIterator の返す「同僚」のイテレーターは、同じ会社で働いていない友人は飛ばすことを除いて、同じことをします。両方のイテレーターは共通インターフェースを実装しており、認証や REST リクエストの送信などの実装状の詳細にかかわらず、クライアントはプロフィールを獲得できます。

クライアント・コードは、コレクションとイテレーターとインターフェースを介してのみやりとりするため、具体的なクラスに結合されていません。アプリを新しいソーシャル・ネットワークに接続すると決めたら、既存のコードを変更する必要はなく、新しいコレクションとイテレーター・クラスを作成するだけですみます。

// コレクション・インターフェースは、イテレーターを生成するためのファクト
// リー・メソッドを宣言しなければならい。プログラムに異なる種類の反復があ
// る場合は、複数のメソッドを宣言可能。
interface SocialNetwork is
    method createFriendsIterator(profileId):ProfileIterator
    method createCoworkersIterator(profileId):ProfileIterator


// 具象コレクションは、それが返す具象イテレーター・クラスと結合される。し
// かし、これらのメソッドのシグネチャーがイテレーター・インターフェースを
// 返すようになっているため、クライアントは具象イテレーターとは結合されな
// い。
class Facebook implements SocialNetwork is
    // …… コレクションのコードの大部分はここに ……

    // イテレーター作成コード。
    method createFriendsIterator(profileId) is
        return new FacebookIterator(this, profileId, "friends")
    method createCoworkersIterator(profileId) is
        return new FacebookIterator(this, profileId, "coworkers")


// すべてのイテレーターに共通のインターフェース。
interface ProfileIterator is
    method getNext():Profile
    method hasMore():bool


// 具象イタレーター・クラス。
class FacebookIterator implements ProfileIterator is
    // イテレーターは、探索対象のコレクションへの参照を必要とする。
    private field facebook: Facebook
    private field profileId, type: string

    // イテレーター・オブジェクトは、他のイテレーターとは独立してコレク
    // ションを探索する。そのため、探索の状態を保存する必要あり。
    private field currentPosition
    private field cache: array of Profile

    constructor FacebookIterator(facebook, profileId, type) is
        this.facebook = facebook
        this.profileId = profileId
        this.type = type

    private method lazyInit() is
        if (cache == null)
            cache = facebook.socialGraphRequest(profileId, type)

    // 各具象イテレーターのクラスは、共通イテレーター・インターフェースの
    // 独自の実装を行う。
    method getNext() is
        if (hasMore())
            result = cache[currentPosition]
            currentPosition++
            return result

    method hasMore() is
        lazyInit()
        return currentPosition < cache.length


// もうひとつ役に立つトリック：クライアント・クラスにコレクション全体への
// アクセスを与える代わりに、イテレーターを渡すことができる。こうすると、
// コレクションそのものをクライアントに露出する必要がなくなる。
//
// さらなる利点：実行時に異なるイテレーターを渡すことで、クライアントのコ
// レクションに対する動作を変更できる。これは、クライアント・コードが具象
// イテレーター・クラスと結合されていないために可能。
class SocialSpammer is
    method send(iterator: ProfileIterator, message: string) is
        while (iterator.hasMore())
            profile = iterator.getNext()
            System.sendEmail(profile.getEmail(), message)


// アプリケーションのクラスはコレクションとイテレーターを設定し、それらを
// クライアント・コードに渡す。
class Application is
    field network: SocialNetwork
    field spammer: SocialSpammer

    method config() is
        if working with Facebook
            this.network = new Facebook()
        if working with LinkedIn
            this.network = new LinkedIn()
        this.spammer = new SocialSpammer()

    method sendSpamToFriends(profile) is
        iterator = network.createFriendsIterator(profile.getId())
        spammer.send(iterator, "Very important message")

    method sendSpamToCoworkers(profile) is
        iterator = network.createCoworkersIterator(profile.getId())
        spammer.send(iterator, "Very important message")

適応性

コレクションが複雑なデータ構造をしており、その複雑さを（利便性やセキュリティー上の理由から）クライアントから隠したい場合、 Iterator パターンを使用します。

イテレーターは、複雑なデータ構造に対する作業の詳細を包み隠し、クライアントがいくつかの簡単なメソッドでコレクションの要素にアクセスできるようにします。このやり方はクライアントに対して便利なだけでなく、クライアントがコレクションと直接やりとりできたとしたら起きるかもしれない不注意、あるいは悪意による行為からコレクションを保護します。

アプリ全体の探索用コードの重複を減らすために、このパターンを使用します。

自明ではない反復アルゴリズムのコードは非常にかさばる傾向があります。アプリのビジネス・ロジック内に配置すると、元のコードの責任を曖昧にし、保守性を低下させる可能性があります。探索コードを指定されたイテレーターに移動することにより、アプリケーションのコードがより無駄がなくクリーンになります。

コードが異なるデータ構造を探索できるようにしたい場合や、これらの構造体の型が事前にわからない場合に、 Iterator を使用します。

このパターンはコレクションとイテレーターの両方に対していくつかの汎用インターフェースを提供します。コードがこれらのインターフェースを使用していれば、これらのインターフェースを実装する様々な種類のコレクションやイテレーターを渡しても問題なく動作します。

実装方法

イテレーター・インターフェースを宣言します。少なくとも、コレクションから次の要素を獲得するためのメソッドを持つ必要があります。しかし、利便性を考え、前要素の獲得、現在位置の確認、探索終了チェックなど、いくつかの他のメソッドを追加することもできます。
コレクションのインターフェースを宣言し、イテレーター取得メソッドを記述します。戻り値の型はイテレーター・インターフェースにする必要があります。いくつかの異なるイテレーターを作る予定の場合は、似たようなメソッドをいくつか宣言してもかまいません。
イテレーターで探索したいコレクションに対して具象イテレーター・クラスを実装します。イテレーター・オブジェクトはコレクションのインスタンス一つとリンクされている必要があります。通常、このリンクはイテレーターのコンストラクターを介して確立されます。
コレクション・インターフェースを実装してコレクション・クラスを作成します。基本的な考え方としては、特定のコレクション・クラス用に調整されたイテレーターを作成するための近道をクライアントに提供するということです。コレクション・オブジェクトは、イテレーターのコンストラクターに自身を渡して、リンクを確立する必要があります。
クライアント・コードを見渡して、すべてのコレクションの探索コードをイテレーターの使用に置き換えます。クライアントは、コレクション要素を反復する必要があるたびに、新しいイテレーター・オブジェクトを獲得します。

長所と短所

単一責任の原則。かさばる探索アルゴリズムを別クラスに抽出することにより、クライアント・コードとコレクションの整理整頓が可能。
開放閉鎖の原則。新しい種類のコレクションとイテレーターを実装し、既存のコードに問題なく渡すことが可能。
各イテレーター・オブジェクトが自身の反復状態を持っているため、同じコレクションを平行して反復可能。
同じ理由で、反復を一時中断して必要な時に再開することが可能。

アプリが単純なコレクションとのみ動作する場合、このパターンの適用は行き過ぎの可能性。
特定の特殊なコレクションの場合、イテレーターの使用は、要素を直接見て行くよりも非効率な可能性。

他のパターンとの関係

Iterators を使用して Composite ツリーを探索することができます。
Factory Method を Iterator と一緒に使って、コレクションのサブクラスが、コレクションと互換な、異なる型のイテレーターを返すようにできます。
現在の反復状態を獲得し、必要に応じてロールバックするために、 Memento を Iterator と一緒に使用できます。
複雑なデータ構造を探索し、その要素に対してある操作を実行するために、 Visitor を Iterator と一緒に使用することができます。要素のクラスが全部異なっていてもかまいません。