В компьютерном программировании итератор — это объект , который позволяет программисту перемещаться по контейнеру , в частности по спискам . [1] [2] [ 3 ] Различные типы итераторов часто предоставляются через интерфейс контейнера . Хотя интерфейс и семантика данного итератора фиксированы, итераторы часто реализуются в терминах структур, лежащих в основе реализации контейнера, и часто тесно связаны с контейнером, чтобы обеспечить операционную семантику итератора. Итератор выполняет обход, а также предоставляет доступ к элементам данных в контейнере, но сам не выполняет итерацию (т . е. не без некоторой значительной свободы, допущенной с этой концепцией или с тривиальным использованием терминологии ) .
Итератор по своему поведению аналогичен курсору базы данных . Итераторы появились на языке программирования CLU в 1974 году.
Внутренние итераторы — это функции более высокого порядка (часто принимающие анонимные функции , но не обязательно), такие как map()
и reduce()
т. д., реализующие обход контейнера, по очереди применяющие данную функцию к каждому элементу. map
Примером может быть функция Python :
цифры = [ 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 ]Squared_digits = Map ( лямбда x : x ** 2 , digits ) # Итерация по этому итератору приведет к получению 0, 1, 4, 9, 16, ..., 81.
Внешний итератор можно рассматривать как тип указателя , который выполняет две основные операции: ссылку на один конкретный элемент в коллекции объектов (называемый доступом к элементу ) и изменение самого себя, чтобы он указывал на следующий элемент (называемый обходом элемента ). [4] Также должен быть способ создать итератор, чтобы он указывал на некоторый первый элемент, а также какой-то способ определить, когда итератор исчерпал все элементы в контейнере. В зависимости от языка и предполагаемого использования итераторы могут также предоставлять дополнительные операции или демонстрировать различное поведение.
Основная цель итератора — позволить пользователю обрабатывать каждый элемент контейнера, изолируя пользователя от внутренней структуры контейнера. [2] Это позволяет контейнеру хранить элементы любым способом, позволяя пользователю обращаться с ними так, как если бы это была простая последовательность или список. Класс итератора обычно разрабатывается в тесной координации с соответствующим классом-контейнером. Обычно контейнер предоставляет методы для создания итераторов.
Счетчик цикла иногда также называют итератором цикла. Однако счетчик циклов обеспечивает только функцию обхода, но не функцию доступа к элементу.
Одним из способов реализации итераторов является использование ограниченной формы сопрограммы , известной как генератор . В отличие от подпрограммы , сопрограмма-генератор может возвращать значения вызывающему объекту несколько раз, а не возвращать значение только один раз. Большинство итераторов естественно выражаются как генераторы, но поскольку генераторы сохраняют свое локальное состояние между вызовами, они особенно хорошо подходят для сложных итераторов с отслеживанием состояния, таких как средства обхода деревьев . Существуют тонкие различия и различия в использовании терминов «генератор» и «итератор», которые различаются в зависимости от автора и языка. [5] В Python генератор — это конструктор итератора : функция, возвращающая итератор. Ниже приведен пример генератора Python, возвращающего итератор для чисел Фибоначчи с использованием оператора Python yield
:
def fibonacci ( limit ): a , b = 0 , 1 для _ в диапазоне ( limit ): выход a a , b = b , a + bfor number in fibonacci ( 100 ): # Генератор создает итератор print ( number )
Некоторые объектно-ориентированные языки, такие как C# , C++ (более поздние версии), Delphi (более поздние версии), Go , Java (более поздние версии), Lua , Perl , Python , Ruby, предоставляют встроенный способ перебора элементов объекта-контейнера без введение явного объекта-итератора. Фактический объект-итератор может существовать в реальности, но если он и существует, то он не отображается в исходном коде языка. [4] [6]
Неявные итераторы часто проявляются с помощью оператора foreach (или его эквивалента), например, в следующем примере Python:
для значения в итерации : print ( value )
В Python итерируемый объект — это объект, который можно преобразовать в итератор, который затем повторяется во время цикла for; это делается неявно.
Или в других случаях они могут быть созданы самим объектом коллекции, как в этом примере Ruby:
итерируемый . каждый делает | ценность | ставит конец значения
Этот стиль итерации иногда называют «внутренней итерацией», поскольку его код полностью выполняется в контексте итерируемого объекта (который контролирует все аспекты итерации), а программист предоставляет только операцию для выполнения на каждом шаге (используя анонимную функцию ).
Языки, поддерживающие понимание списков или подобные конструкции, также могут использовать неявные итераторы во время построения списка результатов, как в Python:
имена = [ человек . имя человека в списке , если человек . мужской ]
Иногда неявная скрытая природа является лишь частичной. В языке C++ имеется несколько шаблонов функций для неявной итерации, например for_each()
. Эти функции по-прежнему требуют явных объектов итератора в качестве исходных входных данных, но последующая итерация не предоставляет пользователю объект итератора.
Итераторы — это полезная абстракция входных потоков — они предоставляют потенциально бесконечный итерируемый (но не обязательно индексируемый) объект. Некоторые языки, такие как Perl и Python, реализуют потоки в качестве итераторов. В Python итераторы — это объекты, представляющие потоки данных. [7] Альтернативные реализации потока включают языки , управляемые данными , такие как AWK и sed .
В процедурных языках обычно используется оператор индекса и счетчик цикла для перебора всех элементов последовательности, например массива. Хотя индексирование также может использоваться с некоторыми объектно-ориентированными контейнерами, использование итераторов может иметь некоторые преимущества: [8]
Возможность модификации контейнера при переборе его элементов стала необходимой в современном объектно-ориентированном программировании, где взаимосвязи между объектами и последствиями операций могут быть неочевидны. Используя итератор, вы изолируетесь от подобных последствий. Однако к этому утверждению следует относиться с долей скептицизма, поскольку чаще всего из соображений эффективности реализация итератора настолько тесно привязана к контейнеру, что предотвращает модификацию базового контейнера, не делая себя недействительным.
Для контейнеров, которые могут перемещать свои данные в памяти, единственный способ не сделать итератор недействительным — это каким-то образом отслеживать все активные в данный момент итераторы и обновлять их на лету. Поскольку количество итераторов в данный момент времени может быть сколь угодно большим по сравнению с размером связанного контейнера, их обновление резко ухудшит гарантию сложности операций контейнера.
Альтернативный способ привязать количество обновлений к размеру контейнера — использовать своего рода механизм дескрипторов, то есть набор косвенных указателей на элементы контейнера, которые должны быть обновлены вместе с контейнером, и позволить итераторам указывать на эти дескрипторы, а не непосредственно элементы данных. Но этот подход отрицательно повлияет на производительность итератора, поскольку для доступа к фактическому элементу данных он должен использовать двойной указатель. Обычно это нежелательно, поскольку многие алгоритмы, использующие итераторы, вызывают операцию доступа к данным итераторов чаще, чем метод продвижения. Поэтому особенно важно иметь итераторы с очень эффективным доступом к данным.
В общем, это всегда компромисс между безопасностью (итераторы всегда остаются действительными) и эффективностью. В большинстве случаев дополнительная безопасность не стоит тех затрат на эффективность, которые за нее приходится платить. Использование альтернативного контейнера (например, односвязного списка вместо вектора) будет лучшим выбором (в целом более эффективным), если необходима стабильность итераторов.
Итераторы можно разделить на категории в зависимости от их функциональности. Вот (неполный) список категорий итераторов: [9] [10]
Различные языки или библиотеки, используемые с этими языками, определяют типы итераторов. Некоторые из них [12]
Итераторы в .NET Framework называются «перечислителями» и представлены интерфейсом 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 . ПолучитьПеречислитель (); while ( iter . MoveNext ()) Консоль . WriteLine ( итер . Текущий ); // неявная версия foreach ( значение MyType в списке ) Console . WriteLine ( значение );
C# 2.0 также поддерживает генераторы: метод, объявленный как возвращающий IEnumerator
(или IEnumerable
), но использующий yield return
оператор " " для создания последовательности элементов вместо возврата экземпляра объекта, будет преобразован компилятором в новый класс, реализующий соответствующий интерфейс. .
Язык C++ широко использует итераторы в своей стандартной библиотеке и описывает несколько категорий итераторов, различающихся набором операций, которые они допускают. К ним относятся прямые итераторы , двунаправленные итераторы и итераторы произвольного доступа , в порядке возрастания возможностей. Все стандартные типы шаблонов контейнеров предоставляют итераторы одной из этих категорий. Итераторы обобщают указатели на элементы массива (которые действительно могут использоваться как итераторы), а их синтаксис напоминает синтаксис арифметики указателей C , где операторы и используются для ссылки на элемент, на который указывает итератор, и операторы арифметики указателей. Like используются для изменения итераторов при обходе контейнера.*
->
++
Обход с использованием итераторов обычно включает один изменяющийся итератор и два фиксированных итератора, которые служат для ограничения проходимого диапазона. Расстояние между ограничивающими итераторами, по количеству применений оператора, ++
необходимого для преобразования нижнего предела в верхний, равно количеству элементов в обозначенном диапазоне; число задействованных различных значений итератора на одно больше. По соглашению, нижний ограничивающий итератор «указывает» на первый элемент диапазона, тогда как верхний ограничивающий итератор указывает не на какой-либо элемент в диапазоне, а скорее сразу за концом диапазона. Для обхода всего контейнера begin()
метод предоставляет нижний и end()
верхний предел. Последний вообще не ссылается ни на один элемент контейнера, но является допустимым значением итератора, с которым можно сравнивать.
В следующем примере показано типичное использование итератора.
std :: vector <int> items ; предметы . push_back ( 5 ); // Добавляем целое значение '5' к вектору 'items'. предметы . push_back ( 2 ); // Добавляем целое значение '2' к вектору 'items'. предметы . push_back ( 9 ); // Добавляем целое значение '9' к вектору 'items'. for ( auto it = items.begin (); it != items.end ( ) ; ++ it ) { // Перебираем 'items' . std :: cout << * it ; // И выводим значение «элементов» для текущего индекса. } // В 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
используется) может быть выполнен с использованием только итераторов. Но типы контейнеров также могут предоставлять такие методы, как 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 ) ; // Цикл для каждой итерации.
То же самое можно добиться, используя std::copy
, передав std::ostream_iterator
значение в качестве третьего итератора:
std :: copy ( c.begin ( ) , c.end ( ), std :: ostream_iterator <ItemType> ( std :: cout , " \ n " ) ) ;
Начиная с C++11 , синтаксис лямбда-функции можно использовать для указания операции, которая будет повторяться в строке, избегая необходимости определять именованную функцию. Вот пример для каждой итерации с использованием лямбда-функции:
ContainerType < ItemType > c ; // Любой стандартный тип контейнера элементов ItemType. // Цикл для каждой итерации с лямбда-функцией. std :: for_each ( c.begin ( ), c.end (), [ ]( const ItemType & i ) { std :: cout << i << std :: endl ; } ) ;
Этот интерфейс , представленный в выпуске Java JDK 1.2, java.util.Iterator
позволяет выполнять итерацию классов контейнеров. Каждый из них Iterator
предоставляет метод next()
and hasNext()
, [18] : 294–295 и может дополнительно поддерживать метод remove()
[18] : 262, 266 . Итераторы создаются соответствующим классом контейнера, обычно с помощью метода с именем iterator()
. [19] [18] : 99 [18] : 217
Метод next()
перемещает итератор и возвращает значение, на которое указывает итератор. Первый элемент получается при первом вызове next()
. [18] : 294–295 Чтобы определить, когда все элементы контейнера были посещены, hasNext()
используется метод тестирования. [18] : 262 В следующем примере показано простое использование итераторов:
Итератор iter = список . итератор (); // Итератор<MyType> iter = list.iterator(); // в J2SE 5.0 while ( iter . hasNext ()) { System . вне . печать ( iter . next ()); if ( iter . hasNext ()) System . вне . Распечатать ( ", " ); }
Чтобы показать, что его hasNext()
можно вызывать повторно, мы используем его для вставки запятых между элементами, но не после последнего элемента.
Этот подход не позволяет должным образом отделить предварительную операцию от фактического доступа к данным. Если элемент данных необходимо использовать более одного раза для каждого продвижения, его необходимо сохранить во временной переменной. Когда необходимо продвижение вперед без доступа к данным (т.е. для пропуска данного элемента данных), доступ, тем не менее, выполняется, хотя возвращаемое значение в этом случае игнорируется.
Для типов коллекций, которые его поддерживают, remove()
метод итератора удаляет из контейнера последний посещенный элемент, сохраняя при этом итератор пригодным для использования. Добавление или удаление элементов путем вызова методов контейнера (тоже из того же потока ) делает итератор непригодным для использования. Попытка получить следующий элемент вызывает исключение. Исключение также выдается, если больше не осталось элементов ( hasNext()
ранее возвращалось false).
Кроме того, java.util.List
существует java.util.ListIterator
аналогичный API, но который позволяет выполнять итерации вперед и назад, предоставляет текущий индекс в списке и позволяет устанавливать элемент списка на его позицию.
В выпуске Java J2SEIterable
5.0 появился интерфейс для поддержки расширенного цикла for
( foreach ) для перебора коллекций и массивов. Iterable
определяет iterator()
метод, который возвращает Iterator
. [18] : 266 Используя расширенный for
цикл, предыдущий пример можно переписать как
for ( MyType obj : list ) { System . вне . печать ( объект ); }
Некоторые контейнеры также используют более старый (начиная с версии 1.0) Enumeration
класс. Он предоставляет методы hasMoreElements()
и nextElement()
, но не имеет методов для изменения контейнера.
В Scala итераторы имеют богатый набор методов, похожих на коллекции, и могут использоваться непосредственно в циклах for. Действительно, и итераторы, и коллекции наследуют общую базовую черту — scala.collection.TraversableOnce
. Однако из-за богатого набора методов, доступных в библиотеке коллекций Scala, таких как map
, collect
и filter
т. д., часто нет необходимости напрямую иметь дело с итераторами при программировании на Scala.
Итераторы и коллекции Java можно автоматически преобразовать в итераторы и коллекции Scala соответственно, просто добавив одну строку
импортировать скалу . коллекция . JavaКонверсии . _
в файл. JavaConversions
Для этого объект предоставляет неявные преобразования . Неявные преобразования — это особенность Scala: методы, которые, будучи видимыми в текущей области видимости, автоматически вставляют вызовы самих себя в соответствующие выражения в соответствующем месте, чтобы выполнить проверку типов, если в противном случае этого бы не произошло.
MATLAB поддерживает как внешнюю, так и внутреннюю неявную итерацию с использованием «родных» массивов или cell
массивов. В случае внешней итерации, когда пользователь несет ответственность за продвижение обхода и запрос следующих элементов, можно определить набор элементов в структуре хранения массива и перемещаться по элементам, используя конструкцию for
-loop. Например,
% Определить массив целых чисел myArray = [ 1 , 3 , 5 , 7 , 11 , 13 ]; for n = myArray % ... сделайте что-нибудь с n disp ( n ) % Эхо целого числа до конца командного окна
обходит массив целых чисел, используя 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: Iterator (Behavioral). cell
Он написан с использованием нового синтаксиса определения класса, представленного в программном обеспечении MATLAB версии 7.6 (R2008a), и представляет собой реализацию одномерного массива абстрактного типа данных списка (ADT) в качестве механизма хранения гетерогенного (по типу данных) набора элементы. Он предоставляет функциональность для явного прямого обхода списка с помощью hasNext()
, next()
и reset()
методы для использования в while
-цикле.
Цикл PHP был представлен в версии 4.0 и стал совместимым с объектами как значениями в версии 4.0 Beta 4. [20] Однако поддержка итераторов была добавлена в PHP foreach
5 посредством введения внутреннего [21] интерфейса. [22] Двумя основными интерфейсами реализации в PHP-скриптах, которые позволяют выполнять итерацию объектов через цикл, являются и . Последний не требует, чтобы реализующий класс объявлял все необходимые методы, вместо этого он реализует метод доступа ( ), который возвращает экземпляр . Стандартная библиотека PHP предоставляет несколько классов для работы со специальными итераторами. [23] PHP также поддерживает генераторы, начиная с версии 5.5. [24] Traversable
foreach
Iterator
IteratorAggregate
getIterator
Traversable
Самая простая реализация — это перенос массива, это может быть полезно для подсказки типов и сокрытия информации .
пространство имен Wikipedia\Iterator ;последний класс ArrayIterator расширяет \Iterator { частный массив $array ; общественная функция __construct ( массив $array ) { $this -> array = $array ; } публичная функция перемотки () : void { echo 'перемотка' , PHP_EOL ; сброс ( $this -> массив ); } публичная функция current () { $value = current ( $this -> array ); echo "текущий: { $value } " , PHP_EOL ; вернуть $значение ; } открытый функциональный ключ () { $key = ключ ( $this -> массив ); echo "key: { $key } " , PHP_EOL ; вернуть $ключ ; } общественная функция next () { $value = next ( $this -> array ); echo "следующий: { $value } " , PHP_EOL ; вернуть $значение ; } общедоступная функция valid () : bool { $valid = $this -> current () !== false ; echo 'valid:' , ( $valid ? 'true' : 'false' ), PHP_EOL ; вернуть $действительный ; } }
Все методы примера класса используются во время выполнения полного цикла 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 = новый \mysqli ( 'host.example.com' , 'имя пользователя' , 'пароль' , 'имя_базы_данных' );// Класс \mysqli_result, возвращаемый вызовом метода, реализует внутренний интерфейс Traversable. foreach ( $mysqli -> query ( 'SELECT `a`, `b`, `c` FROM `table`' , MYSQLI_USE_RESULT ) as $row ) { // Действуем над возвращаемой строкой, которая представляет собой ассоциативный массив. }
Итераторы в Python являются фундаментальной частью языка и во многих случаях остаются незамеченными, поскольку они неявно используются в операторе for
( foreach ), в списочных генераторах и выражениях-генераторах . Все стандартные встроенные типы коллекций Python поддерживают итерацию, а также многие классы, входящие в стандартную библиотеку. В следующем примере показана типичная неявная итерация последовательности:
для значения в последовательности : печать ( значение )
Словари Python (разновидность ассоциативного массива ) также можно перебирать напрямую, когда возвращаются ключи словаря; или items()
метод словаря можно перебрать, где он дает соответствующие пары ключ-значение в виде кортежа:
для ключа в словаре : значение = словарь [ ключ ] печать ( ключ , значение )
для ключа , значения в словаре . элементы (): печать ( ключ , значение )
Однако итераторы можно использовать и определять явно. Для любого типа или класса итерируемой последовательности встроенная функция iter()
используется для создания объекта итератора. Затем объект итератора можно выполнить итерацией с помощью next()
функции, которая внутренне использует __next__()
метод и возвращает следующий элемент в контейнере. (Предыдущее утверждение применимо к Python 3.x. В Python 2.x next()
метод эквивалентен.) StopIteration
Когда не останется больше элементов, будет возбуждено исключение. В следующем примере показана эквивалентная итерация по последовательности с использованием явных итераторов:
it = iter ( последовательность ) , а True : try : value = it . next () # в Python 2.x value = next ( it ) # в Python 3.x, кроме StopIteration : разрыв печати ( значение )
Любой определяемый пользователем класс может поддерживать стандартную итерацию (явную или неявную), определяя __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 = 'один' => 1 , 'два' => 2 , 'три' => 3 ;для %word-to-number -> $pair { say $pair ;}# ВЫХОД: # три => 3 # один => 1 # два => 2для %слово-число . kv -> $key , $value { скажите «$key: $value» }# ВЫХОД: # три: 3 # один: 1 # два: 2для %слово-число . ключи -> $key { say "$key =>" ~ %word-to-number { $key };}# ВЫХОД: # три => 3 # один => 1 # два => 2
Однако итераторы можно использовать и определять явно. Для любого итерируемого типа существует несколько методов, управляющих различными аспектами итерационного процесса. Например, iterator
метод должен возвращать Iterator
объект, а pull-one
метод должен создавать и возвращать следующее значение, если это возможно, или возвращать контрольное значение, IterationEnd
если больше значений создать невозможно. В следующем примере показана эквивалентная итерация по коллекции с использованием явных итераторов:
мои @values = 1 , 2 , 3 ;мой $it := @values . итератор ; # захватываем итератор для @valuesцикл { мое $значение := $it . тянуть один ; # захватываем последнее значение следующей итерации if $value =:= IterationEnd ; # остановить, если мы достигли конца итерации, сказать $value ; }# ВЫХОД: # 1 # 2 # 3
Все итерируемые типы в Raku составляют Iterable
роль, Iterator
роль или и то, и другое. Это Iterable
довольно просто и требует, чтобы компонент iterator
был реализован только составляющим классом. Он Iterator
более сложен и предоставляет ряд методов, таких как pull-one
, которые позволяют выполнять более точную операцию итерации в нескольких контекстах, таких как добавление или удаление элементов или пропуск их для доступа к другим элементам. Таким образом, любой определяемый пользователем класс может поддерживать стандартную итерацию путем составления этих ролей и реализации методов iterator
и/или pull-one
.
Класс DNA
представляет собой цепь ДНК и реализует ее, iterator
составляя Iterable
роль. Цепь ДНК при повторении разбивается на группу тринуклеотидов:
подмножество Strand of Str где { . match ( /^^ <[ACGT]>+ $$/ ) и . символы %% 3 };класс DNA делает Iterable { has $.chain ; новый метод ( Strand:D $chain ) { self . благослови: : $chain } итератор метода ( DNA:D: ){ $.chain . гребень . ротор ( 3 ). итератор }};для ДНК . новый ( 'ГАТТАКАТА' ) { . сказать}# ВЫХОД: # (GAT) # (TAC) # (ATA)скажем ДНК . новый ( «ГАТТАКАТА» ). карта (*. join ). присоединиться ( '-' );# ВЫВОД: # GAT-TAC-ATA
Класс Repeater
состоит из ролей Iterable
и Iterator
:
класс Повторитель делает Iterable делает Iterator { has Any $ .item требуется ; имеет Int $ .times требуется ; имеет Int $!count = 1 ; multi метод new ( $item , $times ) { self . благослови: : $item , : $times ; } итератор метода { self } метод pull-one (--> Mu ){ if $!count <= $!times { $!count += 1 ; вернуть $!элемент } еще { возвращение IterationEnd } }}для репитера . новый ( «Привет» , 3 ) { . сказать}# ВЫВОД: # Привет # Привет # Привет
Ruby реализует итераторы совершенно по-другому; все итерации выполняются посредством передачи замыканий обратного вызова методам контейнера — таким образом Ruby реализует не только базовую итерацию, но и несколько шаблонов итерации, таких как отображение функций, фильтры и сокращение. Ruby также поддерживает альтернативный синтаксис для базового метода итерации each
, следующие три примера эквивалентны:
( 0 ... 42 ) . каждый делает | п | кладет конец
...и...
для n в 0 ... 42 ставит n в конец
или даже короче
42 . раз делать | п | кладет конец
Ruby также может перебирать фиксированные списки, используя Enumerator
s и либо вызывая их #next
метод, либо выполняя для каждого из них, как указано выше.
Rust использует внешние итераторы во всей стандартной библиотеке, в том числе в своем for
цикле, который неявно вызывает next()
метод итератора до тех пор, пока он не будет использован. Например , самый простой for
цикл перебирает Range
тип:
для я в 0 .. 42 { println! ( "{}" , я ); } // Печатает числа от 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 Fibonacci { pub fn new () -> Self { Self ( 0 , 1 ) } } реализовать итератор для Фибоначчи { type Item = u64 ; fn next ( & mut self ) -> Option < Self :: Item > { let next = self . 0 ; себя . 0 = сам . 1 ; себя . 1 = сам . 0 + следующий ; Некоторые ( следующие ) } } пусть fib = Фибоначчи :: new (); для н в фиб . пропустить ( 1 ). шаг_по ( 2 ). возьми ( 4 ) { println! ( "{n}" ); } // Печатает 1, 2, 5 и 13
Пользовательский итератор обычно принимает форму ссылки на код, которая при выполнении вычисляет следующий элемент в списке и возвращает его. Когда итератор достигает конца списка, он возвращает согласованное значение.
Итераторы были представлены как конструкции, позволяющие перебирать абстрактные структуры данных без раскрытия их внутреннего представления.
Вы можете думать об итераторе как об указателе на элемент, который является частью более крупного контейнера элементов.
Внутренний итератор реализуется функциями-членами класса, который имеет логику итерации.
Внешний итератор реализуется отдельным классом, который можно присоединить к объекту, имеющему логику итерации.
Преимущество внешнего итератора заключается в том, что множество итераторов можно активировать одновременно для существующего или одного и того же объекта.
{{cite web}}
: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )Некоторые авторы используют термин «итератор», другие — термин «генератор».
Некоторые проводят между ними тонкие различия.
{{cite web}}
: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )Индекс можно использовать только для контейнеров, которые (эффективно) поддерживают произвольный доступ (т. е. прямой доступ к элементу в заданной позиции).
Итератор — более общее понятие.
Итераторы обеспечивают эффективный обход связанных списков, файлов и ряда других структур данных.
Это часто приводит к созданию более эффективного кода.
{{cite web}}
: CS1 maint: bot: исходный статус URL неизвестен ( ссылка ){{cite web}}
: CS1 maint: bot: исходный статус URL неизвестен ( ссылка )• Типы итераторов iterator и const_iterator относятся к категории прямых итераторов.