ГЛАВА 25. Коллекции, перечислители и итераторы

В этой главе речь пойдет об одной из самых важныхсоставляющих среды .NET Framework: коллекциях. В С# коллекция представляет собой совокупностьобъектов. В среде .NET Framework имеется немало интерфейсов и классов, в которых определяются и реализуютсяразличные типы коллекций. Коллекции упрощают решение многих задач программирования благодаря тому, чтопредлагают готовые решения для создания целого рядатипичных, но порой трудоемких для разработки структурданных. Например, в среду .NET Framework встроены коллекции, предназначенные для поддержки динамическихмассивов, связных списков, стеков, очередей и хеш-таблиц.Коллекции являются современным технологическим средством, заслуживающим пристального внимания всех, ктопрограммирует на С#.Первоначально существовали только классы необобщенных коллекций. Но с внедрением обобщений в версииC# 2.0 среда .NET Framework была дополнена многиминовыми обобщенными классами и интерфейсами. Благодаря введению обобщенных коллекций общее количествоклассов и интерфейсов удвоилось. Вместе с библиотекойраспараллеливания задач (TPL) в версии 4.0 среды .NETFramework появился ряд новых классов коллекций, предназначенных для применения в тех случаях, когда доступ кколлекции осуществляется из нескольких потоков. Нетрудно догадаться, что прикладной интерфейс Collections APIсоставляет значительную часть среды .NET Framework.Кроме того, в настоящей главе рассматриваются два средства, непосредственно связанные с коллекциями: перечислители и итераторы. И те и другие позволяют поочередно обращаться к содержимому класса коллекции в цикле foreach.Краткий обзор коллекций

Главное преимущество коллекций заключается в том, что они стандартизируют обработку групп объектов в программе. Все коллекции разработаны на основе наборачетко определенных интерфейсов. Некоторые встроенные реализации таких интерфейсов, в том числе ArrayList, Hashtable, Stack и Queue, могут применяться в исходном виде и без каких-либо изменений. Имеется также возможность реализоватьсобственную коллекцию, хотя потребность в этом возникает крайне редко.В среде .NET Framework поддерживаются пять типов коллекций: необобщенные,специальные, с поразрядной организацией, обобщенные и параллельные. Необобщенные коллекции реализуют ряд основных структур данных, включая динамический массив, стек, очередь, а также словари, в которых можно хранить пары "ключ-значение".В отношении необобщенных коллекций важно иметь в виду следующее: они оперируют данными типа object.Таким образом, необобщенные коллекции могут служить для хранения данныхлюбого типа, причем в одной коллекции допускается наличие разнотипных данных.Очевидно, что такие коллекции не типизированы, поскольку в них хранятся ссылкина данные типа object. Классы и интерфейсы необобщенных коллекций находятся впространстве имен System.Collections.Специальные коллекции оперируют данными конкретного типа или же делаютэто каким-то особым образом. Например, имеются специальные коллекции для символьных строк, а также специальные коллекции, в которых используется однонаправленный список. Специальные коллекции объявляются в пространстве имен System.Collections.Specialized.В прикладном интерфейсе Collections API определена одна коллекция с поразрядной организацией — это BitArray. Коллекция типа BitArray поддерживает поразрядные операции, т.е. операции над отдельными двоичными разрядами, напримерИ иди исключающее ИЛИ, а следовательно, она существенно отличается своими возможностями от остальных типов коллекций. Коллекция типа BitArray объявляетсяв пространстве имен System.Collections.Обобщенные коллекции обеспечивают обобщенную реализацию нескольких стандартных структур данных, включая связные списки, стеки, очереди и словари. Такиеколлекции являются типизированными в силу их обобщенного характера. Это означает, что в обобщенной коллекции могут храниться только такие элементы данных,которые совместимы по типу с данной коллекцией. Благодаря этому исключаетсяслучайное несовпадение типов. Обобщенные коллекции объявляются в пространствеимен System.Collections.Generic.Параллельные коллекции поддерживают многопоточный доступ к коллекции. Этообобщенные коллекции, определенные в пространстве имен System.Collections.Concurrent.В пространстве имен System.Collections.ObjectModel находится также рядклассов, поддерживающих создание пользователями собственных обобщенных коллекций.Основополагающим для всех коллекций является понятие перечислителя, которыйподдерживается в необобщенных интерфейсах IEnumerator и IEnumerable, а такжев обобщенных интерфейсах IEnumerator и IEnumerable. Перечислитель обеспечивает стандартный способ поочередного доступа к элементам коллекции. Следовательно, он перечисляет содержимое коллекции. В каждой коллекции должна бытьреализована обобщенная или необобщенная форма интерфейса IEnumerable, поэтому элементы любого класса коллекции должны быть доступны посредством методов,определенных в интерфейсе IEnumerator или IEnumerator. Это означает, что,внеся минимальные изменения в код циклического обращения к коллекции одноготипа, его можно использовать для аналогичного обращения к коллекции другого типа.Любопытно, что для поочередного обращения к содержимому коллекции в циклеforeach используется перечислитель.Основополагающим для всех коллекций является понятие перечислителя, которыйподдерживается в необобщенных интерфейсах IEnumerator и IEnumerable, а такжев обобщенных интерфейсах IEnumerator и IEnumerable. Перечислитель обеспечивает стандартный способ поочередного доступа к элементам коллекции. Следовательно, он перечисляет содержимое коллекции. В каждой коллекции должна бытьреализована обобщенная или необобщенная форма интерфейса IEnumerable, поэтому элементы любого класса коллекции должны быть доступны посредством методов,определенных в интерфейсе IEnumerator или IEnumerator. Это означает, что,внеся минимальные изменения в код циклического обращения к коллекции одноготипа, его можно использовать для аналогичного обращения к коллекции другого типа.Любопытно, что для поочередного обращения к содержимому коллекции в циклеforeach используется перечислитель.С перечислителем непосредственно связано другое средство, называемое итератором. Это средство упрощает процесс создания классов коллекций, например специальных, поочередное обращение к которым организуется в цикле foreach. Итераторытакже рассматриваются в этой главе.И последнее замечание: если у вас имеется некоторый опыт программированияна C++, то вам, вероятно, будет полезно знать, что классы коллекций по своей сути подобны классам стандартной библиотеки шаблонов (Standard Template Library — STL),определенной в C++. То, что в программировании на C++ называется контейнером,в программировании на C# называется коллекцией. Это же относится и к Java. Есливы знакомы с библиотекой Collections Framework для Java, то научиться пользоватьсяколлекциями в C# не составит для вас большого труда.В силу характерных отличий каждый из пяти типов коллекций (необобщенных,обобщенных, специальных, с поразрядной организацией и параллельных) будет рассмотрен далее в этой главе отдельно.Необобщенные коллекцииНеобобщенные коллекции вошли в состав среды .NET Framework еще в версии 1.0.Они определяются в пространстве имен System.Collections. Необобщенные коллекции представляют собой структуры данных общего назначения, оперирующие ссылками на объекты. Таким образом, они позволяют манипулировать объектом любого типа,хотя и не типизированным способом. В этом состоит их преимущество и в то же время недостаток. Благодаря тому что необобщенные коллекции оперируют ссылками наобъекты, в них можно хранить разнотипные данные. Это удобно в тех случаях, когда требуется манипулировать совокупностью разнотипных объектов или же когда типы хранящихся в коллекции объектов заранее неизвестны. Но если коллекция предназначаетсядля хранения объекта конкретного типа, то необобщенные коллекции не обеспечиваюттиповую безопасность, которую можно обнаружить в обобщенных коллекциях.Необобщенные коллекции определены в ряде интерфейсов и классов, реализующих эти интерфейсы. Все они рассматриваются далее по порядку.Интерфейсы необобщенных коллекцийВ пространстве имен System.Collections определен целый ряд интерфейсовнеобобщенных коллекций. Начинать рассмотрение необобщенных коллекций следует именно с интерфейсов, поскольку они определяют функциональные возможности,которые являются общими для всех классов необобщенных коллекций. Интерфейсы,служащие опорой для необобщенных коллекций, сведены в табл. 25.1. Каждый из этихинтерфейсов подробно описывается далее.Таблица 25.1. Интерфейсы необобщенных коллекцийИнтерфейс ICollectionИнтерфейс ICollection служит основанием, на котором построены все необобщенные коллекции. В нем объявляются основные методы и свойства для всех необобщенных коллекций. Он также наследует от интерфейса IEnumerable.В интерфейсе ICollection определяются перечисленные ниже свойства.Свойство Count используется чаще всего, поскольку оно содержит количество элементов, хранящихся в коллекции на данный момент. Если значение свойства Countравно нулю, то коллекция считается пустой.В интерфейсе ICollection определяется следующий метод.void СоруТо(Array target, int startIdx)Интерфейс ОписаниеICollection Определяет элементы, которые должны иметь все необобщенные коллекцииIComparer Определяет метод Compare() для сравнения объектов, хранящихся в коллекцииIDictionary Определяет коллекцию, состоящую из пар "ключ-значение"IDictionaryEnumerator Определяет перечислитель для коллекции, реализующей интерфейс IDictionaryIEnumerable Определяет метод GetEnumerator(), предоставляющийперечислитель для любого класса коллекцииIEnumerator Предоставляет методы, позволяющие получать содержимоеколлекции по очередиIEqualityComparer Сравнивает два объекта на предмет равенстваIHashCodeProvider Считается устаревшим. Вместо него следует использовать интерфейс IEqualityComparerIList Определяет коллекцию, доступ к которой можно получить с помощью индексатораIStructuralComparable Определяет метод CompareTo(), применяемый для структурного сравненияIStructuralEquatable Определяет метод Equals(), применяемый для выясненияструктурного, а не ссылочного равенства. Кроме того, определяет метод GetHashCode()Метод СоруТо() копирует содержимое коллекции в массив target, начиная с элемента, указываемого по индексу startIdx. Следовательно, метод СоруТо() обеспечивает в C# переход от коллекции к стандартному массиву.Благодаря тому что интерфейс ICollection наследует от интерфейса IEnumerable,в его состав входит также единственный метод, определенный в интерфейсеIEnumerable. Это метод GetEnumerator(), объявляемый следующим образом.IEnumerator GetEnumerator()Он возвращает перечислитель для коллекции.Вследствие того же наследования от интерфейса IEnumerable в интерфейсе ICollection определяются также четыре следующих метода расширения:AsParallel(), AsQueryable(), Cast() и OfType(). В частности, метод AsParallel()объявляется в классе System.Linq.ParallelEnumerable, метод AsQueryable() —в классе System.Linq.Queryable, а методы Cast() и OfType() — в классе System.Linq.Enumerable. Эти методы предназначены главным образом для поддержки LINQ,хотя их можно применять и в других целях.Интерфейс IListВ интерфейсе IList объявляется такое поведение необобщенной коллекции, которое позволяет осуществлять доступ к ее элементам по индексу с отсчетом от нуля.Этот интерфейс наследует от интерфейсов ICollection и IEnumerable. Помимометодов, определенных в этих интерфейсах, в интерфейсе IList определяется рядсобственных методов. Все эти методы сведены в табл. 25.2. В некоторых из них предусматривается модификация коллекции. Если же коллекция доступна только для чтения или имеет фиксированный размер, то в этих методах генерируется исключениеNotSupportedException.Таблица 25.2. Методы, определенные в интерфейсе IListСвойство Назначениеint Count { get; } Содержит количество элементов в коллекции на данный моментbool IsSynchronized { get; } Принимает логическое значение true, если коллекция синхронизирована, а иначе — логическое значение false. По умолчанию коллекции не синхронизированы. Но для большинства коллекций можнополучить синхронизированный вариантobject SyncRoot { get; } Содержит объект, для которого коллекция можетбыть синхронизированаМетод Описаниеint Add(object value) Добавляет объект value в вызывающую коллекцию.Возвращает индекс, по которому этот объект сохраняетсяvoid Clear() Удаляет все элементы из вызывающей коллекцииbool Contains (object value) Возвращает логическое значение true, если вызывающая коллекция содержит объект value, а иначе — логическое значение falseОкончание табл. 25.2Объекты добавляются в коллекцию типа IList вызовом метода Add(). Обратите внимание на то, что метод Add() принимает аргумент типа object. А посколькуobject является базовым классом для всех типов, то в необобщенной коллекции может быть сохранен объект любого типа, включая и типы значений, в силу автоматической упаковки и распаковки.Для удаления элемента из коллекции служат методы Remove() и RemoveAt(). В частности, метод Remove() удаляет указанный объект, а метод RemoveAt() удаляет объектпо указанному индексу. И для опорожнения коллекции вызывается метод Clear().Для того чтобы выяснить, содержится ли в коллекции конкретный объект, вызывается метод Contains(). Для получения индекса объекта вызывается метод IndexOf(),а для вставки элемента в коллекцию по указанному индексу — метод Insert().В интерфейсе IList определяются следующие свойства.bool IsFixedSize { get; }bool IsReadOnly { get; }Если коллекция имеет фиксированный размер, то свойство IsFixedSize содержитлогическое значение true. Это означает, что в такую коллекцию нельзя ни вставлятьэлементы, ни удалять их из нее. Если же коллекция доступна только для чтения, тосвойство IsReadOnly содержит логическое значение true. Это означает, что содержимое такой коллекции не подлежит изменению.Кроме того, в интерфейсе IList определяется следующий индексатор.object this[int index] { get; set; }Этот индексатор служит для получения и установки значения элемента коллекции.Но его нельзя использовать для добавления в коллекцию нового элемента. С этой целью обычно вызывается метод Add(). Как только элемент будет добавлен в коллекцию,он станет доступным посредством индексатора.Метод Описаниеint IndexOf(object value) Возвращает индекс объекта value, если этот объектсодержится в вызывающей коллекции. Если жеобъект value не обнаружен, то метод возвращаетзначение -1void Insert(int index,object value)Вставляет в вызывающую коллекцию объект valueпо индексу index. Элементы, находившиеся до этого по индексу index и дальше, смещаются вперед,чтобы освободить место для вставляемого объектаvaluevoid Remove(object value) Удаляет первое вхождение объекта value в вызывающей коллекции. Элементы, находившиеся до этогоза удаленным элементом, смещаются назад, чтобыустранить образовавшийся “пробел"void RemoveAt(int index) Удаляет из вызывающей коллекции объект, расположенный по указанному индексу index. Элементы,находившиеся до этого за удаленным элементом,смещаются назад, чтобы устранить образовавшийся“пробел”Интерфейс IDictionaryВ интерфейсе IDictionary определяется такое поведение необобщенной коллекции, которое позволяет преобразовать уникальные ключи в соответствующие значения. Ключ представляет собой объект, с помощью которого значение извлекаетсявпоследствии. Следовательно, в коллекции, реализующей интерфейс IDictionary,хранятся пары "ключ-значение". Как только подобная пара будет сохранена, ее можно извлечь с помощью ключа. Интерфейс IDictionary наследует от интерфейсовICollection и IEnumerable. Методы, объявленные в интерфейсе IDictionary, сведены в табл. 25.3. Некоторые из них генерируют исключение ArgumentNullExceptionпри попытке указать пустой ключ, поскольку пустые ключи не допускаются.Таблица 25.3. Методы, определенные в интерфейсе IDictionaryДля добавления пары "ключ-значение" в коллекцию типа IDictionary служитметод Add(). Обратите внимание на то, что ключ и его значение указываются отдельно. А для удаления элемента из коллекции следует указать ключ этого объекта привызове метода Remove(). И для опорожнения коллекции вызывается метод Clear().Для того чтобы выяснить, содержит ли коллекция конкретный объект, вызывается метод Contains() с указанным ключом искомого элемента. С помощью метода GetEnumerator() получается перечислитель, совместимый с коллекцией типаIDictionary. Этот перечислитель оперирует парами "ключ-значение".В интерфейсе IDictionary определяются перечисленные ниже свойства.Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступныв отдельных списках с помощью свойств Keys и Values.Кроме того, в интерфейсе IDictionary определяется следующий индексатор.object this[object key] { get; set; }Метод Описаниеvoid Add(object key,object value)void Clear()Добавляет в вызывающую коллекцию пару "ключ-значение”, определяемую параметрами key и valueУдаляет все пары "ключ-значение" из вызывающейколлекцииbool Contains(object key) Возвращает логическое значение true, если вызывающая коллекция содержит объект key в качестве ключа,в противном случае — логическое значение falseIDictionaryEnumeratorGetEnumerator()Возвращает перечислитель для вызывающей коллекцииvoid Remove(object key) Удаляет из коллекции элемент, ключ которого равен значению параметра keyСвойство Назначениеbool IsFixedSize { get; } Принимает логическое значение true, если словарьимеет фиксированный размерbool IsReadOnly { get; } Принимает логическое значение true, если словарь доступен только для чтенияICollection Keys { get; } Получает коллекцию ключейICollection Values { get; } Получает коллекцию значенийЭтот индексатор служит для получения и установки значения элемента коллекции,а также для добавления в коллекцию нового элемента. Но в качестве индекса в данномслучае служит ключ элемента, а не собственно индекс.Интерфейсы IEnumerable, IEnumerator и IDictionaryEnumeratorИнтерфейс IEnumerable является необобщенным, и поэтому он должен бытьреализован в классе для поддержки перечислителей. Как пояснялось выше, интерфейс IEnumerable реализуется во всех классах необобщенных коллекций, поскольку он наследуется интерфейсом ICollection. Ниже приведен единственный методGetEnumerator(), определяемый в интерфейсе IEnumerable.IEnumerator GetEnumerator()Он возвращает коллекцию. Благодаря реализации интерфейса IEnumerable можно также получать содержимое коллекции в цикле foreach.В интерфейсе IEnumerator определяются функции перечислителя. С помощью методов этого интерфейса можно циклически обращаться к содержимому коллекции. Еслив коллекции содержатся пары "ключ-значение" (словари), то метод GetEnumerator()возвращает объект типа IDictionaryEnumerator, а не типа IEnumerator. ИнтерфейсIDictionaryEnumerator наследует от интерфейса IEnumerator и вводит дополнительные функции, упрощающие перечисление словарей.В интерфейсе IEnumerator определяются также методы MoveNext() и Reset()и свойство Current. Способы их применения подробнее описываются далее в этойглаве. А до тех пор следует отметить, что свойство Current содержит элемент, получаемый в текущий момент. Метод MoveNext() осуществляет переход к следующемуэлементу коллекции, а метод Reset() возобновляет перечисление с самого начала.Интерфейсы IComparer и IEqualityComparerВ интерфейсе IComparer определяется метод Compare() для сравнения двухобъектов.int Compare(object х, object у)Он возвращает положительное значение, если значение объекта х больше, чем уобъекта у; отрицательное — если значение объекта х меньше, чем у объекта у; и нулевое — если сравниваемые значения равны. Данный интерфейс можно использоватьдля указания способа сортировки элементов коллекции.В интерфейсе IEqualityComparer определяются два метода.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 voidAddRange(Icollection с)public virtual intBinarySearch(objectvalue)Добавляет элементы из коллекции с в конец вызывающей коллекции типа ArrayListВыполняет поиск в вызывающей коллекции значенияvalue. Возвращает индекс найденного элемента. Еслиискомое значение не найдено, возвращает отрицательное значение. Вызывающий список должен быть отсортированПродолжение табл. 25.4Метод Описаниеpublic virtual intBinarySearch(objectvalue, Icomparercomparer)Выполняет поиск в вызывающей коллекции значенияvalue, используя для сравнения способ, определяемыйпараметром comparer. Возвращает индекс совпавшего элемента. Если искомое значение не найдено, возвращает отрицательное значение. Вызывающий списокдолжен быть отсортированpublic virtual intBinarySearch(int index,int count, object value,IComparer comparer)Выполняет поиск в вызывающей коллекции значенияvalue, используя для сравнения способ, определяемыйпараметром comparer. Поиск начинается с элемента,указываемого по индексу index, и включает количествоэлементов, определяемых параметром count. Метод возвращает индекс совпавшего элемента. Если искомое значение не найдено, метод возвращает отрицательное значение. Вызывающий список должен быть отсортированpublic virtual voidСоруТо(Array array)Копирует содержимое вызывающей коллекции в массив array, который должен быть одномерным и совместимым по типу с элементами коллекцииpublic virtual voidСоруТо(Array array, intarrayIndex)Копирует содержимое вызывающей коллекции в массивarray, начиная с элемента, указываемого по индексуarrayIndex. Целевой массив должен быть одномерным и совместимым по типу с элементами коллекцииpublic virtual voidCopyTo(int index, Arrayarray, int arrayIndex,int count)Копирует часть вызывающей коллекции, начиная с элемента, указываемого по индексу index, и включая количество элементов, определяемых параметром count,в массив array, начиная с элемента, указываемого поиндексу arrayIndex. Целевой массив должен быть одномерным и совместимым по типу с элементами коллекцииpublic static ArrayListFixedSize(ArrayList list)public virtual ArrayListGetRange(int index, intcount)Заключает коллекцию list в оболочку типа ArrayListс фиксированным размером и возвращает результатВозвращает часть вызывающей коллекции типаArrayList. Часть возвращаемой коллекции начинается с элемента, указываемого по индексу index, и включает количество элементов, определяемое параметромcount. Возвращаемый объект ссылается на те же элементы, что и вызывающий объектpublic virtual intIndexOf(object value)Возвращает индекс первого вхождения объекта valueв вызывающей коллекции. Если искомый объект не обнаружен, возвращает значение -1public virtual voidInsertRange(int index,ICollection c)Вставляет элементы коллекции с в вызывающую коллекцию, начиная с элемента, указываемого по индексуindexpublic virtual intLastlndexOf(object value)Возвращает индекс последнего вхождения объектаvalue в вызывающей коллекции. Если искомый объектне обнаружен, метод возвращает значение -1Окончание табл. 25.4В классе ArrayList поддерживается также ряд методов, оперирующих элементами коллекции в заданных пределах. Так, в одну коллекцию типа ArrayList можновставить другую коллекцию, вызвав метод InsertRange(). Для удаления из коллекции элементов в заданных пределах достаточно вызвать метод RemoveRange(). А дляМетод Описаниеpublic static ArrayListReadonly(ArrayList list)Заключает коллекцию list в оболочку типаArrayList, доступную только для чтения, и возвращает результатpublic virtual voidRemoveRange(int index,int count)Удаляет часть вызывающей коллекции, начиная с элемента, указываемого по индексу index, и включаяколичество элементов, определяемое параметромcountpublic virtual voidReverse()Располагает элементы вызывающей коллекции в обратном порядкеpublic virtual voidReverse(int index, intcount)Располагает в обратном порядке часть вызывающейколлекции, начиная с элемента, указываемого по индексу index, и включая количество элементов, определяемое параметром countpublic virtual voidSetRange(int index,ICollection c)Заменяет часть вызывающей коллекции, начиная с элемента, указываемого по индексу index, элементамиколлекции сpublic virtual voidSort()Сортирует вызывающую коллекцию по нарастающейpublic virtual voidSort(Icomparer comparer)Сортирует вызывающую коллекцию, используя для сравнения способ, определяемый параметром comparer.Если параметр comparer имеет пустое значение, тодля сравнения используется способ, выбираемый поумолчаниюpublic virtual voidSort(int index, intcount, Icomparercomparer)Сортирует вызывающую коллекцию, используя для сравнения способ, определяемый параметром comparer.Сортировка начинается с элемента, указываемого поиндексу index, и включает количество элементов,определяемых параметром count. Если параметрcomparer имеет пустое значение, то для сравнения используется способ, выбираемый по умолчаниюpublic static ArrayListSynchronized(ArrayListlist)Возвращает синхронизированный вариант коллекциитипа ArrayList, передаваемой в качестве параметраlistpublic virtual object[]ToArray()Возвращает массив, содержащий копии элементов вызывающего объектаpublic virtual ArrayToArray(Type type)Возвращает массив, содержащий копии элементов вызывающего объекта. Тип элементов этого массива определяется параметром typepublic virtual voidTrimToSize()Устанавливает значение свойства 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 boolContains (object obj)Возвращает логическое значение true, если объектobj содержится в вызывающем стеке, а иначе —логическое значение falsepublic virtual object Peek() Возвращает элемент, находящийся на вершине стека, но не удаляет егоpublic virtual object Pop() Возвращает элемент, находящийся на вершине стека, удаляя его по ходу делаpublic virtual voidPush (object obj)Помещает объект obj в стекpublic static StackSynchronized(Stack stack)Возвращает синхронизированный вариант коллекции типа Stack, передаваемой в качестве параметра stackpublic 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. Во второй форме создается пустая очередь, первоначальный размер которой определяет емкость, задаваемая параметромсараcity, а коэффициент роста по умолчанию выбирается для нее равным 2,0. В третьей форме допускается указывать не только емкость (в качестве параметра capacity),но и коэффициент роста создаваемой очереди (в качестве параметра growFactorв пределах от 1,0 до 10,0). И в четвертой форме создается очередь, состоящая из элементов указываемой коллекции col. Ее первоначальная емкость равна количеству указанных элементов, а коэффициент роста по умолчанию выбирается для нее равным 2,0.В классе Queue определяется ряд собственных методов, помимо тех, что ужеобъявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса перечислены в табл. 25.8. Эти методы обычно применяются следующим образом. Для того чтобы поместить объект в очередь,вызывается метод Enqueue(). Если требуется извлечь и удалить первый объект изначала очереди, то вызывается метод Dequeue(). Если же требуется извлечь, но неудалять следующий объект из очереди, то вызывается метод Рееk(). А если методыDequeue() и Рееk() вызываются, когда очередь пуста, то генерируется исключениеInvalidOperationException.Таблица 25.8. Наиболее часто используемые методы, определенные в классе QueueМетод Описаниеpublic virtual void Clear() Устанавливает свойство Count равным нулю, очищая, по существу, очередьpublic virtual boolContains(object obj)Возвращает логическое значение true, если объект obj содержится в вызывающей очереди, а иначе — логическое значение falsepublic virtual objectDequeue()public virtual voidEnqueue(object obj)Возвращает объект из начала вызывающей очереди. Возвращаемый объект удаляется из очередиДобавляет объект obj в конец очередиОкончание табл. 25.8Метод Описаниеpublic virtual object Peek() Возвращает объект из начала вызывающей очереди, но не удаляет егоpublic static QueueSynchronized(Queue queue)Возвращает синхронизированный вариант коллекции типа Queue, передаваемой в качестве параметра queuepublic virtual object[]ToArray()Возвращает массив, который содержит копии элементов из вызывающей очередиpublic virtual voidTrimToSize()Устанавливает значение свойства Capacity равным значению свойства CountВ приведенном ниже примере программы демонстрируется применение классаQueue.// Продемонстрировать применение класса Queue.using System;using System.Collections;class QueueDemo {static void ShowEnq(Queue q, int a) {q.Enqueue(a);Console.WriteLine("Поместить в очередь: Enqueue(" + a + ")");Console.Write("Содержимое очереди: ");foreach(int i in q)Console.Write(i + " ");Console.WriteLine ();}static void ShowDeq(Queue q) {Console.Write("Извлечь из очереди: Dequeue -> ");int a = (int) q.Dequeue();Console.WriteLine(a);Console.Write("Содержимое очереди: ");foreach(int i in q)Console.Write(i + " ");Console.WriteLine();}static void Main() {Queue q = new Queue();foreach(int i in q)Console.Write(i + " ");Console.WriteLine();ShowEnq(q, 22);ShowEnq(q, 65);ShowEnq(q, 91);ShowDeq(q);ShowDeq(q);ShowDeq(q);try {ShowDeq (q);} catch (InvalidOperationException) {Console.WriteLine("Очередь пуста.");}}}Эта программа дает следующий результат.Поместить в очередь: Enqueue(22)Содержимое очереди: 22Поместить в очередь: Enqueue(65)Содержимое очереди: 22 65Поместить в очередь: Enqueue(91)Содержимое очереди: 22 65 91Извлечь из очереди: Dequeue -> 22Содержимое очереди: 65 91Извлечь из очереди: Dequeue -> 65Содержимое очереди: 91Извлечь из очереди: Dequeue -> 91Содержимое очереди:Извлечь из очереди: Dequeue -> Очередь пуста.Хранение отдельных битов в классе коллекции BitArrayКласс BitArray служит для хранения отдельных битов в коллекции. А посколькув коллекции этого класса хранятся биты, а не объекты, то своими возможностями онотличается от классов других коллекций. Тем не менее в классе BitArray реализуются интерфейсы ICollection и IEnumerable как основополагающие элементы поддержки всех типов коллекций. Кроме того, в классе BitArray реализуется интерфейсICloneable.В классе BitArray определено несколько конструкторов. Так, с помощью приведенного ниже конструктора можно сконструировать объект типа BitArray из массивалогических значений.public BitArray(bool[] values)В данном случае каждый элемент массива values становится отдельным битом вколлекции. Это означает, что каждому элементу массива values соответствует отдельный бит в коллекции. Более того, порядок расположения элементов в массиве valuesсохраняется и в коллекции соответствующих им битов.Коллекцию типа BitArray можно также составить из массива байтов, используяследующий конструктор.public BitArray(byte[] bytes)Здесь битами в коллекции становится уже целый их набор из массива bytes, причем элемент bytes[0] обозначает первые 8 битов, элемент bytes[1] — вторые 8 битов и т.д. Аналогично, коллекцию типа BitArray можно составить из массива целочисленных значений, используя приведенный ниже конструктор.public BitArray(int[ ] values)В данном случае элемент values[0] обозначает первые 32 бита, элементvalues[1] — вторые 32 бита и т.д.С помощью следующего конструктора можно составить коллекцию типа BitArray,указав ее конкретный размер:public BitArray(int length)где length обозначает количество битов в коллекции, которые инициализируютсялогическим значением false. В приведенном ниже конструкторе можно указать нетолько размер коллекции, но и первоначальное значение составляющих ее битов.public BitArray(int length, bool defaultValue)В данном случае все биты в коллекции инициализируются значениемdefaultValue, передаваемым конструктору в качестве параметра.И наконец, новую коллекцию типа BitArray можно создать из уже существующей, используя следующий конструктор.public BitArray(BitArray bits)Вновь сконструированный объект будет содержать такое же количество битов, каки в указываемой коллекции bits, а в остальном это будут две совершенно разные коллекции.Коллекции типа BitArray подлежат индексированию. По каждому индексу указывается отдельный бит в коллекции, причем нулевой индекс обозначает младший бит.В классе BitArray определяется ряд собственных методов, помимо тех, что ужеобъявлены в интерфейсах, которые в нем реализуются. Методы этого класса приведены в табл. 25.9. Обратите внимание на то, что в классе BitArray не поддерживаетсяметод Synchronized(). Это означает, что для коллекций данного класса синхронизированная оболочка недоступна, а свойство IsSynchronized всегда имеет логическоезначение false. Тем не менее для управления доступом к коллекции типа BitArrayее можно синхронизировать для объекта, предоставляемого упоминавшимся ранеесвойством SyncRoot.Таблица 25.9. Методы, определенные в классе BitArrayМетод Описаниеpublic BitArray And(BitArrayvalue)Выполняет операцию логического умножения И битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащуюрезультатpublic bool Get(int index) Возвращает значение бита, указываемого по индексу indexpublic BitArray Not() Выполняет операцию поразрядного логического отрицания НЕ битов вызывающей коллекции и возвращает коллекцию типа BitArray, содержащую результатОкончание табл. 25.9В классе BitArray определяется также собственное свойство, помимо тех, что указаны в интерфейсах, которые в нем реализуются.public int Length { get; set; }Свойство Length позволяет установить или получить количество битов в коллекции. Следовательно, оно возвращает такое же значение, как и стандартное свойствоCount, определяемое для всех коллекций. В отличие от свойства Count, свойствоLength доступно не только для чтения, но и для записи, а значит, с его помощью можно изменить размер коллекции типа BitArray. Так, при сокращении коллекции типаBitArray лишние биты усекаются, начиная со старшего разряда. А при расширенииколлекции типа BitArray дополнительные биты, имеющие логическое значениеfalse, вводятся в коллекцию, начиная с того же старшего разряда.Кроме того, в классе BitArray определяется следующий индексатор.public bool this[int index] { get; set; }С помощью этого индексатора можно получать или устанавливать значение элемента.В приведенном ниже примере демонстрируется применение класса BitArray.// Продемонстрировать применение класса BitArray.using System;using System.Collections;class BADemo {public static void ShowBits(string rem,BitArray bits) {Console.WriteLine(rem);for(int i=0; i < bits.Count; i++)Console.Write("{0, -6} ", bits[i]);Console.WriteLine("\n");}static void Main() {BitArray ba = new BitArray(8);byte[] b = { 67 };BitArray ba2 = new BitArray(b);Метод Описаниеpublic BitArray Or(BitArrayvalue)Выполняет операцию логического сложения ИЛИ битов вызывающего объекта и коллекции value. Возвращает коллекцию типа BitArray, содержащуюрезультатpublic void Set(int index,bool value)Устанавливает бит, указываемый по индексу Index,равным значению valuepublic void SetAll(boolvalue)Устанавливает все биты равными значению valuepublic BitArray Xor(BitArrayvalue)Выполняет логическую операцию исключающееИЛИ над битами вызывающего объекта и коллекцииvalue. Возвращает коллекцию типа BitArray, содержащую результатShowBits("Исходное содержимое коллекции ba:", bа);ba = ba.Not();ShowBits("Содержимое коллекции bа после логической операции NOT:", ba);ShowBits("Содержимое коллекции bа2:", bа2);BitArray bа3 = bа.Хоr(bа2);ShowBits("Результат логической операции ba XOR bа2:", bаЗ);}}Эта программа дает следующий результат.Исходное содержимое коллекции Ьа:False False False False False False False FalseСодержимое коллекции ba после логической операции NOT:True True True True True True True TrueСодержимое коллекции bа2:True True False False False False ffrue FalseРезультат логической операции ba XOR ba2:False False True True True True False TrueСпециальные коллекцииВ среде .NET Framework предусмотрен ряд специальных коллекций, оптимизированных для работы с данными конкретного типа иди для их обработки особым образом. Классы этих необобщенных коллекций определены в пространстве имен System.Collections.Specialized и перечислены ниже.Класс специальной коллекции ОписаниеCollectionsUtil Содержит фабричные методы для создания коллекцийHybridDictionary Предназначен для коллекций, в которых для хранения небольшого количества пар “ключ-значение" используется классListDictionary. При превышении коллекцией определенного размера автоматически используется класс Hashtableдля хранения ее элементовListDictionary Предназначен для коллекций, в которых для хранения пар “ключ-значение” используется связный список. Такие коллекции рекомендуются только для хранения небольшого количества элементовNameValueCollection Предназначен для отсортированных коллекций, в которых хранятся пары “ключ-значение”, причем и ключ, и значение относятся к типу stringOrderedDictionary Предназначен для коллекций, в которых хранятся индексируемые пары “ключ-значение”StringCollection Предназначен для коллекций, оптимизированных для хранениясимвольных строкStringDictionary Предназначен для хеш-таблиц, в которых хранятся пары“ключ-значение”, причем и ключ, и значение относятся к типуstringКроме того, в пространстве имен System.Collections определены три базовыхабстрактных класса: CollectionBase, ReadOnlyCollectionBase и DictionaryBase.Эти классы могут наследоваться и служить в качестве отправной точки для разработкисобственных специальных коллекций.Обобщенные коллекцииБлагодаря внедрению обобщений прикладной интерфейс Collections API значительно расширился, в результате чего количество классов коллекций и интерфейсов удвоилось. Обобщенные коллекции объявляются в пространстве имен System.Collections.Generic. Как правило, классы обобщенных коллекций являются не более чем обобщенными эквивалентами рассматривавшихся ранее классов необобщенных коллекций, хотя это соответствие не является взаимно однозначным. Например,в классе обобщенной коллекции LinkedList реализуется двунаправленный список,тогда как в необобщенном эквиваленте его не существует. В некоторых случаях однии те же функции существуют параллельно в классах обобщенных и необобщенных коллекций, хотя и под разными именами. Так, обобщенный вариант класса ArrayListназывается List, а обобщенный вариант класса HashTable — Dictionary. Крометого, конкретное содержимое различных интерфейсов и классов реорганизуется с минимальными изменениями для переноса некоторых функций из одного интерфейса вдругой. Но в целом, имея ясное представление о необобщенных коллекциях, можнобез особого труда научиться применять и обобщенные коллекции.Как правило, обобщенные коллекции действуют по тому же принципу, что и необобщенные, за исключением того, что обобщенные коллекции типизированы. Этоозначает, что в обобщенной коллекции можно хранить только те элементы, которыесовместимы по типу с ее аргументом. Так, если требуется коллекция для хранения несвязанных друг с другом разнотипных данных, то для этой цели следует использоватьклассы необобщенных коллекций. А во всех остальных случаях, когда в коллекциидолжны храниться объекты только одного типа, выбор рекомендуется останавливатьна классах обобщенных коллекций.Обобщенные коллекции определяются в ряде интерфейсов и классов, реализующих эти интерфейсы. Все они описываются далее по порядку.Интерфейсы обобщенных коллекцийВ пространстве имен System.Collections.Generic определен целый ряд интерфейсов обобщенных коллекций, имеющих соответствующие аналоги среди интерфейсов необобщенных коллекций. Все эти интерфейсы сведены в табл. 25.10.Таблица 25.10. Интерфейсы обобщенных коллекцийИнтерфейс ОписаниеICollection Определяет основополагающие свойства обобщенныхколлекцийIComparer Определяет обобщенный метод Compare() для сравнения объектов, хранящихся в коллекцииIDictionary Определяет обобщенную коллекцию, состоящую из пар"ключ-значение’’Окончание табл. 25.10Интерфейс ОписаниеIEnumerable Определяет обобщенный метод GetEnumerator(),предоставляющий перечислитель для любого классаколлекцииEnumerator Предоставляет методы, позволяющие получать содержимое коллекции по очередиIEqualityComparer Сравнивает два объекта на предмет равенстваIList Определяет обобщенную коллекцию, доступ к которойможно получить с помощью индексатораИнтерфейс ICollectionВ интерфейсе ICollection определен ряд свойств, которые являются общимидля всех обобщенных коллекций. Интерфейс ICollection является обобщеннымвариантом необобщенного интерфейса ICollection, хотя между ними имеются некоторые отличия.Итак, в интерфейсе ICollection определены следующие свойства.int Count { get; }bool IsReadOnly { get; }Свойство Count содержит ряд элементов, хранящихся в данный момент в коллекции. А свойство IsReadOnly имеет логическое значение true, если коллекция доступна только для чтения. Если же коллекция доступна как для чтения, так и для записи, тоданное свойство имеет логическое значение false.Кроме того, в интерфейсе ICollection определены перечисленные ниже методы. Обратите внимание на то, что в этом обобщенном интерфейсе определено несколько большее количество методов, чем в его необобщенном аналоге.Некоторые из перечисленных выше методов генерируют исключение NotSupportedException, если коллекция доступна только для чтения.Метод Описаниеvoid Add(T item) Добавляет элемент item в вызывающую коллекцию. Генерирует исключение NotSupportedException, если коллекция доступна только для чтенияvoid Clear() Удаляет все элементы из вызывающей коллекцииbool Contains(T item) Возвращает логическое значение true, если вызывающаяколлекция содержит элемент item, а иначе — логическоезначение falsevoid CopyTo(T[] array,int arrayIndex)Копирует содержимое вызывающей коллекции в массивarray, начиная с элемента, указываемого по индексуarrayIndexvoid Remove(T item) Удаляет первое вхождение элемента item в вызывающейколлекции. Возвращает логическое значение true, еслиэлемент item удален. А если этот элемент не найден в вызывающей коллекции, то возвращается логическое значение falseА поскольку интерфейс ICollection наследует от интерфейсов IEnumerable иIEnumerable, то он включает в себя также обобщенную и необобщенную формыметода GetEnumerator().Благодаря тому что в интерфейсе ICollection реализуется интерфейсIEnumerable, в нем поддерживаются также методы расширения, определенные вклассе Enumerable. Несмотря на то что методы расширения предназначены главнымобразом для поддержки LINQ, им можно найти и другое применение, в том числе ив коллекциях.Интерфейс IListВ интерфейсе IList определяется такое поведение обобщенной коллекции,которое позволяет осуществлять доступ к ее элементам по индексу с отсчетом отнуля. Этот интерфейс наследует от интерфейсов IEnumerable, IEnumerable иICollection и поэтому является обобщенным вариантом необобщенного интерфейса IList. Методы, определенные в интерфейсе IList, перечислены в табл.25.11. В двух из этих методов предусматривается модификация коллекции. Если жеколлекция доступна только для чтения или имеет фиксированный размер, то методыInsert() и RemoveAt() генерируют исключение NotSupportedException.Таблица 25.11. Методы, определенные в интерфейсе IListМетод Описаниеint IndexOf(Т item) Возвращает индекс первого вхождения элемента item ввызывающей коллекции. Если элемент item не обнаружен, то метод возвращает значение -1void Insert(int index,T item)Вставляет в вызывающую коллекцию элемент item поиндексу indexvoid RemoveAtfint index) Удаляет из вызывающей коллекции элемент, расположенный по указанному индексу indexКроме того, в интерфейсе IList определяется индексаторТ this[int index] { get; set; }который устанавливает или возвращает значение элемента коллекции по указанномуиндексу index.Интерфейс IDictionaryВ интерфейсе IDictionary определяется такое поведение обобщенной коллекции, которое позволяет преобразовать уникальные ключи в соответствующие значения. Это означает, что в данном интерфейсе определяется коллекция, вкоторой хранятся пары "ключ-значение". Интерфейс IDictionaryнаследует от интерфейсов IEnumerable, IEnumerable> и ICollection> и поэтому являетсяобобщенным вариантом необобщенного интерфейса IDictionary. Методы, объявленные в интерфейсе IDictionary, приведены в табл. 25.12. Все этиметоды генерируют исключение ArgumentNullException при попытке указать пустой ключ.Кроме того, в интерфейсе IDictionary определены перечисленные ниже свойства.Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступныотдельными списками с помощью свойств Keys и Values.И наконец, в интерфейсе IDictionary определяется следующийиндексатор.TValue this[TKey key] { get; set; }Этот индексатор служит для получения и установки значения элемента коллекции,а также для добавления в коллекцию нового элемента. Следует, однако, иметь в виду,что в качестве индекса в данном случае служит ключ элемента, а не сам индекс.Интерфейсы IEnumerable и IEnumeratorИнтерфейсы IEnumerable и IEnumerator являются обобщенными эквивалентами рассмотренных ранее необобщенных интерфейсов IEnumerable иIEnumerator. В них объявляются аналогичные методы и свойства, да и действуют онипо тому же принципу. Разумеется, обобщенные интерфейсы оперируют даннымитолько того типа, который указывается в аргументе типа.В интерфейсе IEnumerable метод GetEnumerator() объявляется следующимобразом.IEnumerator GetEnumerator()Этот метод возвращает перечислитель типа Т для коллекции. А это означает, чтоон возвращает типизированный перечислитель.Таблица 25.12. Методы, определенные в интерфейсе IDictionaryМетод Описаниеvoid Add(TKey key, TValuevalue)Добавляет в вызывающую коллекцию пару “ключ-значение”, определяемую параметрами key и value.Генерирует исключение ArgumentException, еслиключ key уже находится в коллекцииbool Contains(TKey key) Возвращает логическое значение true, если вызывающая коллекция содержит элемент key в качествеключа, а иначе — логическое значение falsebool Remove(TKey key) Удаляет из коллекции элемент, ключ которого равензначению keybool TryGetValue(TKey key,out TValue value)Предпринимает попытку извлечь значение из коллекции по указанному ключу key и присвоить это значение переменной value. При удачном исходе операции возвращается логическое значение true, а иначе — логическое значение false. Если ключ key ненайден, переменной value присваивается значение,выбираемое по умолчаниюСвойство ОписаниеICollection Keys { get; } Получает коллекцию ключейICollection Values { get; } Получает коллекцию значенийКроме того, в интерфейсе IEnumerable определяются два таких же метода, каки в необобщенном его варианте: MoveNext() и Reset(). В этом интерфейсе объявляется также обобщенный вариант свойства Current.Т Current { get; }Это свойство возвращает ссылку типа Т на следующий объект. А это означает, чтообобщенный вариант свойства Current является типизированным.Но между интерфейсами IEnumerator и IEnumerator имеется одно важноеразличие: интерфейс IEnumerator наследует от интерфейса IDisposable, тогдакак интерфейс IEnumerator не наследует от него. В интерфейсе IDisposable определяется метод Dispose(), который служит для освобождения неуправляемых ресурсов.ПРИМЕЧАНИЕВ интерфейсе IEnumerable реализуется также необобщенный интерфейсIEnumerable. Это означает, что в нем поддерживается необобщенный вариант методаGetEnumerator(). Кроме того, в интерфейсе IEnumerable реализуется необобщенный интерфейс IEnumerator, а следовательно, в нем поддерживаются необобщенные варианты свойства Current.Интерфейс IComparerИнтерфейс IComparer является обобщенным вариантом рассмотренного ранееинтерфейса IComparer. Главное отличие между ними заключается в том, что интерфейс IComparer обеспечивает типовую безопасность. В нем обобщенный вариантметода Compare() объявляется следующим образом.int Compare(Т х, Т у)В этом методе сравниваются объекты х и у. Он возвращает положительное значение, если значение объекта х больше, чем у объекта у; отрицательное — если значениеобъекта х меньше, чем у объекта у; и нулевое значение — если сравниваемые значенияравны.Интерфейс IEqualityComparerИнтерфейс IEqualityComparer полностью соответствует своему необобщенному аналогу EqualityComparer. В нем определяются два следующих метода.bool Equals (Т х, Т у)int GetHashCode(Т obj)Метод Equals() должен возвратить логическое значение true, если значенияобъектов х и у равны. А метод GetHashCode() возвращает хеш-код для объекта obj.Если два сравниваемых объекта равны, то их хеш-коды также должны быть одинаковы.Интерфейс ISetИнтерфейс ISet был добавлен в версию 4.0 среды .NET Framework. Он определяет поведение обобщенной коллекции, реализующей ряд уникальных элементов.Этот интерфейс наследует от интерфейсов IEnumerable, IEnumerable, а такжеICollection. В интерфейсе ISet определен ряд методов, перечисленныхв табл. 25.13. Обратите внимание на то, что параметры этих методов указываются какотносящиеся к типу IEnumerable. Это означает, что в качестве второго аргумента методу можно передать нечто, отличающееся от объектов типа ISet Но чащевсего оба аргумента оказываются экземплярами объектов типа ISetТаблица 25.13. Методы, определенные в интерфейсе ISetМетод Описаниеvoid ExceptWith(Ienumerableother)Удаляет из вызывающего множества те элементы,которые содержатся в другом множестве othervoidIntersectWith(IEnumerableother)После вызова этого метода вызывающее множество содержит пересечение своих элементов с элементами другого множества otherboolIsProperSubsetOf(IEnumerableother)Возвращает логическое значение true, если вызывающее множество является правильным подмножеством другого множества other, а иначе —логическое значение falsebool IsProperSupersetOf(IEnumerable other)возвращает логическое значение true, если вызывающее множество является правильным надмножеством другого множества other, а иначе —логическое значение falsebool IsSubsetOf(IEnumerableother)Возвращает логическое значение true, если вызывающее множество является подмножествомдругого множества other, а иначе — логическоезначение falseboolIsSupersetOf(IEnumerableother)Возвращает логическое значение true, если вызывающее множество является надмножествомдругого множества other, а иначе — логическоезначение falsebool Overlaps(IEnumerableother)Возвращает логическое значение true, если вызывающее множество и другое множество otherсодержат хотя бы один общий элемент, а иначе —логическое значение falsebool SetEquals(IEnumerableother)Возвращает логическое значение true, если всеэлементы вызывающего множества и другого множества other оказываются общими, а иначе — логическое значение false. Порядок расположенияэлементов не имеет значения, а дублирующиесяэлементы во другом множестве other игнорируютсяvoid SymmetricExceptWith(IEnumerable other)После вызова этого метода вызывающее множество будет содержать симметрическую разностьсвоих элементов и элементов другого множестваothervoid UnionWith(IEnumerableother)После вызова этого метода вызывающее множество будет содержать объединение своих элементов и элементов другого множества otherСтруктура KeyValuePairВ пространстве имен System.Collections.Generic определена структураKeyValuePair. Она служит для хранения ключа и его значенияи применяется в классах обобщенных коллекций, в которых хранятся пары "ключ-значение", как, например, в классе Dictionary. В этой структуреопределяются два следующих свойства.public TKey Key { get; };public TValue Value { get; };В этих свойствах хранятся ключ и значение соответствующего элемента коллекции.Для построения объекта типа KeyValuePair служит конструктор:public KeyValuePair(TKey key, TValue value)где key обозначает ключ, a value — значение.Классы обобщенных коллекцийКак упоминалось ранее, классы обобщенных коллекций по большей части соответствуют своим необобщенным аналогам, хотя в некоторых случаях они носят другиеимена. Отличаются они также своей организацией и функциональными возможностями. Классы обобщенных коллекций определяются в пространстве имен System.Collections.Generic. В табл. 25.14 приведены классы, рассматриваемые в этой главе. Эти классы составляют основу обобщенных коллекций.Таблица 25.14. Основные классы обобщенных коллекцийКласс ОписаниеDictionary Сохраняет пары “ключ-значение". Обеспечивает такиеже функциональные возможности, как и необобщенныйкласс HashtableHashSet Сохраняет ряд уникальных значений, используя хеш-таблицуLinkedList Сохраняет элементы в двунаправленном спискеList Создает динамический массив. Обеспечивает такие жефункциональные возможности, как и необобщенныйкласс ArrayListQueue Создает очередь. Обеспечивает такие же функциональные возможности, как и необобщенный класс QueueSortedDictionaryСоздает отсортированный список из пар “ключ-значение”SortedList Создает отсортированный список из пар "ключ-значение”. Обеспечивает такие же функциональные возможности, как и необобщенный класс SortedListSortedSet Создает отсортированное множествоStack Создает стек. Обеспечивает такие же функциональныевозможности, как и необобщенный класс StackПРИМЕЧАНИЕВ пространстве имен System.Collections.Generic находятся также следующиеклассы: класс SynchronizedCollection синхронизированной коллекции на основе класса IList; класс SynchronizedReadOnlyCollection, доступной только для чтения синхронизированной коллекции на основе класса lList; абстрактныйкласс SynchronizedKeyCollection, служащий в качестве базового для класса коллекции System.ServiceModel.UriSchemeKeyedCollection; а также классKeyedByTypeCollection коллекции, в которой в качестве ключей используются отдельные типы данных.Класс ListВ классе List реализуется обобщенный динамический массив. Он ничемпринципиально не отличается от класса необобщенной коллекции ArrayList.В этом классе реализуются интерфейсы ICollection, ICollection, IList,IList, IEnumerable и IEnumerable. У класса List имеются следующиеконструкторы.public List()public List(IEnumerable collection)public List(int capacity)Первый конструктор создает пустую коллекцию класса List с выбираемой поумолчанию первоначальной емкостью. Второй конструктор создает коллекцию типаList с количеством инициализируемых элементов, которое определяется параметромcollection и равно первоначальной емкости массива. Третий конструктор создаетколлекцию типа List, имеющую первоначальную емкость, задаваемую параметромcapacity. В данном случае емкость обозначает размер базового массива, используемого для хранения элементов коллекции. Емкость коллекции, создаваемой в виде динамического массива, может увеличиваться автоматически по мере добавления в нееэлементов.В классе List определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторые из наиболее часто используемых методов этого класса перечислены в табл. 25.15.Таблица 25.15. Наиболее часто используемые методы, определенные в классе ListМетод Описаниеpublic virtual voidAddRange(Icollectioncollection)Добавляет элементы из коллекции collection вконец вызывающей коллекции типа ArrayListpublic virtual intBinarySearch(T item)Выполняет поиск в вызывающей коллекции значения, задаваемого параметром item. Возвращаетиндекс совпавшего элемента. Если искомое значение не найдено, возвращается отрицательноезначение. Вызывающий список должен быть отсортированПродолжение табл. 25.15Метод Описаниеpublic int BinarySearch(Тitem, IComparer comparer)Выполняет поиск в вызывающей коллекции значения, задаваемого параметром item, используя длясравнения указанный способ, определяемый параметром comparer. Возвращает индекс совпавшегоэлемента. Если искомое значение не найдено, возвращается отрицательное значение. Вызывающийсписок должен быть отсортированpublic int BinarySearch(intindex, int count, T item,IComparer comparer)Выполняет поиск в вызывающей коллекции значения, задаваемого параметром item, используя длясравнения указанный способ, определяемый параметром comparer. Поиск начинается с элемента,указываемого по индексу index, и включает количество элементов, определяемых параметромcount. Метод возвращает индекс совпавшегоэлемента. Если искомое значение не найдено, возвращается отрицательное значение. Вызывающийсписок должен быть отсортированpublic List GetRange(intindex, int count)Возвращает часть вызывающей коллекции. Частьвозвращаемой коллекции начинается с элемента,указываемого по индексу index, и включает количество элементов, задаваемое параметром count.Возвращаемый объект ссылается на те же элементы, что и вызывающий объектpublic int IndexOf(T item) Возвращает индекс первого вхождения элементаitem в вызывающей коллекции. Если искомый элемент не обнаружен, возвращается значение -1public void InsertRange(intindex, IEnumerablecollection)Вставляет элементы коллекции collection в вызывающую коллекцию, начиная с элемента, указываемого по индексу indexpublic int LastlndexOf(Titem)Возвращает индекс последнего вхождения элемента item в вызывающей коллекции. Если искомыйэлемент не обнаружен, возвращается значение -1public void RemoveRange(intindex, int count)Удаляет часть вызывающей коллекции, начиная сэлемента, указываемого по индексу index, и включая количество элементов, определяемое параметром countpublic void Reverse() Располагает элементы вызывающей коллекции вобратном порядкеpublic void Reverse(intindex, int count)Располагает в обратном порядке часть вызывающей коллекции, начиная с элемента, указываемогопо индексу index, и включая количество элементов, определяемое параметром countpublic void Sort() Сортирует вызывающую коллекцию по нарастающейВ классе List определяется также собственное свойство Capacity, помимо тех,что уже объявлены в интерфейсах, которые в нем реализуются. Это свойство объявляется следующим образом.public int Capacity { get; set; }Свойство Capacity позволяет установить и получить емкость вызывающей коллекции в качестве динамического массива. Эта емкость равна количеству элементов, которые может содержать коллекция до ее вынужденного расширения. Такая коллекциярасширяется автоматически, и поэтому задавать ее емкость вручную необязательно.Но из соображений эффективности это иногда можно сделать, если заранее известноколичество элементов коллекции. Благодаря этому исключаются издержки на выделение дополнительной памяти.В классе List реализуется также приведенный ниже индексатор, определенный в интерфейсе IList.public Т this[int index] { get; set; }С помощью этого индексатора устанавливается и получается значение элементаколлекции, указываемое по индексу index.В приведенном ниже примере программы демонстрируется применение класса List. Это измененный вариант примера, демонстрировавшего ранее классArrayList. Единственное изменение, которое потребовалось для этого, заключалосьв замене класса ArrayList классом List, а также в использовании параметров обобщенного типа.Окончание табл. 25.15Метод Описаниеpublic voidSort(IСоmраrеr<Т> comparer)Сортирует вызывающую коллекцию, используядля сравнения способ, задаваемый параметромcomparer. Если параметр comparer имеет пустоезначение, то для сравнения используется способ,выбираемый по умолчаниюpublic voidSort(Comparisoncomparison)Сортирует вызывающую коллекцию, используя длясравнения указанный делегатpublic void Sort (int index,int count, IComparercomparer)Сортирует вызывающую коллекцию, используядля сравнения способ, задаваемый параметромcomparer. Сортировка начинается с элемента, указываемого по индексу index, и включает количество элементов, определяемых параметром count.Если параметр comparer имеет пустое значение,то для сравнения используется способ, выбираемыйпо умолчаниюpublic T[] ToArray() Возвращает массив, содержащий копии элементоввызывающего объектаpublic void TrimExcess() Сокращает емкость вызывающей коллекции такимобразом, чтобы она не превышала 10% от количества элементов, хранящихся в ней на данный момент// Продемонстрировать применение класса List.using System;using System.Collections.Generic;class GenListDemo {static void Main() {// Создать коллекцию в виде динамического массива.List lst = new List();Console.WriteLine("Исходное количество элементов: " + lst.Count);Console.WriteLine();Console.WriteLine("Добавить 6 элементов");// Добавить элементы в динамический массив.lst.Add('С');lst.Add('А');lst.Add('Е');lst.Add('В');lst.Add('D');lst.Add('F');Console.WriteLine("Количество элементов: " + lst.Count);// Отобразить содержимое динамического массива,// используя индексирование массива.Console.Write("Текущее содержимое: ");for (int i=0; i < lst.Count; i++)Console.Write(lst[i] + " ");Console.WriteLine("\n");Console.WriteLine("Удалить 2 элемента ");// Удалить элементы из динамического массива.lst.Remove('F');lst.Remove('А');Console.WriteLine("Количество элементов: " + lst.Count);// Отобразить содержимое динамического массива, используя цикл foreach.Console.Write("Содержимое: ");foreach(char с in lst)Console.Write(с + " ");Console.WriteLine("\n");Console.WriteLine("Добавить еще 20 элементов");// Добавить количество элементов, достаточное для// принудительного расширения массива.for(int i=0; i < 20; i++)lst.Add((char)('a' + i));Console.WriteLine("Текущая емкость: " + lst.Capacity);Console.WriteLine("Количество элементов после добавления 20 новых: " +lst.Count);Console.Write("Содержимое: ");foreach(char с in lst)Console.Write(с + " ");Console.WriteLine("\n");// Изменить содержимое динамического массива,// используя индексирование массива.Console.WriteLine("Изменить три первых элемента");lst[0] = 'X';lst [1] = 'Y';lst[2] = 'Z';Console.Write("Содержимое: ");foreach(char с in lst)Console.Write(с + " ");Console.WriteLine();// Следующая строка кода недопустима из-за// нарушения безопасности обобщенного типа.// lst.Add(99); // Ошибка, поскольку это не тип char!}}Эта версия программы дает такой же результат, как и предыдущая.Исходное количество элементов: 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Класс LinkedListВ классе LinkedList создается коллекция в виде обобщенного двунаправленного списка. В этом классе реализуются интерфейсы ICollection, ICollection,IEnumerable, IEnumerable, ISerializable и IDeserializationCallback.В двух последних интерфейсах поддерживается сериализация списка. В классеLinkedList определяются два приведенных ниже открытых конструктора.public LinkedList()public LinkedList(IEnumerable collection)В первом конструкторе создается пустой связный список, а во втором конструкторе — список, инициализируемый элементами из коллекции collection.Как и в большинстве других реализаций связных списков, в классе LinkedListинкапсулируются значения, хранящиеся в узлах списка, где находятся также ссылки напредыдущие и последующие элементы списка. Эти узлы представляют собой объектыкласса LinkedListNode. В классе LinkedListNode предоставляются четыреследующих свойства.public LinkedListNode Next { get; }public LinkedListNode Previous { get; }public LinkedList List { get; }public T Value { get; set; }С помощью свойств Next и Previous получаются ссылки на предыдущий и последующий узлы списка соответственно, что дает возможность обходить список в обоихнаправлениях. Если же предыдущий или последующий узел отсутствует, то возвращается пустая ссылка. Для получения ссылки на сам список служит свойство List.А с помощью свойства Value можно устанавливать и получать значение, находящеесяв узле списка.В классе LinkedList определяется немало методов. В табл. 25.16 приведены наиболее часто используемые методы данного класса. Кроме того, в классе LinkedList определяются собственные свойства, помимо тех, что ужеобъявлены в интерфейсах, которые в нем реализуются. Эти свойства приведеныниже.public LinkedListNode First { get; }public LinkedListNode Last { get; }С помощью свойства First получается первый узел в списке, а с помощью свойства Last — последний узел в списке.Таблица 25.16. Наиболее часто используемые методы, определенные в классе LinkedListМетод Описаниеpublic LinkedListNodeAddAfter(LinkedListNodenode, T value)Добавляет в список узел со значением value непосредственно после указанного узла node. Указываемый узел node не должен быть пустым (null).Метод возвращает ссылку на узел, содержащий значение valuepublic voidAddAfter(LinkedListNodenode, LinkedListNodenewNode)Добавляет в список новый узел newNode непосредственно после указанного узла node. Указываемый узел node не должен быть пустым(null). Если узел node отсутствует в спискеили если новый узел newNode является частьюдругого списка, то генерируется исключениеInvalidOperationExceptionpublic LinkedListNodeAddBefore(LinkedListNodenode, T value)Добавляет в список узел со значением value непосредственно перед указанным узлом node. Указываемый узел node не должен быть пустым (null).Метод возвращает ссылку на узел, содержащий значение valueВ приведенном ниже примере программы демонстрируется применение классаLinkedList.// Продемонстрировать применение класса LinkedList.using System;using System.Collections.Generic;Окончание табл. 25.16Метод Описаниеpublic voidAddBefore(LinkedListNodenode, LinkedListNodenewNode)Добавляет в список новый узел newNode непосредственно перед указанным узлом node.Указываемый узел node не должен быть пустым (null). Если узел node отсутствует в списке или если новый узел newNode является частью другого списка, то генерируется исключениеInvalidOperationExceptionpublic LinkedListAddFirst(T value)Добавляет узел со значением value в начало списка. Метод возвращает ссылку на узел, содержащийзначение valuepublic voidAddFirst(LinkedListNodenode)Добавляет узел node в начало списка. Если узелnode является частью другого списка, то генерируется исключение InvalidOperationExceptionpublic LinkedListAddLast(T value)Добавляет узел со значением value в конец списка. Метод возвращает ссылку на узел, содержащийзначение valuepublic voidAddLast(LinkedListNode node)Добавляет узел node в конец списка. Если узелnode является частью другого списка, то генерируется исключение InvalidOperationExceptionpublic LinkedList Find(Tvalue)Возвращает ссылку на первый узел в списке, имеющий значение value. Если искомое значениеvalue отсутствует в списке, то возвращается пустоезначениеpublic LinkedListFindLast(T value)Возвращает ссылку на последний узел в списке,имеющий значение value. Если искомое значениеvalue отсутствует в списке, то возвращается пустоезначениеpublic bool Remove(T value) Удаляет из списка первый узел, содержащий значение value. Возвращает логическое значение true,если узел удален, т.е. если узел со значением valueобнаружен в списке и удален; в противном случаевозвращает логическое значение falsepublic voidRemove(LinkedList node)Удаляет из списка узел, соответствующий указанному узлу node. Если узел node отсутствует в списке, то генерируется исключениеInvalidOperationExceptionpublic void RemoveFirst() Удаляет из списка первый узелpublic void RemoveLast() Удаляет из списка последний узелclass GenLinkedListDemo {static void Main() {// Создать связный список.LinkedList ll = new LinkedList();Console.WriteLine("Исходное количество элементов в списке: " + ll.Count)Console.WriteLine();Console.WriteLine("Добавить в список 5 элементов");// Добавить элементы в связный список.ll.AddFirst('А');ll.AddFirst('В');ll.AddFirst('С');ll.AddFirst('D');ll.AddFirst('Е');Console.WriteLine("Количество элементов в списке: " + ll.Count);// Отобразить связный список, обойдя его вручную.LinkedListNode node;Console.Write("Отобразить содержимое списка по ссылкам: ");for(node = ll.First; node != null; node = node.Next)Console.Write(node.Value + " ");Console.WriteLine("\n");// Отобразить связный список, обойдя его в цикле foreach.Console.Write("Отобразить содержимое списка в цикле foreach: ");foreach(char ch in 11)Console.Write(ch + " ");Console.WriteLine("\n");// Отобразить связный список, обойдя его вручную в обратном направлении.Console.Write("Следовать по ссылкам в обратном направлении: ");for(node = ll.Last; node != null; node = node.Previous)Console.Write(node.Value + " ");Console.WriteLine("\n");// Удалить из списка два элемента.Console.WriteLine("Удалить 2 элемента из списка");// Удалить элементы из связного списка.ll.Remove('С');ll.Remove('А');Console.WriteLine("Количество элементов в списке: " + ll.Count);// Отобразить содержимое видоизмененного списка в цикле foreach.Console.Write("Содержимое списка после удаления элементов: ");foreach(char ch in ll)Console.Write(ch + " ");Console.WriteLine("\n");// Добавить три элемента в конец списка.ll.AddLast('X');ll.AddLast('Y');ll.AddLast('Z');Console.Write("Содержимое списка после ввода элементов: ");foreach(char ch in ll)Console.Write(ch + " ");Console.WriteLine("\n");}}Ниже приведен результат выполнения этой программы.Исходное количество элементов в списке: 0Добавить в список 5 элементовКоличество элементов в списке: 5Отобразить содержимое списка по ссылкам: Е D С В АОтобразить содержимое списка в цикле foreach: Е D С В АСледовать по ссылкам в обратном направлении: А В С D ЕУдалить 2 элемента из спискаКоличество элементов в списке: 3Содержимое списка после удаления элементов: Е D ВСодержимое списка после ввода элементов: Е D В X Y ZСамое примечательное в этой программе — это обход списка в прямом и обратном направлении, следуя по ссылкам, предоставляемым свойствами Next и Previous.Двунаправленный характер подобных связных списков имеет особое значение дляприложений, управляющих базами данных, где нередко требуется перемещаться посписку в обоих направлениях.Класс DictionaryКласс Dictionary позволяет хранить пары "ключ-значение"в коллекции как в словаре. Значения доступны в словаре по соответствующим ключам. В этом отношении данный класс аналогичен необобщенному классу Hashtable.В классе Dictionary реализуются интерфейсы IDictionary,IDictionary, ICollection, ICollection>, IEnumerable, IEnumerable>,ISerializable и IDeserializationCallback. В двух последних интерфейсах поддерживается сериализация списка. Словари имеют динамический характер, расширяясь помере необходимости.В классе Dictionary предоставляется немало конструкторов.Ниже перечислены наиболее часто используемые из них.public Dictionary()public Dictionary(IDictionary dictionary)public Dictionary(int capacity)В первом конструкторе создается пустой словарь с выбираемой по умолчаниюпервоначальной емкостью. Во втором конструкторе создается словарь с указанным количеством элементов dictionary. А в третьем конструкторе с помощью параметрасараcity указывается емкость коллекции, создаваемой в виде словаря. Если размерсловаря заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера словаря во время выполнения, что, как правило, требует дополнительных затрат вычислительных ресурсов.В классе Dictionary определяется также ряд методов. Некоторые наиболее часто используемые методы этого класса сведены в табл. 25.17.Таблица 25.17. Наиболее часто используемые методы, определенныев классе DictionaryМетод Описаниеpublic void Add(TKey key, TValuevalue)Добавляет в словарь пару “ключ-значение”,определяемую параметрами key и value.Если ключ key уже находится в словаре, то егозначение не изменяется, и генерируется исключение ArgumentExceptionpublic bool ContainsKey(TKeykey)Возвращает логическое значение true, есливызывающий словарь содержит объект key вкачестве ключа; а иначе — логическое значение falsepublic bool ContainsValue(TValuevalue)Возвращает логическое значение true, есливызывающий словарь содержит значениеvalue; в противном случае — логическое значение falsepublic bool Remove(TKey key) Удаляет ключ key из словаря. При удачномисходе операции возвращается логическоезначение true, а если ключ key отсутствует всловаре — логическое значение falseКроме того, в классе Dictionary определяются собственныесвойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются.Эти свойства приведены ниже.Свойство Описаниеpublic IEqualityComparerComparer { get; }Получает метод сравнения для вызывающегословаряpublic Dictionary.KeyCollection Keys { get; }Получает коллекцию ключейpublic Dictionary.ValueCollection Values { get; }Получает коллекцию значенийСледует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типаDictionary.KeyCollection и Dictionary.ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICoirection и IEnumerable.И наконец, в классе Dictionary реализуется приведенный нижеиндексатор, определенный в интерфейсе IDictionary.public TValue this[TKey key] { get; set; }Этот индексатор служит для получения и установки значения элемента коллекции,а также для добавления в коллекцию нового элемента. Но в качестве индекса в данномслучае служит ключ элемента, а не сам индекс.При перечислении коллекции типа Dictionary из нее возвращаются пары "ключ-значение" в форме структуры KeyValuePair.Напомним, что в этой структуре определяются два поля.public TKey Key;public TValue Value;В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair не используется непосредственно, поскольку средства класса Dictionary позволяютработать с ключами и значениями по отдельности. Но при перечислении коллекциитипа Dictionary, например, в цикле foreach перечисляемымиобъектами являются пары типа KeyValuePair.Все ключи в коллекции типа Dictionary должны быть уникальными, причем ключ не должен изменяться до тех пор, пока он служит в качествеключа. В то же время значения не обязательно должны быть уникальными. К тому жеобъекты не хранятся в коллекции типа Dictionary в отсортированном порядке.В приведенном ниже примере демонстрируется применение классаDictionary.// Продемонстрировать применение класса обобщенной// коллекции Dictionary.using System;using System.Collections.Generic;class GenDictionaryDemo {static void Main() {// Создать словарь для хранения имен и фамилий// работников и их зарплаты.Dictionary dict =new Dictionary();// Добавить элементы в коллекцию.diet.Add("Батлер, Джон", 73000);diet.Add("Шварц, Capa", 59000);diet.Add("Пайк, Томас", 45000);diet.Add("Фрэнк, Эд", 99000);// Получить коллекцию ключей, т.е. фамилий и имен.ICollection с = diet.Keys;// Использовать ключи для получения значений, т.е. зарплаты.foreach(string str in с)Console.WriteLine("{0}, зарплата: {1:C}", str, diet[str]);}}Ниже приведен результат выполнения этой программы.Батлер, Джон, зарплата: $73,000.00Шварц, Сара, зарплата: $59,000.00Пайк, Томас, зарплата: $45,000.00Фрэнк, Эд, зарплата: $99,000.00Класс SortedDictionaryВ коллекции класса SortedDictionary пары "ключ-значение"хранятся таким же образом, как и в коллекции класса Dictionary,за исключением того, что они отсортированы по соответствующему ключу. В классе SortedDictionary реализуются интерфейсы IDictionary,IDictionary, ICollection, ICollection>, IEnumerable и IEnumerable>. В классеSortedDictionary предоставляются также следующие конструкторы.public SortedDictionary()public SortedDictionary(IDictionary dictionary)public SortedDictionary(IComparer comparer)public SortedDictionary(IDictionary dictionary,IComparer comparer)В первом конструкторе создается пустой словарь, во втором конструкторе — словарь с указанным количеством элементов dictionary. В третьем конструкторе допускается указывать с помощью параметра comparer типа IComparer способ сравнения, используемый для сортировки, а в четвертом конструкторе — инициализироватьсловарь, помимо указания способа сравнения.В классе SortedDictionary определен ряд методов. Некоторыенаиболее часто используемые методы этого класса сведены в табл. 25.18.Таблица 25.18. Наиболее часто используемые методы, определенныев классе SortedDictionaryМетод Описаниеpublic void Add(TKey key,TValue value)Добавляет в словарь пару "ключ-значение”,определяемую параметрами key и value. Еслиключ key уже находится в словаре, то его значение не изменяется, и генерируется исключениеArgumentExceptionpublic bool ContainsKey(TKeykey)Возвращает логическое значение true, если вызывающий словарь содержит объект key в качестве ключа; в противном случае — логическое значение falseМетод Описаниеpublic boolContainsValue(TValue value)Возвращает логическое значение true, если вызывающий словарь содержит значение value; в противном случае — логическое значение falsepublic bool Remove(TKey key) Удаляет ключ key из словаря. При удачном исходеоперации возвращается логическое значение true,а если ключ key отсутствует в словаре — логическоезначение falseКроме того, в классе SortedDictionary определяются собственные свойства, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже.Следует иметь в виду, что ключи и значения, содержащиеся в коллекции, доступны отдельными списками с помощью свойств Keys и Values. В коллекциях типаSortedDictionary.KeyCollection и SortedDictionary.ValueCollection реализуются как обобщенные, так и необобщенные формы интерфейсов ICollection и IEnumerable.И наконец, в классе SortedDictionary реализуется приведенный ниже индексатор, определенный в интерфейсе IDictionary.public TValue this[TKey key] { get; set; }Этот индексатор служит для получения и установки значения элемента коллекции,а также для добавления в коллекцию нового элемента. Но в данном случае в качествеиндекса служит ключ элемента, а не сам индекс.При перечислении коллекции типа SortedDictionary из неевозвращаются пары "ключ-значение" в форме структуры KeyValuePair. Напомним, что в этой структуре определяются два следующих поля.public TKey Key;public TValue Value;В этих полях содержится ключ или значение соответствующего элемента коллекции. Как правило, структура KeyValuePair не используется непосредственно, поскольку средства класса SortedDictionary позволяют работать с ключами и значениями по отдельности. Но при перечисленииколлекции типа SortedDictionary, например в цикле foreach,перечисляемыми объектами являются пары типа KeyValuePair.Окончание табл. 25.18Свойство Описаниеpublic Icomparer Comparer { get; } Получает метод сравнения для вызывающего словаряpublic SortedDictionary.KeyCollection Keys { get; }Получает коллекцию ключейpublic SortedDictionary.ValueCollection Values { get; }Получает коллекцию значенийВсе ключи в коллекции типа SortedDictionary должны бытьуникальными, причем ключ не должен изменяться до тех пор, пока он служит в качестве ключа. В то же время значения не обязательно должны быть уникальными.В приведенном ниже примере демонстрируется применение классаSortedDictionary. Это измененный вариант предыдущего примера, демонстрировавшего применение класса Dictionary. В данномварианте база данных работников отсортирована по фамилии и имени работника, которые служат в качестве ключа.// Продемонстрировать применение класса обобщенной// коллекции SortedDictionary.using System;using System.Collections.Generic;class GenSortedDictionaryDemo {static void Main() {// Создать словарь для хранения имен и фамилий// работников и их зарплаты.SortedDictionary dict =new SortedDictionary();// Добавить элементы в коллекцию.dict.Add("Батлер, Джон", 73000);dict.Add("Шварц, Capa", 59000);dict.Add("Пайк, Томас", 45000);dict.Add("Фрэнк, Эд", 99000);// Получить коллекцию ключей, т.е. фамилий и имен.ICollection с = dict.Keys;// Использовать ключи для получения значений, т.е. зарплаты.foreach(string str in с)Console.WriteLine("{0}, зарплата: {1:C}", str, diet[str]);}}Эта программа дает следующий результат.Батлер, Джон, зарплата: $73,000.00Пайк, Томас, зарплата: $45,000.00Фрэнк, Эд, зарплата: $99,000.00Шварц, Сара, зарплата: $59,000.00Как видите, список работников и их зарплаты отсортированы по ключу, в качествекоторого в данном случае служит фамилия и имя работника.Класс SortedListВ коллекции класса SortedList хранится отсортированный список пар "ключ-значение". Это обобщенный эквивалент класса необобщенной коллекцииSortedList. В классе SortedList реализуются интерфейсы IDictionary,IDictionary, ICollection, ICollection>, IEnumerable и IEnumerable>. Размерколлекции типа SortedList изменяется динамически, автоматическиувеличиваясь по мере необходимости. Класс SortedList подобен классуSortedDictionary, но у него другие рабочие характеристики. В частности, класс SortedList использует меньше памяти, тогда как классSortedDictionary позволяет быстрее вставлять неупорядоченные элементы в коллекцию.В классе SortedList предоставляется немало конструкторов.Ниже перечислены наиболее часто используемые конструкторы этого класса.public SortedList()public SortedList(IDictionary dictionary)public SortedList(int capacity)public SortedList(IComparer comparer)В первой форме конструктора создается пустой список с выбираемой по умолчанию первоначальной емкостью. Во второй форме конструктора создается отсортированный список с указанным количеством элементов dictionary. В третьей формеконструктора с помощью параметра capacity задается емкость коллекции, создаваемой в виде отсортированного списка. Если размер списка заранее известен, то, указав емкость создаваемой коллекции, можно исключить изменение размера списка вовремя выполнения, что, как правило, требует дополнительных затрат вычислительныхресурсов. И в четвертой форме конструктора допускается указывать с помощью параметра comparer способ сравнения объектов, содержащихся в списке.Емкость коллекции типа SortedList увеличивается автоматически по мере необходимости, когда в список добавляются новые элементы. Если текущая емкость коллекции превышается, то она увеличивается. Преимущество указанияемкости коллекции типа SortedList при ее создании заключается в снижении или полном исключении издержек на изменение размера коллекции.Разумеется, указывать емкость коллекции целесообразно лишь в том случае, если заранее известно, сколько элементов требуется хранить в ней.В классе SortedList определяется ряд собственных методов, помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Некоторыеиз наиболее часто используемых методов этого класса перечислены в табл. 25.19. Следует иметь в виду, что перечислитель, возвращаемый методом GetEnumerator(), служит для перечисления пар "ключ-значение", хранящихся в отсортированном списке ввиде объектов типа KeyValuePair.Таблица 25.19. Наиболее часто используемые методы, определенныев классе SortedListМетод Описаниеpublic void Add(TKey key,TValue value)Добавляет в список пару "ключ-значение”,определяемую параметрами key и value.Если ключ key уже находится в списке, то егозначение не изменяется, и генерируется исключение ArgumentExceptionpublic bool ContainsKey(TK key) Возвращает логическое значение true, если вызывающий список содержит объект key в качестве ключа; а иначе — логическое значение falseОкончание табл. 25.19Кроме того, в классе SortedList определяются собственные свойства,помимо тех, что уже объявлены в интерфейсах, которые в нем реализуются. Эти свойства приведены ниже.И наконец, в классе SortedList реализуется приведенный нижеиндексатор, определенный в интерфейсе IDictionary. Это еще один измененный вариант представленногоМетод Описаниеpublic boolContainsValue(TValue value)Возвращает логическое значение true, есливызывающий список содержит значениеvalue; в противном случае — логическое значение falsepublic IEnumerator<KeyValuePair