Итератор

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

Использование итераторов в обобщённом программировании позволяет реализовать универсальные алгоритмы работы с контейнерами или любыми последовательностями.

Описание

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

Главное предназначение итераторов заключается в предоставлении возможности пользователю обращаться к любому элементу контейнера при сокрытии внутренней структуры контейнера от пользователя. Это позволяет контейнеру хранить элементы любым способом при допустимости работы пользователя с ним как с простой последовательностью или списком. Проектирование класса итератора обычно тесно связано с соответствующим классом контейнера. Обычно контейнер предоставляет методы создания итераторов.

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

Отличия от индексации

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

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

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

• Итератор может накладывать дополнительные ограничения доступа, как например, проверка отсутствия пропусков элементов или повторного перебора одного и того же элемента.

• Итератор позволяет модифицировать объекты контейнера без влияния нам сам итератор. Например, после того, как итератор уже «прошёл» первый элемент, можно вставить дополнительные элементы в начало контейнера без каких-либо нежелательных последствий. При использовании индексации это весьма проблематично из-за смены индексных номеров.

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

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

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

Перебор элементов коллекции с помощью неявного итератора осуществляется при помощи оператора «foreach» (или эквивалентного ему), как например в следующем коде на языке Python:

for Value in List:
    print Value

В других случаях итераторы могут быть созданы самой коллекцией объектов, как в этом примере на языке Ruby:

list.each do |value|
  puts value
end

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

MaleNames = [Person.Name for Person in RosterList if Person.IsMale]

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

Генераторы

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

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

Пример генератора, возвращающего числа Фибоначчи, с применением оператора yield языка Python:

 def fibonacci():
     a, b = 0, 1
     while True:
         yield a       # return a, + запоминает место рестарта для следующего вызова
         a, b = b, a+b

 for number in fibonacci():  # Используем генератор как итератор
     print number

Итераторы в различных языках программирования

Оберон

Обычное обращение к переменным, составляющим ряд, осуществляется по их номеру. При этом адрес требуемой переменной вычисляется как: "адрес 1-й переменной" + "размер переменной" x "заданный номер". При последовательном обращении к таким переменным можно получить значительный выигрыш производительности, если вычислять адрес последующей переменной через адрес предыдущей. Для этого и применяется бегунок. Вид переменных, составляющих ряд, к которым будет осуществляться последовательное обращение, называется опорным видом бегунка, а число переменных ряда, на которое будет перемещаться бегунок после каждого такого обращения, называется шагом бегунка. Шаг бегунка задаётся как целая постоянная. Если при объявлении вида шаг бегунка не указан, то считается, что шаг равен 1.

C++

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

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

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

ContainerType C; // Любой стандартный тип контейнера, например std::list<sometype>
//for (ContainerType::iterator it = C.begin(),end = C.end(); it != end; ++it) {    для изменяемого итератора
//(если вам нужно изменять элементы)
for (ContainerType::const_iterator it = C.begin(),end = C.end(); it != end; ++it) {
    std::cout << *it << std::endl;
}

Существует множество разновидностей итераторов, различающихся своим поведением, включая: однонаправленные, обратные (реверсные) и двунаправленные итераторы; итераторы ввода и вывода; константные итераторы (защищающие контейнер или его элементы от изменения). Тем не менее, не каждый тип контейнера поддерживает любой из этих типов итераторов. Пользователи могут создавать собственные типы итераторов, определяя подклассы на основе стандартного шаблона классов std::iterator.

Безопасность применения итератора определяется раздельно для различных типов стандартных контейнеров; в некоторых случаях итератор допускает изменения контейнера во время итерации.

Неявная итерация также частично поддерживается C++ при помощи шаблонов стандартных функций, как std::for_each()[1] и std::accumulate()[2]. При использовании они должны быть проинициализированы существующими итераторами, обычно 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 );  // Цикл просмотра

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

Java

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

Метод next() переводит итератор на следующее значение и возвращает указываемое значение итератору. При первоначальном создании итератор указывает на специальное значение, находящееся перед первым элементом, поэтому первый элемент можно получить до первого вызова next(). Для определения момента, когда все элементы в контейнере были перебраны, используется тестовый метод hasNext(). Следующий пример демонстрирует простое использование итераторов:

Iterator iter = list.iterator();
//Iterator<MyType> iter = list.iterator();    в J2SE 5.0
while (iter.hasNext())
    System.out.println(iter.next());

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

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

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

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

C# и прочие .NET языки

Итераторы в .NET Framework называются 'перечислителями' (enumerators) и представлены интерфейсом 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())
    Console.WriteLine(iter.Current);

// 'неявная' версия
foreach (MyType value in list)
    Console.WriteLine(value);

C# 2.0 также поддерживает генераторы: метод, объявляемый как возвращаемый IEnumerator (или IEnumerable), но использующий выражение "yield return" (гибкое возвращение) для создания последовательности элементов вместо возвращения сущности объекта, будет превращен компилятором в новый класс, реализующий соответствующий интерфейс.

Python

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

 for value in sequence:
     print value

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

for key in dictionary:
    value = dictionary[key]
    print key, value

for key, value in dictionary.items():
    print key, value

Тем не менее, итераторы могут использоваться и задаваться явным образом. Для любой перечисляемого типа цикла или класса встроенная функция iter() создает итератор. Итератор реализует метод next(), который возвращает следующий элемент в контейнере. Когда элементов больше не остается вызывается ошибка StopIteration. Следующий пример демонстрирует соответствующую циклическую итерацию при помощи явных итераторов:

it = iter(sequence)
while True:
    try:
        value = it.next()
    except StopIteration:
        break
    print value

В следующем примере для Python 2.4 (и выше) итератором является сам файловый объект f, обеспечивающий доступ к файлу как к последовательности строк:

 f = file("README")                    # открытие файла
 print f.next()                        # следующее значение итератора - очередная строка файла
 print sum(len(line) for line in f)    # сумма длин всех остальных строк файла

Любой пользовательский класс может поддерживать стандартную итерацию (явную или неявную) при определении метода __iter__(), который создает итератор. Затем итератору нужно определение метода next(), возвращающего следующий элемент.

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

PHP

В PHP 4 были представлены конструкции цикла просмотра как в языке Perl и некоторых других. Это позволяет простым способом просматривать массивы. В PHP 4 цикл просмотра работает только с массивами и выдает ошибку при попытке использования с переменными разного типа или неинициализированными переменными.

В PHP5 цикл просмотра разрешает итерацию объектов через все открытые члены.

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

Пример A

<?php
  foreach (array_expression as $value)
    echo "$value;\n";
?>

Пример B

<?php
  foreach (array_expression as $key => $value)
    echo "($key)$value;\n";
?>

Пример A перебирает массив, переданный в array_expression. При каждом прохождении цикла значение текущего элемента присваивается переменной $value, а внутренний указатель на массив переходит к следующему элементу (поэтому при следующем проходе цикла вы будете "видеть" следующий элемент).

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

В PHP 5 интерфейс Iterator определяется предварительно, а объекты могут изменяться для управления итерацией.

<?php
  class MyIterator implements Iterator
  {
     private $var = array();
  
     public function __construct($array)
     {
       if (is_array($array)) {
           $this->var = $array;
       }
     }
  
     public function rewind() {
       echo "переход\n";
       reset($this->var);
     }
  
     public function current() {
       $var = current($this->var);
       echo "текущий: $var\n";
       return $var;
     }
  
     public function key() {
       $var = key($this->var);
       echo "ключ: $var\n";
       return $var;
     }
  
     public function next() {
       $var = next($this->var);
       echo "следующий: $var\n";
       return $var;
     }
  
     public function valid() {
       $var = $this->current() !== false;
       echo "правильный: {$var}\n";
       return $var;
     }
  }
?>

Эти методы полностью задействуются в полном цикле просмотра foreach($obj AS $key=>$value). Методы итераторов выполняются в следующем порядке:

 1. rewind() ("переход")
 2. while valid()
     {
       2.1 current() in $value 
       2.3 key() in $key 
       2.4 next()
      }

XL

Итераторы в языке XL являются обобщением генераторов и итераторов.

import IO = XL.UI.CONSOLE

iterator IntegerIterator (var out Counter : integer; Low, High : integer) written Counter in Low..High is
    Counter := Low
    while Counter <= High loop
        yield
        Counter += 1

// Обратите внимание, что отпадает необходимость в отдельном объявлении I, так как 'var out' объявляется в итераторе
// Неявное объявление I как целого числа происходит ниже
for I in 1..5 loop
   IO.WriteLn "I=", I

ActionScript1.0(Flash)

for(i=0; i< array.length; i++){
    trace(array[i]);
}

ActionScript 3.0(Flash/Flex)

Итераторы в ActionScript 3 встроены в сам язык и поддерживаются операторами foreach и for...in. С точки зрения языка, массивы и экземпляры динамических классов являются итераторами:

var obj:Object = {prop1:"a", prop2:"b", prop3:"c"};

// следующий цикл "пробежит" по всем ключам (именам свойств) объекта obj
for(var name:String in obj)
   trace(name);

// следующий цикл "пробежит" по всем значениям свойств объекта obj
foreach(var val:* in obj)
   trace(val);

}

Смотри также

• Итерация
• Итератор (шаблон проектирования)
• Шаблон просмотра
• Шаблоны проектирования
• Курсор (базы данных)

Дополнительные источники

• Статья "Понятие и использование итераторов" от Джошуа Геткомб
• Статья "Технология итерации общего вида и ее оптимизации" (217 Кб) от Стивен Уотт
• Обзор STL
• Итераторы STL
• Что такое итераторы? - Руководство
• Интерфейс в Java
• Описание шаблона
• Boost C++ Iterator Library
• PHP: объектная итерация
• Итераторы библиотеки STL