В компьютерном программировании , итератор является объектом , который позволяет программисту пересекать контейнер , в частности , списки . [1] [2] [3] Различные типы итераторов часто предоставляются через интерфейс контейнера . Хотя интерфейс и семантика данного итератора фиксированы, итераторы часто реализуются в терминах структур, лежащих в основе реализации контейнера, и часто тесно связаны с контейнером, чтобы обеспечить рабочую семантику итератора. Итератор выполняет обход, а также предоставляет доступ к элементам данных в контейнере, но сам не выполняет итерацию.(то есть, не без значительной свободы, взятой с этой концепцией или с банальным использованием терминологии) [ необходима цитата ] . Поведение итератора аналогично курсору базы данных . Итераторы появились в языке программирования CLU в 1974 году.
Описание
Внутренние итераторы
Внутренние итераторы - это функции более высокого порядка (часто использующие анонимные функции ), такие как map , reduce и т. Д., Реализующие обход контейнера, применяя данную функцию к каждому элементу по очереди.
Внешние итераторы и шаблон итератора
Внешний итератор можно рассматривать как тип указателя, который выполняет две основные операции: обращение к одному конкретному элементу в коллекции объектов (называемое доступом к элементу ) и изменение самого себя таким образом, чтобы он указывал на следующий элемент (так называемый обход элемента ). [4] Также должен быть способ создать итератор, чтобы он указывал на какой-то первый элемент, а также способ определить, когда итератор исчерпал все элементы в контейнере. В зависимости от языка и предполагаемого использования итераторы могут также предоставлять дополнительные операции или демонстрировать различное поведение.
Основная цель итератора - позволить пользователю обрабатывать каждый элемент контейнера, изолируя пользователя от внутренней структуры контейнера. [2] Это позволяет контейнеру хранить элементы любым способом, который он пожелает, в то же время позволяя пользователю обращаться с ними, как если бы это была простая последовательность или список. Класс итератора обычно разрабатывается в тесной координации с соответствующим классом контейнера. Обычно контейнер предоставляет методы для создания итераторов.
Счетчик цикла иногда также упоминаются как итератор цикла. Счетчик цикла , однако, только обеспечивает функциональные возможности обхода , а не функциональность доступа элемента.
Генераторы
Один из способов реализации итераторов - использовать ограниченную форму сопрограммы , известную как генератор . В отличие от подпрограммы сопрограмма-генератор может передавать значения вызывающей стороне несколько раз, вместо того, чтобы возвращать только один раз. Большинство итераторов естественно выразить как генераторы, но поскольку генераторы сохраняют свое локальное состояние между вызовами, они особенно хорошо подходят для сложных итераторов с отслеживанием состояния, таких как обходчики дерева . Существуют тонкие различия и различия в использовании терминов «генератор» и «итератор», которые различаются между авторами и языками. [5] В Python генератор - это конструктор итератора : функция, возвращающая итератор. Пример генератора Python, возвращающего итератор для чисел Фибоначчи с использованием yield
оператора Python, следующий:
def fibonacci ( предел ): a , b = 0 , 1 для _ в диапазоне ( предел ): вывести 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]
Категория | Языки |
---|---|
Двунаправленный итератор | C ++ |
Прямой итератор | C ++ |
Итератор ввода | C ++ |
Итератор вывода | C ++ |
Итератор произвольного доступа | C ++ |
Тривиальный итератор | C ++ (старый STL ) [11] |
Типы итераторов
Различные языки или библиотеки, используемые с этими языками, определяют типы итераторов. Некоторые из них [12]
Тип | Языки |
---|---|
Итератор массива | PHP , R [13] |
Кеширующий итератор | PHP |
Постоянный итератор | C ++ , [14] PHP |
Итератор каталогов | PHP, Python |
Итератор фильтра | PHP, R |
Ограничить итератор | PHP |
Итератор списка | Java , [6] R |
Рекурсивный итератор массива | PHP |
Итератор XML | PHP |
На разных языках программирования
C # и другие языки .NET
Итераторы в .NET Framework называются «счетчиками» и представлены IEnumerator
интерфейсом. IEnumerator
предоставляет MoveNext()
метод, который переходит к следующему элементу и указывает, достигнут ли конец коллекции; Current
свойство, чтобы получить значение элемента в настоящее время указал на; и необязательный Reset()
метод для возврата перечислителя в исходное положение. Перечислитель изначально указывает на специальное значение перед первым элементом, поэтому MoveNext()
для начала итерации требуется вызов .
Перечислители обычно получаются путем вызова GetEnumerator()
метода объекта, реализующего IEnumerable
интерфейс. Классы-контейнеры обычно реализуют этот интерфейс. Однако оператор foreach в C # может работать с любым объектом, предоставляющим такой метод, даже если он не реализует IEnumerable
( утиная типизация ). Оба интерфейса были расширены до общих версий в .NET 2.0 .
Ниже показано простое использование итераторов в C # 2.0:
// явная версия IEnumerator < MyType > iter = list . GetEnumerator (); while ( iter . MoveNext ()) Консоль . WriteLine ( итэр . Текущий );// неявная версия foreach ( значение MyType в списке ) Console . WriteLine ( значение );
C # 2.0 также поддерживает генераторы : метод, объявленный как возвращающий IEnumerator
(или IEnumerable
), но использующий yield return
оператор " " для создания последовательности элементов вместо возврата экземпляра объекта, будет преобразован компилятором в новый класс, реализующий соответствующий интерфейс. .
C ++
Язык C ++ широко использует итераторы в своей стандартной библиотеке и описывает несколько категорий итераторов, различающихся набором операций, которые они допускают. К ним относятся прямые итераторы , двунаправленные итераторы и итераторы с произвольным доступом в порядке увеличения возможностей. Все стандартные типы шаблонов контейнеров предоставляют итераторы одной из этих категорий. Итераторы обобщают указатели на элементы массива (которые на самом деле могут быть использованы в качестве итераторы), и их синтаксис разработан , чтобы напоминать , что из C арифметики указателей , где *
и ->
операторы используются для ссылки на элемент , к которому итераторы точки и арифметики указателей такие операторы, как ++
используются, изменяют итераторы при обходе контейнера.
Обход с использованием итераторов обычно включает в себя один изменяющийся итератор и два фиксированных итератора, которые служат для ограничения диапазона, который необходимо пройти. Расстояние между ограничивающими итераторами с точки зрения количества приложений оператора, ++
необходимых для преобразования нижнего предела в верхний, равно количеству элементов в обозначенном диапазоне; количество различных задействованных значений итератора на единицу больше. По соглашению нижний ограничивающий итератор «указывает» на первый элемент в диапазоне, в то время как верхний ограничивающий итератор не указывает на какой-либо элемент в диапазоне, а скорее только за его пределами. Для обхода всего контейнера 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 ) { // Перебираем элементы. std :: cout << * it ; // И вывести значение 'items' для текущего индекса. } // В C ++ 11 то же самое можно сделать без использования каких-либо итераторов: for ( auto x : items ) { std :: cout << x ; // Вывести значение каждого элемента «x» из «items». }// Каждый цикл выводит "529".
Типы итераторов отличаются от типов контейнеров, с которыми они используются, хотя они часто используются вместе. Категория итератора (и, следовательно, операции, определенные для него) обычно зависит от типа контейнера, например, массивы или векторы предоставляют итераторы с произвольным доступом, но наборы (которые используют связанную структуру в качестве реализации) предоставляют только двунаправленные итераторы. Один и тот же тип контейнера может иметь более одного связанного типа итератора; например, std::vector
тип контейнера позволяет обход либо с использованием (необработанных) указателей на его элементы (типа *
), либо значений специального типа std::vector
, а еще один тип предоставляется для «обратных итераторов», операции которых определены таким образом, что Алгоритм, выполняющий обычный (прямой) обход, фактически будет выполнять обход в обратном порядке при вызове с обратными итераторами. Большинство контейнеров также предоставляют отдельный 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()
и hasNext()
способ, и может необязательно поддерживать remove()
метод. Итераторы создаются соответствующим контейнерным классом, обычно с помощью метода с именем iterator()
. [15]
next()
Метод перемещает итератор и возвращает значение , на который указывает итератор. Первый элемент получается при первом обращении к next()
. Чтобы определить, когда все элементы в контейнере были посещены, используется hasNext()
метод тестирования. В следующем примере показано простое использование итераторов:
Итератор iter = list . итератор (); // Итератор iter = list.iterator (); // в J2SE 5.0 while ( iter . hasNext ()) { System . из . печать ( iter . next ()); если ( iter . hasNext ()) System . из . печать ( "," ); }
Чтобы показать, что hasNext()
это можно вызывать повторно, мы используем его для вставки запятых между элементами, но не после последнего элемента.
Этот подход не отделяет должным образом предварительную операцию от фактического доступа к данным. Если элемент данных должен использоваться более одного раза для каждого продвижения, его необходимо сохранить во временной переменной. Когда требуется продвижение без доступа к данным (т. Е. Для пропуска заданного элемента данных), доступ, тем не менее, выполняется, хотя возвращаемое значение в этом случае игнорируется.
Для типов коллекций, которые его поддерживают, remove()
метод итератора удаляет последний посещенный элемент из контейнера, сохраняя при этом итератор пригодным для использования. Добавление или удаление элементов путем вызова методов контейнера (также из того же потока ) делает итератор непригодным для использования. Попытка получить следующий элемент вызывает исключение. Исключение также выдается, если больше не осталось элементов ( hasNext()
ранее было возвращено false).
Кроме того, java.util.List
существует java.util.ListIterator
API с аналогичным API, но который позволяет выполнять итерацию вперед и назад, предоставляет текущий индекс в списке и позволяет устанавливать элемент списка в его позиции.
В выпуске Java J2SE 5.0 появился Iterable
интерфейс для поддержки расширенного цикла for
( foreach ) для перебора коллекций и массивов. Iterable
определяет iterator()
метод, возвращающий Iterator
. Используя расширенный for
цикл, предыдущий пример можно переписать как
для ( MyType obj : list ) { System . из . печать ( объект ); }
Некоторые контейнеры также используют более старый (начиная с 1.0) Enumeration
класс. Он предоставляет hasMoreElements()
и nextElement()
методы, но не имеет методов для изменения контейнера.
Scala
В Scala итераторы имеют богатый набор методов, подобных коллекциям, и могут использоваться непосредственно в циклах for. Действительно, итераторы и коллекции наследуются от общей базовой черты - scala.collection.TraversableOnce
. Однако из-за богатого набора методов, доступных в библиотеке коллекций Scala, таких как map
, collect
и filter
т. Д., Часто нет необходимости иметь дело с итераторами напрямую при программировании на Scala.
Итераторы и коллекции Java могут быть автоматически преобразованы в итераторы и коллекции Scala, соответственно, просто путем добавления одной строки
import scala.collection.JavaConversions._
в файл. Для этого JavaConversions
объект предоставляет неявные преобразования. Неявные преобразования - это особенность Scala: методы, которые, когда они видны в текущей области видимости, автоматически вставляют вызовы самих себя в соответствующие выражения в соответствующем месте, чтобы произвести проверку их типов, когда иначе они бы этого не сделали.
MATLAB
MATLAB поддерживает как внешнюю, так и внутреннюю неявную итерацию, используя либо «собственные» массивы, либо cell
массивы. В случае внешней итерации, когда ответственность за продвижение обхода и запрос следующих элементов ложится на пользователя, можно определить набор элементов в структуре хранения массива и перемещаться по элементам с for
помощью конструкции -loop. Например,
% Определите массив целых чиселmyArray = [ 1 , 3 , 5 , 7 , 11 , 13 ]; для n = myArray % ... сделай что-нибудь disp ( n ) % Вывод целого числа в командное окно конец
проходит по массиву целых чисел с помощью for
ключевого слова.
В случае внутренней итерации, когда пользователь может предоставить операцию итератору для выполнения над каждым элементом коллекции, многие встроенные операторы и функции MATLAB перегружаются для выполнения над каждым элементом массива и неявно возвращают соответствующий выходной массив . Кроме того, arrayfun
и cellfun
функции могут быть использованы для выполнения пользовательской или определенного пользователя операции над «родными» массивами и cell
массивами соответственно. Например,
функция simpleFun % Определите массив целых чиселmyArray = [ 1 , 3 , 5 , 7 , 11 , 13 ]; % Выполните настраиваемую операцию над каждым элементом myNewArray = arrayfun (@ ( a ) myCustomFun ( a ), myArray ); % Выводить результирующий массив в командное окноmyNewArrayфункция outScalar = myCustomFun ( inScalar ) % Просто умножьте на 2outScalar = 2 * inScalar ;
определяет основную функцию, simpleFun
которая неявно применяет настраиваемую подфункцию myCustomFun
к каждому элементу массива с помощью встроенной функции arrayfun
.
В качестве альтернативы может быть желательно абстрагироваться от механизмов контейнера хранения массива от пользователя, определяя настраиваемую объектно-ориентированную реализацию MATLAB шаблона Iterator. Такая реализация, поддерживающая внешнюю итерацию, продемонстрирована в шаблоне проектирования элемента MATLAB Central File Exchange : Iterator (Behavioral) . Это написано в новом синтаксисе определения класса, представленном в программном обеспечении MATLAB версии 7.6 (R2008a), и включает в себя cell
реализацию одномерного массива абстрактного типа данных списка (ADT) в качестве механизма для хранения разнородного (по типу данных) набора элементы. Он обеспечивает функциональные возможности для явного прямого списка обхода с hasNext()
, next()
и reset()
методами для использования в while
-loop.
PHP
РНР «s foreachцикл был введен в версии 4.0 и сделан совместимым с объектами в качестве значений в 4.0 Beta 4. [16] Однако, был добавлена поддержка итераторы в PHP 5 путем введения внутреннего [17] Traversable
интерфейс. [18] Двумя основными интерфейсами для реализации в сценариях PHP, которые позволяют выполнять итерацию объектов через foreach
цикл, являются Iterator
и IteratorAggregate
. Последний не требует, чтобы реализующий класс объявлял все требуемые методы, вместо этого он реализует метод доступа ( getIterator
), который возвращает экземпляр Traversable
. Standard PHP Library предоставляет несколько классов для работы со специальными итераторами. [19] PHP также поддерживает генераторы, начиная с версии 5.5. [20]
Самая простая реализация - это упаковка массива, это может быть полезно для подсказки типов и скрытия информации .
пространство имен Wikipedia \ Iterator ;последний класс ArrayIterator расширяет \ Iterator { частный массив $ array ; публичная функция __construct ( array $ array ) { $ this -> array = $ array ; } публичная функция rewind () : void { echo ' rewinding ' , PHP_EOL ; сбросить ( $ this -> массив ); } публичная функция current () { $ value = current ( $ this -> массив ); эхо "текущий: { $ значение } " , PHP_EOL ; вернуть значение $ ; } публичная функция key () { $ key = key ( $ this -> array ); echo "ключ: { $ key } " , PHP_EOL ; return $ key ; } публичная функция next () { $ value = next ( $ this -> array ); эхо "далее: { $ значение } " , PHP_EOL ; вернуть значение $ ; } общедоступная функция valid () : bool { $ valid = $ this -> current () ! == false ; echo 'valid:' , ( $ valid ? 'true' : 'false' ), PHP_EOL ; return $ действительный ; } }
Все методы класса-примера используются во время выполнения полного цикла 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' , 'имя пользователя' , 'пароль' , ' имя_базы_данных ' );// Класс \ mysqli_result, возвращаемый вызовом метода, реализует внутренний интерфейс Traversable. foreach ( $ mysqli -> query ( 'SELECT `a`,` b`, `c` FROM` table`' , MYSQLI_USE_RESULT ) as $ row ) { // Действие над возвращенной строкой, которая является ассоциативным массивом. }
Python
Итераторы в Python являются фундаментальной частью языка и во многих случаях остаются невидимыми, поскольку они неявно используются в операторе for
( foreach ), в понимании списков и в выражениях генератора . Все стандартные встроенные типы коллекций Python поддерживают итерацию, а также многие классы, входящие в стандартную библиотеку. В следующем примере показана типичная неявная итерация по последовательности:
для значения в последовательности : print ( значение )
Словари Python (форма ассоциативного массива ) также можно перебирать напрямую, когда возвращаются ключи словаря; или items()
метод словаря может быть повторен, где он дает соответствующие пары ключ, значение в виде кортежа:
для ключа в словаре : значение = словарь [ ключ ] print ( ключ , значение )
для ключа , значение в словаре . items (): print ( ключ , значение )
Однако итераторы можно использовать и определять явно. Для любого типа или класса итеративной последовательности встроенная функция 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 : break print ( value )
Любой определяемый пользователем класс может поддерживать стандартную итерацию (неявную или явную), определяя __iter__()
метод, который возвращает объект-итератор. Затем объекту итератора необходимо определить __next__()
метод, который возвращает следующий элемент.
Генераторы Python реализуют этот протокол итераций .
Раку
Итераторы в Raku являются фундаментальной частью языка, хотя обычно пользователям не нужно заботиться об итераторах. Их использование скрывается за итерационных API , такие как for
заявления, map
, grep
, список индексации с .[$idx]
и т.д.
В следующем примере показана типичная неявная итерация по набору значений:
мои @values = 1 , 2 , 3 ;for @values -> $ value { скажем, $ value}# ВЫХОД: # 1 # 2 # 3
Хэши Raku также можно напрямую перебирать; это дает Pair
объекты " ключ-значение" . kv
Метод может быть вызван на хэш перебрать ключа и значения; keys
метод перебора ключей хэша в; и values
метод перебора значений хэша.
мой % word-to-number = 'one' => 1 , 'two' => 2 , 'three' => 3 ;для % слово-число -> $ pair { скажем, $ pair ;}# ВЫВОД: # три => 3 # один => 1 # два => 2для % слово-число . kv -> $ key , $ value { скажем "$ key: $ value" }# ВЫХОД: # три: 3 # один: 1 # два: 2для % слово-число . ключи -> $ key { скажем "$ key =>" ~ % слово в число { $ key };}# ВЫВОД: # три => 3 # один => 1 # два => 2
Однако итераторы можно использовать и определять явно. Для любого итеративного типа существует несколько методов, управляющих различными аспектами итерационного процесса. Например, iterator
метод должен возвращать Iterator
объект, а pull-one
метод должен производить и возвращать следующее значение, если это возможно, или возвращать контрольное значение, IterationEnd
если больше не может быть произведено значений. В следующем примере показана эквивалентная итерация по коллекции с использованием явных итераторов:
мои @values = 1 , 2 , 3 ;мой $ it : = @values . итератор ; # взять итератор для @valuesloop { my $ value : = $ it . тянуть-один ; # захватить последнее значение итерации последним if $ value =: = IterationEnd ; # остановимся, если мы достигли конца итерации say $ value ;}# ВЫХОД: # 1 # 2 # 3
Все повторяющиеся типы в Raku составляют Iterable
роль, Iterator
роль или и то, и другое. Это Iterable
довольно просто и требует, iterator
чтобы класс-составитель только реализовал. Iterator
Является более сложным и предоставляет ряд методов , таких как pull-one
, что позволяет более тонкой операции итерации в нескольких контекстах , таких как добавление или исключение элементов, или пропуска через них , чтобы получить доступ к другим пунктов. Таким образом, любой определяемый пользователем класс может поддерживать стандартную итерацию, составляя эти роли и реализуя методы iterator
и / или pull-one
.
DNA
Класс представляет собой цепь ДНК и реализует iterator
путем составления Iterable
роли. Нить ДНК разделяется на группу тринуклеотидов при повторении:
подмножество Strand из Str, где {. совпадение ( / ^^ <[ACGT]> + $$ / ) и . символы %% 3 };класс DNA делает Iterable { имеет $ .chain ; метод новый ( Strand: D $ chain ) { self . благослови :: $ цепочка } итератор метода ( ДНК: D :) { $ .chain . расческа . ротор ( 3 ). итератор }};для ДНК . new ( 'GATTACATA' ) { . сказать}# ВЫХОД: # (GAT) # (TAC) # (ATA)говорят ДНК . новый ( 'GATTACATA' ). карта (*. присоединиться ). присоединиться ( '-' );# ВЫХОД: # GAT-TAC-ATA
В Repeater
классе сочиняет оба Iterable
и Iterator
роль:
class Repeater делает Iterable делает Iterator { has Any $ .item is required ; имеет Int $ & bull ; в необходимых ; имеет Int $! count = 1 ; мульти- метод новый ( $ item , $ times ) { self . благослови: : $ пункт ,: $ раз ; } method iterator { self } method pull-one (-> Mu ) { if $! count <= $! times { $! count + = 1 ; вернуть $! товар } else { return IterationEnd } }}для повторителя . new ( "Привет" , 3 ) { . сказать}# ВЫВОД: # Привет # Привет # Привет
Рубин
Ruby реализует итераторы совершенно иначе; все итерации выполняются посредством передачи закрытий обратного вызова методам контейнера - таким образом Ruby реализует не только базовую итерацию, но также несколько шаблонов итераций, таких как отображение функций, фильтры и сокращение. Ruby также поддерживает альтернативный синтаксис для основного метода итерации each
, следующие три примера эквивалентны:
( 0 ... 42 ) . каждый делать | п | ставит п конец
...а также...
для n в 0 ... 42 кладет n в конец
или даже короче
42 . раз делать | п | ставит п конец
Ruby также может перебирать фиксированные списки, используя Enumerator
s и либо вызывая их #next
метод, либо выполняя для каждого из них, как указано выше.
Ржавчина
В Rust можно выполнять итерацию по элементу векторов или создавать собственные итераторы. Каждый итератор имеет адаптеры ( map
, filter
, skip
, take
, ...).
для n в 0 .. 42 { println! ( "{}" , П ); }
Ниже fibonacci()
функция возвращает настраиваемый итератор.
для i в fibonacci (). пропустить ( 4 ). take ( 4 ) { println! ( "{}" , i ); }
Смотрите также
- Итерация , в которой вместо того, чтобы разработчик неоднократно вызывать итератор для получения новых значений, итерация вызывается повторно для обработки новых фрагментов данных - пример инверсии управления .
- Шаблон дизайна
- Итерация
- Шаблон итератора
- Диапазон
- Шаблон посетителя
- Указатель (компьютерное программирование)
Рекомендации
- ^ Gatcomb, Джошуа. «Понимание и использование итераторов» . Perl.com. Архивировано из оригинала на 2005-06-16 . Проверено 8 августа 2012 .
Пользовательский итератор обычно принимает форму ссылки на код, которая при выполнении вычисляет следующий элемент в списке и возвращает его. Когда итератор достигает конца списка, он возвращает согласованное значение.
- ^ а б Ватт, Стивен М. «Техника универсальной итерации и ее оптимизация» (PDF) . Университет Западного Онтарио, факультет компьютерных наук. Архивировано из оригинального (PDF) 16 сентября 2006 года . Проверено 8 августа 2012 .
Итераторы были введены как конструкции, позволяющие перебирать абстрактные структуры данных без раскрытия их внутреннего представления.
- ^ Алекс Аллен. «Итераторы STL» . Cprogramming.com - Ваш ресурс по C и C ++ . Проверено 8 августа 2012 .
Вы можете думать об итераторе как о указывающем на элемент, который является частью более крупного контейнера элементов.
- ^ а б «Разница между внешним итератором и внутренним итератором» . CareerRide.COM. 2009-04-03. Архивировано из оригинала на 2009-04-03 . Проверено 8 августа 2012 .
Внутренний итератор реализуется функциями-членами класса, который имеет логику итераций. Внешний итератор реализуется отдельным классом, который может быть присоединен к объекту, имеющему логику итераций. Преимущество внешнего итератора заключается в том, что многие итераторы могут быть активными одновременно для существующего или того же объекта.
- ^ Ватт, Стивен М. «Техника универсальной итерации и ее оптимизация» (PDF) . Университет Западного Онтарио, факультет компьютерных наук. Архивировано из оригинального (PDF) 16 сентября 2006 года . Проверено 8 августа 2012 .
Некоторые авторы используют термин "итератор", а другие - термин "генератор". Некоторые делают тонкие различия между ними.
- ^ а б Фриман, Эрик; Фриман, Элизабет; Кэти, Сьерра; Берт, Бейтс (2004). Хендриксон, Майк; Лукидес, Майк (ред.). "Шаблоны проектирования прежде всего" (мягкая обложка) . 1 . О'РЕЙЛИ: 338. ISBN 978-0-596-00712-6. Проверено 9 августа 2012 . Цитировать журнал требует
|journal=
( помощь ) - ^ «Глоссарий - документация Python 3.8.4» . Проверено 15 июля 2020 .
- ^ Вечерина, Иван (01.02.2006). "индекс против итератора" . БАЙТОВ. Архивировано из оригинала на 2006-02-01 . Проверено 8 августа 2012 .
Индекс может использоваться только для контейнеров, которые (эффективно) поддерживают произвольный доступ (т.е. прямой доступ к элементу в данной позиции). Итератор - это более общее понятие. Итераторы предлагают эффективный обход связанных списков, файлов и ряда других структур данных. Это часто приводит к созданию более эффективного кода.
- ^ Кевин Уотерсон. «C ++ Iteratoren: Iterator-Kategorien» (на немецком языке). cppreference.com . Проверено 9 августа 2012 .
- ^ Кевин Уотерсон. «Итераторы: концепции» . sgi . Проверено 9 августа 2012 .
- ^ larsmans (06.03.2011). «Типы итераторов: выход против ввода против прямого итератора с произвольным доступом» . переполнение стека. Архивировано из оригинала на 2011-03-06 . Проверено 9 августа 2012 .
- ^ Кевин Уотерсон. «Введение в SPL: Введение в стандартную библиотеку PHP (SPL)» . PHPRO.ORG . Проверено 9 августа 2012 .
- ^ Кольер, Эндрю. «Итераторы в R» . Проверено 16 ноября 2013 года .
- ^ "Класс шаблона concurrent_unordered_set" . Строительные блоки Intel Threading для открытого исходного кода. Архивировано из оригинала на 2015-05-01 . Проверено 9 августа 2012 .
• Типы итератора iterator и const_iterator относятся к категории прямого итератора.
- ^ "java.util: Итератор интерфейса : Сводка метода" . Oracle . Проверено 8 августа 2012 .
- ^ «Журнал изменений PHP 4» . Группа PHP. 2000-02-20 . Проверено 13 октября 2015 .
- ^ Внутренний относится к тому факту, что интерфейс не может быть реализован в сценариях PHP, только висходном коде C (язык программирования) .
- ^ «Проходной интерфейс» . Группа PHP . Проверено 13 октября 2015 .
- ^ «Итераторы» . Группа PHP . Проверено 13 октября 2015 .
- ^ «Журнал изменений PHP 5» . Группа PHP. 2013-06-20 . Проверено 13 октября 2015 .
Внешние ссылки
- Объяснение Iterator, Iterable и ListIterator в Java
- .NET интерфейс
- Статья Джошуа Гэткомба « Понимание и использование итераторов »
- Статья Стивена М. Ватта « Методика общей итерации и ее оптимизация » (217 КБ)
- Итераторы
- Библиотека итераторов Boost C ++
- Java интерфейс
- PHP: итерация объекта
- Итераторы STL
- Что такое итераторы? - Справочное описание