Во сметачкото програмирање, итератор е објект кој често се наоѓа во класа наречена контејнер. Контејнер е компонента која може да содржи други компоненти во неа. Различни типови на итератори често се сретнуваат во контејнери. Иако интерфејсот и семантиката на даден итератор се фиксни, итераторите често се спроведуваат во однос на основните структури на објектната - имплементација и често се тесно поврзани со контејнер за да се овозможи оперативна семантика на итератор. Итераторите вршат попречување и даваат пристап до податочни елементи во објектите, но не вршат повторување.
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()); }