Итератор

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

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

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

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

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

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

Некоторые объектно-ориентированные языки, такие как 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(), выполняющие такую неявную итерацию. Тем не менее, они все равно требуют явного задания итератора в качестве параметра. Но после инициализации последующая итерация происходит неявно без использования какого-либо итератора. Начиная со стандарта С++11 язык также поддерживает неявную итерацию в цикле for[2].

Одним из способов реализации итераторов является использование сопроцедур, которые могут возвращать управление (и вычисленные результаты) несколько раз, запоминая своё состояние и точку возврата в предыдущем вызове. В некоторых языках сопроцедуры могут быть представлены особого вида функциями, называемыми генераторами. Генератор — функция, которая помнит, в каком месте был предыдущий 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++ широко использует итераторы в STL, поддерживающей несколько различных типов итераторов, включая 'однонаправленные итераторы', 'двунаправленные итераторы' и 'итераторы произвольного доступа'. Все стандартные шаблоны типов контейнеров реализуют разнообразный, но постоянный набор типов итераторов. Синтаксис стандартных итераторов сделан похожим на обычные указатели языка Си, где операторы * и -> используются для указания элемента, на который указывает итератор, а такие арифметические операторы указателя, как ++, используются для перехода итератора к следующему элементу.

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

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

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

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

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

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

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

Начиная со стандарта C++11 итераторы могут использоваться неявно в цикле for, реализуя функциональность обхода всех элементов контейнера:

#include <vector>
#include <iostream>

int main(void)
{
    std::vector<int> v;
    v.push_back(1);
    v.push_back(2);
    v.push_back(3);
    for (auto e : v) {
        std::cout << e << std::endl; // Выведет значение каждого элемента
    }
    return 0;
}

Представленный в релизе 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);

Итераторы в .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 являются неотъемлемой частью языка и во многих случаях неявно используются в выражении 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 = open("README")                     # открытие файла
 print(f.next())                        # следующее значение итератора - очередная строка файла
 print(sum(len(line) for line in f))    # сумма длин всех остальных строк файла

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

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

В 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 позволяет изменять содержимое массива во время итерации для чего достаточно указать, что значение $value будет получаться как ссылка (в терминах PHP) то есть так &$value.

<?php
  $arr = array(1,2,3,4,5);
  foreach ($arr as &$value)
    $value++; // увеличим каждое значение на единицу
  // теперь $arr содержит значения: 2,3,4,5,6
?>

В 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()
      }

Предыдущий пример можно значительно упростить, если использовать интерфейс IteratorAggregate, который обязывает разработчика реализовать всего один метод getIterator()

<?php
  class MyIterator implements IteratorAggregate
  {
     private $var = array();

     public function __construct(array $array)
     {
           // проверка типа осуществляется интерпретатором: __construct(array $array)
           $this->var = $array;
     }

     public function getIterator() {
       return new ArrayIterator($this->var);
     }
  }
?>

Итераторы в языке 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

Итераторы в 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);

}

В стандартной библиотеке языка Haskell определён класс типов «Traversable»[3][4]:

class (Functor t, Foldable t) => Traversable t where
        traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Здесь t — это некоторый полиморфный тип (возможно, контейнер или коллекция), f — «эффектный» тип (например, ввод-вывод, изменение явного состояния или возможность ошибки). «traverse» является специализацией функтора и свёртки, что выражено в контексте (заголовке) класса.

Например, для бинарного дерева метод «traverse» может быть определён следующим образом:

data Tree a = Empty
            | Leaf a
            | Node (Tree a) a (Tree a)

instance Traversable Tree
    traverse f Empty        = pure Empty
    traverse f (Leaf x)     = Leaf <__SUB_LEVEL_SECTION_14__gt; f x
    traverse f (Node l k r) = Node <__SUB_LEVEL_SECTION_14__gt; traverse f l <*> f k <*> traverse f r

Пример использования:

-- | Напечатать содержимое каждого узла дерева.
printTree tree = traverse print tree

-- | Эта функция принимает некоторую бинарную функцию g и дерево,
-- проходит по дереву, применяя g к каждому узлу (второй аргумент
-- запрашивается со стандартного ввода) и возвращает изменённое дерево.
combineWithStdin :: (Read c) => (a -> c -> b) -> Tree a -> IO (Tree b)
combineWithStdin g = traverse combine
  where
    combine x = g x <__SUB_LEVEL_SECTION_14__gt; readLn

{- Пример:
tree = Node (Node (Leaf 3) 6 (Leaf 9)) 10
            (Node (Leaf 9) 0 Empty)

$ combineWithStdin (+) tree
> 10
> 20
> 30
> 40
> 50
> 60
$ Node (Node (Leaf 13) 26 (Leaf 39)) 50 (Node (Leaf 59) 60 Empty)
-}

На основе методов класса типов «Traversable» можно строить собственные функции с определённой стратегией обхода.

В компиляторе GHC, начиная с версии 6.12, появились расширения «-XDeriveFunctor» «-XDeriveFoldable» и «-XDeriveTraversable» для автоматического создания экземпляров соответствующих классов типов. Пример:

data Tree a = Empty
            | Leaf a
            | Node (Tree a) a (Tree a)
  deriving (Functor, Foldable, Traversable)