bool Equals(object х, object у)
int GetHashCode(object obj)
Метод Equals() возвращает логическое значение true, если значения объектов х
и у равны. А метод GetHashCode() возвращает хеш-код для объекта obj.
Интерфейсы IStructuralComparable и IStructuralEquatable
Оба интерфейса IStructuralComparable и IStructuralEquatable добавлены в
версию 4.0 среды .NET Framework. В интерфейсе IStructuralComparable определя
ется метод CompareTo(), который задает способ структурного сравнения двух объектов
для целей сортировки. (Иными словами, Метод CompareTo() сравнивает содержимое
объектов, а не ссылки на них.) Ниже приведена форма объявления данного метода.
int CompareTo(object other, IComparer comparer)
Он должен возвращать -1, если вызывающий объект предшествует другому объекту
other; 1, если вызывающий объект следует после объекта other; и наконец, 0, если
значения обоих объектов одинаковы для целей сортировки. А само сравнение обеспе
чивает объект, передаваемый через параметр comparer.
Интерфейс IStructuralEquatable служит для выяснения структурного равен
ства путем сравнения содержимого двух объектов. В этом интерфейсе определены сле
дующие методы.
bool Equals(object other, IEqualityComparer comparer)
int GetHashCode(IEqualityComparer comparer)
Метод Equals() должен возвращать логическое значение true, если вызывающий
объект и другой объект other равны. А метод GetHashCode() должен возвращать
хеш-код для вызывающего объекта. Результаты, возвращаемые обоими методами,
должны быть совместимы. Само сравнение обеспечивает объект, передаваемый через
параметр comparer.
Структура DictionaryEntry
В пространстве имен System.Collections определена структура DictionaryEntry.
Необобщенные коллекции пар "ключ-значение" сохраняют эти пары в объекте типа
DictionaryEntry. В данной структуре определяются два следующих свойства.
public object Key { get; set; }
public object Value { get; set; }
Эти свойства служат для доступа к ключу или значению, связанному с элементом
коллекции. Объект типа DictionaryEntry может быть сконструирован с помощью
конструктора:
public DictionaryEntry(object key, object value)
где key обозначает ключ, a value — значение.
Классы необобщенных коллекций
А теперь, когда представлены интерфейсы необобщенных коллекций, можно пе
рейти к рассмотрению стандартных классов, в которых они реализуются. Ниже при
ведены классы необобщенных коллекций, за исключением коллекции типа BitArray,
рассматриваемой далее в этой главе.
Класс Описание
ArrayList Определяет динамический массив, т.е. такой массив, который может при
необходимости увеличивать свой размер
Hashtable Определяет хеш-таблицу для пар “ключ-значение”
Queue Определяет очередь, или список, действующий по принципу “первым при
шел — первым обслужен”
SortedList Определяет отсортированный список пар “ключ-значение”
Stack Определяет стек, или список, действующий по принципу "первым пришел —
последним обслужен”
Каждый из этих классов коллекций подробно рассматривается и демонстрируется
далее на конкретных примерах.
Класс ArrayList
В классе ArrayList поддерживаются динамические массивы, расширяющиеся и
сокращающиеся по мере необходимости. В языке C# стандартные массивы имеют фик
сированную длину, которая не может изменяться во время выполнения программы.
Это означает, что количество элементов в массиве нужно знать заранее. Но иногда тре
буемая конкретная длина массива остается неизвестной до самого момента выполне
ния программы. Именно для таких ситуаций и предназначен класс ArrayList. В клас
се ArrayList определяется массив переменной длины, который состоит из ссылок на
объекты и может динамически увеличивать и уменьшать свой размер. Массив типа
ArrayList создается с первоначальным размером. Если этот размер превышается, то
массив автоматически расширяется. А при удалении объектов из такого массива он
автоматически сокращается. Коллекции класса ArrayList широко применяются в
практике программирования на С#. Именно поэтому они рассматриваются здесь под
робно. Но многие способы применения коллекций класса ArrayList распространя
ются и на другие коллекции, в том числе и на обобщенные.
В классе ArrayList реализуются интерфейсы ICollection, IList, IEnumerable
и ICloneable. Ниже приведены конструкторы класса ArrayList.
public ArrayList()
public ArrayList(ICollection c)
public ArrayList(int capacity)
Первый конструктор создает пустую коллекцию класса ArrayList с нулевой перво
начальной емкостью. Второй конструктор создает коллекцию типа ArrayList с коли
чеством инициализируемых элементов, которое определяется параметром с и равно
первоначальной емкости массива. Третий конструктор создает коллекцию, имеющую
указанную первоначальную емкость, определяемую параметром сараcity. В данном
случае емкость обозначает размер базового массива, используемого для хранения эле
ментов коллекции. Емкость коллекции типа ArrayList может увеличиваться автома
тически по мере добавления в нее элементов.
В классе ArrayList определяется ряд собственных методов, помимо тех, что уже
объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто
используемых методов класса ArrayList перечислены в табл. 25.4. Коллекцию класса
ArrayList можно отсортировать, вызвав метод Sort(). В этом случае поиск в отсо
ртированной коллекции с помощью метода BinarySearch() становится еще более
эффективным. Содержимое коллекции типа ArrayList можно также обратить, вы
звав метод Reverse().
Таблица 25.4. Наиболее часто используемые методы, определенные в классе ArrayList
Метод Описание
public virtual void
AddRange(Icollection с)
public virtual int
BinarySearch(object
value)
Добавляет элементы из коллекции с в конец вызываю
щей коллекции типа ArrayList
Выполняет поиск в вызывающей коллекции значения
value. Возвращает индекс найденного элемента. Если
искомое значение не найдено, возвращает отрицатель
ное значение. Вызывающий список должен быть отсо
ртирован
Продолжение табл. 25.4
Метод Описание
public virtual int
BinarySearch(object
value, Icomparer
comparer)
Выполняет поиск в вызывающей коллекции значения
value, используя для сравнения способ, определяемый
параметром comparer. Возвращает индекс совпавше
го элемента. Если искомое значение не найдено, воз
вращает отрицательное значение. Вызывающий список
должен быть отсортирован
public virtual int
BinarySearch(int index,
int count, object value,
IComparer comparer)
Выполняет поиск в вызывающей коллекции значения
value, используя для сравнения способ, определяемый
параметром comparer. Поиск начинается с элемента,
указываемого по индексу index, и включает количество
элементов, определяемых параметром count. Метод воз
вращает индекс совпавшего элемента. Если искомое зна
чение не найдено, метод возвращает отрицательное зна
чение. Вызывающий список должен быть отсортирован
public virtual void
СоруТо(Array array)
Копирует содержимое вызывающей коллекции в мас
сив array, который должен быть одномерным и совме
стимым по типу с элементами коллекции
public virtual void
СоруТо(Array array, int
arrayIndex)
Копирует содержимое вызывающей коллекции в массив
array, начиная с элемента, указываемого по индексу
arrayIndex. Целевой массив должен быть одномер
ным и совместимым по типу с элементами коллекции
public virtual void
CopyTo(int index, Array
array, int arrayIndex,
int count)
Копирует часть вызывающей коллекции, начиная с эле
мента, указываемого по индексу index, и включая ко
личество элементов, определяемых параметром count,
в массив array, начиная с элемента, указываемого по
индексу arrayIndex. Целевой массив должен быть одно
мерным и совместимым по типу с элементами коллекции
public static ArrayList
FixedSize(ArrayList list)
public virtual ArrayList
GetRange(int index, int
count)
Заключает коллекцию list в оболочку типа ArrayList
с фиксированным размером и возвращает результат
Возвращает часть вызывающей коллекции типа
ArrayList. Часть возвращаемой коллекции начинает
ся с элемента, указываемого по индексу index, и вклю
чает количество элементов, определяемое параметром
count. Возвращаемый объект ссылается на те же эле
менты, что и вызывающий объект
public virtual int
IndexOf(object value)
Возвращает индекс первого вхождения объекта value
в вызывающей коллекции. Если искомый объект не об
наружен, возвращает значение -1
public virtual void
InsertRange(int index,
ICollection c)
Вставляет элементы коллекции с в вызывающую кол
лекцию, начиная с элемента, указываемого по индексу
index
public virtual int
LastlndexOf(object value)
Возвращает индекс последнего вхождения объекта
value в вызывающей коллекции. Если искомый объект
не обнаружен, метод возвращает значение -1
Окончание табл. 25.4
В классе ArrayList поддерживается также ряд методов, оперирующих элемента
ми коллекции в заданных пределах. Так, в одну коллекцию типа ArrayList можно
вставить другую коллекцию, вызвав метод InsertRange(). Для удаления из коллек
ции элементов в заданных пределах достаточно вызвать метод RemoveRange(). А для
Метод Описание
public static ArrayList
Readonly(ArrayList list)
Заключает коллекцию list в оболочку типа
ArrayList, доступную только для чтения, и возвра
щает результат
public virtual void
RemoveRange(int index,
int count)
Удаляет часть вызывающей коллекции, начиная с эле
мента, указываемого по индексу index, и включая
количество элементов, определяемое параметром
count
public virtual void
Reverse()
Располагает элементы вызывающей коллекции в обрат
ном порядке
public virtual void
Reverse(int index, int
count)
Располагает в обратном порядке часть вызывающей
коллекции, начиная с элемента, указываемого по индек
су index, и включая количество элементов, определяе
мое параметром count
public virtual void
SetRange(int index,
ICollection c)
Заменяет часть вызывающей коллекции, начиная с эле
мента, указываемого по индексу index, элементами
коллекции с
public virtual void
Sort()
Сортирует вызывающую коллекцию по нарастающей
public virtual void
Sort(Icomparer comparer)
Сортирует вызывающую коллекцию, используя для срав
нения способ, определяемый параметром comparer.
Если параметр comparer имеет пустое значение, то
для сравнения используется способ, выбираемый по
умолчанию
public virtual void
Sort(int index, int
count, Icomparer
comparer)
Сортирует вызывающую коллекцию, используя для срав
нения способ, определяемый параметром comparer.
Сортировка начинается с элемента, указываемого по
индексу index, и включает количество элементов,
определяемых параметром count. Если параметр
comparer имеет пустое значение, то для сравнения ис
пользуется способ, выбираемый по умолчанию
public static ArrayList
Synchronized(ArrayList
list)
Возвращает синхронизированный вариант коллекции
типа ArrayList, передаваемой в качестве параметра
list
public virtual object[]
ToArray()
Возвращает массив, содержащий копии элементов вы
зывающего объекта
public virtual Array
ToArray(Type type)
Возвращает массив, содержащий копии элементов вы
зывающего объекта. Тип элементов этого массива опре
деляется параметром type
public virtual void
TrimToSize()
Устанавливает значение свойства Capacity равным
значению свойства Count
перезаписи элементов коллекции типа ArrayList в заданных пределах элементами
из другой коллекции служит метод SetRange(). И наконец, элементы коллекции
можно сортировать или искать в заданных пределах, а не во всей коллекции.
По умолчанию коллекция типа ArrayList не синхронизирована. Для получения
синхронизированной оболочки, в которую заключается коллекция, вызывается метод
Synchronized().
В классе ArrayList имеется также приведенное ниже свойство Capacity, помимо
свойств, определенных в интерфейсах, которые в нем реализуются.
public virtual int Capacity { get; set; }
Свойство Capacity позволяет получать и устанавливать емкость вызывающей кол
лекции типа ArrayList. Емкость обозначает количество элементов, которые может
содержать коллекция типа ArrayList до ее вынужденного расширения. Как упоми
налось выше, коллекция типа ArrayList расширяется автоматически, и поэтому за
давать ее емкость вручную необязательно. Но из соображений эффективности это ино
гда можно сделать, если количество элементов коллекции известно заранее. Благодаря
этому исключаются издержки на выделение дополнительной памяти.
С другой стороны, если требуется сократить размер базового массива коллекции
типа ArrayList, то для этой цели достаточно установить меньшее значение свойства
Capacity. Но это значение не должно быть меньше значения свойства Count. Напом
ним, что свойство Count определено в интерфейсе ICollection и содержит количе
ство объектов, хранящихся в коллекции на данный момент. Всякая попытка установить
значение свойства Capacity меньше значения свойства Count приводит к генериро
ванию исключения ArgumentOutOfRangeException. Поэтому для получения такого
количества элементов коллекции типа ArrayList, которое содержится в ней на дан
ный момент, следует установить значение свойства Capacity равным значению свой
ства Count. Для этой цели можно также вызвать метод TrimToSize().
В приведенном ниже примере программы демонстрируется применение класса
ArrayList. В ней сначала создается коллекция типа ArrayList, а затем в эту коллек
цию вводятся символы, после чего содержимое коллекции отображается. Некоторые
элементы затем удаляются из коллекции, и ее содержимое отображается вновь. После
этого в коллекцию вводятся дополнительные элементы, что вынуждает увеличить ее
емкость. И наконец, содержимое элементов коллекции изменяется.
// Продемонстрировать применение класса ArrayList.
using System;
using System.Collections;
class ArrayListDemo {
static void Main() {
// Создать коллекцию в виде динамического массива.
ArrayList al = new ArrayList();
Console.WriteLine("Исходное количество элементов: " + al.Count);
Console.WriteLine();
Console.WriteLine("Добавить 6 элементов");
// Добавить элементы в динамический массив.
al.Add('С');
al.Add('A');
al.Add('E');
al.Add('В');
al.Add('D');
al.Add('F');
Console.WriteLine("Количество элементов: " + al.Count);
// Отобразить содержимое динамического массива,
// используя индексирование массива.
Console.Write("Текущее содержимое: ");
for(int i=0; i < al.Count; i++)
Console.Write(al[i] + " ");
Console.WriteLine("\n");
Console.WriteLine("Удалить 2 элемента");
// Удалить элементы из динамического массива.
al.Remove('F');
al.Remove('A');
Console.WriteLine("Количество элементов: " + al.Count);
// Отобразить содержимое динамического массива, используя цикл foreach.
Console.Write("Содержимое: ");
foreach(char с in al)
Console.Write(с + " ");
Console.WriteLine("\n");
Console.WriteLine("Добавить еще 20 элементов");
// Добавить количество элементов, достаточное для
// принудительного расширения массива.
for (int i=0; i < 20; i++)
al.Add((char)('a' + i));
Console.WriteLine("Текущая емкость: " + al.Capacity);
Console.WriteLine("Количество элементов после добавления 20 новых: " +
al.Count);
Console.Write("Содержимое: ");
foreach(char с in al)
Console.Write(с + " ");
Console.WriteLine("\n");
// Изменить содержимое динамического массива,
// используя индексирование массива.
Console.WriteLine("Изменить три первых элемента");
al[0] = 'X';
al[1] = 'Y';
al[2] = 'Z';
Console.Write("Содержимое: ");
foreach(char с in al)
Console.Write(c + "
Console.WriteLine();
}
}
Вот к какому результату приводит выполнение этой программы.
Исходное количество элементов: 0
Добавить 6 элементов
Количество элементов: 6
Текущее содержимое: С А Е В D F
Удалить 2 элемента
Количество элементов: 4
Содержимое: С Е В D
Добавить еще 20 элементов
Текущая емкость: 32
Количество элементов после добавления 20 новых: 24
Содержимое: C E B D a b c d e f g h i j k l m n o p q r s t
Изменить три первых элемента
Содержимое: X Y Z D a b c d e f g h i j k l m n o p q r s t
Сортировка и поиск в коллекции типа ArrayList
Коллекцию типа ArrayList можно отсортировать с помощью метода Sort().
В этом случае поиск в отсортированной коллекции с помощью метода BinarySearch()
становится еще более эффективным. Применение обоих методов демонстрируется
в приведенном ниже примере программы.
// Отсортировать коллекцию типа ArrayList и осуществить в ней поиск.
using System;
using System.Collections;
class SortSearchDemo {
static void Main() {
// Создать коллекцию в виде динамического массива.
ArrayList al = new ArrayList();
// Добавить элементы в динамический массив.
al.Add(55);
al.Add(43);
al.Add(-4);
al.Add(88);
al.Add(3);
al.Add(19);
Console.Write("Исходное содержимое: ");
foreach(int i in al)
Console.Write(i + " ");
Console.WriteLine("\n");
// Отсортировать динамический массив.
al.Sort();
// Отобразить содержимое динамического массива, используя цикл foreach.
Console.Write("Содержимое после сортировки: ");
foreach(int i in al)
Console.Write(i + " ");
Console.WriteLine("\n");
Console.WriteLine("Индекс элемента 43: " +
al.BinarySearch(43));
}
}
Ниже приведен результат выполнения этой программы.
Исходное содержимое: 55 43 -4 88 3 19
Содержимое после сортировки: -4 3 19 43 55 88
Индекс элемента 43: 3
В одной и той же коллекции типа ArrayList могут храниться объекты любого
типа. Тем не менее во время сортировки и поиска в ней эти объекты приходится срав
нивать. Так, если бы список объектов в приведенном выше примере программы со
держал символьную строку, то их сравнение привело бы к исключительной ситуации.
Впрочем, для сравнения символьных строк и целых чисел можно создать специальные
методы. О таких методах сравнения речь пойдет далее в этой главе.
Получение массива из коллекции типа ArrayList
В работе с коллекцией типа ArrayList иногда требуется получить из ее содер
жимого обычный массив. Этой цели служит метод ТоАrrау(). Для преобразования
коллекции в массив имеется несколько причин. Две из них таковы: потребность в уско
рении обработки при выполнении некоторых операций и необходимость передавать
массив методу, который не перегружается, чтобы принять коллекцию. Но независимо
от конкретной причины коллекция типа ArrayList преобразуется в обычный массив
довольно просто, как показано в приведенном ниже примере программы.
// Преобразовать коллекцию типа ArrayList в обычный массив.
using System;
using System.Collections;
class ArrayListToArray {
static void Main() {
ArrayList al = new ArrayList();
// Добавить элементы в динамический массив.
al.Add(1);
al.Add(2);
al.Add(3);
al.Add(4);
Console.Write("Содержимое: ");
foreach(int i in al)
Console.Write(i + " ");
Console.WriteLine();
// Получить массив.
int[] ia = (int[]) al.ToArray(typeof(int));
int sum = 0;
// Просуммировать элементы массива.
for(int i=0; i ");
int a = (int) st.Pop();
Метод Описание
public virtual void Clear() Устанавливает свойство Count равным нулю, очи
щая, по существу, стек
public virtual bool
Contains (object obj)
Возвращает логическое значение true, если объект
obj содержится в вызывающем стеке, а иначе —
логическое значение false
public virtual object Peek() Возвращает элемент, находящийся на вершине сте
ка, но не удаляет его
public virtual object Pop() Возвращает элемент, находящийся на вершине сте
ка, удаляя его по ходу дела
public virtual void
Push (object obj)
Помещает объект obj в стек
public static Stack
Synchronized(Stack stack)
Возвращает синхронизированный вариант коллек
ции типа Stack, передаваемой в качестве параме
тра stack
public virtual object[]
ToArray()
Возвращает массив, содержащий копии элементов
вызывающего стека
Console.WriteLine(a);
Console.Write("Содержимое стека: ");
foreach(int i in st)
Console.Write(i + " ");
Console.WriteLine();
}
static void Main() {
Stack st = new Stack ();
foreach(int i in st)
Console.Write(i + " ");
Console.WriteLine();
ShowPush(st, 22);
ShowPush(st, 65);
ShowPush(st, 91);
ShowPop(st);
ShowPop(st);
ShowPop(st);
try {
ShowPop(st);
} catch (InvalidOperationException) {
Console.WriteLine("Стек пуст.");
}
}
}
Ниже приведен результат выполнения этой программы. Обратите внимание на то,
как обрабатывается исключение InvalidOperationException, генерируемое при
попытке извлечь элемент из пустого стека.
Поместить в стек: Push (22)
Содержимое стека: 22
Поместить в стек: Push(65)
Содержимое стека: 65 22
Поместить в стек: Push (91)
Содержимое стека: 91 65 22
Извлечь из стека: Pop -> 91
Содержимое стека: 65 22
Извлечь из стека: Pop -> 65
Содержимое стека: 22
Извлечь из стека: Pop -> 22
Содержимое стека:
Извлечь из стека: Pop -> Стек пуст.
Класс Queue
Еще одной распространенной структурой данных является очередь, действующая
по принципу: первым пришел — первым обслужен. Это означает, что первым из оче
реди извлекается элемент, помещенный в нее первым. Очереди часто встречаются в
реальной жизни. Многим из нас нередко приходилось стоять в очередях к кассе в бан
ке, магазине или столовой. В программировании очереди применяются для хранения
таких элементов, как процессы, выполняющиеся в данный момент в системе, списки
приостановленных транзакций в базе данных или пакеты данных, полученные по Ин
тернету. Кроме того, очереди нередко применяются в области имитационного моде
лирования.
Класс коллекции, поддерживающий очередь, носит название Queue. В нем реали
зуются интерфейсы ICollection, IEnumerable и ICloneable. Этот класс создает
динамическую коллекцию, которая расширяется, если в ней необходимо хранить вво
димые элементы. Так, если в очереди требуется свободное место, ее размер увеличива
ется на коэффициент роста, который по умолчанию равен 2,0.
В классе Queue определяются приведенные ниже конструкторы.
public Queue()
public Queue (int capacity)
public Queue (int capacity, float growFactor)
public Queue (ICollection col)
В первой форме конструктора создается пустая очередь с выбираемыми по умол
чанию емкостью и коэффициентом роста 2,0. Во второй форме создается пустая оче
редь, пе