предисловие

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

остальная часть этого ответа была написана задолго до того, как такая вещь существовала (фактически, до того, как сам 2.8.0 был выпущен).

вы можете найдите статью об этом как Scala SID #3. Другие документы в этой области также должны быть интересны людям, заинтересованным в различиях между Scala 2.7 и 2.8.

я буду цитировать из статьи, выборочно, и дополнять некоторые мои мысли. Есть также некоторые изображения, созданные Matthias at decodified.com, и оригинальные файлы SVG можно найти здесь.

классы/черты коллекции сами

на самом деле существует три иерархии признаков для коллекций: одна для изменяемых коллекций, одна для неизменяемых коллекций и одна, которая не делает никаких предположений о коллекциях.

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

на следующем рисунке показана неспецифическая иерархия, введенная с помощью Scala 2.8:

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

график незыблемые иерархии:

график для изменяемой иерархии:

легенда:

вот сокращенное изображение ASCII иерархии коллекции, для тех, кто не может видеть изображения.

                    Traversable
                         |
                         |
                      Iterable
                         |
      +------------------+--------------------+
     Map                Set                  Seq
      |                  |                    |
      |             +----+----+         +-----+------+
    Sorted Map  SortedSet   BitSet   Buffer Vector LinearSeq

Параллельные Коллекции

когда Scala 2.9 представила параллельные коллекции, одной из целей дизайна было сделать их использование максимально бесшовным. Проще говоря, один можно заменить непараллельную (последовательную) коллекцию на параллельную и мгновенно пожинать плоды.

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

два для поддержки параллельных коллекций были созданы новые иерархии.

иерархия параллельных коллекций имеет те же имена для признаков, но предшествует Par:ParIterable,ParSeq,ParMap и ParSet. Обратите внимание, что нет ParTraversable, так как любая коллекция, поддерживающая параллельный доступ, способна поддерживать более сильный ParIterable черта. Он также не имеет некоторых из более специализированных черт, присутствующих в последовательной иерархии. Вся эта иерархия находится под каталог scala.collection.parallel.

классы, реализующие параллельные коллекции также отличаются, с ParHashMap и ParHashSet как для изменяемых, так и для неизменяемых параллельных коллекций, плюс ParRange и ParVector реализация immutable.ParSeq и ParArray реализация mutable.ParSeq.

также существует другая иерархия, которая отражает черты последовательных и параллельных коллекций, но с префиксом Gen:GenTraversable,GenIterable,GenSeq,GenMap и GenSet. Эти черты родителям как для параллельных, так и для серийных коллекций. Это означает, что метод принимает Seq не может получить параллельную коллекцию, но метод принятия GenSeq предполагается работа как с последовательными, так и с параллельными коллекциями.

учитывая то, как эти иерархии были структурированы, код, написанный для Scala 2.8, был полностью совместим с Scala 2.9 и требовал последовательного поведения. Без перезаписи он не может использовать преимущества параллельных коллекций, но необходимые изменения очень малы.

Использование Параллельных Коллекций

любую коллекцию можно преобразовать в параллельную, вызвав метод par на нем. Аналогично, любая коллекция может быть преобразована в последовательную путем вызова метода seq на нем.

если коллекция уже была запрошена (параллельная или последовательная), преобразование не будет выполнено. Если кто-то звонит seq на параллельной коллекции или par на серийный коллекция, однако, будет создана новая коллекция с запрошенной характеристикой.

не путай seq, который превращает коллекцию в непараллельную коллекцию, с toSeq, который возвращает a Seq создается из элементов коллекции. Звоню toSeq на параллельной коллекции вернет a ParSeq, не серийная коллекция.

Основные Черты

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

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

Trait TraversableOnce

эта черта очень похожа на черту Traversable описано ниже, но с ограничением, что вы можете использовать только его один раз. Что есть, любые методы, вызываемые на TraversableOnceмая сделать его непригодным для использования.

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

, потому что TraversableOnce объединяет коллекции и итераторы, it не отображается на предыдущих графиках,которые касаются только коллекций.

Черта Проходимым

в верхней части коллекция иерархия признака Traversable. Его единственная абстрактная операция -

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

операция предназначена для обхода всех элементов коллекции и применения данной операции f к каждому элемент. Приложение выполняется только для его побочного эффекта; на самом деле любой результат функции f отбрасывается инструкция foreach.

проходимые объекты могут быть конечными или бесконечными. Примером бесконечного проходимого объекта является поток натуральных чисел Stream.from(0). Метод hasDefiniteSize указывает, возможно ли создание коллекции бесконечный. Если hasDefiniteSize возвращает true, коллекция, безусловно, конечна. Если он возвращает false, то коллекция еще не была полностью разработана, поэтому она может быть бесконечной или конечной.

этот класс определяет методы, которые могут быть эффективно реализовано в терминах foreach (более 40 из них).

Черта Iterable

эта черта объявляет абстрактный метод iterator это возвращает итератор, который дает все элементы коллекции один за другим. Элемент foreach метод Iterable реализуется в терминах iterator. Подклассы Iterable часто переопределение оператора foreach с прямым реализации для повышения эффективности.

класс Iterable также добавляет некоторые менее часто используемые методы Traversable, которым может быть эффективно реализован только в том случае, если iterator доступно. Они кратко излагаются ниже.

xs.iterator          An iterator that yields every element in xs, in the same order as foreach traverses elements.
xs takeRight n       A collection consisting of the last n elements of xs (or, some arbitrary n elements, if no order is defined).
xs dropRight n       The rest of the collection except xs takeRight n.
xs sameElements ys   A test whether xs and ys contain the same elements in the same order

Другие Особенности

после Iterable есть три основные черты, которые наследуют от него:Seq,Set и Map. У всех троих есть apply метод и все три использовать тег PartialFunction черта, но смысл apply отличается в каждом случае.

я доверяю смыслу Seq,Set и Map интуитивно понятен. После они, классы разбиваются на конкретные реализации, которые предлагают определенные гарантии в отношении производительности, и методы, которые он делает доступными в результате этого. Также доступны некоторые черты с дальнейшими уточнениями, такие как LinearSeq,IndexedSeq и SortedSet.

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

базовые классы и черт

• Traversable -- Basic класс коллекции. Может быть реализован только с foreach.
  • TraversableProxy -- прокси для Traversable. Просто точка self в настоящий сборник.
  • TraversableView -- A проходимый с некоторыми нестрогими методами.
  • TraversableForwarder -- пересылает большинство методов в underlying, за исключением toString,hashCode,equals,stringPrefix,newBuilder,view и все вызовы, создающие новый итерационный объект того же типа.
  • mutable.Traversable и immutable.Traversable -- то же самое вещь как Traversable, но ограничение типа коллекции.
  • другие особые случаи Iterable классов, например MetaData существует.
  • Iterable -- коллекция, для которой Iterator может быть создан (через iterator).
    • IterableProxy,IterableView,mutable и immutable.Iterable.
• Iterator -- черта, которая не является потомком Traversable. Определить next и hasNext.
  • CountedIterator -- An Iterator определение count, который возвращает элементы до сих пор.
  • BufferedIterator -- определяет head, который возвращает следующий элемент, не потребляя его.
  • другие особые случаи Iterator классов, например Source существует.

Карты

• Map -- An Iterable на Tuple2, который также предоставляет методы для получения значение (второй элемент кортежа) задается ключом (первый элемент кортежа). Расширяется PartialFunction как хорошо.
  • MapProxy -- A Proxy на Map.
  • DefaultMap -- черта, реализующая некоторые из Mapабстрактные методы.
  • SortedMap -- A Map чьи ключи сортируются.
    • immutable.SortMap
      • immutable.TreeMap -- реализация класса immutable.SortedMap.
  • immutable.Map
    • immutable.MapProxy
    • immutable.HashMap -- класс, реализующий immutable.Map через ключ хеширования.
    • immutable.IntMap -- класс, реализующий immutable.Map специализированных для Int ключи. Использует дерево, основанное на двоичных цифрах ключей.
    • immutable.ListMap -- класс, реализующий immutable.Map через списки.
    • immutable.LongMap -- реализация класса immutable.Map специализированных для Long ключи. Смотрите IntMap.
    • есть дополнительные классы, оптимизированные для определенного количества элементов.
  • mutable.Map
    • mutable.HashMap -- класс, реализующий mutable.Map через ключ хеширования.
    • mutable.ImmutableMapAdaptor -- класс, реализующий a mutable.Map из существующего immutable.Map.
    • mutable.LinkedHashMap -- ?
    • mutable.ListMap -- реализация класса mutable.Map через списки.
    • mutable.MultiMap -- класс, принимающий более одного отдельного значения для каждого ключа.
    • mutable.ObservableMap -- A mixin, который при смешивании с Map, публикует события для наблюдателей через Publisher интерфейс.
    • mutable.OpenHashMap -- класс, основанный на открытом алгоритме хэширования.
    • mutable.SynchronizedMap -- A mixin который должен быть смешан с Map чтобы предоставить его версию с синхронизированные методы.
    • mutable.MapProxy.

Последовательности

• Seq -- последовательность элементов. Предполагается четко определенный размер и повторение элементов. Расширяется PartialFunction как хорошо.
  • IndexedSeq -- последовательности, которые поддерживают доступ к элементам O(1) и вычисление длины O(1).
    • IndexedSeqView
    • immutable.PagedSeq -- реализация IndexedSeq где элементы создаются по требованию функцией, переданной через конструктор.
    • immutable.IndexedSeq
      • immutable.Range -- разделенная последовательность целых чисел, замкнутая на нижнем конце, открытая на верхнем конце и с шагом.
        • immutable.Range.Inclusive -- A Range закрыт на верхнем конце, а также.
        • immutable.Range.ByOne -- A Range чей Шаг 1.
      • immutable.NumericRange -- более общая версия Range, который работает с любым Integral.
        • immutable.NumericRange.Inclusive,immutable.NumericRange.Exclusive.
        • immutable.WrappedString,immutable.RichString -- обертки, которые позволяют видеть String как Seq[Char], сохраняя при этом String методы. Я не уверен, в чем разница между ними.
    • mutable.IndexedSeq
      • mutable.GenericArray -- An Seqмассив как структура. Обратите внимание, что "класс" Array это Java Array, который является скорее методом хранения памяти, чем классом.
      • mutable.ResizableArray -- внутренний класс, используемый классами на основе изменяемых массивов.
      • mutable.PriorityQueue,mutable.SynchronizedPriorityQueue -- классы, реализующие приоритетные очереди -- очереди, в которых элементы удаляются в соответствии с Ordering во-первых, и порядок очереди в последнюю очередь.
      • mutable.PriorityQueueProxy -- абстрактное Proxy для a PriorityQueue.
  • LinearSeq -- черта для линейных последовательностей, с эффективным временем для isEmpty,head и tail.
    • immutable.LinearSeq
      • immutable.List -- неизменяемая, односвязная реализация списка.
      • immutable.Stream -- ленивый-список. Его элементы вычисляются только по требованию, но запоминаются (хранятся в памяти) впоследствии. Это может быть теоретически бесконечный.
    • mutable.LinearSeq
      • mutable.DoublyLinkedList -- список с изменяемым prev,head (elem) и tail (next).
      • mutable.LinkedList -- список с изменяемым head (elem) и tail (next).
      • mutable.MutableList -- класс, используемый внутри для реализации классов на основе изменяемых списков.
        • mutable.Queue,mutable.QueueProxy -- структура данных, оптимизированная для FIFO (First-In, Первый выход) операции.
        • mutable.QueueProxy -- A Proxy на mutable.Queue.
  • SeqProxy,SeqView,SeqForwarder
  • immutable.Seq
    • immutable.Queue -- класс, реализующий оптимизированную по FIFO (First-In, First-Out) структуру данных. Нет общего суперкласса, как mutable и immutable очереди.
    • immutable.Stack -- класс, реализующий a ЛИФО-оптимизирован (последний в, первым вышел) структура данных. Нет общего суперкласса, как mutableimmutable стеки.
    • immutable.Vector -- ?
    • scala.xml.NodeSeq -- специализированный класс XML, который расширяет immutable.Seq.
    • immutable.IndexedSeq -- как показано выше.
    • immutable.LinearSeq -- как показано выше.
  • mutable.ArrayStack -- класс, реализующий оптимизированную для LIFO структуру данных с использованием массивов. Якобы значительно быстрее чем обычный стек.
  • mutable.Stack,mutable.SynchronizedStack -- классы, реализующие оптимизированную для LIFO структуру данных.
  • mutable.StackProxy -- A Proxy на mutable.Stack..
  • mutable.Seq
    • mutable.Buffer -- последовательность элементов, которые могут быть изменены путем добавления, добавления или вставки новых элементов.
      • mutable.ArrayBuffer -- реализация mutable.Buffer класс, с постоянным амортизированным временем для добавления, обновления и случайного операции доступа. Он имеет некоторые специализированные подклассы, такие как NodeBuffer.
      • mutable.BufferProxy,mutable.SynchronizedBuffer.
      • mutable.ListBuffer -- буфер, поддерживаемый списком. Он обеспечивает постоянное время добавления и добавления, причем большинство других операций являются линейными.
      • mutable.ObservableBuffer -- A mixin черта, которая, при смешивании с Buffer, обеспечивает события уведомления через Publisher интерфейсы.
      • mutable.IndexedSeq -- как видно выше.
      • mutable.LinearSeq -- как показано выше.

Наборы

• Set -- набор-это коллекция, которая включает в себя не более одного объекта.
  • BitSet -- набор целых чисел, хранящихся в виде битов.
    • immutable.BitSet
    • mutable.BitSet
  • SortedSet -- набор, элементами которого являются упорядоченный.
    • immutable.SortedSet
      • immutable.TreeSet -- реализация a SortedSet на основе дерева.
  • SetProxy -- A Proxy на Set.
  • immutable.Set
    • immutable.HashSet -- реализация Set на основе хеширования элементов.
    • immutable.ListSet -- реализация Set на основе списков.
    • существует дополнительный набор классов чтобы обеспечить оптимизированные реализации для наборов от 0 до 4 элементов.
    • immutable.SetProxy -- A Proxy для неизменяемого Set.
  • mutable.Set
    • mutable.HashSet -- реализация Set на основе хеширования элементов.
    • mutable.ImmutableSetAdaptor -- класс, реализующий изменяемый Set от неизменного Set.
    • LinkedHashSet -- реализация Set на основе списки.
    • ObservableSet -- A mixin черта, которая, при смешивании с Set, обеспечивает события уведомления через Publisher интерфейс.
    • SetProxy -- A Proxy на Set.
    • SynchronizedSet -- A mixin черта, которая, при смешивании с Set, обеспечивает события уведомления через Publisher взаимодействие.

---

• почему существуют подобные классы (например, TraversableLike)

это было сделано для достижения максимального повторного использования кода. Бетон generic реализация для классов с определенной структурой (проходимая, карта и т. д.) выполняется в подобных классах. Классы, предназначенные для общего потребления, затем переопределить некоторые методы, которые могут быть optmized.

• для чего предназначены сопутствующие методы (например, список.компаньон)

Строитель для классов, т. е. объект, который знает, как создавать экземпляры этого класса таким образом, который может быть использован такими методами, как map, создается методом в сопутствующем объекте. Итак, чтобы построить объект типа X, мне нужно получить этот строитель из сопутствующего объекта X. К сожалению, в Scala нет способа получить из класса X объект X. Из-за этого существует метод, определенный в каждом экземпляре X, companion, который возвращает сопутствующий объект класса X.

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

• как я знаю, какие неявные объекты находятся в области видимости в данной точке

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

эти импликаты существуют для того, чтобы методы в коллекциях определялись в родительских классах, но все же возвращали коллекцию того же типа. Например,map метод определяется на TraversableLike, а если вы использовали на List вы получаете List обратно.