Iterator

Iterator – obiekt pozwalający na sekwencyjny dostęp do wszystkich elementów lub części zawartych w innym obiekcie, zwykle kontenerze lub liście. Iterator jest czasem nazywany kursorem, zwłaszcza w zastosowaniach związanych z bazami danych.

Opis

Iterator można rozumieć jako rodzaj wskaźnika udostępniającego dwie podstawowe operacje: odwołanie się do konkretnego elementu w kolekcji (dostęp do elementu) oraz modyfikację samego iteratora tak, by wskazywał na kolejny element (sekwencyjne przeglądanie elementów). Musi także istnieć sposób utworzenia iteratora tak, by wskazywał na pierwszy element, oraz sposób określenia, kiedy iterator wyczerpał wszystkie elementy w kolekcji. W zależności od języka i zamierzonego zastosowania iteratory mogą dostarczać dodatkowych operacji lub posiadać różne zachowania.

Podstawowym celem iteratora jest pozwolić użytkownikowi przetworzyć każdy element w kolekcji bez konieczności zagłębiania się w jej wewnętrzną strukturę. Pozwala to kolekcji przechowywać elementy w dowolny sposób, podczas gdy użytkownik może traktować ją jak zwykłą sekwencję lub listę. Klasa iteratora jest zwykle projektowana wraz z klasą odpowiadającej mu kolekcji i jest z nią ściśle powiązana. Zwykle to kolekcja dostarcza metod tworzących iteratory.

Porównanie z indeksowaniem

W językach proceduralnych do iteracji po wszystkich elementach sekwencji, np. tablicy, zwykle używa się indeksowania. Choć podejście to da się zastosować do niektórych kontenerów obiektowych, stosowanie iteratorów może mieć swoje zalety.

• Pobieranie elementów przez indeks może być nieodpowiednie dla niektórych struktur danych, zwłaszcza dla struktur bez swobodnego dostępu lub z powolnym dostępem, jak listy czy struktury drzewiaste.

• Iteratory mogą dostarczać jednorodnego sposobu na iterowanie po strukturach danych wszystkich rodzajów, tym samym czyniąc kod bardziej czytelnym, uniwersalnym i mniej wrażliwym na zmiany w strukturze danych.

• Iterator może nakładać dodatkowe ograniczenia na dostęp, np. uniemożliwiając pominięcie elementów lub powtórny dostęp do wcześniej odwiedzonych elementów.

• Iterator może pozwolić na modyfikację kolekcji bez zaburzania (inwalidacji) iteracji. Na przykład po przejściu za pierwszy element może on umożliwiać wstawianie nowych elementów na początek kolekcji z przewidywalnymi skutkami. Jest to problematyczne w wypadku indeksowania, gdyż trzeba zmodyfikować zmienne indeksowe.

Zdolność kontenera do bycia modyfikowanym w trakcie iteracji po jego elementach stało się konieczne w nowoczesnym programowaniu obiektowym, gdzie zależności pomiędzy obiektami i skutkami operacji mogą nie być oczywiste. Użycie iteratora izoluje od tego rodzaju problemów.

Iteratory domyślne

Niektóre języki obiektowe, np. Perl czy Python posiadają wbudowane mechanizmy iteracji po elementach kontenera bez wprowadzania jawnego obiektu iteratora. Przejawia się to zwykle istnieniem jakiegoś rodzaju operatora for-each, jak w poniższych przykładach:

# Perl, iteracja wbudowana
foreach $val (@list) {
    print "$val\n";
}

# Python, iteracja wbudowana
for Value in List:
    print Value

W języku C++ występuje także szablon funkcji std::for_each() pozwalający na podobną iterację, wymaga jednak podania jawnego obiektu iteratora na wejściu.

Generatory

Generator jest specjalnym rodzajem iteratora, w którym kontener nie jest kompletny. Pozwala to na przetwarzanie element po elemencie kolekcji abstrakcyjnych lub nawet nieskończonych. Generatory są powszechne w językach funkcyjnych oraz w językach, które zapożyczają niektóre idee programowania funkcyjnego. Generatory często implementuje się jako kontynuacje.

Iteratory w różnych językach programowania

C++

W C++ iteratory są szeroko wykorzystywane w bibliotece STL. Wszystkie standardowe szablony kontenerów dostarczają bogatego i spójnego zestawu iteratorów. Składnia standardowych iteratorów została zaprojektowana tak, by przypominała składnię zwykłej arytmetyki na wskaźnikach w C, gdzie do wskazania elementu, na który wskazuje iterator używa się operatorów * i ->, a operatory arytmetyki wskaźnikowej takie, jak ++ przesuwają iterator do następnego elementu.

Iteratory stosuje się zwykle w parach, gdzie jeden jest używany do właściwej iteracji, zaś drugi oznacza koniec kolekcji. Iteratory tworzone są przez odpowiadający im kontener standardowymi metodami, takimi jak begin() i end(). Iterator zwrócony przez begin() wskazuje na pierwszy element, podczas gdy iterator zwrócony przez end() wskazuje na pozycję za ostatnim elementem kontenera

Gdy iterator przejdzie za ostatni element, jest on z definicji równy specjalnej wartości iteratora końcowego. Poniższy przykład pokazuje typowe użycie iteratora:

ContainerType C; // Dowolny standardowy typ kontenera, np. std::list<sometype>
ContainerType::iterator A = C.begin();
ContainerType::iterator Z = C.end();
while (A != Z) {
    ContainerType::value_type value = *A;
    std::cout << value << std::endl;
    ++A;
}

Istnieje wiele rodzajów iteratorów o różnych zachowaniach, w tym: przesuwające się do przodu, wstecz oraz dwukierunkowe; iteratory o swobodnym dostępie; iteratory wejściowe i wyjściowe; wreszcie iteratory stałe, zabezpieczające kontener lub jego elementy przed modyfikacją. Nie każdy typ kontenera obsługuje każdy typ iteratora. Użytkownicy mogą tworzyć własne typy iteratorów przez dziedziczenie klas ze standardowego szablonu klasy std::iterator.

Bezpieczeństwo iteratorów jest zdefiniowane oddzielnie dla każdego z typów standardowych kontenerów, a w niektórych przypadkach iteratory dopuszczają dużą swobodę w modyfikowaniu kontenera podczas iteracji.

Java

Od wersji 1.2 interfejs java.util.Iterator umożliwia iterowanie po kolekcjach. Każdy Iterator posiada metody next() i hasNext(), oraz opcjonalnie może implementować metodę remove(). Iteratory tworzone są metodą iterator() odpowiedniej klasy kolekcji.

Metoda next() przesuwa iterator i zwraca wartość, na którą wskazuje iterator. Zaraz po utworzeniu iterator wskazuje na specjalną wartość przed pierwszym elementem, tak by pierwszy element był pobrany przy pierwszym wywołaniu next(). Do sprawdzenia, czy odwiedzono wszystkie elementy kolekcji stosuje się metodę hasNext(). Następujący przykład pokazuje proste użycie iteratorów:

Iterator it = list.iterator();
while (it.hasNext()) {
    Object val = it.next();
    System.out.println(val.toString());
}

Dla kolekcji, które obsługują tę funkcjonalność, ostatnio odwiedzony element można usunąć z kolekcji metodą remove() iteratora. Większość innych rodzajów modyfikacji kolekcji podczas iteracji nie gwarantuje bezpieczeństwa.

Python

Iteratory są jednym z podstawowych elementów Pythona i często są w ogóle niezauważalne, gdyż są niejawnie wykorzystywane w pętlach for. Wszystkie standardowe typy sekwencyjne w Pythonie, jak również wiele klas w bibliotece standardowej, udostępniają iterację. Poniższy przykład pokazuje typową niejawną iterację po kolekcji:

for value in sequence:
    print value

Możliwa jest również iteracja po kolekcjach niesekwencyjnych, jak np. dict (tablica asocjacyjna):

# Iteracja po kluczach
for key in dictionary:
    print key

# Iteracja po wartościach
for value in dictionary.itervalues():
    print value

# Iteracja po parach (klucz, wartość)
for key, value in dictionary.iteritems():
    print key, value

Iteratory można również definiować i używać jawnie. Do pobrania iteratora z kolekcji typu sekwencyjnego wykorzystuje się funkcję wbudowaną iter(). Tak utworzony iterator posiada metodę next(), która przy każdym wywołaniu zwraca kolejny element kolekcji. Gdy nie ma więcej elementów, metoda ta rzuca wyjątek StopIteration. Poniższy przykład pokazuje iterację po sekwencji z jawnym iteratorem, równoważną przedstawionej powyżej:

it = iter(sequence)
try:
    while True:
        val = it.next()
        print val
except StopIteration:
    pass

Dowolna zdefiniowana przez użytkownika klasa może udostępniać standardową iterację (niejawną lub jawną), jeśli posiada metodę __iter__() zwracającą iterator. Z kolei zwrócony iterator musi posiadać również metodę __iter__() oraz metodę next().

W Pythonie możliwe jest również użycie generatorów - specjalnego rodzaju iteratorów po niezrealizowanej kolekcji. Generatora używa się tak, jak iteratora, tyle, że sama iterowana kolekcja nie istnieje. Zamiast tego elementy obliczane są na bieżąco.

JavaScript

W wersji ES6 (ES2015) języka JavaScript, gdy wprowadzono pętlę for..of wprowadzono także protokół iteratorów oraz generatory do języka. Iteratorami zostały tablice oraz ciągi znaków.

Przykład użycia protokołu iteratora:

const text = "tekst";
const iterator = text[Symbol.iterator]();
console.log(iterator + ''); // "[object String Iterator]"

console.log(iterator.next()); // { value: "t", done: false }
console.log(iterator.next()); // { value: "e", done: false }
console.log(iterator.next()); // { value: "k", done: false }
console.log(iterator.next()); // { value: "s", done: false }
console.log(iterator.next()); // { value: "t", done: false }
console.log(iterator.next()); // { value: undefined, done: true }

Dzięki iteratorom możliwe jest użycie pętli for..of:

for (let ch of text) {
   console.log(ch);
}
// "t"
// "e"
// "k"
// "s"
// "t"

Generatory jest to szybki sposób tworzenia iteratorów, jest to tzw. cukier syntaktyczny.

function* counter(n) {
   while (n >= 0) {
     yield n--;
   }
}
for (let c of counter(10)) {
   console.log(c);
}
// 10
// 9
// 8
// 7
// 6
// 5
// 4
// 3
// 2
// 1
// 0

Sather

W języku Sather iteratory są specjalnym typem obiektu, który jest uogólnieniem iteratora z innych języków programowania. W szczególności w pętli loop tego języka można wykorzystywać jednocześnie wiele iteratorów.

Zobacz też

• iteracja
• wzorzec wizytatora

Linki zewnętrzne

• Biblioteka iteratorów Boost dla C++