Итератор

В компьютерном программировании итератор объект — это , который постепенно обеспечивает доступ к каждому элементу коллекции по порядку.

Коллекция может предоставлять через свой интерфейс несколько итераторов , которые предоставляют элементы в разном порядке, например вперед и назад.

Итератор часто реализуется в терминах структуры, лежащей в основе реализации коллекции, и часто тесно связан с коллекцией, чтобы обеспечить операционную семантику итератора.

Итератор по поведению аналогичен курсору базы данных .

Итераторы появились на языке программирования CLU в 1974 году.

Шаблон

Основная статья: Шаблон «Итератор»

Итератор обеспечивает доступ к элементу коллекции ( доступ к элементу ) и может изменить свое внутреннее состояние, чтобы обеспечить доступ к следующему элементу ( обход элемента ). Он также обеспечивает создание и инициализацию первого элемента и указывает, все ли элементы пройдены. В некоторых контекстах программирования итератор предоставляет дополнительные функции.

Итератор позволяет потребителю обрабатывать каждый элемент коллекции, изолируя его от внутренней структуры коллекции. Коллекция может хранить элементы любым способом, а потребитель может получить к ним доступ как к последовательности.

В объектно-ориентированном программировании класс итератора обычно разрабатывается в тесной координации с соответствующим классом коллекции. Обычно коллекция предоставляет методы для создания итераторов.

Счетчик цикла иногда также называют итератором цикла. Однако счетчик циклов обеспечивает только функцию обхода, но не функцию доступа к элементу.

Генератор

Основная статья: Генератор (информатика)

Одним из способов реализации итератора является использование ограниченной формы сопрограммы , известной как генератор . В отличие от подпрограммы , сопрограмма-генератор может возвращать значения вызывающему объекту несколько раз, а не возвращать значение только один раз. Большинство итераторов естественно выражаются как генераторы, но поскольку генераторы сохраняют свое локальное состояние между вызовами, они особенно хорошо подходят для сложных итераторов с отслеживанием состояния, таких как средства обхода деревьев . Существуют тонкие различия и различия в использовании терминов «генератор» и «итератор», которые различаются в зависимости от автора и языка. В Python генератор — это конструктор итератора : функция, возвращающая итератор. Пример генератора Python, возвращающего итератор для чисел Фибоначчи с использованием Python yield заявление следует:

def fibonacci(limit):
    a, b = 0, 1
    for _ in range(limit):
        yield a
        a, b = b, a + b

for number in fibonacci(100): # The generator constructs an iterator
    print(number)

Внутренний итератор

— Внутренний итератор это функция более высокого порядка (часто принимающая анонимные функции ), которая обходит коллекцию, применяя функцию к каждому элементу. Например, Python map Функция применяет функцию, определенную вызывающим абонентом, к каждому элементу:

digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

squared_digits = map(lambda x: x**2, digits)
# Iterating over this iterator would result in 0, 1, 4, 9, 16, ..., 81.

Неявный итератор

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

Неявный итератор часто проявляется в синтаксисе языка как foreach.

В Python объект коллекции можно перебирать напрямую:

for value in iterable:
    print(value)

В Ruby итерация требует доступа к свойству итератора:

iterable.each do |value|
  puts value
end

Этот стиль итерации иногда называют «внутренней итерацией», поскольку его код полностью выполняется в контексте итерируемого объекта (который контролирует все аспекты итерации), а программист предоставляет только операцию для выполнения на каждом шаге (используя анонимную функцию ).

Языки, поддерживающие понимание списков или подобные конструкции, также могут использовать неявные итераторы во время построения списка результатов, как в Python:

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

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

Транслировать

Дополнительная информация: Поток (вычисления)

Итераторы — это полезная абстракция входных потоков — они предоставляют потенциально бесконечный итерируемый (но не обязательно индексируемый) объект. Некоторые языки, такие как Perl и Python, реализуют потоки в качестве итераторов. В Python итераторы — это объекты, представляющие потоки данных. Альтернативные реализации потока включают языки , управляемые данными , такие как AWK и sed .

Контраст с индексацией

Вместо использования итератора многие языки допускают использование оператора индекса и счетчика цикла для доступа к каждому элементу. Хотя индексирование можно использовать с коллекциями, использование итераторов может иметь такие преимущества, как:

• Счетные циклы подходят не для всех структур данных, в частности для структур данных без произвольного доступа или с медленным произвольным доступом , таких как списки или деревья .
• Итераторы могут обеспечить согласованный способ перебора структур данных всех типов и, следовательно, сделать код более читабельным, пригодным для повторного использования и менее чувствительным к изменению структуры данных.
• Итератор может наложить дополнительные ограничения на доступ, например гарантировать, что элементы не могут быть пропущены или что ранее посещенный элемент не может быть доступен во второй раз.
• Итератор может позволить изменять объект коллекции, не делая итератор недействительным. Например, как только итератор выйдет за пределы первого элемента, можно будет вставить дополнительные элементы в начало коллекции с предсказуемыми результатами. При индексировании это проблематично, поскольку номера индексов должны меняться.

Возможность изменения коллекции при переборе ее элементов стала необходимой в современном объектно-ориентированном программировании, где взаимосвязи между объектами и последствиями операций могут быть неочевидны. Используя итератор, вы изолируетесь от подобных последствий. Однако к этому утверждению следует относиться с долей скептицизма, поскольку чаще всего из соображений эффективности реализация итератора настолько тесно привязана к коллекции, что предотвращает модификацию базовой коллекции, не делая себя недействительной.

Для коллекций, которые могут перемещать свои данные в памяти, единственный способ не сделать итератор недействительным — для коллекции каким-то образом отслеживать все активные в данный момент итераторы и обновлять их на лету. Поскольку количество итераторов в данный момент времени может быть сколь угодно большим по сравнению с размером связанной коллекции, их обновление резко ухудшит гарантию сложности операций с коллекцией.

Альтернативный способ привязать количество обновлений к размеру коллекции — использовать своего рода механизм дескриптора, то есть набор косвенных указателей на элементы коллекции, которые должны быть обновлены вместе с коллекцией, и позволить итераторам указывать на эти дескрипторы, а не непосредственно элементы данных. Но этот подход отрицательно повлияет на производительность итератора, поскольку для доступа к фактическому элементу данных он должен использовать двойной указатель. Обычно это нежелательно, поскольку многие алгоритмы, использующие итераторы, вызывают операцию доступа к данным итераторов чаще, чем метод продвижения. Поэтому особенно важно иметь итераторы с очень эффективным доступом к данным.

В общем, это всегда компромисс между безопасностью (итераторы всегда остаются действительными) и эффективностью. В большинстве случаев дополнительная безопасность не стоит тех затрат на эффективность, которые за нее приходится платить. Использование альтернативной коллекции (например, односвязного списка вместо вектора) будет лучшим выбором (в целом более эффективным), если необходима стабильность итераторов.

Классификация

Категории

Итераторы можно разделить на категории в зависимости от их функциональности. Вот (неполный) список категорий итераторов:

Категория	Языки
Двунаправленный итератор	С++
Прямой итератор	С++
Входной итератор	С++
Выходной итератор	С++
Итератор произвольного доступа	С++
Тривиальный итератор	C++ (старый STL )

Типы

Различные языки или библиотеки, используемые с этими языками, определяют типы итераторов. Некоторые из них

Тип	Языки
Итератор массива	PHP , Р
Кэширующий итератор	PHP
Постоянный итератор	С++ , PHP
Итератор каталога	PHP, Питон
Итератор фильтра	PHP, Р
Ограничить итератор	PHP
Список итераторов	Ява , Р
Рекурсивный итератор массива	PHP
XML-итератор	PHP

На разных языках программирования

.СЕТЬ

Итераторы в .NET Framework (т.е. C#) называются «перечислителями» и представляются IEnumerator интерфейс. IEnumerator обеспечивает MoveNext() метод, который переходит к следующему элементу и указывает, достигнут ли конец коллекции; а Current свойство, чтобы получить значение элемента, на который в данный момент указывает. и необязательный Reset() метод, чтобы перемотать перечислитель обратно в исходное положение. Перечислитель изначально указывает на специальное значение перед первым элементом, поэтому вызов MoveNext() требуется, чтобы начать итерацию.

Перечислители обычно получаются путем вызова метода GetEnumerator() метод объекта, реализующий IEnumerable интерфейс. а Current свойство, чтобы получить значение элемента, на который в данный момент указывает; Классы-контейнеры обычно реализуют этот интерфейс. Однако оператор 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", создающий последовательность элементов вместо возврата экземпляра объекта, будет преобразован компилятором в новый класс, реализующий соответствующий интерфейс.

С++

Язык C++ широко использует итераторы в своей стандартной библиотеке и описывает несколько категорий итераторов, различающихся набором операций, которые они допускают. К ним относятся прямые итераторы , двунаправленные итераторы и итераторы произвольного доступа , в порядке возрастания возможностей. Все стандартные типы шаблонов контейнеров предоставляют итераторы одной из этих категорий. Итераторы обобщают указатели на элементы массива (которые действительно могут использоваться как итераторы), а их синтаксис разработан так, чтобы напоминать C арифметику указателей , где * и -> операторы используются для ссылки на элемент, на который указывает итератор, и арифметические операторы указателя, такие как ++ используются для изменения итераторов при обходе контейнера.

Обход с использованием итераторов обычно включает один изменяющийся итератор и два фиксированных итератора, которые служат для ограничения проходимого диапазона. Расстояние между предельными итераторами, по количеству применений оператора ++ необходимый для преобразования нижнего предела в верхний, равный количеству элементов в обозначенном диапазоне; число задействованных различных значений итератора на одно больше. По соглашению нижний ограничивающий итератор «указывает» на первый элемент диапазона, тогда как верхний ограничивающий итератор указывает не на какой-либо элемент в диапазоне, а скорее сразу за концом диапазона. Для обхода всего контейнера begin() метод обеспечивает нижний предел, и end() верхний предел. Последний вообще не ссылается ни на один элемент контейнера, но является допустимым значением итератора, с которым можно сравнивать.

В следующем примере показано типичное использование итератора.

std::vector<int> items;
items.push_back(5); // Append integer value '5' to vector 'items'.
items.push_back(2); // Append integer value '2' to vector 'items'.
items.push_back(9); // Append integer value '9' to vector 'items'.

for (auto it = items.begin(); it != items.end(); ++it) { // Iterate through 'items'.
  std::cout << *it; // And print value of 'items' for current index.
}
// In C++11, the same can be done without using any iterators:
for (auto x : items) {
  std::cout << x; // Print value of each element 'x' of 'items'.
}

// Both of the for loops print "529".

Типы итераторов отделены от типов контейнеров, с которыми они используются, хотя они часто используются совместно. Категория итератора (и, следовательно, операций, определенных для него) обычно зависит от типа контейнера: например, массивы или векторы предоставляют итераторы произвольного доступа, а наборы (которые используют связанную структуру в качестве реализации) предоставляют только двунаправленные итераторы. Один и тот же тип контейнера может иметь более одного связанного типа итератора; например std::vector<T> Тип контейнера допускает обход либо с использованием (необработанных) указателей на его элементы (типа *<T>) или значения специального типа std::vector<T>::iteratorи еще один тип предусмотрен для «обратных итераторов», операции которых определены таким образом, что алгоритм, выполняющий обычный (прямой) обход, фактически будет выполнять обход в обратном порядке при вызове с обратными итераторами. Большинство контейнеров также имеют отдельный const_iterator тип, для которого намеренно не определены операции, позволяющие изменять указанные значения.

Простой обход объекта-контейнера или диапазона его элементов (включая изменение этих элементов, если только const_iterator используется) можно выполнить только с помощью итераторов. Но типы контейнеров также могут предоставлять такие методы, как insert или erase которые изменяют структуру самого контейнера; это методы класса контейнера, но, кроме того, для указания желаемой операции требуется одно или несколько значений итератора. Хотя возможно одновременное использование нескольких итераторов, указывающих на один и тот же контейнер, операции по изменению структуры могут сделать недействительными определенные значения итераторов (стандарт определяет для каждого случая, может ли это быть так); использование недействительного итератора является ошибкой, которая приведет к неопределенному поведению, и о таких ошибках не требуется сигнализировать системе времени выполнения.

Неявная итерация также частично поддерживается 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 that will process each item of the collection.
  std::cout << i << std::endl;
}

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"));

Начиная с C++11 , синтаксис лямбда-функции можно использовать для указания операции, которая будет повторяться в строке, избегая необходимости определять именованную функцию. Вот пример для каждой итерации с использованием лямбда-функции:

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 << std::endl; });

Ява

Представленный в выпуске Java JDK 1.2, java.util.Iterator интерфейс позволяет выполнять итерацию классов контейнера. Каждый Iterator обеспечивает next() и hasNext() метод, и может опционально поддерживать remove() метод. Итераторы создаются соответствующим классом контейнера, обычно с помощью метода с именем iterator().

The 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() ранее возвращал false).

Кроме того, для java.util.List есть java.util.ListIterator с аналогичным API, но который позволяет выполнять итерации вперед и назад, предоставляет текущий индекс в списке и позволяет устанавливать элемент списка на его позицию.

представлены В выпуске Java J2SE 5.0 были Iterable интерфейс для поддержки расширенного for ( foreach ) цикл для перебора коллекций и массивов. Iterable определяет iterator() метод, который возвращает Iterator. Использование расширенного for цикл, предыдущий пример можно переписать как

for (MyType obj : list) {
    System.out.print(obj);
}

Некоторые контейнеры также используют более старую версию (начиная с версии 1.0). Enumeration сорт. Он обеспечивает hasMoreElements() и nextElement() методы, но не имеет методов для изменения контейнера.

Скала

В Scala итераторы имеют богатый набор методов, похожих на коллекции, и могут использоваться непосредственно в циклах for. Действительно, и итераторы, и коллекции наследуют общую базовую черту — scala.collection.TraversableOnce. Однако из-за богатого набора методов, доступных в библиотеке коллекций Scala, таких как map, collect, filter и т. д., зачастую при программировании на Scala нет необходимости напрямую иметь дело с итераторами.

Итераторы и коллекции Java можно автоматически преобразовать в итераторы и коллекции Scala соответственно, просто добавив одну строку

import scala.collection.JavaConversions._

в файл. JavaConversions Для этого объект предоставляет неявные преобразования. Неявные преобразования — это особенность Scala: методы, которые, будучи видимыми в текущей области видимости, автоматически вставляют вызовы самих себя в соответствующие выражения в соответствующем месте, чтобы выполнить проверку типов, если в противном случае этого бы не произошло.

МАТЛАБ

MATLAB поддерживает как внешнюю, так и внутреннюю неявную итерацию, используя либо «родные» массивы, либо cell массивы. В случае внешней итерации, когда пользователь несет ответственность за продвижение обхода и запрос следующих элементов, можно определить набор элементов в структуре хранения массива и перемещаться по элементам, используя for-конструкция цикла. Например,

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

for n = myArray
   % ... do something with n
   disp(n)  % Echo integer to Command Window
end

обходит массив целых чисел, используя for ключевое слово.

В случае внутренней итерации, когда пользователь может предоставить итератору операцию для выполнения над каждым элементом коллекции, многие встроенные операторы и функции MATLAB перегружаются для выполнения над каждым элементом массива и неявного возврата соответствующего выходного массива. . Кроме того, arrayfun и cellfun функции можно использовать для выполнения пользовательских или определяемых пользователем операций над «родными» массивами и cell массивы соответственно. Например,

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.

В качестве альтернативы может быть желательно абстрагировать механизмы контейнера хранения массива от пользователя путем определения пользовательской объектно-ориентированной реализации MATLAB шаблона итератора. Такая реализация, поддерживающая внешнюю итерацию, продемонстрирована в шаблоне проектирования элемента MATLAB Central File Exchange: Iterator (Behavioral) . Это написано в новом синтаксисе определения класса, представленном в программном обеспечении MATLAB версии 7.6 (R2008a), и имеет одномерное представление. cell массивовая реализация абстрактного типа данных списка (ADT) как механизма хранения разнородного (по типу данных) набора элементов. Он предоставляет функциональность для явного прямого обхода списка с помощью hasNext(), next() и reset() методы использования в while-петля.

PHP

UML class diagram of the Iterator interface in PHP

PHP ​ foreach Цикл был представлен в версии 4.0 и стал совместимым с объектами как значениями в версии 4.0 Beta 4. Однако поддержка итераторов была добавлена ​​в PHP 5 благодаря введению внутреннего Traversable интерфейс. Два основных интерфейса для реализации в сценариях PHP, которые позволяют выполнять итерацию объектов с помощью foreach петля Iterator и IteratorAggregate. Последний не требует, чтобы реализующий класс объявлял все необходимые методы, вместо этого он реализует метод доступа ( getIterator), который возвращает экземпляр Traversable. Стандартная библиотека PHP предоставляет несколько классов для работы со специальными итераторами. PHP также поддерживает генераторы, начиная с версии 5.5.

Самая простая реализация — это перенос массива, это может быть полезно для подсказки типов и сокрытия информации .

namespace Wikipedia\Iterator;

final class ArrayIterator extends \Iterator
{
    private array $array;

    public function __construct(array $array)
    {
        $this->array = $array;
    }

    public function rewind(): void
    {
        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(): bool
    {
        $valid = $this->current() !== false;
        echo 'valid: ', ($valid ? 'true' : 'false'), PHP_EOL;
        return $valid;
    }
}

Все методы примера класса используются во время выполнения полного цикла foreach ( foreach ($iterator as $key => $current) {}). Методы итератора выполняются в следующем порядке:

1. $iterator->rewind() гарантирует, что внутренняя структура начинается с самого начала.
2. $iterator->valid() возвращает true в этом примере.
3. $iterator->current() возвращаемое значение сохраняется в $value.
4. $iterator->key() возвращаемое значение сохраняется в $key.
5. $iterator->next() переходит к следующему элементу внутренней структуры.
6. $iterator->valid() возвращает false и цикл прерывается.

Следующий пример иллюстрирует класс PHP, реализующий Traversable интерфейс, который можно обернуть в IteratorIterator класс для воздействия на данные до того, как они будут возвращены в foreach петля. Использование вместе с MYSQLI_USE_RESULT константа позволяет сценариям PHP перебирать наборы результатов с миллиардами строк с очень небольшим использованием памяти. Эти функции не являются исключительными ни для PHP, ни для его реализаций классов MySQL (например, PDOStatement класс реализует Traversable интерфейс тоже).

mysqli_report(MYSQLI_REPORT_ERROR | MYSQLI_REPORT_STRICT);
$mysqli = new \mysqli('host.example.com', 'username', 'password', 'database_name');

// The \mysqli_result class that is returned by the method call implements the internal Traversable interface.
foreach ($mysqli->query('SELECT `a`, `b`, `c` FROM `table`', MYSQLI_USE_RESULT) as $row) {
    // Act on the returned row, which is an associative array.
}

Питон

Итераторы в Python являются фундаментальной частью языка и во многих случаях остаются незамеченными, поскольку они неявно используются в for ( foreach ), в списках и в выражениях генератора . Все стандартные встроенные типы коллекций Python поддерживают итерацию, а также многие классы, входящие в стандартную библиотеку. В следующем примере показана типичная неявная итерация последовательности:

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() метод эквивалентен.) A 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__() метод, который возвращает следующий элемент.

Python Генераторы реализуют этот протокол итерации .

Раку

Итераторы в Raku являются фундаментальной частью языка, хотя обычно пользователям не нужно заботиться об итераторах. Их использование скрыто за API-интерфейсами итерации, такими как for заявление, map, grep, индексация списка с помощью .[$idx], и т. д.

В следующем примере показана типичная неявная итерация над набором значений:

my @values = 1, 2, 3;
for @values -> $value {
    say $value
}
# OUTPUT:
# 1
# 2
# 3

Хэши Raku также можно перебирать напрямую; это дает ключ-значение Pair объекты. kv метод можно вызвать для хеша для перебора ключа и значений; тот keys метод для перебора ключей хеша; и values метод для перебора значений хеша.

my %word-to-number = 'one' => 1, 'two' => 2, 'three' => 3;
for %word-to-number -> $pair {
    say $pair;
}
# OUTPUT:
# three => 3
# one => 1
# two => 2

for %word-to-number.kv -> $key, $value {
    say "$key: $value" 
}
# OUTPUT:
# three: 3
# one: 1
# two: 2

for %word-to-number.keys -> $key {
    say "$key => " ~ %word-to-number{$key};
}
# OUTPUT:
# three => 3
# one => 1
# two => 2

Однако итераторы можно использовать и определять явно. Для любого итерируемого типа существует несколько методов, управляющих различными аспектами итерационного процесса. Например, iterator метод должен возвращать Iterator объект, и pull-one метод должен создавать и возвращать следующее значение, если это возможно, или возвращать контрольное значение IterationEnd если больше ценностей не может быть произведено. В следующем примере показана эквивалентная итерация по коллекции с использованием явных итераторов:

my @values = 1, 2, 3;
my $it := @values.iterator;          # grab iterator for @values

loop {
    my $value := $it.pull-one;       # grab iteration's next value
    last if $value =:= IterationEnd; # stop if we reached iteration's end
    say $value;
}
# OUTPUT:
# 1
# 2
# 3

Все итерируемые типы в Raku составляют Iterable роль, Iterator роль или обе. Iterable довольно просто и требует только iterator который будет реализован составляющим классом. Iterator является более сложным и предоставляет ряд методов, таких как pull-one, что позволяет более точно выполнять итерацию в нескольких контекстах, например добавлять или удалять элементы или пропускать их для доступа к другим элементам. Таким образом, любой определяемый пользователем класс может поддерживать стандартную итерацию путем составления этих ролей и реализации iterator и/или pull-one методы.

The DNA класс представляет цепь ДНК и реализует iterator путем составления Iterable роль. Цепь ДНК при повторении разбивается на группу тринуклеотидов:

subset Strand of Str where { .match(/^^ <[ACGT]>+ $$/) and .chars %% 3 };
class DNA does Iterable {
    has $.chain;
    method new(Strand:D $chain) {
        self.bless: :$chain
    }
 
    method iterator(DNA:D:){ $.chain.comb.rotor(3).iterator }
};

for DNA.new('GATTACATA') {
    .say
}
# OUTPUT:
# (G A T)
# (T A C)
# (A T A)

say DNA.new('GATTACATA').map(*.join).join('-');
# OUTPUT:
# GAT-TAC-ATA

The Repeater класс включает в себя как Iterable и Iterator роли:

class Repeater does Iterable does Iterator {
    has Any $.item  is required;
    has Int $.times is required;
    has Int $!count = 1;
    
    multi method new($item, $times) {
        self.bless: :$item, :$times;
    }
    
    method iterator { self }
    method pull-one(--> Mu){ 
        if $!count <= $!times {
            $!count += 1;
            return $!item
        }
        else {
            return IterationEnd
        }
    }
}

for Repeater.new("Hello", 3) {
    .say
}

# OUTPUT:
# Hello
# Hello
# Hello

Руби

Ruby реализует итераторы совершенно по-другому; все итерации выполняются посредством передачи замыканий обратного вызова методам контейнера — таким образом Ruby реализует не только базовую итерацию, но и несколько шаблонов итерации, таких как отображение функций, фильтры и сокращение. Ruby также поддерживает альтернативный синтаксис для базового метода итерации. each, следующие три примера эквивалентны:

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

...и...

for n in 0...42
  puts n
end

или даже короче

42.times do |n|
  puts n
end

Ruby также может перебирать фиксированные списки, используя Enumerators и либо позвонить им #next метод или выполнить для каждого из них, как указано выше.

Ржавчина

Rust использует внешние итераторы во всей стандартной библиотеке, в том числе в ее for цикл, который неявно вызывает next() метод итератора, пока он не будет использован. Самый простой for цикл, например, перебирает Range тип:

for i in 0..42 {
    println!("{}", i);
}
// Prints the numbers 0 to 41

В частности, for цикл будет вызывать значение into_iter() метод, который возвращает итератор, который, в свою очередь, возвращает элементы в цикл. for (или любой метод, использующий итератор), продолжается до тех пор, пока не будет next() метод возвращает None значение (итерации, дающие элементы, возвращают Some(T) значение, где T — тип элемента).

Все коллекции, предоставляемые стандартной библиотекой, реализуют IntoIterator черта (то есть они определяют into_iter() метод). Сами итераторы реализуют Iterator признак, который требует определения next() метод. Кроме того, любой тип реализации Iterator автоматически предоставляется реализация для IntoIterator который возвращается сам.

Итераторы поддерживают различные адаптеры ( map(), filter(), skip(), take()и т. д.) как методы, автоматически предоставляемые Iterator черта.

Пользователи могут создавать собственные итераторы, создавая тип, реализующий Iterator черта. Пользовательские коллекции могут реализовать IntoIterator типаж и возвращать связанный тип итератора для своих элементов, что позволяет использовать их непосредственно в for петли. Ниже Fibonacci type реализует собственный неограниченный итератор:

struct Fibonacci(u64, u64);

impl Fibonacci {
    pub fn new() -> Self {
        Self(0, 1)
    }
}

impl Iterator for Fibonacci {
    type Item = u64;

    fn next(&mut self) -> Option<Self::Item> {
        let next = self.0;
        self.0 = self.1;
        self.1 = self.0 + next;

        Some(next)
    }
}

let fib = Fibonacci::new();
for n in fib.skip(1).step_by(2).take(4) {
    println!("{n}");
}
// Prints 1, 2, 5, and 13

См. также

• итерируемый
• Шаблон проектирования (информатика) — многоразовый дизайн для написания кода, обеспечивающий четко определенную функцию. Страницы, отображающие краткие описания целей перенаправления.
• Диапазон (информатика) - концепция компьютерного программирования. Страницы, отображающие описания викиданных в качестве запасного варианта.
• Шаблон посетителя . Шаблон проектирования программного обеспечения.

Внешние ссылки

• Объяснение Java-итераторов, Iterable и ListIterator
• .NET-интерфейс
• Статья « Понимание и использование итераторов ». Джошуа Гэткомба
• Статья « Техника общей итерации и ее оптимизации » (217 КБ) Стивена М. Уотта
• Итераторы
• Библиотека итераторов Boost C++
• Java-интерфейс
• PHP: итерация объектов
• STL-итераторы
• Что такое итераторы? - Справочное описание