This work is licensed with Creative Commons Attribution 3.0 Unported License.
You are able:
- to Share — to copy, distribute and transmit the work
- to Remix — to adapt the work

Автор: Leonid Krashenko
e-mail: Leonid.Krashenko@gmail.com

Перевод данного руководства - одна из тем атома Org1 (орг ван), см. http://trac.assembla.com/org1/wiki/WikiStart

= Глава 8. Классы коллекций =

Танго предоставляет набор классов коллекций, иногда также называемых классов контейнеров. Они расположены в пакете {{{tango.util.collection}}} наряду с некоторыми шаблонными контейнерами. 

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

Хорошей практикой является определение т.н. {{{alias}}} (псевдонимов):

{{{
#!cpp
alias LinkSeq!(int) MyIntList;

auto list = new MyIntList;
list.add(1);
}}}

== Типы контейнеров ==

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

||          || Array    || Link                 || Tree    || Hash    ||
|| Bag      || ArrayBag ||                      || TreeBag ||         ||
|| Set      ||          ||                      ||         || HashSet ||
|| Sequence || ArraySeq || LinkSeq, CircularSeq ||         ||         ||
|| Map      ||          || LinkMap              || TreeMap || HashMap ||

==== Bag ====

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

==== Set ====

В этом контейнере сущности не дублируются. '''Set''' и '''Bag''' отличаются тем, что последний может хранить дублирующиеся сущности.

==== Sequence ==== 

Данный контейнер хранит сущности в порядке их добавления. 

==== Map ====

Это ассоциативный контейнер. У него есть множество уникальных ключей, каждый из которых привязан к некоторому значению. {{{Ключ}}} и {{{Значение}}} - шаблонные параметры. 

==== Arrays ====

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

==== Linked lists ====

Связанные списки. Эти контейнеры увеличивают свой размер, взимая за это постоянную ценю. То есть добавление в начало списка, вставка или добавление в конец списка выполняются за постоянное число операций. Недостаток в том, что поиск элемента в середине связанного списка требует итерации по списку. Для больших коллекций этот процесс занимает длительное время. 

==== Trees ====

Деревья.  Эти контейнеры используют двоичное дерево для доступа к элементам. Цена вставки и извлечения низкая. 

==== Hash ====

Хэши. Это самые быстрые контейнеры, однако им требуется больше памяти. И элементы также должны поддерживать хорошую реализацию {{{toHash()}}}.

== Обзор моделей и методов ==

 * Связь между классами коллекций
 * Методы классов коллекций
 
=== Создание коллеций ===

Простейший путь - инстанциировать непосредственно, используя переменную {{{auto}}} для удержания ссылки:

{{{
#!cpp
    auto list2 = new LinkSeq!( int );
}}}

В большинстве случаев коллекции используются больше, чем 1 раз, поэтому полезно придумать {{{alias}}}:

{{{
#!cpp
    alias LinkSeq!( char[] ) StrList;
    StrList list1 = new StrList;
}}}

=== Добавление и удаление элементов ===

У каждого типа контейнера есть свой набор методов.

{{{
#!cpp
    list1.append( "The first item in list1" );
    list2.prepend( 2 );
}}}

См. раздел [MethodsExposedByTheCollectionClasses Методы классов коллекций].

=== Доступ к элементам ===

Обычно, простейший паттерн такой:

{{{
#!cpp
    foreach (key, value; map)
             Stdout.formatln ("Key: {0}, Value: {1}", key, value);
}}}

Можно использовать только {{{value}}} вместо обоих {{{key}}} и {{{value}}}. Совместное их ипользование использует несколько более эффективный алгоритм доступа к каждому элементу (или паре элементов), т.к. они позволяют избежать действий с кучей при инстанциировании {{{Iterator}}}.

Коллекции также позволяют работать с итераторами, поддерживая как паттерн {{{foreach}}}, так и известный паттерн {{{more()/next()}}}. Каждый контейнер содержит методы, инстанциирующие соответствующий {{{Iterator}}}:

{{{
#!cpp
    auto it = map.keys();

    // The call to .more returns true if there are more elements,
    // and switches the iterator to the next one if available.
    while(it.more){
          char[] key; 
          auto value = it.get(key);
          Stdout.formatln ("Key: {0}, Value:{1}", key, value);
    }
}}}

Для ассоциативных контейнеров метод итератора {{{get}}} имеет выходной параметр для получения ключа. 

Метод {{{keys()}}} используется для получения множества ключей. Для "нормальных" контейнеров вроде {{{LinkSeq}}} и др. метод {{{elements()}}} используется для получения подходящего итератора. Каждый контейнер также поддерживает foreach() непосредственно. 

=== Асинхронные мутации в процессе итерации ===

Итераторы чувствительны к изменениям в контейнере во время своей работы, и они бросают исключение, если такие изменения произойдут. (!!!)

=== Меры предосторожности ===

В настоящее время невозможно изменять контейнер во время итерации с помощью {{{foreach}}} или с использованием итератора. Для того, чтобы удалить конкретные элементы из контейнера необходимо делать это в 2 этапа: найти элементы для удаления, затем удалить их.

{{{
#!cpp
// 1. Build a list of elements to delete
auto dellist = new LinkSeq!(int);
foreach( int i; container ){
  if( i >= 3 && i < 7 ){
    // container.remove( i ); /* NOT POSSIBLE */
    dellist.append( i );
  }
}
// 2. Iterate over this deletion list and
// delete the items in the original container.
foreach( int i; dellist ){
    container.remove( i );
}
}}}

Это может быть поправлено в будущем. 

== InterleavingIterator ==

Сплетающий итератор. Этот более сложный итератор демонстрирует, почему итераторы остаются полезными, даже когда у нас появилась конструкция {{{foreach}}}:

{{{InterleavingIterator}}}-ы позволяют комбинировать элементы двух различных перечислений так, как если бы они были одним перечислением (!!!). Иногда это позволяет избежать использования коллекции в процессе комбинирования двух множеств {{{elements()}}}, которые должны быть собраны вместе для дальнейшей совместной обработки. 

Доступ к элементам осуществляется (через {{{get()}}}) в стиле "переплетения". Новое перечисление формируется переплетением двух перечислений до тех пор, пока одно из них не закончится, после чего в новое множество добавляются оставшиеся элементы другого:

{{{
#!cpp
import tango.util.collection.ArrayBag;
import tango.util.collection.iterator.InterleavingIterator;

void testInterleavingIterator(){
    int[] result;

    // Create and fill the containers
    auto l1 = new LinkSeq!(int);
    auto l2 = new ArraySeq!(int);
    for( int i = 0; i < 6; i+=2 ){
        l1.append( i );
        l2.append( i+1 );
    }

    // define the InterleavingIterator
    auto it = new InterleavingIterator!(int)(l1.elements, l2.elements);

    // use the InterleavingIterator to iterate over the container
    while (it.more)
        result ~= it.get;

    // test the result
    assert(result == [0, 1, 2, 3, 4, 5], "testInterleavingIterator");
}
}}}

== FilteringIterator ==

Фильрующий итератор. Он позволяет фильтровать элементы из перечислений до того, как они станут доступны потребителям (т.е. вызывающим {{{get()}}}).

{{{
#!cpp
import tango.util.collection.LinkSeq;
import tango.util.collection.ArraySeq;
import tango.util.collection.iterator.FilteringIterator;

void testFilteringIterator(){
    int[] result;
    alias ArrayBag!(int) IntBag;

    // Create and fill the container
    auto ib = new IntBag;
    for( int i = 0; i < 20; i++ ){
        ib.add( i );
    }

    // define the FilteringIterator with a function literal
    auto it = new FilteringIterator!(int)( ib.elements(), (int i){ 
        return i >= 3 && i < 7; 
    });

    // use the FilteringIterator to iterate over the container
    while (it.more())
        result ~= it.get();

    // test the result
    assert( result == [ 3, 4, 5, 6 ], "testFilteringIterator" );
}
}}}

== Компараторы ==

Отсортированные контейнеры вроде деревьев нуждаются в возможности сравнения элементов. Пользователь может указывать, какой алгоритм будет использован для сравнения. Например, строки могут быть отсортированы по-разному. Если вам нужен контейнер типа {{{Bag}}} с методом {{{addIf}}}, реализующим ваш собственный метод сравнения, добиться этого можно так:

{{{
#!cpp
    // Create a bag that is not case sensitive
    auto nameSet = new TreeBag!(char[])( null, 
      new class() Comparator!(char[]){
        int compare( char[] first, char[] second ){
            return Ascii.icompare( first, second );
        }
    });

    nameSet.addIf( "Alice" );
    nameSet.addIf( "Bob" );
    nameSet.addIf( "aliCe" ); // will not be added
}}}

== Отражатели ==

Каждый контейнер может иметь предикат, также называемый отражателем (screener). Его определение можно найти в классе {{{Collection}}}.

{{{
#!cpp
    alias bool delegate(T) Predicate;
}}}

Этот делегат будет вызываться каждый раз, когда в контейнер добавляется новый элемент. Если отражатель возвращает "ложь", то контейнер бросает исключение {{{IllegalElementException}}}.

{{{
#!cpp
    // Создадим контейнер с ограничением
    auto ratioSamples = new ArraySeq!(float)( (float v){
        // ограничим элемент диапазоном 0.0 .. 0.99999..
        return v >= 0.0f && v < 1.0f;
    });

    // Попробуем что-нибудь вставить
    try{
        ratioSamples.append( 0.0f );      // OK
        ratioSamples.append( 0.5f );      // OK
        ratioSamples.append( 0.99999f );  // OK
        ratioSamples.append( 1.0f );      // Bang
        // никогда до сюда не дойдем
        assert( false );
    } catch( IllegalElementException e ){
    }
}}}

Чтобы проверить, разрешен ли элемент данным контейнером, используйте метод {{{bool allows( T )}}} класса {{{Collection}}}.

== Сумка и Множество (Bag и Set) ==

Сумки [Bags] суть коллекции, поддерживающие дублирующиеся элементы. Множества [Sets] поддерживают только уникальные элементы. Последовательность элементов для обоих из них не определена. Исключением является {{{TreeBag}}}, элементы которого располагаются в их естественном порядке. (...)

Все {{{bags}}} поддерживают метод {{{addIf}}}, и могут использоваться как множества ({{{sets}}}).

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

== Sequence, упорядоченное хранилище ==

Последовательности (Sequences) являются индексированными, последовательно упорядоченными коллекциями. Индексы принадлежат диапазону {{{0 .. size()-1}}}. Доступ по индексу подлежит проверке, исключение выбрасывается если индекс выходит за границы диапазона. 

Гарантируется, что обход (через {{{more()/get()}}}) перечисления {{{elements()}}} для всех последовательностей будет происходить в соответствующем порядке. 

 * [Seq] является интерфейсом для всех последовательностей
 * [ArraySeq] реализует класс, используя массив. Лучше всего его использовать, когда размер хранилища меняется не так часто, или если требуется быстрый доступ к элементу по индексу. 
 * [LinkSeq] реализует класс, используя узлы элементов, размещаемых в памяти динамически и связанных друг с другом. Такая реализация позволяет легко добавлять элементы в начало или удалять их оттуда (с помощью {{{take()}}}). Произвольный доступ к элементам по индексу медленен, т.к. в этом случае приходится следовать по ссылкам от начала хранилища. 
 * [CircularSeq] похож на {{{LinkSeq}}}. Однако этот класс использует дважды связанные ячейки, позволяя таким образом уравнять цену операций добавления или удаления элементов, независимо от того, происходит это в начале или в конце списка. 
 
== Map, ассоциативный контейнер ==

[Maps] (карты) поддерживают элементы с ключами. Любой объект может служить ключем для элемента. Ключи уникальны и ассоциированы каждый с одним значением. 

{{{
#!cpp
    import tango.store.HashMap;
    // ...
    alias HashMapT!(char[], char[]) StrStrMap;

    auto map = new StrStrMap();
    map.add("key1", "value1");
    char[] key = "key1";
    Stdout.format ("Key: {0}, Value:{1}", key, map.get(key)).newline;
}}}

== Hash против Tree ==

{{{Set}}}-ы и {{{Map}}}-ы имеют реализации, основанные как на деревьях, так и на хэшах. Когда какую использовать?

Использование дерева подразумевает необходимость навигации по структуре дерева для поиска элемента. Количество этапов для обхода примерно равно {{{O(log2(n))}}}.

Когда вы используете хэш-таблицу, используется массив для хранения заданного числа (...). Хэш-функция требуется для вычисления хэша от значения объекта. Хэш представляет собой n-битное целое число, уникальное для каждого объекта. Одно и тоже содержание объекта должно отражаться в одном и том же значении хэша. Это значение используется каждый раз, когда (...). 

В лучшем случае алгоритм может сразу найти элемент ( если (...) содержит всего 1 элемент). Доступ тогда занимает постоянное время или {{{O(1)}}}. Но если (...) содержит множество элементов, тогда (в зависимости от реализации) это проводит к линейному поиску. В хорошей хеш-таблице такого происходить не должно. Чтобы удостовериться, что (...) не  заполнены польностью, под них должен быть выделен большой массив. Это значит, хэш-таблице требуется гораздо больше времени, чем дереву, а также хорошая хэш-функция. 

== Встроенные массивы языка Ди и хэш-таблицы против ArraySeq и HashMap ==

Язык Ди сам по себе поддерживает встроенные динамические массивы и хэши. Зачем использовать шаблонные контейнеры?

Используйте встроенные массивы/хэши, если они покрывают все ваши нужды. Не забывайте, однако, что {{{ArraySeq/HashMap}}} предоставляют дополнительные возможности: 

 * функция-отражатель для ограничения диапазона вставляемых элементов. 
 * Итераторы, реализующие различное поведения.
 * Коллекции библиотеки Танго совместимы друг с другом, т.к. они реализуют общие интерфейсы. Поэтому теоретически возможно заместить контейнер {{{ArraySeq}}} контейнером {{{LinkSeq}}} в случае, если вы используете только методы {{{View}}}.
 
== В заключении ==

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