WYPRZEDAŻ ZIMOWA TRWA!

Iterator

Znany też jako: Kursor

Cel

Iterator to behawioralny wzorzec projektowy, pozwalający sekwencyjnie przechodzić od elementu do elementu jakiegoś zbioru bez konieczności eksponowania jego formy (lista, stos, drzewo, itp.).

Wzorzec projektowy Iterator

Problem

Kolekcje są jednym z najpopularniejszych typów danych wśród programistów, mimo że są to po prostu kontenery przechowujące grupy obiektów.

Różne rodzaje kolekcji

Różne rodzaje kolekcji.

Większość kolekcji przechowuje swoje elementy w prostych listach, ale niektóre są zbudowane w oparciu o stosy, drzewa, grafy i inne złożone struktury.

Jednak niezależnie od struktury kolekcji musi ona udostępniać dostęp do swoich elementów tak, aby można było używać ich gdzie indziej w programie. Powinien istnieć jakiś sposób przejścia po każdym elemencie kolekcji bez konieczności powtórnego dostępu do jakiegoś elementu.

Wydaje się to łatwe, jeśli mamy do czynienia z kolekcją ustrukturyzowaną w formie listy. Tworzymy pętlę przechodzącą po elementach i gotowe. Ale jak przejść sekwencyjnie, element po elemencie, przez złożoną strukturę, jak np. drzewo? Na początku być może wystarczy poruszanie się w głąb, ale kolejnego dnia pojawi się wymóg przechodzenia wszerz. Jeszcze później okazuje się, że przydałaby się możliwość losowego dostępu do dowolnego elementu drzewa.

Różne algorytmy sekwencyjnego poruszania się

Zawartość tej samej kolekcji można przejrzeć na wiele różnych sposobów.

Dodawanie kolejnych algorytmów przechodzenia przez kolekcję stopniowo przyćmiewa jej główne zadanie, którym jest efektywne przechowywanie danych. Ponadto niektóre algorytmy mogą być zoptymalizowane pod kątem konkretnego zastosowania, więc włączanie ich do uogólnionej klasy kolekcji byłoby dziwne.

Z drugiej strony, kod klienta który ma za zadanie działać na różnych kolekcjach może nawet nie być zainteresowany sposobem w jaki przechowują one elementy. Jednak skoro wszystkie kolekcje udostępniają różne sposoby dostępu do swoich elementów, to nie ma innego wyjścia, niż związać swój kod z klasą konkretnej kolekcji.

Rozwiązanie

Główną ideą wzorca Iterator jest ekstrakcja zadań związanych z przechodzeniem przez elementy kolekcji do osobnego obiektu zwanego iteratorem.

Iteratory implementują różne algorytmy sekwencyjnego dostępu.

Iteratory implementują różne algorytmy sekwencyjnego dostępu do kolejnych elementów. Wiele obiektów iterator może przeskakiwać po elementach jednej kolekcji jednocześnie.

Oprócz implementowania samego algorytmu, obiekt iteratora hermetyzuje wszystkie szczegóły sposobu przechodzenia przez kolejne elementy, jak bieżąca pozycja, czy ilość pozostałych elementów. Dzięki temu wiele iteratorów może jednocześnie przeglądać tę samą kolekcję, niezależnie od siebie.

Zazwyczaj, iteratory udostępniają jedną główną metodę pobierającą elementy kolekcji. Klient może wywoływać ją raz za razem aż przestanie ona zwracać kolejne obiekty, co oznacza osiągnięcie końca zbioru.

Wszystkie iteratory muszą implementować ten sam interfejs. Czyni to kod klienta kompatybilnym z dowolną kolekcją czy algorytmem przechodzenia o ile istnieje odpowiedni iterator. Jeśli potrzebny jest specjalny sposób przeglądania kolekcji, można stworzyć nową klasę iteratora, bez konieczności dokonywania zmian w kolekcji lub w kodzie klienta.

Analogia do prawdziwego życia

Różne sposoby zwiedzania Rzymu

Różne sposoby zwiedzania Rzymu.

Zamierzasz odwiedzić Rzym na parę dni i zwiedzić wszystkie najważniejsze miejsca i atrakcje turystyczne. Ale na miejscu łatwo zmarnować sporo czasu chodząc w kółko, nie mogąc znaleźć nawet Koloseum.

Z drugiej strony, można kupić aplikację wirtualnego przewodnika na smartfon i nawigować z jej pomocą. Sprytne i niedrogie, a dodatkowo można zatrzymać się przy dowolnym miejscu na ile się chce.

Trzecia alternatywa to poświęcenie części swojego wycieczkowego budżetu na wynajęcie przewodnika który zna miasto jak własną kieszeń. Przewodnik mógłby dostosować trasę wycieczki do twoich preferencji, pokazać wszystko co najciekawsze i opowiedzieć wiele ciekawych historii. Byłoby miło, ale również i drożej.

Wszystkie te opcje — losowo obrane kierunki, smartfonowy przewodnik i wynajęty przewodnik — stanowią iteratory pozwalające na dostęp do wielkiej kolekcji widoków i atrakcji Rzymu.

Struktura

Struktura wzorca projektowego IteratorStruktura wzorca projektowego Iterator
  1. Interfejs Iterator deklaruje działania niezbędne do sekwencyjnego przechodzenia przez elementy kolekcji: pobieranie kolejnego elementu, ustalenie bieżącej pozycji, powrót do pierwszego elementu, itp.

  2. Konkretne Iteratory implementują specyficzne algorytmy przeglądania kolekcji. Obiekt iterator powinien samodzielnie śledzić postęp tego procesu. Pozwala to wielu iteratorom na jednoczesne przeglądanie tej samej kolekcji.

  3. Interfejs Kolekcja deklaruje jedną lub więcej metod służących kompatybilności kolekcji z iteratorami. Zwracany typ metody musi być zadeklarowany jako interfejs iterator, aby konkretne kolekcje mogły zwracać różne rodzaje iteratorów.

  4. Konkretne Kolekcje zwracają nowe instancje konkretnych klas iteratorów za każdym razem gdy klient ich zażąda. Pewnie ciekawi cię gdzie jest reszta kodu kolekcji? Nie martw się, powinien znajdować się w tej samej klasie. Po prostu te szczegóły nie są istotne dla konkretnego wzorca, więc je pomijamy.

  5. Klient współpracuje zarówno z kolekcjami jak i iteratorami za pośrednictwem ich interfejsów. Dzięki temu nie jest sprzężony z konkretnymi klasami, pozwalając na pracę z różnymi kolekcjami i operatorami w tym samym kodzie klienta.

    Zazwyczaj klienci nie tworzą iteratorów sami, lecz otrzymują je od kolekcji. Ale w pewnych przypadkach klient może stworzyć iterator bezpośrednio — na przykład gdy sam definiuje swój specjalny iterator.

Pseudokod

W poniższym przykładzie, wzorzec Iterator służy przejściu przez specjalny typ kolekcji, który hermetyzuje dostęp do diagramu relacji pomiędzy profilami na Facebooku. Kolekcja udostępnia wiele iteratorów które mogą przeglądać kolejne profile na różne sposoby.

Struktura przykładu użycia wzorca Iterator

Przykład iteracji po kolejnych profilach użytkowników.

Iterator przyjaciele może służyć przeglądaniu zaprzyjaźnionych profili danej osoby. Współpracownicy robi to samo, ale pomija osoby które nie pracują wraz ze wskazaną osobą. Oba iteratory implementują wspólny interfejs który pozwala klientom pobierać profile bez zagłębiania się w szczegóły implementacyjne takie jak uwierzytelnianie, czy wysyłanie żądań REST.

Kod klienta nie jest sprzężony z konkretnymi klasami, ponieważ współpracuje z kolekcjami i iteratorami wyłącznie za pośrednictwem interfejsów. Jeśli postanowisz połączyć swoją aplikację z nowym portalem społecznościowym, musisz jedynie dostarczyć odpowiednie klasy kolekcji i iteratora, bez konieczności dokonywania zmian istniejącego kodu.

// Interfejs kolekcja musi deklarować metodę wytwórczą do
// produkowania iteratorów. Można zadeklarować wiele metod jeśli
// potrzebujesz kilku różnych sposobów iterowania.
interface SocialNetwork is
    method createFriendsIterator(profileId):ProfileIterator
    method createCoworkersIterator(profileId):ProfileIterator


// Każda konkretna kolekcja jest powiązana z zestawem
// konkretnych klas iteratorów jakie zwraca. Ale klient nie jest
// z nimi powiązany, bo sygnatury tych metod zwracają typ
// interfejs iteratora.
class Facebook implements SocialNetwork is
    // ... Większość kodu kolekcji powinna znaleźć się tutaj ...

    // Kod kreacyjny iteratora.
    method createFriendsIterator(profileId) is
        return new FacebookIterator(this, profileId, "friends")
    method createCoworkersIterator(profileId) is
        return new FacebookIterator(this, profileId, "coworkers")


// Wspólny interfejs wszystkich iteratorów.
interface ProfileIterator is
    method getNext():Profile
    method hasMore():bool


// Konkretna klasa iteratora.
class FacebookIterator implements ProfileIterator is
    // Iterator potrzebuje odniesienia do kolekcji po elementach
    // której ma przechodzić.
    private field facebook: Facebook
    private field profileId, type: string

    // Obiekt iteratora przechodzi po elementach kolekcji
    // niezależnie od innych iteratorów. Dlatego musi
    // przechowywać stan iteracji.
    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)

    // Każda konkretna klasa iteratora posiada własną
    // implementację wspólnego interfejsu iteratora.
    method getNext() is
        if (hasMore())
            result = cache[currentPosition]
            currentPosition++
            return result

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


// Oto kolejna użyteczna sztuczka: możesz przekazać iterator
// klasie klienckiej zamiast dawać jej dostęp do całej kolekcji.
// Dzięki temu nie trzeba eksponować całej kolekcji klientowi.
//
// Kolejna zaleta takiego podejścia to możliwość zmiany sposobu
// w jaki klient współpracuje z kolekcją w trakcie działania
// programu poprzez przekazanie klientowi innego iteratora. Jest
// to możliwe ponieważ kod klienta nie jest sprzęgnięty z
// konkretnymi klasami iteratora.
class SocialSpammer is
    method send(iterator: ProfileIterator, message: string) is
        while (iterator.hasMore())
            profile = iterator.getNext()
            System.sendEmail(profile.getEmail(), message)


// Klasa aplikacji konfiguruje kolekcje i iteratory, a następnie
// przekazuje je kodowi klienta.
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")

Zastosowanie

Stosuj wzorzec Iterator gdy kolekcja z którą masz do czynienia posiada skomplikowaną strukturę, ale zależy ci na ukryciu jej przed klientem (dla wygody, lub dla bezpieczeństwa).

Iterator hermetyzuje szczegóły współpracy ze złożonymi strukturami danych, dając klientowi pewną liczbę prostych metod służących dostępowi do elementów kolekcji. To podejście jest dla klienta wygodne, ale również chroni kolekcję przed nieuważnym lub złośliwym działaniem, którego ryzyko istnieje przy bezpośredniej pracy ze strukturą.

Stosuj wzorzec w celu redukcji duplikowania kodu przeglądania elementów zbiorów na przestrzeni całego programu.

Kod nietrywialnych algorytmów iteracji bywa obszerny. Gdy umieści się go w ramach logiki biznesowej aplikacji, zwykle zaciera główną odpowiedzialność pierwotnego kodu i czyni go trudniejszym do utrzymania. Przeniesienie kodu przeglądania elementów do stosownych iteratorów pomaga uczynić kod aplikacji czystszym i prostszym.

Stosuj Iterator gdy chcesz, aby twój kod był w stanie przeglądać elementy różnych struktur danych, lub gdy nie znasz z góry szczegółów ich struktury.

Wzorzec Iterator udostępnia parę ogólnych interfejsów zarówno kolekcji, jak i iteratorów. Skoro twój kod korzysta z tych interfejsów, to będzie nadal działał, nawet gdy przekażesz mu różne rodzaje kolekcji i iteratorów, o ile implementują te interfejsy.

Jak zaimplementować

  1. Zadeklaruj interfejs iteratora. W najprostszym przypadku musi posiadać metodę pobierającą kolejny element kolekcji. Ale dla wygody możesz dodać parę innych metod, np. do pobierania poprzedniego elementu, śledzenia bieżącej pozycji i ustalenia końca procesu iteracji.

  2. Zadeklaruj interfejs kolekcji i opisz metodę pobierającą iteratory. Typ zwracany przez metodę powinien być zgodny z interfejsem iteratora. Możesz zadeklarować podobne metody, jeśli zamierzasz mieć wiele różnych grup iteratorów.

  3. Zaimplementuj konkretne klasy iterator dla kolekcji które powinny być możliwe do przeglądania za pomocą iteratorów. Obiekt iterator musi być powiązany z jedną instancją kolekcji. Zazwyczaj tworzy się takie powiązanie w konstruktorze iteratora.

  4. Zaimplementuj interfejs kolekcji w swoich klasach kolekcji. Główną ideą jest udostępnienie klientowi skrótu do tworzenia iteratorów optymalnych dla danej klasy kolekcji. Obiekt kolekcji musi przekazywać siebie samego do konstruktora iteratora aby stworzyć między nimi powiązanie.

  5. Przejrzyj swój kod klienta i zamień cały kod przeglądania kolekcji na wykorzystujący iteratory. Klient pobiera nowy obiekt iteratora za każdym razem gdy chce przejrzeć zawartość kolekcji.

Zalety i wady

  • Zasada pojedynczej odpowiedzialności. Można uprzątnąć kod klienta i kolekcje, ekstrahując obszerny kod przeglądania do osobnych klas.
  • Zasada otwarte/zamknięte. Można zaimplementować nowe typy kolekcji i iteratorów oraz przekazywać je do istniejącego kodu bez psucia czegokolwiek.
  • Można przeglądać tę samą kolekcję równolegle wieloma iteratorami, gdyż każdy z nich przechowuje informacje o swoim stanie.
  •  Z powyższego powodu można opóźniać iterację i kontynuować ją gdy zachodzi taka potrzeba.
  • Zastosowanie tego wzorca będzie przesadą jeśli twoja aplikacja korzysta wyłącznie z prostych kolekcji.
  • Używanie iteratora może być mniej efektywne niż bezpośrednie przejście po elementach jakiejś wyspecjalizowanej kolekcji.

Powiązania z innymi wzorcami

  • Iteratory służą do sekwencyjnego przemieszczania się po drzewie Kompozytowym element po elemencie.

  • Możesz zastosować Metodę wytwórczą wraz z Iteratorem aby pozwolić podklasom kolekcji zwracać różne typy iteratorów kompatybilnych z kolekcją.

  • Można zastosować Pamiątkę wraz z Iteratorem by zapisać bieżący stan iteracji, co pozwoli w razie potrzeby do niego powrócić.

  • Połączenie Odwiedzającego z Iteratorem może służyć sekwencyjnemu przeglądowi elementów złożonej struktury danych i wykonaniu na nich jakiegoś działania, nawet jeśli te elementy są obiektami różnych klas.

Przykłady kodu

Iterator w języku C# Iterator w języku C++ Iterator w języku Go Iterator w języku Java Iterator w języku PHP Iterator w języku Python Iterator w języku Ruby Iterator w języku Rust Iterator w języku Swift Iterator w języku TypeScript