Итератор

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание[править | править вики-текст]

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

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

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

Отличия от индексации[править | править вики-текст]

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

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

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

Неявные итераторы[править | править вики-текст]

Некоторые объектно-ориентированные языки, такие как 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, и при следующем вызове возобновляет работу с прерванного места.

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

Пример генератора, возвращающего числа Фибоначчи, с применением оператора 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 = open("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 позволяет изменять содержимое массива во время итерации для чего достаточно указать, что значение $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[править | править вики-текст]

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

Haskell[править | править вики-текст]

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

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 <$> f x
    traverse f (Node l k r) = Node <$> 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 `fmap` 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)

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

Ссылки[править | править вики-текст]

Литература[править | править вики-текст]

  • Николас А. Солтер, Скотт Дж. Клепер C++ для профессионалов = Professional C++. — Диалектика, Вильямс, 2006. — С. 637-639. — 912 с. — ISBN 5-8459-1065-Х.