28.C#. Коллекции.
Библиотека коллекций .NET размещается в пространстве имен System.Collections.Generic и содержит ряд обобщенных (generic) интерфейсов и классов (рис.). Интерфейс IEnumerable представляет коллекцию, позволяющую выполнять перебор своих элементов.
Интерфейс ICollection — это коллекция общего вида. Объявляет операции добавления, удаления элементов, проверки на принадлежность элементов коллекции.
Интерфейс IList представляет собой коллекцию-список, т. е. коллекцию элементов, упорядоченных в соответствии с их целочисленными индексами. Аналогичен интерфейсу List в Java Collections Framework.
Интерфейс IDictionary аналогичен интерфейсу Map в Java Collections Framework и представляет собой коллекцию-карту, т. е. коллекцию элементов, каждому из которых поставлен в соответствие некоторый ключ. Классы из библиотеки коллекций BCL являются скорее реализациями тех или иных структур данных, чем реализациями интерфейсов.
Класс List реализует список на основе динамического массива. Данный класс поддерживает порядок элементов на основе их индексов и обладает достаточно развитым интерфейсом.
Класс Dictionary реализует коллекцию-карту (т. е. коллекцию пар «ключ-значение»).
Класс HashSet реализует коллекцию-множество, т. е. коллекцию, которая не может содержать дублирующиеся элементы. Данный класс был добавлен в .NET Framework 3.5.
Классы Queue, Stack и LinkedList представляют структуры данных очередь, стек и двусвязный линейный список соответственно. Классы SortedDictionary и SortedList представляют коллекцию-карту, отсортированную по ключу. Они представляют собой деревья двоичного поиска. Отличия:
• SortedList использует меньше памяти, чем SortedDictionary;
• SortedList медленнее выполняет операции вставки и удаления при работе с
неотсортированными данными (SortedList — O(n), SortedDictionary — O(log n));
• SortedList работает быстрее, если список сразу заполняется на основе отсортированных данных;
• SortedList поддерживает эффективное индексированное извлечение ключей и
значений.
29.Java. Коллекции.
Коллекция — это объект, являющийся контейнером для других объектов. Библиотеки классов Java и .NET содержат классы и интерфейсы, обеспечивающие работу с коллекциями.
Библиотека коллекций в Java расположена в пакете java.util и представляет собой набор
интерфейсов и реализаций этих интерфейсов (рис).
Все интерфейсы отражают следующие аспекты коллекций:
• может ли изменяться размер;
• имеет ли значение порядок элементов;
• уникальность элементов.
С коллекциями можно выполнять следующие основные операции:
• добавлять объекты; удалять объекты;определять, содержится ли объект в коллекции; получать объект из коллекции (не удаляя его); осуществлять итерационный проход по коллекции.
Можно выделить следующие виды коллекций:
• списки — представляют списки элементов (классы, реализующие интерфейс List);
• множества — коллекции уникальных элементов (классы, реализующие интерфейс Set);
• карты — коллекции, представляющие отображение «ключ-значение» (классы, реализующие интерфейс Map);
• очереди — коллекции, для которых определен порядок обработки элементов (классы, реализующие интерфейс Queue).
Кроме того, существуют следующие подвиды коллекций:
• неупорядоченные (unordered);
• упорядоченные неотсортированные (ordered unsorted);
• упорядоченные отсортированные (ordered sorted).
Коллекция называется упорядоченной, если она осуществляет итерацию по своим элементам в некотором неслучайном порядке. Упорядоченная коллекция называется отсортированной, если порядок элементов в коллекции определяется свойствами самих элементов. Как правило используется т. н. естественный порядок (natural order). Для строк это — алфавитный порядок, для чисел — расположение по возрастанию и т. п. Для некоторого произвольного класса Foo естественный порядок будет определен, если этот класс реализует интерфейс Comparable (этот интерфейс позволяет определить правила сравнения экземпляров класса друг с другом). Кроме того правила сравнения можно определить, реализуя интерфейс Comparator .
Интерфейс List
Классы, реализующие данный интерфейс, с каждым своим элементом ассоциируют некоторый индекс и определяют ряд операций, основанных на использовании индекса элементов: получение элемента по его индексу (get), получение индекса заданного элемента (indexOf), добавление элемента в указанную позицию (add) и т. п. Коллекции-списки являются упорядоченными по значениям индексов элементов.
Класс ArrayList. Этот класс можно рассматривать как динамический массив. Он обеспечивает быструю итерацию и быстрый доступ к элементам по их индексам (random access). Класс LinkedList реализует двусвязный линейный список. Итерация по данной коллекции может осуществляться медленнее, чем по ArrayList, а вот операции добавления и удаления элементов являются достаточно быстрыми. Данный класс реализует ряд методов для добавления и удаления элементов из начала и из конца списка (этих методов нет в интерфейсе List), что позволяет использовать этот класс как стек или очередь. Начиная с Java 5, класс LinkedList реализует интерфейс Queue. Класс Vector. Аналогичен классу ArrayList, за исключением того, что методы данного класса являются потокобезопасными. Данный класс присутствует в библиотеке Java с ранних версий и считается устаревшим. Сейчас рекомендуется использовать класс ArrayList, а для обеспечения безопасности в многопоточном приложении можно использовать утилитарные методы класса Collections.
Интерфейс Set
Классы, реализующие данный интерфейс, обеспечивают уникальность элементов в пределах коллекции (для определения, идентичны ли объекты, используется метод equals).
Класс HashSet. Этот класс реализует неупорядоченную коллекцию без дублирующихся элементов. Для повышения производительности класс использует хэш-коды объектов.
Класс LinkedHashSet представляет собой версию HashSet, которая поддерживает порядок элементов: проход по элементам осуществляется в порядке их добавления. Элементы этой коллекции объединены в линейный двусвязный список. Класс TreeSet. Является одной из отсортированных коллекций (другая — TreeMap). Этот класс основан на использовании красно-черных деревьев и обеспечивает проход по
элементам в порядке их возрастания.
Интерфейс Map
Классы, реализующие данный интерфейс, позволяют уникальным объектам-ключам ставить в соответствие объекты-значения. Данная коллекция позволяет осуществлять поиск значения по его ключу, получать коллекцию всех ключей или коллекцию всех значений. Для определения равенства ключей используется метод equal. Класс HashMap. Этот класс реализует неупорядоченную коллекцию-карту. Для размещения ключей в памяти и повышения производительности доступа класс использует хэш-коды объектов. В данной коллекции среди объектов-ключей может содержаться одно значение null, а среди объектов-значений — любое количество значений null. Класс LinkedHashMap поддерживает порядок элементов: проход по элементам осуществляется в порядке их добавления. При добавлении и удалении элементов данная коллекция работает медленнее HashMap, однако, она обеспечивает более быструю итерацию.Класс TreeMap представляет отсортированную (в естественном порядке) коллекцию-карту. Класс Hashtable. Данный класс присутствует в библиотеке с ранних версий и представляет собой потокобезопасную версию класса HashMap. В отличие от HashMap, не позволяет использовать значения null ни в качестве ключей, ни в качестве значений.
Интерфейс Queue
Классы, реализующие данный интерфейс, представляют собой коллекцию элементов, которые должны обрабатываться в некотором порядке (обычно используется правило FIFO – First-In, First-Out). Класс PriorityQueue. В этой очереди обработка элементов осуществляется не в порядке добавления, а в порядке их относительных приоритетов. Приоритет определяется либо естественным порядком элементов, либо объектом Comparator .