В компьютерном программировании итератор — это объект , который постепенно предоставляет доступ к каждому элементу коллекции по порядку. [1] [2] [3]
Коллекция может предоставлять несколько итераторов через свой интерфейс , которые предоставляют элементы в разном порядке, например, вперед и назад.
Итератор часто реализуется в терминах структуры, лежащей в основе реализации коллекции, и часто тесно связан с коллекцией, чтобы обеспечить операционную семантику итератора.
Итератор по своему поведению похож на курсор базы данных .
Итераторы появились в языке программирования CLU в 1974 году.
Итератор обеспечивает доступ к элементу коллекции ( доступ к элементу ) и может изменять свое внутреннее состояние, чтобы обеспечить доступ к следующему элементу ( обход элемента ). [4] Он также обеспечивает создание и инициализацию первого элемента и указывает, все ли элементы были пройдены. В некоторых контекстах программирования итератор обеспечивает дополнительную функциональность.
Итератор позволяет потребителю обрабатывать каждый элемент коллекции, изолируя потребителя от внутренней структуры коллекции. [2] Коллекция может хранить элементы любым способом, в то время как потребитель может получать к ним доступ как к последовательности.
В объектно-ориентированном программировании класс итератора обычно разрабатывается в тесной координации с соответствующим классом коллекции. Обычно коллекция предоставляет методы для создания итераторов.
Счетчик цикла иногда также называют итератором цикла. Однако счетчик цикла обеспечивает только функциональность обхода, а не функциональность доступа к элементам.
Один из способов реализации итератора — через ограниченную форму сопрограммы , известную как генератор . В отличие от подпрограммы , сопрограмма генератора может возвращать значения своему вызывающему объекту несколько раз, а не возвращать только один раз. Большинство итераторов естественным образом выражаются как генераторы, но поскольку генераторы сохраняют свое локальное состояние между вызовами, они особенно хорошо подходят для сложных итераторов с сохранением состояния, таких как обходчики деревьев . Существуют тонкие различия и отличия в использовании терминов «генератор» и «итератор», которые различаются у разных авторов и языков. [5] В Python генератор — это конструктор итератора : функция, которая возвращает итератор. Ниже приведен пример генератора Python, возвращающего итератор для чисел Фибоначчи с использованием оператора Python yield:
def fibonacci ( limit ): a , b = 0 , 1 для _ в диапазоне ( limit ): yield a a , b = b , a + bдля числа в последовательности Фибоначчи ( 100 ): # Генератор создает итератор print ( число )Внутренний итератор — это функция более высокого порядка (часто принимающая анонимные функции ), которая обходит коллекцию, применяя функцию к каждому элементу. Например, mapфункция Python применяет функцию, определенную вызывающей стороной, к каждому элементу:
цифры = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]squared_digits = map ( lambda x : x ** 2 , digits ) # Итерация по этому итератору даст результат 0, 1, 4, 9, 16, ..., 81.Некоторые объектно-ориентированные языки, такие как C# , C++ (более поздние версии), Delphi (более поздние версии), Go , Java (более поздние версии), Lua , Perl , Python , Ruby предоставляют встроенный способ итерации по элементам коллекции без явного итератора. Объект итератора может существовать, но не представлен в исходном коде. [4] [6]
Неявный итератор часто проявляется в синтаксисе языка как foreach.
В Python объект коллекции можно итерировать напрямую:
для значения в итерируемом : print ( value )В Ruby для итерации требуется доступ к свойству итератора:
итерируемый . каждый do | значение | помещает значение конец Этот стиль итерации иногда называют «внутренней итерацией», поскольку его код полностью выполняется в контексте итерируемого объекта (который управляет всеми аспектами итерации), а программист только предоставляет операцию для выполнения на каждом шаге (используя анонимную функцию ).
Языки, поддерживающие списочные представления или подобные конструкции, также могут использовать неявные итераторы во время построения результирующего списка, как в Python:
имена = [ человек . имя для человека в списке, если человек . мужчина ]Иногда неявная скрытая природа является лишь частичной. В языке C++ есть несколько шаблонов функций для неявной итерации, например for_each(). Эти функции по-прежнему требуют явных объектов итератора в качестве начальных входных данных, но последующая итерация не предоставляет объект итератора пользователю.
Итераторы — это полезная абстракция входных потоков — они предоставляют потенциально бесконечный итерируемый (но не обязательно индексируемый) объект. Несколько языков, такие как Perl и Python, реализуют потоки как итераторы. В Python итераторы — это объекты, представляющие потоки данных. [7] Альтернативные реализации потока включают языки , управляемые данными , такие как AWK и sed .
Вместо использования итератора многие языки позволяют использовать оператор индексации и счетчик циклов для доступа к каждому элементу. Хотя индексация может использоваться с коллекциями, использование итераторов может иметь такие преимущества, как: [8]
Возможность изменения коллекции при итерации ее элементов стала необходимой в современном объектно-ориентированном программировании, где взаимосвязи между объектами и последствия операций могут быть неочевидны. Используя итератор, человек изолируется от подобных последствий. Однако это утверждение следует воспринимать с долей скепсиса, поскольку чаще всего, по соображениям эффективности, реализация итератора настолько тесно связана с коллекцией, что она действительно исключает изменение базовой коллекции, не делая себя недействительной.
Для коллекций, которые могут перемещать свои данные в памяти, единственный способ не сделать итератор недействительным — это каким-то образом отслеживать все активные в данный момент итераторы и обновлять их на лету. Поскольку количество итераторов в определенный момент времени может быть произвольно большим по сравнению с размером связанной коллекции, обновление их всех резко ухудшит гарантию сложности операций коллекции.
Альтернативным способом ограничения количества обновлений относительно размера коллекции было бы использование своего рода механизма дескрипторов, то есть коллекции косвенных указателей на элементы коллекции, которые должны обновляться вместе с коллекцией, и позволить итераторам указывать на эти дескрипторы вместо того, чтобы напрямую на элементы данных. Но такой подход негативно скажется на производительности итератора, поскольку он должен выполнить двойной указатель, следующий за ним, чтобы получить доступ к фактическому элементу данных. Обычно это нежелательно, поскольку многие алгоритмы, использующие итераторы, вызывают операцию доступа к данным итераторов чаще, чем метод advance. Поэтому особенно важно иметь итераторы с очень эффективным доступом к данным.
В целом, это всегда компромисс между безопасностью (итераторы всегда остаются действительными) и эффективностью. В большинстве случаев дополнительная безопасность не стоит той цены эффективности, которую приходится за нее платить. Использование альтернативной коллекции (например, односвязного списка вместо вектора) было бы лучшим выбором (глобально более эффективным), если требуется стабильность итераторов.
Итераторы можно классифицировать по их функциональности. Вот (неполный) список категорий итераторов: [9] [10]
Различные языки или библиотеки, используемые с этими языками, определяют типы итераторов. Некоторые из них [12]
Итераторы в .NET Framework (т. е. C#) называются «перечислителями» и представлены интерфейсом IEnumerator. [15] : 189–190, 344 [16] : 53–54 IEnumerator предоставляет MoveNext()метод, который переходит к следующему элементу и указывает, достигнут ли конец коллекции; [15] : 344 [16] : 55–56 [17] : 89 свойство Current, чтобы получить значение элемента, на который в данный момент указывается. [15] : 344 [16] : 56 [17] : 89 и необязательный Reset()метод, [15] : 344 MoveNext() чтобы перемотать перечислитель обратно в его начальное положение. Перечислитель изначально указывает на специальное значение перед первым элементом, поэтому для начала итерации требуется вызов .
Перечислители обычно получаются путем вызова GetEnumerator()метода объекта, реализующего IEnumerableинтерфейс. [16] : 54–56 [17] : 54–56 свойство Current, чтобы получить значение элемента, на который в данный момент указывается; [15] : 344 [16] : 56 [17] : 89 Классы контейнеров обычно реализуют этот интерфейс. Однако оператор foreach в C# может работать с любым объектом, предоставляющим такой метод, даже если он его не реализует IEnumerable( утиная типизация ). [17] : 89 Оба интерфейса были расширены до универсальных версий в .NET 2.0 .
Ниже показано простое использование итераторов в C# 2.0:
// явная версия IEnumerator < MyType > iter = list . GetEnumerator (); while ( iter . MoveNext ()) Console . WriteLine ( iter . Current ); // неявная версия foreach ( значение MyType в списке ) Console.WriteLine ( значение ) ; C# 2.0 также поддерживает генераторы: метод, объявленный как возвращающий IEnumerator(или IEnumerable), но использующий yield returnоператор " " для создания последовательности элементов вместо возврата экземпляра объекта, будет преобразован компилятором в новый класс, реализующий соответствующий интерфейс.
Язык C++ широко использует итераторы в своей стандартной библиотеке и описывает несколько категорий итераторов, различающихся по набору операций, которые они позволяют. К ним относятся прямые итераторы , двунаправленные итераторы и итераторы с произвольным доступом , в порядке возрастания возможностей. Все стандартные типы шаблонов контейнеров предоставляют итераторы одной из этих категорий. Итераторы обобщают указатели на элементы массива (которые действительно могут использоваться как итераторы), и их синтаксис разработан так, чтобы напоминать арифметику указателей C , где операторы и используются для ссылки на элемент, на который указывает итератор, а операторы арифметики указателей, такие как , используются для изменения итераторов при обходе контейнера.*->++
Обход с использованием итераторов обычно включает один изменяющийся итератор и два фиксированных итератора, которые служат для ограничения диапазона для обхода. Расстояние между ограничивающими итераторами, с точки зрения количества применений оператора, ++необходимых для преобразования нижнего предела в верхний, равно количеству элементов в указанном диапазоне; количество различных значений итератора, задействованных, на единицу больше. По соглашению, нижний ограничивающий итератор «указывает» на первый элемент в диапазоне, в то время как верхний ограничивающий итератор не указывает ни на один элемент в диапазоне, а указывает сразу за концом диапазона. Для обхода всего контейнера метод begin()предоставляет нижний предел и end()верхний предел. Последний вообще не ссылается ни на один элемент контейнера, но является допустимым значением итератора, с которым можно сравнивать.
В следующем примере показано типичное использование итератора.
std :: vector < int > items ; items . push_back ( 5 ); // Добавляем целочисленное значение '5' к вектору 'items'. items . push_back ( 2 ); // Добавляем целочисленное значение '2' к вектору 'items'. items . push_back ( 9 ); // Добавляем целочисленное значение '9' к вектору 'items'. for ( auto it = items . begin (), end = items . end (); it != end ; ++ it ) { // Перебираем 'items'. std :: cout << * it ; // И выводим значение 'items' для текущего индекса. } // В C++11 то же самое можно сделать без использования итераторов: for ( auto x : items ) { std :: cout << x ; // Выводим значение каждого элемента 'x' из 'items'. } // Оба цикла for выводят «529».Типы итераторов отделены от типов контейнеров, с которыми они используются, хотя эти два типа часто используются совместно. Категория итератора (и, следовательно, операции, определенные для него) обычно зависит от типа контейнера, например, массивы или векторы предоставляют итераторы произвольного доступа, но множества (которые используют связанную структуру в качестве реализации) предоставляют только двунаправленные итераторы. Один и тот же тип контейнера может иметь более одного связанного типа итератора; например, std::vector<T>тип контейнера позволяет выполнять обход либо с использованием (сырых) указателей на свои элементы (типа *<T>), либо значений специального типа std::vector<T>::iterator, а еще один тип предоставляется для «обратных итераторов», операции которых определены таким образом, что алгоритм, выполняющий обычный (прямой) обход, фактически выполнит обход в обратном порядке при вызове с обратными итераторами. Большинство контейнеров также предоставляют отдельный const_iteratorтип, для которого операции, которые позволили бы изменять указанные значения, намеренно не определены.
Простой обход объекта-контейнера или диапазона его элементов (включая изменение этих элементов, если не const_iteratorиспользуется a) может быть выполнен с использованием одних только итераторов. Но типы контейнеров также могут предоставлять методы, такие как insertили , eraseкоторые изменяют структуру самого контейнера; это методы класса контейнера, но, кроме того, для указания желаемой операции требуется одно или несколько значений итератора. Хотя возможно иметь несколько итераторов, указывающих на один и тот же контейнер одновременно, операции изменения структуры могут сделать некоторые значения итератора недействительными (стандарт указывает для каждого случая, может ли это быть так); использование недействительного итератора является ошибкой, которая приведет к неопределенному поведению, и такие ошибки не должны сигнализироваться системой времени выполнения.
Неявная итерация также частично поддерживается в C++ посредством использования стандартных шаблонов функций, таких как 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 ); // Цикл итерации for-each. Того же самого можно добиться std::copy, используя передачу std::ostream_iteratorзначения в качестве третьего итератора:
std :: copy ( c.begin ( ) , c.end ( ) , std :: ostream_iterator < ItemType > ( std :: cout , " \n " )); Начиная с C++11 , синтаксис лямбда-функции может использоваться для указания операции, которая должна быть итерирована в строке, избегая необходимости определять именованную функцию. Вот пример итерации for-each с использованием лямбда-функции:
ContainerType < ItemType > c ; // Любой стандартный тип контейнера элементов ItemType. // Цикл итерации for-each с лямбда-функцией. std :: for_each ( c . begin (), c . end (), []( const ItemType & i ) { std :: cout << i << std :: endl ; }); Представленный в выпуске Java JDK 1.2, java.util.Iteratorинтерфейс позволяет итерацию классов контейнеров. Каждый Iteratorпредоставляет метод next()и [18] : 294–295 и может опционально поддерживать метод [18] : 262, 266. Итераторы создаются соответствующим классом контейнера, обычно методом с именем . [19] [18] : 99 [18] : 217 hasNext()remove()iterator()
Метод next()продвигает итератор и возвращает значение, на которое указывает итератор. Первый элемент получается при первом вызове next(). [18] : 294–295 Чтобы определить, когда были посещены все элементы в контейнере, hasNext()используется тестовый метод. [18] : 262 В следующем примере показано простое использование итераторов:
Итератор iter = list.iterator ( ) ; // Итератор <MyType> iter = list.iterator() ; // в 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. [18] : 266 Используя расширенный 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 соответственно, просто добавив одну строку
импорт scala.коллекция.JavaConversions._ в файл. JavaConversionsОбъект предоставляет неявные преобразования для этого. Неявные преобразования являются особенностью Scala: методы, которые, когда они видны в текущей области видимости, автоматически вставляют вызовы самих себя в соответствующие выражения в соответствующем месте, чтобы заставить их проверять типы, когда в противном случае они этого не делали бы.
MATLAB поддерживает как внешнюю, так и внутреннюю неявную итерацию с использованием либо «родных» массивов, либо cellмассивов. В случае внешней итерации, когда ответственность за продвижение обхода и запрос следующих элементов лежит на пользователе, можно определить набор элементов в структуре хранения массива и пройти по элементам с помощью forконструкции -loop. Например,
% Определить массив целых чисел myArray = [ 1 , 3 , 5 , 7 , 11 , 13 ]; for n = myArray % ... сделать что-нибудь с n disp ( n ) % Вывести целое число в командное окно end просматривает массив целых чисел, используя forключевое слово.
В случае внутренней итерации, когда пользователь может предоставить операцию итератору для выполнения над каждым элементом коллекции, многие встроенные операторы и функции MATLAB перегружаются для выполнения над каждым элементом массива и неявного возврата соответствующего выходного массива. Кроме того, функции arrayfunи cellfunмогут быть использованы для выполнения пользовательских или определяемых пользователем операций над «родными» массивами и cellмассивами соответственно. Например,
function simpleFun % Определить массив целых чисел myArray = [ 1 , 3 , 5 , 7 , 11 , 13 ]; % Выполнить пользовательскую операцию над каждым элементом myNewArray = arrayfun (@( a ) myCustomFun ( a ), myArray ); % Вывести результирующий массив в командное окно myNewArrayfunction outScalar = myCustomFun ( inScalar ) % Просто умножаем на 2 outScalar = 2 * inScalar ; определяет основную функцию simpleFun, которая неявно применяет пользовательскую подфункцию myCustomFunк каждому элементу массива, используя встроенную функцию arrayfun.
В качестве альтернативы может быть желательно абстрагировать механизмы контейнера хранения массивов от пользователя, определив пользовательскую объектно-ориентированную реализацию шаблона итератора MATLAB. Такая реализация, поддерживающая внешнюю итерацию, продемонстрирована в элементе MATLAB Central File Exchange Design Pattern: Iterator (Behavioral). Это написано в новом синтаксисе определения классов, введенном в версии программного обеспечения MATLAB 7.6 (R2008a), и включает cellреализацию одномерного массива абстрактного типа данных List (ADT) в качестве механизма для хранения неоднородного (по типу данных) набора элементов. Он предоставляет функциональность для явного прямого обхода спискаhasNext() с помощью методов , next()и reset()для использования в whileцикле .
Цикл PHP был представлен в версии 4.0 и стал совместимым с объектами как значениями в 4.0 Beta 4. foreach[ 20] Однако поддержка итераторов была добавлена в PHP 5 посредством введения внутреннего [21] Traversable интерфейса. [22] Два основных интерфейса для реализации в скриптах PHP, которые позволяют итерировать объекты через foreachцикл, — это Iteratorи IteratorAggregate. Последний не требует, чтобы реализующий класс объявлял все требуемые методы, вместо этого он реализует метод доступа ( getIterator), который возвращает экземпляр Traversable. Стандартная библиотека PHP предоставляет несколько классов для работы со специальными итераторами. [23] PHP также поддерживает генераторы с версии 5.5. [24]
Самая простая реализация — это обертывание массива, это может быть полезно для подсказки типа и сокрытия информации .
пространство имен Wikipedia\Итератор ;окончательный класс ArrayIterator расширяет \Iterator { частный массив $array ; публичная функция __construct ( массив $array ) { $this -> массив = $array ; } публичная функция rewind () : void { echo 'перемотка' , PHP_EOL ; сброс ( $this -> массив ); } публичная функция current () { $value = current ( $this -> array ); echo "current: { $value } " , PHP_EOL ; return $value ; } публичная функция key () { $key = key ( $this -> array ); echo "key: { $key } " , PHP_EOL ; return $key ; } публичная функция 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) {}). Методы итератора выполняются в следующем порядке:
$iterator->rewind()обеспечивает начало внутренней структуры.$iterator->valid()в этом примере возвращает true .$iterator->current()Возвращаемое значение сохраняется в $value.$iterator->key()Возвращаемое значение сохраняется в $key.$iterator->next()переходит к следующему элементу внутренней структуры.$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' );// Класс \mysqli_result, возвращаемый вызовом метода, реализует внутренний интерфейс Traversable. foreach ( $mysqli -> query ( 'SELECT `a`, `b`, `c` FROM `table`' , MYSQLI_USE_RESULT ) as $row ) { // Действуем над возвращенной строкой, которая является ассоциативным массивом. }Итераторы в Python являются фундаментальной частью языка и во многих случаях остаются незамеченными, поскольку они неявно используются в операторе for( foreach ), в списочных включениях и в выражениях генератора . Все стандартные встроенные типы коллекций Python поддерживают итерацию, а также многие классы, являющиеся частью стандартной библиотеки. В следующем примере показана типичная неявная итерация по последовательности:
для значения в последовательности : print ( value )Словари Python (разновидность ассоциативного массива ) также можно перебирать напрямую, когда возвращаются ключи словаря; или items()можно перебирать метод словаря, когда он возвращает соответствующие пары ключ-значение в виде кортежа:
для ключа в словаре : значение = словарь [ ключ ] печать ( ключ , значение )для ключа , значения в словаре . items (): print ( key , value )Однако итераторы можно использовать и определять явно. Для любого типа или класса итерируемой последовательности встроенная функция iter()используется для создания объекта итератора. Затем объект итератора можно итерировать с помощью next()функции, которая использует __next__()метод внутри, возвращающий следующий элемент в контейнере. (Предыдущее утверждение применимо к Python 3.x. В Python 2.x next()метод эквивалентен.) StopIterationИсключение будет вызвано, когда не останется больше элементов. Следующий пример показывает эквивалентную итерацию по последовательности с использованием явных итераторов:
it = iter ( sequence ) while True : try : value = it.next () # в Python 2.x value = next ( it ) # в Python 3.x except StopIteration : break print ( value ) Любой пользовательский класс может поддерживать стандартную итерацию (явную или неявную), определяя __iter__()метод, который возвращает объект итератора. Затем объект итератора должен определить __next__()метод, который возвращает следующий элемент.
Генераторы Python реализуют этот протокол итерации .
Итераторы в Raku являются фундаментальной частью языка, хотя обычно пользователи не должны заботиться об итераторах. Их использование скрыто за API итераций, такими как оператор for, map, grep, индексация списков с помощью .[$idx]и т. д.
В следующем примере показана типичная неявная итерация по коллекции значений:
мои @values = 1 , 2 , 3 ; для @values -> $value { скажем $value}# ВЫХОД: # 1 # 2 # 3Хэши Raku также могут быть напрямую итерированы; это дает Pairобъекты ключ-значение. kvМетод может быть вызван для хеша для итерации по ключу и значениям; keysметод для итерации по ключам хеша; и valuesметод для итерации по значениям хеша.
мой %word-to-number = 'one' => 1 , 'two' => 2 , 'three' => 3 ; для %word-to-number -> $pair { say $pair ;}# ВЫХОД: # три => 3 # один => 1 # два => 2для %слово-в-число . kv -> $key , $value { say "$key: $value" }# ВЫХОД: # три: 3 # один: 1 # два: 2для %слово-в-число . ключи -> $ключ { say "$ключ => " ~ %слово-в-число { $ключ };}# ВЫХОД: # три => 3 # один => 1 # два => 2Однако итераторы можно использовать и определять явно. Для любого итерируемого типа существует несколько методов, которые управляют различными аспектами итерационного процесса. Например, iteratorметод должен возвращать Iteratorобъект, а pull-oneметод должен производить и возвращать следующее значение, если это возможно, или возвращать контрольное значение IterationEnd, если больше значений не может быть произведено. В следующем примере показана эквивалентная итерация по коллекции с использованием явных итераторов:
my @values = 1 , 2 , 3 ; my $it := @values . iterator ; # захватываем итератор для @valuesloop { my $value := $it . pull-one ; # захватить последнее значение итерации if $value =:= IterationEnd ; # остановиться, если мы достигли конца итерации say $value ; }# ВЫХОД: # 1 # 2 # 3Все итерируемые типы в Raku составляют Iterableроль, Iteratorроль или обе. IterableДовольно прост и требует только iteratorреализации составным классом. IteratorБолее сложен и предоставляет ряд методов, таких как pull-one, что позволяет выполнять более тонкую операцию итерации в нескольких контекстах, таких как добавление или исключение элементов или пропуск их для доступа к другим элементам. Таким образом, любой определяемый пользователем класс может поддерживать стандартную итерацию, составляя эти роли и реализуя методы iteratorи/или pull-one.
Класс DNAпредставляет собой цепь ДНК и реализует iteratorпутем составления Iterableроли. Цепь ДНК разделяется на группу тринуклеотидов при итерации:
подмножество Strand of Str , где { . match ( /^^ <[ACGT]>+ $$/ ) и . chars %% 3 }; класс DNA выполняет Iterable { имеет $.chain ; метод new ( Strand:D $chain ) { self . bless: : $chain } метод итератор ( ДНК:D: ){ $.цепь . комб . ротор ( 3 ). итератор }};для ДНК . новый ( 'ГАТТАКАТА' ) { . сказать}# ВЫХОД: # (GAT) # (TAC) # (ATA)сказать ДНК . новый ( 'GATTACATA' ). карта (*. join ). join ( '-' ); # ВЫХОД: # GAT-TAC-ATAКласс Repeaterобъединяет роли Iterableи Iterator:
класс Repeater делает Iterable делает Iterator { имеет Any $.item требуется ; имеет Int $.times требуется ; имеет Int $ ! count = 1 ; мульти метод новый ( $item , $times ) { self . bless: : $item , : $times ; } метод итератор { сам } метод pull-one (--> Mu ) { если $!count <= $!times { $!count += 1 ; вернуть $!item } иначе { вернуть ИтерациюКонец } }}для Повторителя . новый ( "Привет" , 3 ) { . сказать}# ВЫХОД: # Привет # Привет # ПриветRuby реализует итераторы совершенно иначе; все итерации выполняются посредством передачи замыканий обратного вызова в методы контейнера — таким образом Ruby реализует не только базовую итерацию, но и несколько шаблонов итерации, таких как отображение функций, фильтры и сокращение. Ruby также поддерживает альтернативный синтаксис для базового метода итерации each, следующие три примера эквивалентны:
( 0 ... 42 ) . каждый делает | n | помещает n конец ...и...
для n в диапазоне 0 ... 42 помещает n в конец или даже короче
42 . раз сделать | н | положить н конец Ruby также может перебирать фиксированные списки, используя Enumerators и либо вызывая их #nextметод, либо выполняя для них for each, как указано выше.
Rust использует внешние итераторы во всей стандартной библиотеке, в том числе в своем forцикле, который неявно вызывает next()метод итератора, пока он не будет использован. Самый простой forцикл, например, выполняет итерацию по Rangeтипу:
for i in 0 .. 42 { println! ( "{}" , i ); } // Печатает числа от 0 до 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тип реализует пользовательский неограниченный итератор:
структура Фибоначчи ( u64 , u64 ); impl Фибоначчи { pub fn new () -> Self { Self ( 0 , 1 ) } } impl Итератор для Фибоначчи { type Item = u64 ; fn next ( & mut self ) -> Option < Self :: Item > { let next = self . 0 ; self . 0 = self . 1 ; self . 1 = self . 0 + next ; Некоторые ( следующие ) } } let fib = Fibonacci :: new (); for n in fib . skip ( 1 ). step_by ( 2 ). take ( 4 ) { println! ( "{n}" ); } // Печатает 1, 2, 5 и 13 Пользовательский итератор обычно принимает форму ссылки на код, которая при выполнении вычисляет следующий элемент в списке и возвращает его. Когда итератор достигает конца списка, он возвращает согласованное значение.
Итераторы были введены как конструкции, позволяющие выполнять циклы по абстрактным структурам данных, не раскрывая их внутреннего представления.
Вы можете представить себе итератор как указатель на элемент, который является частью большего контейнера элементов.
Внутренний итератор реализуется функциями-членами класса, который имеет логику итерации. Внешний итератор реализуется отдельным классом, который может быть присоединен к объекту, имеющему логику итерации. Преимущество внешнего итератора в том, что многие итераторы могут быть активны одновременно на существующем или одном и том же объекте.
{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )Некоторые авторы используют термин итератор, а другие термин генератор. Некоторые проводят тонкие различия между ними.
{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )Индекс может использоваться только для контейнеров, которые (эффективно) поддерживают произвольный доступ (т. е. прямой доступ к элементу в заданной позиции). Итератор — более общая концепция. Итераторы предлагают эффективный обход связанных списков, файлов и ряда других структур данных. Это часто приводит к генерации более эффективного кода.
{{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка ){{cite web}}: CS1 maint: бот: исходный статус URL неизвестен ( ссылка )•Типы итераторов iterator и const_iterator относятся к категории прямых итераторов
