Collections

Последовательности. Трейт Seq, IndexedSeq и LinearSeq

Language

Трейт Seq представляет из себя последовательность. Последовательность - это своего рода итерируемая сущность, у которой есть длина (length) и элементы с фиксированным индексом, начинающийся от 0.

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

  • Размера и индексации операции apply, isDefinedAt, length, indices, и lengthCompare. Для Seq, операция apply означает запрос по индексу; Так как последовательность типа Seq[T] частично определённая функция, которая принимает в качестве аргумента Int (как индекс) и в результате выдает элемент последовательности типа T. Другими словами Seq[T] расширяет PartialFunction[Int, T]. Элементы последовательности индексируются от нуля до length(длинна последовательности) минус еденицу. Метод length на последовательностях является ссылкой на метод size общий коллекциях. Метод lengthCompare позволяет сравнивать длины последовательностей с Int, даже если длина последовательностей бесконечна.
  • Операции поиска индекса indexOf, lastIndexOf, indexOfSlice, lastIndexOfSlice, indexWhere, lastIndexWhere, segmentLength, которые возвращают индекс элемента, равный заданному значению или совпадающий с каким-либо предикатом.
  • Операции сложения prepended, prependedAll, appended, appendedAll, padTo, которые возвращают новые последовательности, полученные добавлением элементов в начале или в конце последовательности.
  • Операции обновления updated, patch, которые возвращают новую последовательность полученную заменой некоторых элементов исходной последовательности
  • Операции сортировки sorted, sortWith, sortBy, которые сортируют последовательность элементов в соответствии с различными критериями
  • Операции разворота reverse, reverseIterator, которые выдают или обрабатывают элементы последовательности в обратном порядке.
  • Сравнения startsWith, endsWith, contains, containsSlice, corresponds, search, которые сопоставляют две последовательности или осуществляют поиск элементов в последовательности.
  • Операции с множествами intersect, diff, distinct, distinctBy, которые выполняют операции как у множеств с элементами двух последовательностей либо удаляют дубликаты.

Если последовательность изменяемая (мутабельная), то у нее есть операция update (обновления), которая обновляет элементы последовательности используя побочные эффекты. Как всегда в Scala синтаксис типа seq(idx) = elem - это просто сокращение от seq.update(idx, elem), поэтому update - это просто более удобный вариант синтаксиса. Обратите внимание на разницу между update (обновить) и updated (обновленный). updated доступен для всех последовательностей и всегда возвращает новую последовательность вместо того, чтобы модифицировать исходную.

Операции на Классе Seq

ПРИМЕР ЧТО ДЕЛАЕТ
Размера и индексация:  
xs(i) (эквивалентно xs apply i). Выдает элемент xs на позиции i.
xs isDefinedAt i Проверяет есть ли i в xs.indices.
xs.length Длина последовательности (тоже самое что и size).
xs lengthCompare n Возвращает -1 если x короче n, +1 если длиннее, и 0 такогоже размера что и n. Работает даже если последовательность бесконечна, например, LazyList.from(1) lengthCompare 42 возвращает положительное значение.
xs.indices Диапазон индексов xs, от 0 до xs.length - 1`.
Поиск по индексу  
xs indexOf x Индекс первого элемента в xs равного x.
xs lastIndexOf x Индекс последнего элемента в xs равного x.
xs indexOfSlice ys Первый индекс элемента в xs начиная с которого можно сформировать последовательность эквивалентную ys (существует несколько вариантов).
xs lastIndexOfSlice ys Последний индекс элемента в xs начиная с которого можно сформировать последовательность эквивалентную ys (существует несколько вариантов).
xs indexWhere p Первый индекс элемента который удовлетворяет условию p (существует несколько вариантов).
xs.segmentLength(p, i) Длина самого длинного непрерывного сегмента элементов в xs, начиная с которого удовлетворяется условие p.
Сложения:  
xs.prepended(x)
либо x +: xs
Новая последовательность, состоящая из x добавленный перед xs.
xs.prependedAll(ys)
либо ys ++: xs
Новая последовательность, состоящая из всех элементов ys добавленных перед xs.
xs.appended(x)
либо xs :+ x
Новая последовательность, состоящая из x добавленных после xs.
xs.appendedAll(ys)
либо xs :++ ys
Новая последовательность, состоящая из всех элементов ys добавленных после xs.
xs.padTo(len, x) Последовательность, получаемая в результате добавления значения x к xs до тех пор пока не будет достигнута длина len.
Обновления:  
xs.patch(i, ys, r) Последовательность, получаемая в результате замены r элементов xs, начиная с i заменяя их на ys.
xs.updated(i, x) Создает копию xs в которой элемент с индексом i заменён на x.
xs(i) = x (эквивалентно xs.update(i, x), доступно только у mutable.Seq). Заменяет элемент xs с индексом i на x.
Сортировка:  
xs.sorted Новая последовательность, полученная при сортировке элементов xs используя стардартную схему упорядочивания элементов типа xs.
xs sortWith lt Новая последовательность, полученная при сортировке элементов xs при помощи операции сравнения lt.
xs sortBy f Новая последовательность, полученная при сортировке элементов xs. Сравнение при сортировке происходит между двумя элементами полученных после выполнения функции f на исходных элементах.
Развороты:  
xs.reverse Последовательность с элементами xs в обратном порядке.
xs.reverseIterator Итератор, выдающий все элементы xs в обратном порядке.
Сравнения:  
xs sameElements ys Проверка на то, содержат ли xs и ys одни и те же элементы в одном и том же порядке.
xs startsWith ys Проверяет, начинается ли xs с последовательности ys. (существует несколько вариантов).
xs endsWith ys Проверяет, заканчивается ли xs последовательностью ys. (существует несколько вариантов).
xs contains x Проверяет, есть ли в xs элемент равный x.
xs search x Проверяет, есть ли в отсортированной последовательности xs элемент, равный x, такой поиск может быть более эффективным чем xs contains x.
xs containsSlice ys Проверяет, есть ли у xs непрерывная подпоследовательность, равная ys.
(xs corresponds ys)(p) Проверяет, удовлетворяют ли соответствующие элементы xs и ys бинарному предикату p.
Операции над множествами:  
xs intersect ys Операция пересечения на множестве между последовательностей xs и ys, сохраняющее порядок элементов в xs.
xs diff ys Операция расхождения на множестве между последовательностей xs и ys, сохраняющее порядок элементов в xs.
xs.distinct Подпоследовательность xs, которая не содержит дублирующих друг друга элементов.
xs distinctBy f Подпоследовательность xs, которая не содержит дублирующего элемента после применения функции преобразования f. Например, List("foo", "bar", "quux").distinctBy(_.length) == List("foo", "quux")

У трейта Seq есть два дочерних трейта LinearSeq, и IndexedSeq. Они не добавляют никаких новых операций, но у каждого из них разные характеристики производительности: у LinearSeq эффективные операции head и tail, в то время как у IndexedSeq эффективные операции apply, length и (если мутабельная) update. Часто используемые варианты LinearSeq - это scala.collection.immutable.List и scala.collection.immutable.LazyList. А наиболее часто используемые IndexedSeq - это scala.Array и scala.collection.mutable.ArrayBuffer. Класс Vector представляет собой компромисс между IndexedSeq и LinearSeq. У него эффективные, как обращение по индексу, так и последовательный обход элементов. Поэтому вектора хорошая основа для смешанных моделей доступа, где используются как индексированный, так и последовательный доступ. Позже мы расскажем больше о векторах.

В мутабельном варианте IndexedSeq добавляет операции преобразования ее элементов в самой коллекции (в отличие от таких операций как map и sort, доступных на базовом трейте Seq, для которых результат - это новая коллекция).

Операции на Классе mutable.IndexedSeq

ПРИМЕР ЧТО ДЕЛАЕТ
Преобразования:  
xs.mapInPlace(f) Преобразует все элементы xs, применяя функцию f к каждому из них.
xs.sortInPlace() Сортирует коллекцию xs.
xs.sortInPlaceWith(c) Сортирует коллекцию xs в соответствии с заданной функцией сравнения c.
xs.sortInPlaceBy(f) Сортирует коллекцию xs в соответствии с порядком, определяемым на результате после применения функции f к каждому элементу.

Буферы

Важной подкатегорией мутабельных последовательностей является Bufferы. Они позволяют не только изменять существующие элементы, но и добавлять, вставлять и удалять элементы. Основными новыми методами, поддерживаемыми буфером, являются append и appendAll для добавления элементов в конце, prepend и prependAll для добавления спереди, insert и insertAll для вставок элементов, а также remove, subtractOne и subtractAll для удаления элементов. Краткая информация об этих операциях представлена в таблице ниже.

Два часто используемых варианта реализации буферов - ListBuffer и ArrayBuffer. Как следует из названия, ListBuffer основан на List и поддерживает эффективное преобразование его элементов в List (список), тогда как ArrayBuffer - основан на Array (массиве), он также может быть быстро преобразован в массив.

Операции на Классе Buffer

ПРИМЕР ЧТО ДЕЛАЕТ
Сложения:  
buf append x
либо buf += x
Добавляет в конец буфера элемент x возвращая этот самый буфер buf в качестве результата.
buf appendAll xs
либоbuf ++= xs
Добавляет все элементы xs в конец буфер.
buf prepend x
либо x +=: buf
Добавляет элемент x в начало буфера.
buf prependAll xs
либо xs ++=: buf
Добавляет все элементы xs в начало буфера.
buf.insert(i, x) Вставляет элемент x на позицию i в буфер.
buf.insertAll(i, xs) Вставляет все элементы в xs на позицию i в буфер.
buf.padToInPlace(n, x) Добавляет элемент x в буфер до тех пор, пока там не будет n элементов.
Удаления:  
buf subtractOne x
либо buf -= x
Удаляет элемент x из буфера.
buf subtractAll xs
либо buf --= xs
Удаляет элементы xs из буфера.
buf remove i Удаляет элемент на позиции i из буфера.
buf.remove(i, n) Удаляет n элементов начиная с позиции i из буфера.
buf trimStart n Удаляет первых n элементов из буфера.
buf trimEnd n Удаляет последние n элементов из буфера.
buf.clear() Удаляет все элементы из буфера.
Замена:  
buf.patchInPlace(i, xs, n) Заменяет (не более чем) n элементов буфера элементами из xs, начиная с позиции i в буфере.
Клонирование:  
buf.clone() Новый буфер с теми же элементами, что и buf.

Contributors to this page: