У програмирању, итератор је објекат који омогућује програмеру да пролази кроз колекцију, нарочито листу.Watt, Stephen M. "A Technique for Generic Iteration and Its Optimization" (PDF). Различите интерфејсне колекције често пружају различите врсте итератора. Иако су интерфејс и семантика датог итератора фиксне, итератори се често имплементирани у виду структура које су основи колекције и често су чврсто повезани са колекцијом да би се омогућила оперативна семантика итератора. Трeба имати на уму да итератор врши прелазак и такође даје приступ елементима колекције, али не извршава понављање (тј, не без неког значајног одузимања слободе тог концепта или са тривијалним коришћењем технологије). Итератор је по понашању сличан курсору базе података. Итератори датирају још од CLU програмског језика из 1974.
Опис Екстерни итератори и шаблон итератора
Спољашњи итератор се може разматрати као тип показивача који има две примарне операције: упућује на један посебан елемент у колекцији објеката (зове се приступ елементу) и допуна себе тако да указује на следећи елемент (зове се пролаз елемента). Такође мора постојати начин да се створи итератор тако да указује на неки први елемент као и начин да се одреди када ће итератор истрошити све елементе колекције. У зависности од језика и намене, итератори могу омогућити додатне операције или показати различита понашања.
Примарна сврха итератора је да дозволи кориснику да изврши процес над сваким елементом колекције док изолује корисника од унутрашње структуре колекције. Ово омогућава садржини да складишти елементи на било који начин док дозвољава кориснику да их третира као да су секвенца или листа. Класа итератора је углавном дизајнирана у тесној сарадњи са класом колекције. Обично, колекција омогућава методе за креирање итератора
Имати на уму да се бројач петље такође назива и итератор петље. Бројач петље, међутим, само омогућава пролаз функционалности и нефункционалност приступа елемента.
Генератори Један начин имплементације итератора је коришћење ограниченог облика надпрограма, познатог као генератор. Супротно њему је потпрограм, генератор надпрограма може преузети вредности његовог позивача неколико пута, уместо да их враћа. Већина итератора су природно изразити као генератори, али пошто генератори чувају своју локалну наредбу између призива, они су посебно добро опремљени за компликоване, наредбене итераторе, као обилазак стабла. Постоје суптилне разлике и одлике у коришћењу термина "генератор" и "итератор", који верирају између аутора и језика. У Пајтону, генератор је конструктор итератора: функција која враћа итератор. Пример Пајтоновог генератора који враћа итератор су Фибоначијеви бројеви који користе Пајтоновуyield наредбу: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): # Генератор конструише итератор print(number)
Имплицитни итератори Неки објектно-оријентисани језици као што су C#, C++ (раније верзије), Delphi (раније верзије), Гоу, Јава (раније верзије), Lua, Перл, Пајтон, Руби пружају суштински начин понављања кроз елементе садржине објекта без упознавања са објектним експлицитним итератором. Стварни итератор може постојати у реалности, али ако се то деси он није експониран изворном коду језика.
Имплицитни итератору се често манифестују "форич" изјавом (или еквивалетно), као што је следећи пример у Пајтону: for value in iterable: print valueУ Пајтону, итерабла је објекат који може бити конвертован у итератор, који је касније понављан током for петље; ово се дешава имплицитно.
Или други пут могу бити креиране саме од себе збирком објеката, као у овом примеру код Рубија:iterable.each do |value| puts value endОвај стил понављања се понекад назива и "интерно понављање" зато што се његов код потпуно извршава унутар контекста објекта (то контролише све аспекта понављања), и програмер само омогућава операцију да се изврши сваког корака (користећи анонимну функцију).
Језици који подржавају листу схватања или сличних конструкција могу такође користити имплицитне итераторе током конструкције листе резултата, као у Пајтону:names = [person.name for person in roster if person.male]Понекад је имплицитна природа сакривена делимично. С++ језик има неколико функционалних шаблона за имплицитно понављање, као што је for_each(). Ове функције идаље захтевају експлицитан објекат итератора као њихов први улаз, али касније понављање не излаже објекат итератора корисникуT
Потоци Итератори су корисна апстракција улазних токова- они обезбеђују потенцијалну бесконачан итерабилни (али не нужно изменљи) објекат. Неколико језика, као што је Перл и Пајтон, спроводе потоке као итераторе. Алтернативне имплементације потока укључују податке-вођене језика, као што су AWK и сед.
Разлике са индексима У поступним језицима често се користе подскрипни оператори и бројач петље да би се петљало кроз све елементе у секвенци као што је низ. Иако индексовање се може такође користити са неком објектно-оријентисаном садржином, коришћење итератора може имати предности:Vecerina, Ivan (2006-02-01). "index vs iterator". Бројање петљи не одговара свим структурама података, посебно структуре података са насумичним приступом подацима или без њих, као што су листе и стабла. Итератори могу омогућити доследан начин да понове над структуром података свих врста, а саммим тим да направе код читљивијим, за вишекратну употребу, и мање осетљив на промене у структури података. Итератор може наметнути додатна ограничења на приступ, као што је обезбеђење да елементи не могу бити прескочени или да претходно посећени елементи не могу имати приступ други пут. Итератор може дозовлити објекту садржине да буде измењен без поништавања итератора. На пример, када је итератор напредовао даље од првог елемента могуће је унети додатне елементе на почетак садржине са предвидивим резултатима. Са индексовањем ово је проблематично пошто се бројеви индекса морају мењати.
Могућност садржине да буде променљива док се понавља кроз њене елементе је постала неопходна у објектно-оријентисаном програмирању, где су међусобни односи између објеката и ефекат операција не може бити очигледан. Крошћењем итератора један је изолован од ових последица. Ова тврдња, међутим, мора се узети са резервом, јер је чешће него не, из ефикасних разлога, имплементација итератора је тесно повезана за садржину који не спречава измену основне садржине без поништавања себе.
За садржине које се могу кретари кроз њихове податке у меморији, једини начин да не пониште итератор је, за садржину, да некако прати кретање свих тренутно живих итератора и ажурира их у ходу. Пошто број итератора у датом тренутку може бити произвољно велики у односу на величину везане садржине, ажурирањем свих њих ће драстично утицати на сложеност гаранције операција садржине.
Алтернативни начин да се задржи број исправки везаних у односу на величину садржине би био да се користи нека врста механизма ручки, то је колекција индиректних показивача елемената садржине која мора бити ажурирана са садржином, и да допусти показивачу итератора овим ручкама директно елементима података. Али овај приступ ће негативно утицати на перформанс итератора, јер он мора остварити дупли показивач пратећи приступ стварном елементу података. Ово обично није пожељно, зато што многи алгоритми користе итераторе да позову приступ података итератора чешће него методу унапред. Зато је посебно важно имати итераторе са веома ефикасним приступом подацима.
Све у свему, ово је увек компромис између сигурности (итератори осталу увек валидни) и ефикасности. Већину времена, додата сигурност није вредна цене ефиканости за плаћање. Користећи алтернативну садржину (на пример једнострука повезана листа уместо вектора) би био бољи избор (глобално ефикасније) ако је стабилност итератора потребна.
Класификовање итератора
Категорије итератора Итератори могу бити категоризовани по њиховој функционалности. Овде је (не-коначна) листа категорија итератора: Категорија ЈезициДвосмерни итератор C++Напредни итератор C++Улазни итератор C++Излазни итераторC++Стандарна библиотека шаблона C++Тривијални итератор C++ (старији STL)
Типови итератора Различити језици или библиотеке коришћене овим језицима дефинишу типове итератора. Неки од њих су: Type LanguagesИтератор низа PHP, R Хватајући итератор PHPИтератор константе C++,. PHPИнтератор директоријума PHP, ПајтонИтератор филтера PHP, RИтератор ограничења PHPИтератор листеЈава, R Итератор рекурзивног низа PHPXML итератор PHP
У различитим програмским језицима
C# и остали .NET језици Итератору у . NET Framework се зову "пописивачи" и и представљају се помоћу IEnumerator интерфеса. IEnumerator омогућује MoveNext() методу, која се пласира у наредни елемент и указује да је постигнут крај збирке ; Current власништво, да би се добила вредност елемента тренутно указаног; и опционалнаtReset() метода, да се премота пописивач назад на његову почетну позицију. Пописивач у почетку позакује специјалну вредност пре првог елемента, тако да позив на MoveNext() је тражен како би почело понављање.
Пописивачи се обично добијају позивом на GetEnumerator() методу објеката који се спроводи над IEnumerable интерфејсом. Класе садржине обично спроводе овај интерфејс. Међутим, форич изјава у C# могу да раде на било ком објекту који пружа такву методу, чак и ако се не спроводи IEnumerable. Оба интерфејса су се проширила на генеричке верзије у . NET 2.0.
У наставку следи коришћење итератора у C# 2.0:// експлицитна верзија IEnumerator<MyType> iter = list.GetEnumerator(); while (iter.MoveNext()) Console.WriteLine(iter.Current);
// имплицитна верзија foreach (MyType value in list) Console.WriteLine(value);C# 2.0 такође подржава генераторе: мерода која је декларисана као повратна IEnumerator (или IEnumerable), али користи "yield return" изјаву да произведе низ елемената умест да враћа инстанцу објеката, ће бити трансформисан од стране компајлера у нову класу спроводећи одговарајући интерфејс.
C++ C++ језик прави широк спектар итератора у његовој Стандардној Библиотеци Шаблона, која омогућује неколико различитих итератора, укључујући напредни итератор, бидирекциони итератор, и стандардну библиотеку итератора. Све врсте стандардних контеинера пружају богат и доследан скуп типова итератора. Синтакса стандардних итератора је дизајнирана да подсећа на обичне C аритметичке показиваче, где * и -> оператори се користе као референца елемента који итератор показује, и аритметички показивачи оператора као што је ++ се корсите да унапреде итератор на следећи ниво.
Итератори се обично користе у паровима, где се један користи за понављање и други служи да обележи крај збирке. Итератори су направљени од стране одговарајуће класе садржине користећи се стандардним методама као сто су begin() и end(). Итераторе враћен од begin() показује на први елемент, док итератор враћен од end() је специјална вредност која помиње никакав елемент. Када је итератор напредовао изнад последњег елемент он је по дефиницији једнак специјалном крају вредности итератора.
Следећи пример показује типично коришћење итератора.std::vector<int> items; items.push_back(1); // Повећај целобројну вредност '1' на вектор 'ставки' items.push_back(2); // Повећај целобројну вредност '2' на вектор 'ставки' items.push_back(3); // Повећај целобројну вредност '3' на вектор 'ставки'
for (std::vector<int>::iterator i = items.begin(); i != items.end(); ++i) { // Iterate through 'items' std::cout << *i; // И штампај вредност од 'ставки' за тренутни индекс } //in C++11 for(auto i:items){ std::cout << i; // И штампај вредност од 'ставки' } //