Коллекции и структуры данных

Лабораторная работа №16

Реализация механизма создания коллекции и применение коллекций в программах

Цель работы:

Научиться разрабатывать программы, которые реализуют механизм создания коллекции, и применять коллекции в программах с использованием среды Visual Studio.Net.

Теоретические сведения

Многие алгоритмы не зависят от типов данных, с которыми они работают. Про­стейшими примерами могут служить сортировка и поиск. Возможность отделить алгоритмы от типов данных предоставляют классы-прототипы (generics) — классы, имеющие в качестве параметров типы данных. Чаще всего эти классы применяются для хранения данных, то есть в качестве контейнерных классов, или коллекций.

Во вторую версию библиотеки .NET добавлены параметризованные коллекции для представления основных структур данных, применяющихся при создании программ, — стека, очереди, списка, словаря и т. д. Эти коллекции, расположен­ные в пространстве имен System.Collections.Generic, дублируют аналогичные коллекции пространства имен System.Collections, рассмотренные в разделе «Про­странство имен System.CoIlections». В табл. 1 приводится соответствие между обычными и параметризованными коллекциями библиотеки .NET (параметры, определяющие типы данных, хранимых в коллекции, указаны в угловых скобках).

Таблица 1. Параметризованные коллекции библиотеки .NET версии 2.0

У коллекций, описанных в библиотеке .NET версий 1.0 и 1.1, есть два основных недостатка, обусловленных тем, что в них хранятся ссылки на тип object:

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

• при хранении в коллекции элементов значимых типов выполняется большой объем действий по упаковке и распаковке элементов, что в значительной сте­пени снижает эффективность работы.

Параметром класса-прототипа является тип данных, с которым он работает. Это избавляет от перечисленных недостатков. В качестве примера рассмотрим при­менение универсального «двойника» класса ArrayLi st — класса List — для хранения коллекции объектов классов Monster и Daemon.

Листинг 1 . Использование универсальной коллекции List

В листинге 1 две коллекции. Первая (stado) содержит элементы пользователь­ских классов, которые находятся в библиотеке MonsterL.ib.clll. В коллекции, для которой объявлен тип элементов Monster, благода­ря полиморфизму можно хранить элементы любого производного класса, но не элементы других типов. Казалось бы, по сравнению с обычными коллекциями это ограничение, а не универсальность, однако на практике коллекции, в которых действительно требует­ся хранить значения различных, не связанных межу собой типов, почти не ис­пользуются. Достоинством же такого ограничения является то, что компилятор может выполнить контроль типов во время компиляции, а не выполнения про­ граммы, что повышает ее надежность и упрощает поиск ошибок. Коллекция 1 int состоит из целых чисел, причем для работы с ними не требуются ни операции упаковки и распаковки, ни явные преобразования типа при получении элемента из коллекции, как это было в обычных коллекциях. Классы-прототипы называют также родовыми или шаблонными, поскольку они представляют собой образцы, по которым во время выполнения программы строятся конкретные классы. При этом сведения о классах, которые являются параметрами классов-прототипов, извлекаются из метаданных.

Классы коллекций в C#

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

Приложения, предназначенные для платформы .NET Framework версии 2.0 или более поздней, должны использовать универсальные классы коллекций в пространстве имен System.Collections.Generic, обеспечивающие повышенную безопасность типа и эффективность по сравнению с нестандартными аналогами.

Классы коллекций имеют следующие свойства

• Классы коллекций заданы как часть пространства имен System.Collections илиSystem.Collections.Generic.
• Большинство классов коллекций являются производными от интерфейсов ICollection, IComparer, IEnumerable, IList, IDictionary иIDictionaryEnumerator и их универсальных эквивалентов.
• Универсальные классы коллекций обеспечивают повышенную безопасность типа, а в некоторых случаях позволяют повысить производительность, особенно когда они хранят типы значений.

Коллекции и структуры данных

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

Для управления коллекцией используйте классы из пространств имен System.Collections,System.Collections.Generic и System.Collections.Concurrent для добавления, удаления и изменения либо отдельных элементов коллекции, либо диапазона элементов. Коллекцию можно скопировать целиком в другую коллекцию.

Некоторые классы System.Collections предоставляют возможность сортировки, и большинство из них индексированы. Управление памятью осуществляется автоматически, а вместимость коллекции увеличивается по мере необходимости. Синхронизация обеспечивает потокобезопасность при доступе к членам коллекции. Любой класс System.Collections может создать свой собственный нумератор, облегчающий выполнение итерации элементов.

Определение коллекций

Коллекция представляет собой набор объектов схожих типов, сгруппированных вместе.

Объекты любого типа могут быть сгруппированы в одну коллекцию типа Object, чтобы воспользоваться преимуществами конструкций, свойственных языку. Например, оператор foreach языка C# предполагает, что все объекты коллекции имеют один и тот же тип.

Однако в коллекции типа Object происходит дополнительная индивидуальная обработка элементов, к примеру, упаковка и распаковка или преобразования, что влияет на производительность коллекции. Упаковка и распаковка обычно происходят при сохранении или извлечении типа значений из коллекции типа Object.

Универсальные коллекции, такие как List<T> и строго типизированные неуниверсальные коллекции, такие как StringCollection, позволяют избежать проблем с производительностью, если тип элемента является типом, для которого предназначена коллекция (например, сохранение или извлечение строк из StringCollection). Кроме того, при добавлении элемента в строго типизированную коллекцию выполняется автоматическая проверка типа такого элемента. По этим причинам настоятельно рекомендуется использовать универсальные коллекции классов всегда, когда это возможно.

Рассмотрим пример работы с коллекцией.

Класс ArrayList

Реализует интерфейс IList с помощью массива с динамическим увеличением размера до нужного значения.

Пространство имен:System.Collections

Сборка: mscorlib (в mscorlib.dll)

Сортировка списка ArrayList не гарантируется. Необходимо отсортировать список ArrayList перед выполнением операций (таких, как BinarySearch), для которых требуется отсортированный список ArrayList.

Емкость коллекции ArrayList — это количество элементов, которое может вместить коллекция ArrayList. Когда в коллекцию ArrayList добавляются элементы, ее емкость автоматически увеличивается должным образом посредством перераспределения. Емкость может быть уменьшена посредством вызова метода TrimToSize или с помощью явного задания свойства Capacity.

Доступ к элементам этой коллекции осуществляется с помощью целочисленного индекса. Индексы в этой коллекции начинаются с нуля.

Коллекция ArrayList принимает null т.е. пустая ссылка как допустимое значение и разрешает дублировать элементы.

Использование многомерных массивов в качестве элементов коллекции ArrayList не поддерживается.

using System;

using System.Collections;

public class SampleArrayList {

public static void Main() {

// Создает и инициализирует новый ArrayList.

ArrayList myAL = new ArrayList();

myAL.Add("Hello");

myAL.Add("World");

myAL.Add("!");

// Выводит свойства и значения элементов ArrayList.

Console.WriteLine( "myAL" );

Console.WriteLine( " Count: {0}", myAL.Count );

Console.WriteLine( " Capacity: {0}", myAL.Capacity );

Console.Write( " Values:" );

PrintValues( myAL );

}

public static void PrintValues( IEnumerable myList ) {

foreach ( Object obj in myList )

Console.Write( " {0}", obj );

Console.WriteLine();

}

}