Итератор (от ― перечислитель) — интерфейс, предоставляющий доступ к элементам коллекции (массива или контейнера) и навигацию по ним. В различных системах итераторы могут иметь разные общепринятые названия. В терминах систем управления базами данных итераторы называются курсорами. В простейшем случае итератором в низкоуровневых языках является указатель.
Использование итераторов в обобщённом программировании позволяет реализовать универсальные алгоритмы работы с контейнерами.
Описание Главное предназначение итераторов заключается в предоставлении возможности пользователю обращаться к любому элементу контейнера при сокрытии внутренней структуры контейнера от пользователя. Это позволяет контейнеру хранить элементы любым способом при допустимости работы пользователя с ним как с простой последовательностью или списком. Проектирование класса итератора обычно тесно связано с соответствующим классом контейнера. Обычно контейнер предоставляет методы создания итераторов.
Итератор похож на указатель своими основными операциями: он указывает на отдельный элемент коллекции объектов (предоставляет доступ к элементу) и содержит функции для перехода к другому элементу списка (следующему или предыдущему). Контейнер, который реализует поддержку итераторов, должен предоставлять первый элемент списка, а также возможность проверить, перебраны ли все элементы контейнера (является ли итератор конечным). В зависимости от используемого языка и цели, итераторы могут поддерживать дополнительные операции или определять различные варианты поведения.
Иногда счётчик цикла называют «итератором цикла». Тем не менее, счётчик цикла обеспечивает только перебор элементов, но не доступ к элементу.
Отличия от индексации
В процедурных языках программирования широко используется индексация, основанная на счётчике цикла, для перебора всех элементов последовательности (например, массива). Хотя индексация может использоваться совместно с некоторыми объектно-ориентированными контейнерами, использование итераторов даёт свои преимущества: Индексация не подходит для некоторых структур данных, в частности, для структур данных с медленным произвольным доступом или вообще без поддержки такового (например, список или дерево). Итераторы предоставляют возможность последовательного перебора любых структур данных, поэтому делают код более читаемым, удобным для повторного использования и менее чувствительным к изменениям структур данных. Итераторы могут предоставлять дополнительные возможности при навигации по элементам. Например, проверку отсутствия пропусков элементов или защиту от повторного перебора одного и того же элемента. Некоторые контейнеры могут предоставлять возможность модифицировать свои объекты без влияния на сам итератор. Например, после того, как итератор уже «прошёл» первый элемент, можно вставить дополнительные элементы в начало контейнера без каких-либо нежелательных последствий. При использовании индексации это проблематично из-за смены номеров индексов. Возможность модификации контейнера во время итерации его элементов стала необходимой в современном объектно-ориентированном программировании, где взаимосвязи между объектами и последствия выполнения операций могут быть не слишком очевидными. Использование итератора избавляет от этих видов проблем.
Неявные итераторы Некоторые объектно-ориентированные языки, такие как 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(), выполняющие такую неявную итерацию. Тем не менее, они все равно требуют явного задания итератора в качестве параметра. Но после инициализации последующая итерация происходит неявно без использования какого-либо итератора. Начиная со стандарта C++11 язык также поддерживает неявную итерацию в цикле for.
Генераторы
Одним из способов реализации итераторов является использование сопроцедур, которые могут возвращать управление (и вычисленные результаты) несколько раз, запоминая своё состояние и точку возврата в предыдущем вызове. В некоторых языках сопроцедуры могут быть представлены особого вида функциями, называемыми генераторами. Генератор — функция, которая помнит, в каком месте был предыдущий 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() — на воображаемый несуществующий элемент, следующий за последним.
Когда итератор выходит за последний элемент, то по определению это равно специальному конечному значению итератора. Нижеследующий пример демонстрирует типичное использование итератора:
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; }
Java Представленный в релизе JDK 1.2 языка Java интерфейс обеспечивает итерацию контейнерных классов. Каждый Iterator реализует методы и и дополнительно может поддерживать метод . Итераторы создаются соответствующими контейнерными классами, как правило методом 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() удаляет последний 'посещенный' элемент из контейнера. Почти все остальные типы модификации контейнера во время итерации являются небезопасными.
Кроме того, для существует со схожим API, но позволяющем прямую и обратную итерации, обеспечивая определение текущего индекса в списке и переход к элементу по его позиции.
В релиз J2SE 5.0 был представлен интерфейс для поддержки улучшенного цикла for (foreach) для переборки в коллекциях и массивах. Iterable определяет метод , возвращающий Iterator. Используя улучшенный цикл for прошлый пример можно переписать в виде
for (MyType obj : list) System.out.print(obj);
C# и прочие .NET языки