Направо към съдържанието

Итератор (шаблон)

от Уикипедия, свободната енциклопедия

Итератор (на английски: Iterator) е поведенчески шаблон за дизайн, който се използва в обектно-ориентираното програмиране. Итераторът предоставя начин за последователен достъп до елементите на обект, без да е нужна вътрешна информация за обекта. В компютърно програмиране, итератор е обект, който дава възможност на програмиста да преминава през структура от данни. Различни видове итератори често са предоставяни чрез интерфейс контейнер. Въпреки че интерфейсът и семантиката на даден итератор са фиксирани, итераторите често се прилагат по отношение на свързаните с тях структури за изпълнение и често са плътно свързани към контейнера, за да отговарят на семантиката на Итератора. Трябва да се има предвид, че итераторът чете и също така дава достъп до елементите в една структура от данни, но не изпълнява итерация (при тривиално използване на терминологията). Итераторът поведенчески е подобен на курсора на база данни.

Външни итератори и модела итератор

[редактиране | редактиране на кода]

Външно итераторът може да се представи като тип указател, който има две основни операции: Съотнасяне на един конкретен елемент в колекцията на обект и самото му модифициране така, че да сочи към следващия елемент.

В зависимост от езика и предназначението, итераторите могат също да предоставят допълнителни операции или да притежават различни поведения.

Основната цел на итератора е да позволи на потребителя да обработва всеки елемент на структурата от данни, докато изолира потребителя от вътрешната им структура. Итераторният клас обикновено е проектиран в тясно координиране със съответния клас на контейнера. Обикновено, класът-структура от данни осигурява методи за създаване на итератори.

Един от начините за прилагане на итератори е да се използва ограничена форма на coroutine, известна като генератор. За разлика от подпрограма, генераторът може да извика една стойност няколко пъти, вместо само веднъж.

Пример за генератор в Phyton, който връща итератор за номерата на Фибоначи:

def fibonacci(limit):
    a, b, c = 0, 1, 0
    while c < limit:
        yield a
        a, b, c = b, a+b, c+1
for number in fibonacci(100): # The generator constructs an iterator
    print(number)

Някои обектно-ориентирани езици като C#, C++ (по-нови версии), Delphi (по-нови версии), Go, Java (по-нови версии), Lua, Perl, Python, Ruby предоставят присъщ начин за итериране през елементите на структура от данни без въвеждането на изричен итератор. Итератор действително може да съществува, но ако е така той не е изложен в програмния код.

Косвените итератори най-често се изразяват чрез цикъла "foreach" (или еквивалентен), като в следващия пример на Python:

for value in iterable:
    print value

В Python "iterable" е обект, към който може да се прикачи итератор, който след това се повтаря по време на цикъл. Или в други случаи, те могат да бъдат създадени от самия обект, като в този Ruby код:

iterable.each do |value|
  puts value
end

Итераторите са полезна абстракция на входящите потоци – те предоставят потенциално безкрайно повтаряне на обект. Няколко езика, като Perl и Python, прилагат потоци като итератори. Алтернативни реализации на поток включват data-driven езици, като AWK.

Класифициране на итератори

[редактиране | редактиране на кода]

Итераторите могат да бъдат категоризирани в зависимост от тяхната функционалност. Ето един (неизчерпателен) списък на категории:

Категория Език
Bidirectional iterator C++
Forward iterator C++
Input iterator C++
Output iterator C++
Random access iterator C++
Trivial iterator C++ (old STL)[1]

Различни езици или библиотеки, използвани с тези езици определят вида итератор. Някои от тях са:

Вид Език
Array iterator PHP, R[2]
Caching iterator PHP
Constant iterator C++,[3] PHP
Directory iterator PHP, Python
Filter iterator PHP, R
Limit iterator PHP
List iterator Java, R
Recursive array iterator PHP
XML iterator PHP

Езикът C++ имплементира широкото използване на итератори в своята Стандартната библиотека, която осигурява достъп до няколко различни видове итератори, включително препращащи итератори, двупосочни итератори и итератори с произволен достъп. Всички стандартни видове шаблонни контейнери предоставят богат и последователен набор от видове итератори. Синтаксисът на стандартните итератори е проектиран да наподобява този на стандартната C аритметиката с указатели, като операторите ‘* и ‘->’ се използват за показване на елемента, към който итераторът сочи.

Итераторите обикновено се използват, чрез извикване на метода GetEnumerator () на обекта за изпълнение на IEnumerable интерфейса. Класове-контейнери обикновено въвеждат този интерфейс, въпреки това foreach твърдението в C# може да работи с всеки обект, който предоставя такъв метод, дори ако той не се изпълни от IEnumerable.
Следните примери показва използването на итератори в C #:

// explicit version
IEnumerator<MyType> iter = list.GetEnumerator();
while (iter.MoveNext())
    Console.WriteLine(iter.Current);
// implicit version
foreach (MyType value in list)
    Console.WriteLine(value);

Представен в Java JDK 1.2 издание, "java.util.Iterator" интерфейсът позволява итериране на класове. Всеки итератор осигурява "next()" и "hasNext()" метод и може да поддържа "remove()" метод. Итераторите са създадени от съответните съдържащи класове, обичайно от метод наречен "iterator()". Методът "next()" преминава през итератора и връща стойността посочена от итератора. Първият елемент е получен при първото извинкване на следващ "next()". За да се определи кога всички елементи в контейнера са били посетени се използва "hasNext()" метода.

Следващият пример показва проста употреба на итератори:

Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator(); in J2SE 5.0
while (iter.hasNext()) {
    System.out.print(iter.next());
    if (iter.hasNext())
      System.out.print(", ");
}

В Scala, итератори имат богат набор от методи, подобни на колекции, и могат да бъдат използвани директно в for цикли. Всъщност, както итераторите, така и колекциите наследяват от общите черти на – scala.collection.TraversableOnce. Въпреки това, заради богатият набор от методи, които съществуват в Scala колекциите, като например map, collect, filter и т.н., то не се налага често да боравим с итератори директно при програмирането в Scala.

Java итератори и колекции могат автоматично да бъдат превърнати в Scala итератори и колекции, просто чрез добавяне на един-единствен ред

import scala.collection.JavaConversions към файла. Обектът JavaConversions осигурява имплицитни превръщания. Косвените преобразувания са характерни за Scala: методи, които, когато са видими в текущия обхват, автоматично се извикват в най-подходящото място, за да се typecheck-нат когато те иначе не биха.

PHP 4 въведе foreach конструкцията, подобно на Perl и някои други езици. Това просто дава лесен начин за обхождане на масиви. foreach работи само върху масиви в PHP 4, и ще изведе грешка, когато се опитате да го използвате на променлива с различен тип данни или неинициализирана променлива. В PHP 5, foreach е позволено за итериране върху обект през всички публични членове.

Има два синтаксиса; Вторият е незначително, но полезно разширение на първият.

Пример A

foreach (array_expression as $value) { echo "$value\n"; }

Пример Б

foreach (array_expression as $key => $value) { echo "($key)$value\n"; }

В Пример А итерираме върху масива обозначен с array_expression. На всяко завъртане на цикъла стойността на текущия елемент се записва в $value и вътрешният указател на масива се увеличава с единица (така, че при следващо завъртане на цикъла ще гледа към следващия елемент).

В Пример Б имаме същата функционалност като в Пример А. В допълнение текущият ключ на елемента (в нашият случай array_expression) ще бъде записан в променливата $key при всяко завъртане на цикъла.

Интерфейсът на итератора е предефиниран в PHP 5 и обектите могат да бъдат персонализирани, за да се справят с итерацията.

class MyIterator implements Iterator {     private $var = array();

    public function __construct($array) {         if (is_array($array)) {

          $this->var = $array;

        }     }

    public function rewind() {         echo "rewinding\n";         reset($this->var);     }

    public function current() {         $var = current($this->var);         echo "current: $var\n";         return $var;     }

    public function key() {         $var = key($this->var);         echo "key: $var\n";         return $var;     }

    public function next() {         $var = next($this->var);         echo "next: $var\n";         return $var;     }

    public function valid() {         $var = $this->current() !== false;         echo "valid: {$var}\n";         return $var;     } }

Тези методи биват използвани в пълна foreach($obj AS $key=>$value)последователност. Методите на итераторите се изпълняват в следния ред:

1. rewind() 2. while valid() {        2.1 current() in $value        2.3 key() in $key        2.4 next()       }

Итераторите в Python са основна част от езика, а и в много случаи са невидими тъй като по презумпция се използва в for (foreach) декларация, в list comprehensions, и в generator expressions. Всички стандартно вградени видове колекции в Пайтън поддържат итерация, както и много класове, които са част от стандартната библиотека. Следващият пример показва типична имплицитна итерация върху последователност:

for value in sequence:

print (value)

Python речниците (форма на асоциативен масив) също могат да бъдат директно итерирани, когато ключовете на речника се връщат; или метода items на речник може да се итерира отново, където той получава съответната ключ, стойност двойка като кортеж:

for key in dictionary:
    value = dictionary[key]
    print(key, value)
for key, value in dictionary.items():
    print(key, value)

Итераторите могат да се използват и дефинират изрично. За всеки тип итерираща последователност или клас, вградената функция iter () се използва за създаване на итератор обект. Итериращият обект може след това да се итерира с функцията next(), която използва вътрешно метода __next __ (), който връща следващия елемент в контейнера. (Предишното изявление се отнася за Python 3.x. В Python 2.x, метода next() е еквивалентен.). Ще възникне StopIteration exception, когато не са останали повече елементи. Следващият пример показва еквивалентна итерация върху последователност използвайки експлицитни итератори:

it = iter(sequence)
while True:
    try:
        value = it.next() # in Python 2.x
        value = next(it) # in Python 3.x
    except StopIteration:
        break
    it = iter(it)
    print(value)
  1. c | Types of iterator : Output vs. Input vs. Forward vs. Random Access Iterator - Stack Overflow // stackoverflow. Архивиран от оригинала. Посетен на 30 март 2022.
  2. Collier, Andrew. Iterators in R // Архивиран от оригинала на 2018-10-18. Посетен на 16 ноември 2013.
  3. concurrent_unordered_set Template Class // Intel Threading Building Blocks for Open Source. Архивиран от оригинала на 2015-05-01. Посетен на 9 август 2012. •The iterator types iterator and const_iterator are of the forward iterator category