Пакет scala.collection.immutable

Непустой список, характеризуемый головой и хвостом.

Класс для неизменяемых битовых наборов.

Битовые наборы — это множества неотрицательных целых чисел, которые представлены массивами переменной длины бит, упакованными в 64-битные слова. Занимаемая память битового набора определяется наибольшим числом, хранящимся в нем.

Карта по умолчанию, которая реализует методы + и - карт. Это делается с использованием создателя по умолчанию для карт, определенного в объекте Map. Экземпляры, которые наследуются от DefaultMap[A, B], по-прежнему должны определить:

def get(key: A): Option[B]
def iterator: Iterator[(A, B)]

Он ссылается обратно на исходную карту.

Также может быть целесообразно переопределить foreach или size, если можно найти эффективные реализации.

Этот класс реализует неизменяемые карты с использованием хэш-дерева.

Примечание: Создатель этого хэш-мапа может возвращать специализированные представления для небольших карт.

Этот класс реализует неизменяемые множества с использованием хэш-дерева.

Примечание: Создатель этого хэш-множества может возвращать специализированные представления для небольших множеств.

Подтракт от collection.IndexedSeq, который представляет индексированные последовательности, гарантированные неизменяемыми.

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

Индексированные последовательности не добавляют никаких новых методов к Seq, но обещают эффективные реализации схем произвольного доступа.

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

Примечание: Этот класс с версии 2.8 в значительной степени устарел по сравнению с HashMap.

Базовый тракт для итерируемых коллекций, гарантированных неизменяемыми.

Это базовый тракт для всех неизменяемых коллекций Scala, которые определяют метод iterator для пошагового перебора элементов коллекции по одному. Реализации этого тракта должны предоставить конкретный метод с сигнатурой:

def iterator: Iterator[A]

Они также должны предоставить метод newBuilder для создания билдера для коллекций того же типа.

Этот тракт реализует метод Iterable foreach метода, проходя по всем элементам с помощью iterator. Подклассы должны переопределить foreach более эффективным способом, если это возможно.

Этот тракт добавляет методы iterator, sameElements, takeRight, dropRight к методам, унаследованным от тракта `Traversable`.

Примечание: Этот тракт заменяет каждый метод, использующий break в TraversableLike, на версию с итератором.

Подтракт от collection.LinearSeq , который представляет последовательности, гарантированные неизменяемыми.

Линейные последовательности имеют достаточно эффективные методы head, tail, и isEmpty. Если эти методы обеспечивают самый быстрый способ обхода коллекции, коллекция Coll, которая расширяет этот тракт, также должна расширять LinearSeqOptimized[A, Coll[A]].

Класс для неизменяемых связанных списков, представляющих упорядоченные коллекции элементов типа A.

Этот класс поставляется с двумя реализующими case-классами scala.Nil и scala.::, которые реализуют абстрактные члены isEmpty, head и tail.

Этот класс оптимален для паттернов доступа «последним вошел — первым вышел» (LIFO), подобных стеку. Если вам нужен другой паттерн доступа, например, произвольный доступ или FIFO, рассмотрите использование коллекции, более подходящей для этого, чем List.

Примечание: Несмотря на то, что это неизменяемая коллекция, при построении внутри используется изменяемое состояние. Эти изменения состояния незаметны в однопоточном коде, но могут привести к гонкам в некоторых многопоточных сценариях. Состояние нового экземпляра коллекции может не быть «опубликовано» (в смысле спецификации Java Memory Model), поэтому несинхронизированная не-volatile-чтение из другого потока может наблюдать объект в некорректном состоянии (см. scala/bug#7838 для получения подробностей). Обратите внимание, что такое чтение не гарантирует, что оно когда-либо увидит записанный объект, и поэтому не должно использоваться, независимо от этой проблемы. Самый простой способ решения — обмениваться значениями между потоками через переменную volatile.

Производительность

Время: List имеет O(1) операцию добавления в начало и доступ к началу/концу списка. Большинство других операций занимают O(n) по количеству элементов в списке. Это включает в себя индексный поиск элементов, length, append и reverse.

Память: List реализует структурное совместное использование хвостового списка. Это означает, что многие операции имеют нулевую или постоянную стоимость памяти.

val mainList = List(3, 2, 1)
val with4 =    4 :: mainList  // re-uses mainList, costs one :: instance
val with42 =   42 :: mainList // also re-uses mainList, cost one :: instance
val shorter =  mainList.tail  // costs nothing as it uses the same 2::1::Nil instances as mainList

Этот класс реализует неизменяемые карты, используя структуру данных на основе списков. Итераторы и методы обхода карты ListMap посещают пары ключ-значение в порядке их первоначального вставки.

Элементы хранятся во внутренней структуре в обратном порядке вставки, то есть самый новый ключ находится в начале списка. Таким образом, такие методы, как head и tail, имеют сложность O(n), а last и init — O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого числа элементов.

Экземпляры ListMap представляют пустые карты; их можно создать, либо вызвав конструктор напрямую, либо применив функцию ListMap.empty.

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

Элементы хранятся во внутренней структуре в обратном порядке вставки, то есть самый новый элемент находится в начале списка. Таким образом, такие методы, как head и tail, имеют сложность O(n), а last и init — O(1). Другие операции, такие как вставка или удаление элементов, также имеют сложность O(n), что делает эту коллекцию подходящей только для небольшого числа элементов.

Экземпляры ListSet представляют пустые множества; их можно создать, либо вызвав конструктор напрямую, либо применив функцию ListSet.empty.

Специализированная структура неизменяемых карт для длинных ключей, основанная на быстрых объединяемых картах длинных чисел Окасаки и Гилла. По сути, это trie, основанное на двоичных цифрах целых чисел.

Примечание: Этот класс с версии 2.8 в значительной степени устарел по сравнению с HashMap.

Обобщённый трейт для неизменяемых карт. Конкретные классы должны предоставлять функциональность для абстрактных методов в Map:

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def + [V1 >: V](kv: (K, V1)): Map[K, V1]
def -(key: K): Map[K, V]

Обобщённый шаблон для неизменяемых карт от ключей типа K до значений типа V. Для реализации конкретной карты, необходимо предоставить реализации следующих методов (где This — тип фактической реализации карты):

def get(key: K): Option[V]
def iterator: Iterator[(K, V)]
def + [V1 >: V](kv: (K, V)): Map[K, V1]
def - (key: K): This

Если вы хотите, чтобы методы-трансформаторы, такие как take, drop, filter, возвращали тот же тип карты, вы также должны переопределить:

def empty: This

Также рекомендуется переопределить методы foreach и size для повышения эффективности.

NumericRange — более обобщённая версия класса Range, работающая с произвольными типами. Она должна быть снабжена реализацией типа диапазона Integral.

Фабрики для вероятных типов включают Range.BigInt, Range.Long, и Range.BigDecimal. Range.Int существует для полноты, но Int-основанный scala.Range должен быть более производительным.

val r1 = new Range(0, 100, 1)
val veryBig = Int.MaxValue.toLong + 1
val r2 = Range.Long(veryBig, veryBig + 100, 1)
assert(r1 sameElements r2.map(_ - veryBig))

Объекты Queue реализуют структуры данных, позволяющие вставлять и извлекать элементы в порядке очереди (FIFO).

Очередь реализована как пара списков, один содержащий элементы in, а другой — out. Элементы добавляются в список in и удаляются из списка out. Когда список out пустеет, очередь поворачивается путём замены списка out на in.reverse, а in на Nil.

Добавление элементов в очередь всегда имеет стоимость O(1). Удаление элементов имеет стоимость O(1), за исключением случая, когда требуется поворот, в этом случае взимается стоимость O(n), где n — количество элементов в очереди. В этом случае операции удаления с стоимостью O(1) гарантированы. Удаление элемента в среднем занимает O(1).

Класс Range представляет целые значения в диапазоне [start;end) с ненулевым значением шага step. Это особый случай индексированного последовательности. Например:

val r1 = 0 until 10
val r2 = r1.start until r1.end by r1.step + 1
println(r2.length) // = 5

Диапазоны, содержащие более Int.MaxValue элементов, могут быть созданы, но эти переполненные диапазоны имеют ограниченные возможности. Любой метод, который может потребовать создание коллекции длиной более Int.MaxValue, или может быть запрошен для индексирования за пределами Int.MaxValue элементов, выбросит исключение. Переполненные диапазоны можно безопасно уменьшить, изменив размер шага (например, by 3) или взяв/отбросив элементы. contains, equals, и доступ к концам диапазона (head, last, tail, init) также разрешены для переполненных диапазонов.

Подкласс collection.Seq, представляющий гарантированно неизменяемые последовательности.

Последовательности являются особыми случаями итерируемых коллекций класса Iterable. В отличие от итерируемых коллекций, последовательности всегда имеют определенный порядок элементов. Последовательности предоставляют метод apply для индексирования. Индексы варьируются от 0 до length последовательности. Последовательности поддерживают ряд методов для поиска вхождения элементов или подпоследовательностей, включая segmentLength, prefixLength, indexWhere, indexOf, lastIndexWhere, lastIndexOf, startsWith, endsWith, indexOfSlice.

Еще один способ рассматривать последовательность — как отображение PartialFunction от Int значений к типу элементов последовательности. Метод isDefinedAt последовательности возвращает true для интервала от 0 до length.

К последовательностям можно получить доступ в обратном порядке их элементов, используя методы reverse и reverseIterator.

Последовательности имеют два основных подкласса, IndexedSeq и LinearSeq, которые дают различные гарантии производительности. IndexedSeq обеспечивает быстрый произвольный доступ к элементам и быструю операцию length. LinearSeq обеспечивает быстрый доступ только к первому элементу через head, но также имеет быструю операцию tail.

Обобщённый трайт для неизменяемых множеств.

Множество — это коллекция, не содержащая дублирующих элементов.

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

def contains(key: A): Boolean
def iterator: Iterator[A]
def +(elem: A): This
def -(elem: A): This

Если вы хотите, чтобы методы, такие как take, drop, filter возвращали множество того же типа, вы также должны переопределить:

def empty: This

Также рекомендуется переопределить методы foreach и size для повышения эффективности.

Карта, ключи которой отсортированы.

Подкласс collection.SortedSet, представляющий отсортированные неизменяемые множества.

Класс Stream реализует ленивые списки, где элементы вычисляются только при необходимости. Вот пример:

import scala.math.BigInt
object Main extends App {

  lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(fibs.tail).map { n => n._1 + n._2 }

  fibs take 5 foreach println
}

// prints
//
// 0
// 1
// 1
// 2
// 3

Класс Stream также использует запоминание результатов (мемоизацию), так что ранее вычисленные значения преобразуются из Stream элементов в конкретные значения типа A. Чтобы проиллюстрировать, мы изменим содержимое значения fibs выше и возьмём ещё несколько значений:

import scala.math.BigInt
object Main extends App {

  lazy val fibs: Stream[BigInt] = BigInt(0) #:: BigInt(1) #:: fibs.zip(
    fibs.tail).map(n => {
      println("Adding %d and %d".format(n._1, n._2))
      n._1 + n._2
    })

  fibs take 5 foreach println
  fibs take 6 foreach println
}

// prints
//
// 0
// 1
// Adding 0 and 1
// 1
// Adding 1 and 1
// 2
// Adding 1 and 2
// 3

// And then prints
//
// 0
// 1
// 1
// 2
// 3
// Adding 2 and 3
// 5

В приведённом выше примере есть несколько тонких моментов.

Определение fibs является val а не методом. Для запоминания результатов Stream нам нужно хранилище информации, и val позволяет это сделать. Хотя значение Stream фактически изменяется во время доступа, это не меняет концепции его неизменяемости. После запоминания результатов значения не меняются, и значения, которые ещё не были запомнены, по-прежнему «существуют», просто они ещё не были вычислены. Следует проявлять осторожность при использовании запоминания результатов; вы можете очень быстро израсходовать много памяти, если не будете внимательны. Причина в том, что запоминание результатов для Stream создаёт структуру, похожую на scala.collection.immutable.List. Пока что-то ссылается на голову списка, голова ссылается на хвост, и так далее рекурсивно. Если же ничего не ссылается на голову (например, мы использовали def для определения Stream), то, как только она больше не используется напрямую, она исчезает.Обратите внимание, что некоторые операции, включая drop, dropWhile, flatMap или collect могут обработать большое количество промежуточных элементов перед возвращением. Это неизбежно приводит к удержанию головы, так как они являются методами для Stream, а поток содержит собственную голову. Для вычислений такого рода, где запоминание результатов нежелательно, используйте Iterator, если это возможно.

// For example, let's build the natural numbers and do some silly iteration
// over them.

// We'll start with a silly iteration
def loop(s: String, i: Int, iter: Iterator[Int]): Unit = {
  // Stop after 200,000
  if (i < 200001) {
    if (i % 50000 == 0) println(s + i)
    loop(s, iter.next, iter)
  }
}

// Our first Stream definition will be a val definition
val stream1: Stream[Int] = {
  def loop(v: Int): Stream[Int] = v #:: loop(v + 1)
  loop(0)
}

// Because stream1 is a val, everything that the iterator produces is held
// by virtue of the fact that the head of the Stream is held in stream1
val it1 = stream1.iterator
loop("Iterator1: ", it1.next, it1)

// We can redefine this Stream such that all we have is the Iterator left
// and allow the Stream to be garbage collected as required.  Using a def
// to provide the Stream ensures that no val is holding onto the head as
// is the case with stream1
def stream2: Stream[Int] = {
  def loop(v: Int): Stream[Int] = v #:: loop(v + 1)
  loop(0)
}
val it2 = stream2.iterator
loop("Iterator2: ", it2.next, it2)

// And, of course, we don't actually need a Stream at all for such a simple
// problem.  There's no reason to use a Stream if you don't actually need
// one.
val it3 = new Iterator[Int] {
  var i = -1
  def hasNext = true
  def next(): Int = { i += 1; i }
}
loop("Iterator3: ", it3.next, it3)

Интересно, что tail работает вообще. В определении fibs у нас есть начальное (0, 1, Stream(...)), поэтому tail детерминировано. Если бы мы определили fibs таким образом, что только 0 были бы конкретными, то определение tail потребовало бы вычисления tail, что привело бы к бесконечной рекурсии и переполнению стека. Если мы определим определение, где хвост изначально не вычислим, то у нас будет бесконечная рекурсия:

// The first time we try to access the tail we're going to need more
// information which will require us to recurse, which will require us to
// recurse, which...
lazy val sov: Stream[Vector[Int]] = Vector(0) #:: sov.zip(sov.tail).map { n => n._1 ++ n._2 }

Определение fibs выше создаёт больше объектов, чем необходимо, в зависимости от того, как вы хотите его реализовать. Следующая реализация предоставляет более «эффективную» реализацию из-за того, что она имеет более прямой путь к самим числам:

lazy val fib: Stream[Int] = {
  def loop(h: Int, n: Int): Stream[Int] = h #:: loop(n, h + n)
  loop(1, 1)
}

Обратите внимание, что mkString принудительно вычисляет Stream, но addString нет. В обоих случаях Stream , который содержит или заканчивается циклом (например, lazy val s: Stream[Int] = 0 #:: s ), преобразует дополнительные проходы через цикл в .... Кроме того, addString будет отображать не-запомненный хвост как ?.

Интерфейс, описывающий строкоподобные коллекции.

Этот класс служит оболочкой, предоставляющей для scala.Predef.String все операции, найденные в индексированных последовательностях. По мере необходимости String неявно преобразуются в экземпляры этого класса.

Разница между этим классом и WrappedString заключается в том, что вызов методов преобразования, таких как filter и map , приведет к объекту String, в то время как WrappedString останется WrappedString.

Тракт для итерируемых коллекций, гарантированно неизменяемых.

Это базовый тракт всех типов неизменяемых коллекций Scala. Он реализует поведение, общее для всех коллекций, в терминах метода foreach со следующей сигнатурой:

def foreach[U](f: Elem => U): Unit

Классы коллекций, смешивающие этот тракт, предоставляют конкретный foreach метод, который перебирает все элементы, содержащиеся в коллекции, применяя к каждому заданную функцию. Они также должны предоставить метод newBuilder, который создаёт билдер для коллекций того же типа.

Итерируемый класс может или не может иметь два свойства: строгость и упорядоченность. Ни то, ни другое не представлено как тип.

Экземпляры строгого класса коллекции вычисляют все свои элементы, прежде чем они могут быть использованы как значения. В отличие от этого, экземпляры нестрогого класса коллекции могут отложить вычисление некоторых своих элементов до тех пор, пока экземпляр не станет доступен как значение. Типичным примером нестрогого класса коллекции является scala.collection.immutable.Stream. Более общим классом примеров являются TraversableViews.

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

Типичным примером класса коллекции, который не упорядочен, является HashMap объектов. Порядок обхода для хеш-карт будет зависеть от хеш-кодов его элементов, и эти хеш-коды могут отличаться от одного запуска к другому. В отличие от этого, LinkedHashMap упорядочен, потому что его метод foreach посещает элементы в порядке их вставки в HashMap.

Этот класс реализует неизменяемые карты, используя дерево.

Этот класс реализует неизменяемые множества, используя дерево.

Вектор — универсальная неизменяемая структура данных. Обеспечивает произвольный доступ и обновления за время, близкое к постоянному, а также очень быстрые добавление в начало и в конец. Поскольку векторы хорошо сбалансированы между быстрым случайным выбором и быстрыми случайными функциональными обновлениями, они в настоящее время являются стандартной реализацией неизменяемых индексированных последовательностей. Он основан на little-endian bit-mapped vector trie с коэффициентом ветвления 32. Локальность очень высокая, но не непрерывная, что хорошо подходит для очень больших последовательностей.

Примечание: Несмотря на то, что это неизменяемая коллекция, в реализации используется изменчивое состояние во время построения. Эти изменения состояния незаметны в однопоточном коде, но могут привести к гонкам в некоторых многопоточных сценариях. Состояние нового экземпляра коллекции может не быть «опубликовано» (в смысле спецификации модели памяти Java), поэтому несинхронизированное неявное чтение из другого потока может увидеть объект в некорректном состоянии (см. scala/bug#7838 для получения дополнительных сведений). Обратите внимание, что такое чтение не гарантируется, что оно когда-либо увидит написанный объект вообще, и поэтому не должно использоваться, независимо от этой проблемы. Самый простой способ обойти это — обмениваться значениями между потоками через volatile переменную.

Класс для построения экземпляров Vector. Этот билдер многоразового использования.

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

Разница между этим классом и StringOps заключается в том, что вызов методов преобразования, таких как filter и map, приведет к объекту типа WrappedString вместо String.

Это простой класс-оболочка для `scala.collection.immutable.Map`.

Он наиболее полезен для динамического сборки настраиваемых абстракций карт с помощью композиции объектов и переадресации.

Реализация ленивых вычисляемых последовательностей, где элементы хранятся в "страницах", т.е. массивах фиксированного размера.

Последовательность страниц создается с помощью функции, которая производит больше элементов по запросу. Функция производителя - more, похожа на метод чтения в java.io.Reader. Функция more принимает три параметра: массив элементов, начальный индекс и конечный индекс. Она должна попытаться заполнить массив между начальным и конечным индексами (исключая конечный индекс). Она возвращает количество произведенных элементов или -1, если конечная логическая входная последовательность была достигнута до чтения любого элемента.

Это простой класс-оболочка для scala.collection.immutable.Set.

Он наиболее полезен для динамического сборки настраиваемых абстракций множеств с использованием композиции объектов и переадресации.

Этот класс реализует неизменяемые стеки с использованием структуры данных на основе списка.

Примечание: Этот класс существует только по историческим причинам и в качестве аналога изменяемых стеков. Вместо неизменяемого стека можно просто использовать список.