Итератор

Од Википедија — слободната енциклопедија
Прејди на прегледникот Прејди на пребарувањето

Во компјутерско програмирање, итератор е објект кој често се наоѓа во класа наречена контејнер. Контејнер е компонента која може да содржи други компоненти во неа. Различни типови на итератори често се сретнуваат во контејнери. Иако интерфејсот и семантиката на даден итератор се фиксни, итераторите често се спроведуваат во однос на основните структури на објектната - имплементација и често се тесно поврзани со контејнер за да се овозможи оперативна семантика на итератор. Итераторите вршат попречување и даваат пристап до податочни елементи во објектите, но не вршат повторување.

1.1 Главен дел - Итератор

Надворешен итератор може да се смета за еден вид на покажувач кој има две примарни операции: референцирање еден одреден елемент во објектот (наречен пристап кон одреден елемент), и само модифицирање така што укажува на следниот елемент (наречен пристап кон следниот елемент). Исто така, мора да постои начин да се создаде итератор така што ќе укажува на првиот елемент, како и некој начин да се утврди кога итераторот ги исцрпил сите елементи од класата. Во зависност од јазикот и нивната наменска употреба, итераторите исто така може да обезбедат дополнителни операции или покажуваат различни однесувања. Основната цел на итераторот е да му овозможи на корисникот да може да го процесира секој елемент од класата додека на корисникот не му е отворена внатрешната структура на класата. Ова и овозможува на класата да чува елементи на било кој начин, притоа овозможувајќи му на корисникот да ја третира како да е едноставна секвенца или листа. Итератор класата е обично дизајнирана во тесна координација со соодветна контејнер класа. Обично контејнерот обезбедува методи за креирање итератори. Loop counter понекогаш исто така се нарекува циклус - итератор. Loop counter, сепак, само обезбедува функционалност со сите елементи, а не функционалност за пристап до одредени елементи.

1.1.1 Генератори

Еден од начините за спроведување итератори е да се користи посебен вид на функција, позната како генератор, што може да ги врати вредностите повеќе пати (наместо да се вратат само еднаш). Повеќето итератори можат да се наречат генератори, но затоа што генераторите ја зачувуваат нивната состојба, тие се особено добро прилагодени за комплицирани, постојани итератори, како што се дрво траверсерите (tree traversers) . Еден пример на генератор е враќање на Фибоначи броевите со користење на Пајтон:

def fibonacci():

    a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

for number in fibonacci(): # Use the generator as an iterator

    print number

1.1.2 Имплицитни итератори

Некои објектно-ориентирани јазици како Perl, Python, C #, Ruby и подоцнежните верзии на Јава и Делфи обезбедуваат внатрешен начин на процесирање преку елементите на класа објект без воведување на експлицитни итератор објекти. Вистински итератор објект може да постои во реалноста, но ако постои не е изложен во изворниот код на јазикот. Имплицитните итератори често се манифестираат со "foreach" состојба (или еквивалентен), како на пример во следните Пајтон пример: for value in iterable:

   print value

Pecatenje na ovaj tekst

iterable.each do |value|

 puts value

end


Ова стил понекогаш се нарекува "внатрешно повторување", бидејќи неговиот код целосно се извршува во контекст на повторувачки објект (кој ги контролира сите аспекти на повторување) и програмерот само обезбедува работата да се изврши во секој чекор (со користење на анонимна функција). Јазици кои ја поддржуваат листата comprehensions или слични конструкции, исто така може да ги користат имплицитните итератори за време на изградбата на листата со резултати, како во Python:

names = [person.name for person in roster if person.male]

C + + јазикот има неколку функциски шаблони, како што for_each(), кои овозможуваат слични имплицитни повторувања. Сепак, тие уште бараат експлицитни итератор објекти како нивниот првичен влез. Но, еднаш иницијализиранота подредено повторување се случува имплицитно без континуираната употреба на било кој изложен итератор објект.

1.1.3 Контрасти со индексирање

Во процедуралните јазици вообичаено е да се користи индексирање врз основа на loop counter за да се поминат сите елементи во низа. Иако индексирањето, исто така, може да се користи со некои објектно - ориентирани контејнери, употребата на итераторите може да има некои предности: • Броење јамки не е погодно за сите структури на податоци, особено структури на податоци со или без бавно - случаен пристап, како листи или дрва. • Итераторите можат да обезбедат конзистентен начин да функционираат на структури на податоци од сите видови, а со тоа и да го направат кодот повеќе читлив, а помалку чувствителен на промени во структурата на податоци. • Еден итератор може да изврши дополнителни рестрикции за пристап, како што се: осигурување дека елементите не можат да бидат прескокнати или дека врз претходно посетен елемент не може да се пристапи по втор пат. • Еден итератор може да им овозможи на контејнер објектите да бидат изменети без онеспособување на итераторот. Со индексирање ова е проблематично, бидејќи индексот на броеви мора да се промени. Способноста на контејнерот да биде изменет за време на процесирањето преку неговите елементи постана неопходно во модерното објектно - ориентирано програмирање, каде меѓусебните односи помеѓу предметите и ефектите од работењето не можат да бидат очигледни. Со користење на итератор е изолирана од овие видови на последици.

1.2 Итератори во различни јазици за програмирање

1.2.1 C + +

C + + јазикот прави широка употреба на итераторите во својата стандардна темплејт библиотека, која овозможува неколку различни видови на итератори, вклучувајќи forward итератори, двонасочни итератори и итератори на случаен пристап. Сите стандардни контејнер темплејт видови обезбедуваат богат и доследен збир на типови на итератори. Синтаксата на стандардни итератори е дизајнираана да личи на онаа на обичниот C аритметички пкажувач, каде * и -> се користат за упатување на елементот каде што ќе покаже итераторот и аритметичките покажувачки оператори како + + се користи за да се префрли итераторот на следниот елемент. Итераторите обично се користат во парови, каде што прво се користи за вистинските повторувања и после служи за да се означи крајот на колекцијата. Итераторите се креирани од страна на соодветните контејнер класи со користење на стандардни методи како што се begin() и end(). Итераторот кој има begin()укажува на првиот елемент, додека итераторот кој се состои од end()е посебна вредност која не упатува на било кој елемент. Следниот пример прикажува една типична употреба на итератор.

std::vector<int> items; items.push_back(1); //Add integer '1' to the back of vector 'items' items.push_back(2); //Add integer '2' to the back of vector 'items' items.push_back(3); //Add integer '3' to the back of vector 'items'

for (std::vector<int>::iterator i = items.begin(); i != items.end(); ++i) { //Iterate through 'items'

  std::cout << *i; //And print current index of 'items'

}

//Pecati 123

Постојат многу видови на итератори, секој со малку поинакво однесување, вклучувајќи: forward, reverse, и двонасочни итератори; итератори со случаен пристап; влезни и излезни итератори и const итератори (со кои се штитат контејнерите или елементите од промена). Сепак, не секој вид на контејнер поддржува секаков вид на итератор. Можно е корисниците да создадат свои итератор - видови од кои произлегуваат поткласи од стандардниот std::iterator - class template. Итератор - безбедноста се дефинира одделно за различни видови на стандардни контејнери, во некои случаи итераторот е многу попустлив со дозволување контејнерот да се промени за време на процесирањето. Имплицитното повторување е исто така делумно поддржано со C + + со користење на стандардни функциски шаблони, како што се: std::for_each(), std::copy()и std::accumulate(). Кога се користи тие мора да се иницијализирани со постоечките итератори, обично begin и end, кои го дефинираат опсегот во кој се случува повторувањето. Овој пример покажува користење на for_each:

ContainerType<ItemType> C; // Any standard container type of ItemType elements void ProcessItem( const ItemType& I ) // Function which will process each item of the collection {

  std::cout << I << '\n';

}

std::for_each(C.begin(), C.end(), ProcessItem); // A for-each iteration loop

           Истото може да се постигне со користење на std::copy и std::ostream_iterator:

std::copy(C.begin(), C.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));

Ограничување е дека оваа техника не му дозволува на телото на секој циклус да биде прогласено за внатрешно, барајќи некој функциски покажувач или функциски објект да биде прогласен на друго место и помине како аргумент. Ова може да биде делумно надоместено со користење на библиотека, како што е Boost и користење на ламбда за да имплицитно генерира функциски објекти со познати инфикс операторски синтакси. Сепак, бидејќи Boost се спроведува во нивото на библиотеки, наместо суштински во јазикот, одредени операции треба да се направат преку околини. Во следната ревизија на C + +, позната како C + +0x, природно ќе го поддржи ламбда функциската синтакса, дозволувајќи му на функциското темплејт тело да биде прогласено за внатрешно. Еве еден пример за за - секое повторување користење на функција ламбда:

ContainerType<ItemType> C; // Any standard container type of ItemType elements

// A for-each iteration loop with a lambda function std::for_each(C.begin(), C.end(), [](const ItemType& I){std::cout << I << '\n';} );

1.2.2 C # и други. NET јазици

Итераторите во .NET Framework се нарекуваат "попишувачи" и се претставени од IEnumerator интерфејсот. IEnumerator обезбедува: MoveNext() метод, кој напредува на следниот елемент и покажува дали е постигнат крајот од колекцијата; Current property, за да се добие вредноста на елементот кој е посочен во тој момент и optional Reset()- метод, за да го премота инумераторот на почетната состојба (позиција). Енумераторот првично укажува на посебна вредност пред првиот елемент, па потребен е повик за MoveNext() за да започне процесирањето. Енумераторите обично се добиваат со повикување на GetEnumerator() методот на објект за имплеменнтирање на IEnumerable интерфејсот. Контејнер класите обично го имплементираат овој интерфејс. Сепак, foreach изјавата во C # може да работи на било кој објект користејќи таков метод, дури и ако тоа не го спроведува IEnumerable. Двата интерфејси се проширени во генерички верзии на .NET 2.0. Следново покажува едноставна употреба на итератори во C # 2.0:

// explicit version IEnumerator<MyType> iter = list.GetEnumerator(); while (iter.MoveNext())

   Console.WriteLine(iter.Current);

// implicit version foreach (MyType value in list)

   Console.WriteLine(value);

C # 2.0, исто така, поддржува генератори: метод, кој е прогласен за враќање IEnumerator (или IEnumerable), но ја користи " yield return " изјавата за да се произведе низа на елементи наместо враќање на примерот за објектот, ќе се трансформира од страна на компајлерот во нова класа спроведувајќи соодветен интерфејс.

1.2.3 Јава

Во Јава 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.println(iter.next());

}

За собирање видови кои го подржуваат, remove() методот на итератор ги отстранува неодамна посетените елементи од контејнерот. Повеќето други видови на модификација на контејнери додека трае процесирањето се небезбедни. Дополнително, за java.util.List постои java.util.ListIterator со сличен API, но кој им овозможува повторување нанапред и наназад, го обезбедува сегашниот индекс во листата и им овозможува поставување во листата елементи на својата позиција. J2SE 5,0 на Java воведе Iterable интерфејс за поддршка за for (foreach) јамка за процесирањето над збирки и низи. Iterable дефинира iterator()метод кој враќа итератор. Пример за користење на for:

for (MyType obj : list){

   System.out.print(obj);

}

1.2.4 Руби

Руби спроведува итератори сосема поинаку, сите повторувања се направи со callback контејнер методи. На овој начин не само што Руби ги спроведува основните повторувања, но исто така и неколку модели на повторување како функциско мапирање, филтри и намалување. Руби, исто така, поддржува алтернативна синтакса за основниот итератор - метод each, следните три примери се еднакви:

(0...42).each do |n|

puts n

end ...и... for n in 0...42

puts n

end или пократко: 42.times do |n|

puts n

end Руби, исто така, може да итерира преку фиксни листи со користење на попишувачите (енумератори) и со повикување на нивниот следен метод. Или прави за секој од нив, како и погоре во примерот.

1.2.5 Пајтон

Итераторите во Python се основен дел од јазикот и во голем број случаи поминуваат невидени како што се имплицитно користени во for циклусот, во листата comprehensions, и во генератор изразите. Целиот Пајтон стандард вграден во низа класи поддржува итератори, како и многу класи кои се дел од стандардната библиотека. Следниот пример покажува типично имплицитно повторување низ низа:

for value in sequence:
    print(value)

Пајтон речниците (форма на асоцијативна низа), исто така може директно да се итерираат во текот:

for key in dictionary:

   value = dictionary[key]
   print(key, value)

for key, value in dictionary.items():

   print(key, value)

Итераторите сепак може да се користат и дефинираат експлицитно. За секој iterable тип, секвенца или класа, функцијата iter() се користи за да се создаде итератор објект. Итератор објектот тогаш може да се потврди со next() функцијата, која го користи __next__() методот внатрешно, кој го враќа следниот елемент во контејнерот. Претходната изјава се однесува на Python 3.x. Во Python 2.x, next() метод е еквивалентен.) StopIteration исклучокот ќе се употреби кога нема повеќе елементи. Следниот пример покажува еквивалентно повторување на низа елементи со користење на експлицитни итератори:

it = iter(sequence) while True:

   try:
       value = it.next() # in Python 2.x
       value = next(it) # in Python 3.x
   except StopIteration:
       break
   print(value)

Секоја дефинирана класа може да поддржи стандарден итератор (имплицитно или експлицитно), со дефинирање на __iter__() метод што создава итератор објект. Итератор објектот тогаш треба да дефинира __next__() метод, кој го враќа следниот елемент.

1.2.6 PHP

Во PHP 4 воведена е изградба foreach, слично како Perl и некои други јазици. Ова едноставно дава лесен начин за итерирање над низи. Foreach работи само на низи во PHP 4 и издава грешка при обид да се користи на променлива со различен тип на податок или uninitialized променлива. Во PHP 5, foreach е дозволено на итерирање на објект преку сите јавни членови. Постојат две синтакси, а втората е мала но корисна екстензија на првата.

Пример 1

<?php

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

?> Пример 2

 <?php
 foreach (array_expression as $key => $value)
   echo "($key)$value\n";

?>

Во примерот 1 во секој циклус вредноста на тековниот елемент е доделена на $value и внатрешниот покажувач е преместен за еден (па во следниот циклус, ќе се гледа следниот елемент). Примерот Б има иста функционалност како погоре. Покрај тоа, клучот на тековниот елемент (во овој случај, array_expression) ќе биде доделен на променливата $key во секој циклус. Итератор интерфејсот е пре - дефиниран во PHP 5 и објектите може да се прилагодат на итерирање.

<?php

 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;
    }
 }

?>

These methods are all being used in a complete foreach($obj AS $key=>$value) sequence.
The methods of Iterators are executed in the following order:
1.  rewind()
2.  while valid()
    {
      2.1 current() in $value
      2.3 key() in $key
      2.4 next()
     }

1.2.7 MATLAB

MATLAB ги поддржува и двете надворешни и внатрешни имплицитни повторувања со користење или "мајчини" низи или cell низи. Во случај на надворешено повторување каде што одговорноста е на корисникот да ги користи сите елементи и да ги посочува следните, може да се дефинира множество на елементи во низа за складирање и да се вртат и користат во циклус сите со помош на for циклус. На пример: % Define an array of integers myArray = [1,3,5,7,11,13];

for n = myArray

  % ... raboti nesto so n
  disp(n)  % Echo integer to Command Window

end преминува низа на цели броеви со користење на клучни зборови.

Во случај на внатрешнo повторување каде што корисникот може да ја препушти операцијата на итераторот да работи со сите елементи во колекцијата, многу вградени оператори и функции од MATLAB се преоптоварени да се извршува функција над секој елемент од низа и да се врати соодветен излез. Исто така, arrayfun и cellfun функциите можат да бидат користени за работење напреддефинирани операции од корисникот. На пример:

function simpleFun % Define an array of integers myArray = [1,3,5,7,11,13];

% Perform a custom operation over each element myNewArray = arrayfun(@(a)myCustomFun(a),myArray);

% Echo resulting array to Command Window myNewArray


function outScalar = myCustomFun(inScalar) % Simply multiply by 2 outScalar = 2*inScalar;

Дефинира примарна функција simpleFun која додава подфункција myCustomFun на секој елемент во низата со користенје на вградена arrayfun функција.