У програмирању, итератор је објекат који омогућује програмеру да пролази кроз колекцију, нарочито листу.[1][2][3] Различите интерфејсне колекције често пружају различите врсте итератора. Иако су интерфејс и семантика датог итератора фиксне, итератори се често имплементирани у виду структура које су основи колекције и често су чврсто повезани са колекцијом да би се омогућила оперативна семантика итератора. Трeба имати на уму да итератор врши прелазак и такође даје приступ елементима колекције, али не извршава понављање (тј, не без неког значајног одузимања слободе тог концепта или са тривијалним коришћењем технологије). Итератор је по понашању сличан курсору базе података. Итератори датирају још од CLU програмског језика из 1974.
Опис
Екстерни итератори и шаблон итератора
Спољашњи итератор се може разматрати као тип показивача који има две примарне операције: упућује на један посебан елемент у колекцији објеката (зове се приступ елементу) и допуна себе тако да указује на следећи елемент (зове се пролаз елемента).[4] Такође мора постојати начин да се створи итератор тако да указује на неки први елемент као и начин да се одреди када ће итератор истрошити све елементе колекције. У зависности од језика и намене, итератори могу омогућити додатне операције или показати различита понашања.
Примарна сврха итератора је да дозволи кориснику да изврши процес над сваким елементом колекције док изолује корисника од унутрашње структуре колекције.[2] Ово омогућава садржини да складишти елементи на било који начин док дозвољава кориснику да их третира као да су секвенца или листа. Класа итератора је углавном дизајнирана у тесној сарадњи са класом колекције. Обично, колекција омогућава методе за креирање итератора
Имати на уму да се бројач петље такође назива и итератор петље. Бројач петље, међутим, само омогућава пролаз функционалности и нефункционалност приступа елемента.
Генератори
Један начин имплементације итератора је коришћење ограниченог облика надпрограма, познатог као генератор. Супротно њему је потпрограм, генератор надпрограма може преузети вредности његовог позивача неколико пута, уместо да их враћа. Већина итератора су природно изразити као генератори, али пошто генератори чувају своју локалну наредбу између призива, они су посебно добро опремљени за компликоване, наредбене итераторе, као обилазак стабла. Постоје суптилне разлике и одлике у коришћењу термина "генератор" и "итератор", који верирају између аутора и језика.[2] У Пајтону, генератор је конструктор итератора: функција која враћа итератор. Пример Пајтоновог генератора који враћа итератор су Фибоначијеви бројеви који користе Пајтонову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, Перл, Пајтон, Руби пружају суштински начин понављања кроз елементе садржине објекта без упознавања са објектним експлицитним итератором. Стварни итератор може постојати у реалности, али ако се то деси он није експониран изворном коду језика.[4][5]
Имплицитни итератору се често манифестују "форич" изјавом (или еквивалетно), као што је следећи пример у Пајтону:
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 и сед.
Разлике са индексима
У поступним језицима често се користе подскрипни оператори и бројач петље да би се петљало кроз све елементе у секвенци као што је низ. Иако индексовање се може такође користити са неком објектно-оријентисаном садржином, коришћење итератора може имати предности:[6]
- Бројање петљи не одговара свим структурама података, посебно структуре података са насумичним приступом подацима или без њих, као што су листе и стабла.
- Итератори могу омогућити доследан начин да понове над структуром података свих врста, а саммим тим да направе код читљивијим, за вишекратну употребу, и мање осетљив на промене у структури података.
- Итератор може наметнути додатна ограничења на приступ, као што је обезбеђење да елементи не могу бити прескочени или да претходно посећени елементи не могу имати приступ други пут.
- Итератор може дозовлити објекту садржине да буде измењен без поништавања итератора. На пример, када је итератор напредовао даље од првог елемента могуће је унети додатне елементе на почетак садржине са предвидивим резултатима. Са индексовањем ово је проблематично пошто се бројеви индекса морају мењати.
Могућност садржине да буде променљива док се понавља кроз њене елементе је постала неопходна у објектно-оријентисаном програмирању, где су међусобни односи између објеката и ефекат операција не може бити очигледан. Крошћењем итератора један је изолован од ових последица. Ова тврдња, међутим, мора се узети са резервом, јер је чешће него не, из ефикасних разлога, имплементација итератора је тесно повезана за садржину који не спречава измену основне садржине без поништавања себе.
За садржине које се могу кретари кроз њихове податке у меморији, једини начин да не пониште итератор је, за садржину, да некако прати кретање свих тренутно живих итератора и ажурира их у ходу. Пошто број итератора у датом тренутку може бити произвољно велики у односу на величину везане садржине, ажурирањем свих њих ће драстично утицати на сложеност гаранције операција садржине.
Алтернативни начин да се задржи број исправки везаних у односу на величину садржине би био да се користи нека врста механизма ручки, то је колекција индиректних показивача елемената садржине која мора бити ажурирана са садржином, и да допусти показивачу итератора овим ручкама директно елементима података. Али овај приступ ће негативно утицати на перформанс итератора, јер он мора остварити дупли показивач пратећи приступ стварном елементу података. Ово обично није пожељно, зато што многи алгоритми користе итераторе да позову приступ података итератора чешће него методу унапред. Зато је посебно важно имати итераторе са веома ефикасним приступом подацима.
Све у свему, ово је увек компромис између сигурности (итератори осталу увек валидни) и ефикасности. Већину времена, додата сигурност није вредна цене ефиканости за плаћање. Користећи алтернативну садржину (на пример једнострука повезана листа уместо вектора) би био бољи избор (глобално ефикасније) ако је стабилност итератора потребна.
Класификовање итератора
Категорије итератора
Итератори могу бити категоризовани по њиховој функционалности. Овде је (не-коначна) листа категорија итератора:[7][7]
Типови итератора
Различити језици или библиотеке коришћене овим језицима дефинишу типове итератора. Неки од њих су:[7]
У различитим програмским језицима
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; // И штампај вредност од 'ставки'
}
//
//Prints 123
Постоје много сорти итератора сваки са мало различитим понашањем, укључујући: напред, назад и бидеркционе итератора; стандардна библиотека шаблона; улазећи и излазећи итератори; и константни итератори (који штити садржину или његове елементе од модификације). Међутим, не подржава сваки тип садржине сваки тип итератора. Могуће је за кориснике да направе свој тип итератора помоћу извођења подкласе од стандардног std::iterator шаблона класе.
Безбедност итератора се дефинише одвојено за различите типове стандарних садржина, у неким случајевима итератор је веома допустив у дозовли садржине да се промени док понавља
Имплицитна итерације је делимично подржана од стране C++ кроз коришћење стандардних функција шаблона, као што јеt std::for_each(),
std::copy()
и
std::accumulate().
Када су коришћени морају бити покренути са постојећим итератором, обично begin и end, који дефинишу опсег на коме се понављање извршава. Али ниједан експлицитни објекат итератора није изложен док понављање траје. Овај пример показује коришћење for_each.
ContainerType<ItemType> C; // Било која стандардна садржина типа ItemType елемената
void ProcessItem(const ItemType& I) { // Функција која ће процесофати сваку ставку збрике
std::cout << I << std::endl;
}
std::for_each(C.begin(), C.end(), ProcessItem); // Фор-ич итерација петље
Исто се може постићи користећи std::copy и std::ostream_iterator
std::copy(C.begin(), C.end(), std::ostream_iterator<ItemType>(std::cout, "\n"));
Ограничење је то да ова техника не дозвољава телу форич петље да буде декларисана у реду, захтева показивач функције или објекат функције да буде декларисан негде другде и да прође као аргумент. Ово се може делимично надокнадити користећи збирку као што је Буст и користећи ламбду да се имплицитно генерише функција објеката са познатом уметнутом синтаксом оператора. Међутим, пошто се Буст спроводи на нивоу библиотеке, него истински у језику, неке ствари се морају урадити помоћи заобилазнице.
Тренутни стандард C++, C++11, изворно подржава ламбда функцију синтаксе, што дозвољава функцији шаблона тела да буде декларисана у реду.
Овде је пример форич понављања користећи ламбда функцију
ContainerType<ItemType> C; // Било која стандардна садржина типа ItemType елемената
// Фор-ич итерација петље са ламбда функцијом
std::for_each(C.begin(), C.end(), [](const ItemType& I){ std::cout << I << std::endl; });
Јава
Представљен у Јави ЈДК 1.2 издању, java.util.IteratorIterator дајеnext()hasNext()remove()iterator().[12]
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(", ");
}
Да би се показало даhasNext() може бити позван неколико пута, користима га да убацимо запете између елемената али не после последњег елемента.
Умајте на уму да овај приступ не раздваја правилно напредну операцију од правог приступа података. Ако елемент податак мора бити коришћен више од сваког напредног, потребно је да буде сачуван у привременој променљивој. Када је напредовање потребно без приступа података (тј. да се прескочи дати елемент података), приступ је ипак изведен, иако је враћена вредност игнорисана у овом случају.
За типове збирки који подржавају то,remove() метода итератора брише најпосећеније елементре из садржине, док чува употребљиве од стране итератора. Додавање или уклањање елемената позивањем меотда садржине (такође од исте нити) чини итератор бескорисним. Покшај да се следећи елемент избаци ствара изузетак. Изузетак се такође одбацује ако нема преосталих елемената (hasNext() је враћено са нетачно).
Поред тога, за java.util.Listjava.util.
J2SE 5.0 издање Јаве представило јеIterablefor (форич) петљу за понављање над збиркама и низовима. Iterable дефинишеiterator()Iterator. Користећи побољшану for петљу, претходни пример може бити записан као
for (MyType obj : list) {
System.out.print(obj);
}
Неке садржине користе старије (још у 1.0) Enumeration класе. То омогућујеhasMoreElements() и nextElement() методе, али нема методе да промени садржину.
Скала
У Скали, итератори имају богат избор метода сличних збиркама, и могу се користити директно у for петљама. Наравно, ова итератора и збирке наслеђују честу заједничку особину- scala.collection.TraversableOnce. Међутим, због богатог избора метода које су доступне у билбиотеци збирке Скале, као што је map, collect, filter, итд., често је неопходно да се опходи са итераторима директно када се програмира у Скали.
Јавини итератори и колекције могу бити аутоматски конвертоване у Скалине итераторе и колекције, односно, једноставно додајући један ред
import scala.collection.JavaConversions._
у директоријум. ЈаваКонверзија објекат омогућује имплицитну конверзију. Имплицитне конверзије су карактеристичне за Скалу: методе које, када су видљиве у тренутном видокругу, аутоматски убацују позиве сами себи у релевантне експресије у пристојно место како бих натерали да се преоверавају када они то не би тели.
MATLAB
MATLAB подржава и спољне и унутрашње имплицитно понављање користећи "природне " редове или cell редове. У случају спољног понављања где је терет над корисником да унапреди пролаз и да захтева следеће елементе, може се дефинисати скуп елемената унутар низа структуре складишта и пренети елементе користећи се for-конструкцијом петље. На пример,
% Дефинисати низ целих бројева
myArray = [1,3,5,7,11,13];
for n = myArray
% ... радити нешто са n
disp(n) % Echo цео број за Command Window
end
пролази кроз низ целих бројева користећиfor кључну реч.
У случају унутрашњег понављања где корисник може снабдевати пореацију итератора да изврши над свим елементима збирке, многи направљени оператори и MATLAB функције су преоптерећени извршењем над сваким елементом низа и враћају имплицитно одговарајући излазни низ. Осим тога, arrayfun и cellfun функције могу бити искоришћене за израду слободних или десинисаних од стране корисника операција над "природним" низовима и cell низова респективно. На пример,
function simpleFun
% Дефинисати низ целих бројева
myArray = [1,3,5,7,11,13];
% Извршити произвољну операцију над сваким елементом
myNewArray = arrayfun(@(a)myCustomFun(a), myArray);
% Echo резултујући низ за Command Window
myNewArray
function outScalar = myCustomFun(inScalar)
% Једноставно помножен са 2
outScalar = 2*inScalar;
дефинише примерну функцију simpleFun која имплицитно прихвата слободну подфункцију myCustomFun сваког елемента низа који користи направљену функцијуarrayfun.
Алтернативно, може бити пожељно да се механизми садржине за складиштење низова учине апстрактним од стране корисника дефинисањем произвољне објектно-оријентисане MATLAB имплементације Шаблона Итератора. Таква имплементација која подржава спољну итерацију је демонстрирана у МАТLAB-у Централној Размени Фајлова ставка Дизајн Шаблона: Итератор (Понашање) . Ово је написано у новој дефиницији класе синтаксе представљен са MATLAB софтвером верзије 7.6(R2008a) и има реализацију једно-димензионалног cell низа Апстрактне Листе Типа Података(АДТ) као механизам за чување хетерогена ( типа података) сета елемената. То омогучује функционалност за експлицитну напредну Листу пролаза саhasNext(), next() и reset() метода за коришћење у while-петљи.
PHP
PHP-ова форич петља је представљена у верзији 4.0 и компатибилна је са предметима као вредности у 4.0 Бета 4 Форич петља.[13] Међутим, подршка за итераторе је додата у PHP 5 кроз представљање интерног[14] Преносиог интерфејс.[15] Два главна интерфејса за реализацију у PHP скриптама који омогућују предметима да буду понављани преко форич петље су Итератор и АгрегатИтератора. Ово последље не захтева имплементацију класе како би се декларисале све тражене методе, уместо тога оно убацује методу ацесоара (getIterator) која враћа инстанцу Преносног . Стандардна PHP Библиотека омогућује неколико класа да раде са специјалним итераторима.[16] PHP такође подржава Генераторе још од 5.5.[17]
Најједноставнија имплементација је умотавањем низа, ово може бити корисно за куцање и сакривање информација.
namespace Wikipedia\Iterator;
final class ArrayIterator extends \Iterator {
private $array;
public function __construct(array $array) {
$this->array = $array;
}
public function rewind() {
echo 'rewinding' , PHP_EOL;
reset($this->array);
}
public function current() {
$value = current($this->array);
echo "current: {$value}" , PHP_EOL;
return $value;
}
public function key() {
$key = key($this->array);
echo "key: {$key}" , PHP_EOL;
return $key;
}
public function next() {
$value = next($this->array);
echo "next: {$value}" , PHP_EOL;
return $value;
}
public function valid() {
$valid = $this->current() !== false;
echo 'valid: ' , ($valid ? 'true' : 'false') , PHP_EOL;
return $valid;
}
}
Све метода примера класе се користе током извршења комплетне форич петље (foreach ($iterator as $key => $current) {}). Итераторове методе се извршавају по следећем редоследу:
$iterator->rewind() осигурава да унутрашња структура почне испочетка.
$iterator->valid() враћа тачно у овом примеру.
$iterator->current() враћена вредност је сачувана у $value.
$iterator->key() враћена вредност је сачувана у $key.
$iterator->next() напредује на следећи елемент у унутрашњој структури.
$iterator->valid() враћа нетачно и шетља је прекинута.
Следећи пример илуструје PHP класу која убацује Преносни интерфејс, који би могао бити обмотан у ИтераторИтератор цласу да делује на податке пре него што се врати у форич петљу. Коришћење заједно са MYSQLI_USE_RESULT константом дозвољава PHP скриптама да понављају резултате сетова са билионима редова са сваким мали коришћењем меморије. Ове карактеристике нису искључиво за PHP или за његову MySQL имплементацију класе (нпр. PDOНаредба класе убацује Преносни интерфејс такође).
mysqli_report(MYSQLI_REPORT_ERROR | MYSQLI_REPORT_STRICT);
$mysqli = new \mysqli('host.example.com', 'username', 'password', 'database_name');
// \mysqli_result класа које је враћена методом позива имплемената интерног Taversable сучеља.
foreach ($mysqli->query('SELECT `a`, `b`, `c` FROM `table`', MYSQLI_USE_RESULT) as $row) {
// Делује на враћени ред, који је асоцијативни низ.
}
Пајтон
Итератору у Пајтону су фундаментални део језика и у многим случајевима прођу невиђени пошто се имплицитно користе у for (форич) наредбама, у листама схватања и у експресијама генератора. Све Пајтонове стандардне збирке типова подржавају понављање, као и много класе које су део стандардне библиотеке. Следећи пример показује типично имплицитно понављање преко секвенце:
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)
Итератори међутим се могу користити и дефинисати експлицитно. ЗА сваку итераблу типа секвенце или класе, уграђена функција iter() се користи да направи предмет итератора. Предмет итератора може бити понављан саi next() функцијом која користи __next__() методу изнутра, која враћа следећи елемент садржине (претходна наредба се односи на Пајтон 3.x. У Пајтон 2.x, next() метода је еквививалентна). StopIteration изузетак ће се подићи када нема преосталих елемената. Следећи пример показује еквивалентно понављање над секвенцом користећи експлицитне итераторе:
it = iter(sequence)
while True:
try:
value = it.next() # у Пајтону 2.x
value = next(it) # у Пајтону 3.x
except StopIteration:
break
it = iter(it)
print(value)
Било која класа дефинисана од корисника може подржати стандардно понављање (било имплицитно или експлицитно) дефинишући методу __iter__() која враћа предмет итератора. Предмет итератора онда тражи да се дефинише __next__() метода која враћа следећи елемент и __iter__() методу која враћа следећи предмет итератора за коришћење
Пајтонов генератор убацује овај протокол понављања.
Руби
Руби убацује итераторе доста другачије; сва понављања се дешавају уз помоћ доношења повратног затварања метода садржине- на овај начин Руби не само да убацује основно понављање али такође неколико шаблона понављања као функција маповања, филтера и смањивања. Руби такође подржава алтернативну синтаксу основног метода понављања each, слдећа три примера су еквивалентна:
(0...42).each do |n|
puts n
end
…и…
for n in 0...42
puts n
end
или краће
42.times do |n|
puts n
end
Рубу може понављати над поправљеним листама користећи Пописиваче или позивањем њихове #следеће метода или радћи форич петљу над њима, као што је горе .
Види још
Референце
- ^ Gatcomb, Joshua.
- ^ а б в Watt, Stephen M. "A Technique for Generic Iteration and Its Optimization" (PDF).
- ^ Alex Allain.
- ^ а б "Difference between an external iterator and an internal iterator".
- ^ Freeman, Eric; Freeman, Elisabeth; Kathy, Sierra; Bert, Bates (2004).
- ^ Vecerina, Ivan (2006-02-01). "index vs iterator".
- ^ а б в Kevin Waterson.
- ^ larsmans (2011-03-06).
- ^ Collier, Andrew.
- ^ "concurrent_unordered_set Template Class" Архивирано на сајту Wayback Machine (1. мај 2015).
- ^ Freeman, Eric; Freeman, Elisabeth; Kathy, Sierra; Bert, Bates (2004).
- ^ "java.util: Interface Iterator<E>: Method Summary".
- ^ "PHP 4 ChangeLog".
- ^ Internal refers to the fact that the interface cannot be implemented in PHP scripts, only in the C (programming language) source.
- ^ "The Traversable interface".
- ^ "Iterators".
- ^ "PHP 5 ChangeLog".
Спољашње везе
