Collections

Итераторы

Language

Итератор (Iterator) - это не коллекция, а скорее способ поочередного доступа к элементам коллекции. Есть две основные операции у итератора - это next и hasNext. Вызов метода it.next() на итераторе it вернет следующий элемент и изменит его состояние. Повторный вызов next на том же итераторе выведит следующий элемент идущий после ранее возвращённого. Если больше нет элементов для возврата, вызов команды next кинет исключение NoSuchElementException. Вы можете узнать, есть ли еще элементы для возврата с помощью метода hasNext у Итератора.

Самый простой способ “обойти” все элементы, возвращаемые итератором it - это использование циклов с while-loop:

while (it.hasNext)
  println(it.next())

У итераторов в Scala есть аналоги большинству методов, которые вы можете найдти в классах Traversable, Iterable и Seq. Например, метод “foreach”, который на итераторе выполняет процедуру на каждом элементе, возвращаемого итератором. Используя foreach, описанный выше цикл можно сократить до:

it foreach println

Как всегда, “for выражения” могут быть использованы в качестве альтернативного синтаксиса для выражений, включающих в себя foreach, map, ` WithFilter и flatMap`, поэтому еще одним способом вывести все элементы, возвращаемые итератором, будет:

for (elem <- it) println(elem)

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

Другие общие операции между Iterator и Iterable, имеют одни и те же свойства. Например, итераторы предоставляют метод map, который возвращает новый итератор:

scala> val it = Iterator("a", "number", "of", "words")
it: Iterator[java.lang.String] = <iterator>
scala> it.map(_.length)
res1: Iterator[Int] = <iterator>
scala> it.hasNext
res2: Boolean = true
scala> res1 foreach println
1
6
2
5
scala> it.hasNext
res4: Boolean = false

Как видите, после вызова функции it.map итератор it не остановился в конце, в отличии от res1.foreach который проходит через весь итератор, после чего it остается в самом конце.

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

scala> val it = Iterator("a", "number", "of", "words")
it: Iterator[java.lang.String] = <iterator>
scala> it dropWhile (_.length < 2)
res4: Iterator[java.lang.String] = <iterator>
scala> res4.next()
res5: java.lang.String = number

Обратите внимание еще раз, что сам итераторit был изменен вызовом dropWhile: теперь он указывает на второе слово number в списке. Фактически, it и результат res4 возвращаемый послеdropWhile возвращают одну и туже последовательность элементов.

Чтобы избежать такое поведение, как вариант можно использовать duplicate (дублировать используемый итератор), вызывая методы на разных итераторах. Каждый из двух итераторов будет обрабатывать точно такие же элементы, как и тот, из которого состоит итераторатор it:

scala> val (words, ns) = Iterator("a", "number", "of", "words").duplicate
words: Iterator[String] = <iterator>
ns: Iterator[String] = <iterator>

scala> val shorts = words.filter(_.length < 3).toList
shorts: List[String] = List(a, of)

scala> val count = ns.map(_.length).sum
count: Int = 14

Оба итератора работают независимо друг от друга: продвижение одного не влияет на другого, так что каждый из них может быть модифицирован независимо от другого. Может создаться впечатление что итератор подвергается двойному обходу над элементами, но это не так, результат достигается за счет внутреннего буферизации. Как обычно, базовый итератор it не пригоден для прямого использования и должен быть исключен из дальнейших операций.

Обобщая вышесказанное, итераторы ведут себя как коллекции, если после вызова метода на них сам итератор больше не вызывается. В библиотеке коллекции Scala это достигается явным образом с помощью абстракции IterableOnce, который является общим суперкласом для Iterable и Iterator. У IterableOnce[A] только два метода: iterator: Iterator[A] и knownSize: Int.

Если объект IterableOnce является Iterator, то его операция iterator всегда возвращает себя, в своем текущем состоянии, но если он Iterable, то операция iterator всегда возвращает новый Iterator. Типовой вариант использования IterableOnce - в качестве типа аргумента для методов, которые могут принимать или итератор или коллекцию в качестве аргумента. Примером может служить метод соединения concat в классе Iterable. Он принимает IterableOnce параметр, поэтому вы можете соединять элементы, поступающие или из итератора или коллекции.

Все операции на итераторах собраны в таблице ниже.

Операции на классе Iterator

ПРИМЕР ЧТО ДЕЛАЕТ
Абстрактные Методы:  
it.next() Возвращает следующий элемент итератора переводя его позицию на следующее место.
it.hasNext Возвращает true если итератор it может выдать следующий элемент.
Варьирования:  
it.buffered Буффиризированный итератор возвращающий все элементы it.
it grouped size Итератор, который производит элементы от it в последовательностях фиксированного размера (“чанках”).
it sliding size Итератор, который производит элементы от it в последовательностях полученных от прохождения окна фиксированного размера над элементами итератора.
Дублирования:  
it.duplicate Пара итераторов, каждый из которых может независимо возвращать все элементы it.
Сложения:  
it concat jt
либо it ++ jt
Итератор, возвращающий все элементы, от итератора it, за которым следуют все элементы, возвращаемые итератором jt.
it.padTo(len, x) Итератор, который в начале возвращает все элементы it а затем следуют копии x пока не будет достигнута длина len.
Отображения:  
it map f Итератор, получаемый при применении функции f к каждому элементу, возвращаемому из it.
it flatMap f Итератор, получаемый при применении производящей итераторы функции f к каждому элементу it с последующим объединением результатов.
it collect f Итератор, получаемый при применении частично определенной функции f к каждому элементу it для которого она определена с последующим сбором результатов.
Преобразования:  
it.toArray Собирает элементы, полученные от it в массив.
it.toList Собирает элементы, полученные от it в список.
it.toIterable Собирает элементы, полученные от it в итерируемую сущность.
it.toSeq Собирает элементы, полученные от it в последовательность.
it.toIndexedSeq Собирает элементы, полученные от it в индексируюмую последовательность.
it.toLazyList Собирает элементы, полученные от it в ленивый лист.
it.toSet Собирает элементы, полученные от it во множество.
it.toMap Собирает пары ключ/значение, полученные от it в мапу.
Копирования:  
it.copyToArray(arr, s, n) Копирует максимум n элементов, возвращаемых it в массив arr, начиная с индекса s. Два последних аргумента необязательные.
Иформации о размере:  
it.isEmpty Проверяет, пуст ли итератор ( в противоположность hasNext ).
it.nonEmpty Проверяет, содержит ли коллекция элементы (псевдоним для hasNext).
it.size Выдает количество элементов итератора it. Примечание: после этой операции it будет находится в конце!
it.length Тоже что и it.size.
it.knownSize Выдает количество элементов итератора, если их можно узнать без изменения состояния итератора, иначе -1.
Поиск и получение элементов:  
it find p Опшен возвращаемый из it, содержащий первый элемент, который удовлетворяет условию p, или None, если ни один из элементов не подходит. Примечание: итератор находится на следующем после найденного элемента или в конце, если ни одного не найдено.
it indexOf x Индекс первого элемента, возвращаемого it, который равен x. Примечание: итератор перемещается в позицию после найденого элемента.
it indexWhere p Индекс первого элемента, возвращаемого it, который удовлетворяет условию p. Примечание: итератор перемещается в позицию после этого элемента.
Дочернии итераторы:  
it take n Итератор, возвращающий первые n элементов it. Примечание: он переместится в позицию после n элемента, или в конец, если содержит меньше, чем n элементов.
it drop n Итератор, который начинается с (n+1) элемента it. Примечание: it переместится в ту же самую позицию.
it.slice(m,n) Итератор, возвращающий фрагмент элементов из it, начиная с m элемента и заканчивая перед n элементом.
it takeWhile p Итератор, возвращающий элементы из it до тех пор, пока условие p истинно.
it dropWhile p Итератор пропускает элементы из it до тех пор, пока условие p является истинным, после чего возвращает остаток.
it filter p Итератор, возвращающий все элементы из it, удовлетворяющие условию p.
it withFilter p То же самое, что и it filter p. Требуется для возможности использовать итераторы в for-выражениях.
it filterNot p Итератор, возвращающий все элементы из it, которые не удовлетворяют условию p.
it.distinct Итератор, возвращающий элементы из it без дубликатов.
ПодГруппы:  
it partition p Разделяет it на пару из двух итераторов: один возвращает все элементы из it, которые удовлетворяют предикату p, а другой возвращает все элементы из it, которые не удовлетворяют.
it span p Разделяет it на пару из двух итераторов: один возвращает все начальные элементы it, удовлетворяющие предикату p, а другой возвращает все остальные элементы it.
Сведения об элементах:  
it forall p Логический показатель, указывающий, все ли элементы из it соответствуют условию p.
it exists p Логический показатель, указывающий, есть ли хоть один элемент из it, который соответствует условию p.
it count p Возвращает количество элементов из it, удовлетворяющих предикату p.
Свертки:  
it.foldLeft(z)(op) Применяет двустороннюю операцию op между последовательно идущими элементами, возвращаемыми итератором it, слева направо и начинающимися с z.
it.foldRight(z)(op) Применяет двустороннюю операцию op между последовательно идущими элементами, возвращаемыми итератором it, справа налево и начинающимися с z.
it reduceLeft op Применяет двустороннюю операцию op между последовательно идущими элементами, возвращаемыми итератором it, идущие слева направо.
it reduceRight op Применяет двустороннюю операцию op между последовательно идущими элементами, возвращаемыми итератором it, идущие справа налево.
Специальные Свертки:  
it.sum Сумма значений числовых элементов, возвращаемых итератором it.
it.product Произведение значений числовых элементов, возвращаемых итератором it.
it.min Минимальное из значений элементов у которых есть порядок, возвращаемых итератором it.
it.max Максимальное из значений элементов у которых есть порядок, возвращаемых итератором it.
Связывания:  
it zip jt Итератор состоящий из пар соответствующих элементов, возвращаемых итераторами it и jt
it.zipAll(jt, x, y) Итератор состоящий из пар соответствующих элементов, возвращаемых итераторами it и jt , где более короткий итератор расширяется, чтобы соответствовать более длинному, добавляя элементы x или y.
it.zipWithIndex Итератор состоящий из пар элементов итератора it и его индекса
Обновления:  
it.patch(i, jt, r) Итератор, получаемый из it, заменив r элементов, начиная с i на итератор jt.
Сравнения:  
it sameElements jt Проверяет, возвращают ли итераторы it и jt одни и те же элементы в одном и том же порядке. Примечание: Использование итераторов после этой операции не определено и может быть изменено в дальнейшем.
Строковые:  
it.addString(b, start, sep, end) Добавляет строку в StringBuilder b, который выводит все элементы it через разделитель sep, заключенный между строками start и end. start, sep, end - необязательные параметры.
it.mkString(start, sep, end) Преобразует коллекцию в строку, которая выводит все элементы it через разделитель sep, заключенный между строками start и end. start, sep, end - необязательные параметры.

Ленивость

В отличие от операций непосредственно на конкретных коллекциях типа List, операции на Iterator ленивы.

Ленивая операция не сразу вычисляет результаты. Вместо этого она рассчитывает результаты тогда когда они непосредственно запрашиваются.

Поэтому выражение (1 to 10).iterator.map(println) не выведет ничего на экран. Метод map в данном случае не применяет функцию в аргументе к значениям в диапазоне, вместо этого будет возвращен новый Iterator, который будет выполнять операции тогда когда будет запрошен их результат. Добавление .toList в конец этого выражения фактически вызовет вывод элементов на печать.

Как следствие, такие методы как map или filter не обязательно применят функцию в аргументе ко всем входным элементам. Выражение (1 to 10).iterator.map(println).take(5).toList выводит только значения от 1 до 5, поскольку это те значения, которые запрашиваются у Iterator, возвращаемого из map.

Это одна из причин, того почему важно использовать только чистые функции в качестве аргументов для map, filter, fold и подобных методов. Помните, что чистая функция не имеет побочных эффектов, поэтому println обычно не используется в map. Здесь println используется лишь для демонстрации “ленивости”, которую с чистыми функциями не заметно.

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

def zipWithIndex[A](i: Iterator[A]): Iterator[(Int, A)] =
  Iterator.from(0).zip(i)

Буферезированные итераторы

Иногда вам нужен итератор, который может “заглянуть вперед”, чтобы вы могли оценить следующий элемент, который будет возвращен без перемещения позиции. Рассмотрим, например, задачу пропуска впереди идущих пустых строк из итератора, который возвращает последовательность строк. У вас может возникнуть соблазн написать следующее

def skipEmptyWordsNOT(it: Iterator[String]) =
  while (it.next().isEmpty) {}

Но если присмотреться к этому коду внимательнее, то становится понятно, что такой код не корректен: код действительно пропустит ведущие пустые строки, но он также пропустит первую непустую строку it!

Решение этой проблемы заключается в использовании буферизированного итератора. Класс BufferedIterator базирующийся на классе Iterator предоставляет один дополнительный метод, head. Вызов head на буферизированном итераторе вернет его первый элемент, но не продвинет итератор дальше. С помощью буферизированного итератора можно пропустить пустые слова следующим образом.

def skipEmptyWords(it: BufferedIterator[String]) =
  while (it.head.isEmpty) { it.next() }

Каждый итератор может быть преобразован в буферизированный после вызова метода buffered. Например:

scala> val it = Iterator(1, 2, 3, 4)
it: Iterator[Int] = <iterator>
scala> val bit = it.buffered
bit: scala.collection.BufferedIterator[Int] = <iterator>
scala> bit.head
res10: Int = 1
scala> bit.next()
res11: Int = 1
scala> bit.next()
res12: Int = 2
scala> bit.headOption
res13: Option[Int] = Some(3)

Обратите внимание, что вызов метода head на буферизированном итераторе bit не продвигает его вперед. Поэтому последующий вызов bit.next() возвращает то же значение, что и bit.head.

Как обычно, базовый итератор не должен в дальнейшем использоваться напрямую и должен быть исключен из операций.

Буферизированный итератор буферизирует только следующий элемент, когда вызывается head. Другие производные итераторы, например произведенные от вызова duplicate и partition, могут буферизировать любое количество подпоследовательностей дочерних итераторов. Впрочем, итераторы могут быть эффективно объединены используя метод ++:

scala> def collapse(it: Iterator[Int]) = if (!it.hasNext) Iterator.empty else {
     | var head = it.next
     | val rest = if (head == 0) it.dropWhile(_ == 0) else it
     | Iterator.single(head) ++ rest
     | }
collapse: (it: Iterator[Int])Iterator[Int]

scala> def collapse(it: Iterator[Int]) = {
     | val (zeros, rest) = it.span(_ == 0)
     | zeros.take(1) ++ rest
     | }
collapse: (it: Iterator[Int])Iterator[Int]

scala> collapse(Iterator(0, 0, 0, 1, 2, 3, 4)).toList
res14: List[Int] = List(0, 1, 2, 3, 4)

В первой версии, любые встречаемые нули сбрасываются, а затем строится требуемый результат как объединенный итератор, который в свою очередь просто вызывает два входящих в него итератора. Во втором варианте collapse неиспользованные нули буферизируются внутри.

Contributors to this page: