Сообщений 25    Оценка 230 [+0/-1]         Оценить  
Система Orphus

Коллекции в .NET Framework Class Library

Автор: Владислав Чистяков (VladD2)
The RSDN Group

Источник: RSDN Magazine #6-2003
Опубликовано: 24.06.2004
Исправлено: 10.12.2016
Версия текста: 1.0
Введение
Виды коллекций, включенные в FCL
Интерфейсы, используемые коллекциями.
Специализированные коллекции
Интерфейс IEnumerable
Интерфейс IEnumerator
Интерфейс ICollection
Интерфейс IList
IDictionary
Реализации
Массивы
ArrayList
Stack
Queue
BitArray
Hashtable
SortedList
Пользовательские типизированные коллекции
DataSet и DataTable
Generic-коллекции
Еще раз о производительности
Коллекции, которых нет в .NET Framework

Введение

На каком бы языке вы не программировали, вы неизбежно столкнетесь с проблемой хранения и обработки наборов данных. От выбора структур хранения данных и алгоритмов в значительной степени зависит производительность, да и качество создаваемого вами ПО. Поэтому знание стандартных коллекций, а также умение грамотно и по месту применить их, дает возможность писать более быстрые и надежные программы. Казалось бы, доскональное знание стандартных коллекций должно быть обязательным для программиста. Однако, заглянув в форумы сайта www.rsdn.ru, можно только удивиться обилию вопросов, связанных с организацией данных. Стало быть, этот вопрос требует подробного рассмотрения.

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

Итак, в .NET коллекция представляет собой объект. Даже самый примитивный массив является объектом. Массив можно создать, у него есть методы и свойства, и как все другие классы, он является ссылочным типом.

Виды коллекций, включенные в FCL

Коллекцией в дальнейшем будет называться некоторая конечная совокупность объектов, с которыми можно совершать те или иные действия. Так, обычно по отношению к коллекции можно осуществлять перебор ее элементов. Физические реализации коллекций могут быть совершенно разными. Во Framework Class Library (FCL) коллекции в основном размещаются в пространстве имен System.Collections. Их список приведен в таблице 1.

Тип коллекции Назначение
Встроенные массивы Обычные массивы, поддерживаемые CLR напрямую. В совестимых с CLR языках они являются полноценными объектами.
ArrayList Является реализацией абстракции списка на базе массива, Позволяет динамически изменять размер, добавлять и удалять элементы. По сути, динамический массив, позволяющий хранить ссылки на объекты.
Hashtable Реализует абстракцию «словарь» (Dictionary, коллекцию пар «ключ-значение») на основе алгоритма хэш-таблицы.
SortedList Реализация абстракции словаря и списка на базе сортированного массива.
Stack Реализует абстракцию «стек» – коллекцию, позволяющую осуществлять доступ к элементам по принципу FILO (First In – Last Out, первым пришел – последним ушел). В качестве хранилища используется массив.
Queue Реализует абстракцию «очередь» – коллекцию, позволяющую осуществлять доступ к элементам по принципу FIFO (First In – First Out, первым пришел – первым ушел). В качестве хранилища используется массив.
BitArray Позволяет создавать битовые массивы и управлять ими.
Таблица 1. Коллекции, доступные в .NET Framework.

В .NET Framework массив не относится к числу коллекций, хотя по своему предназначению массивы тоже являются коллекциями. Массивы отделены от коллекций потому, что они поддерживаются средой исполнения непосредственно. Мы еще вернемся к разговору о них.

Интерфейсы, используемые коллекциями.

Классы коллекций в FCL в большинстве своем реализуют некоторый набор интерфейсов (см. таблицу 2):

Название Описание
IEnumerable Предоставляет итератор, который поддерживает простой перебор элементов коллекции.
ICollection Определяет методы, позволяющие определить количество элементов в коллекции, а также методы синхронизации для коллекций.
IList Представляет интерфейс коллекции объектов, каждый из которых может быть получен по индексу. Также определяет методы модификации коллекции.
IDictionary Представляет интерфейс коллекции пар «ключ-значение».
ICloneable Определяет метод, позволяющий создать копию объекта.
Таблица 2. Стандартные интерфейсы, реализуемые коллекциями в .NET.

Кроме непосредственно реализуемых коллекциями интерфейсов, перечисленных в таблице 2, имеется также набор дополнительных интерфейсов, используемых коллекциями или возвращаемых ими. Их список приведент в таблице 3.

Название Описание
IComparer Определяет метод, осуществляющий сравнение двух объектов.
IEnumerator Определяет методы, позволяющие осуществить простой перебор элементов коллекции. Возвращается методом GetEnumerator интерфейса IEnumerable.
IComparable Используется при поиске и сортировке объектов. Может быть реализован типами, для которых определены операции сравнения.
IDictionaryEnumerator Позволяет перебрать элементы словаря.
IHashCodeProvider Определяет метод, позволяющий вычислить хэш-код для объекта.
Таблица 3. Дополнительные интерфейсы, используемые коллекциями.

Обратите внимание, что одной из отличительных особенностей FCL является то, что названия интерфейсов отражают описываемые ими абстракции. Точно так же названия классов отражают реализацию абстракций, определенных интерфейсами. Например, абстракция «словарь» (по-другому ее еще называют map) описывается интерфейсом IDictionary и реализуется классами Hashtable и SortedList. Название класса Hashtable отражает, что в качестве основного алгоритма реализации в нем используется алгоритм хэш-таблицы, а в SortedList – сортированного массива.

Специализированные коллекции

В FCL существует пространство имен System.Collections.Specialized. Оно содержит набор специализированных коллекций, которые могут иногда сократить время разработки. Я не буду подробно описывать входящие в него классы и структуры, и ограничусь только описанием их возможностей (см. таблицу 4), так как принцип их использования очень похож на стандартные коллекции, входящие в пространство имен System.Collections.

Коллекция Описание
CollectionsUtil Вспомогательный класс, позволяющий упростить создание коллекций, нечувствительных к регистру при хранении строк.
HybridDictionary Реализация IDictionary, использующая ListDictionary, если количество элементов в коллекции мало (меньше девяти), и Hashtable, если количество элементов в коллекции превышает 9. Такое изощренное средство экономии памяти. :)
ListDictionary Реализация IDictionary, использующая однонаправленный связанный список. Рекомендуется Microsoft для коллекций, в которых заведомо не будет более 10 элементов. Честно говоря, сомнительная оптимизация. Но слова из песни не выкинешь.
NameObjectCollectionBase Абстрактный базовый класс для коллекций, позволяющих использовать в качестве ключей строковые значения. Позволяет индексировать коллекцию ключами. В основном методы и свойства этого класса помечены модификатором protected и имеют префикс Base. Это позволяет не выставлять наружу нетипизированные методы и свойства базового класса. Ассоциация ключей и значений осуществляется с помощью скрытой хэш-таблицы.Слово Object в названии подчеркивает, что в качестве значений в коллекции хранятся ссылки на Object.
NameObjectCollectionBase. KeysCollection Реализует интерфейс ICollection и индексатор, возвращающий тип данных string. Используется как реализация коллекции ключей в классе NameObjectCollectionBase.
NameValueCollection Позволяет хранить отсортированный список строк и ассоциированные с ним строковые значения. Коллекцию можно индексировать как с помощью строковых ключей, так и с помощью порядкового индекса.Интересной особенностью коллекции является то, что она позволяет хранить в одном ключе несколько строковых значений, которые конкатенируются перед возвратом пользователю.
StringCollection Простая реализация коллекции строк. Для хранения списка используется ArrayList. Индексация производится последовательным целочисленным индексом. Коллекция позволяет хранить повторяющиеся значения и null.
StringDictionary Строго типизированная реализация IDictionary, позволяющая хранить ассоциации строк со строками. В качестве хранилища используется Hashtable.
StringEnumerator Итератор для класса StringCollection. Также типизированный.
BitVector32 Структура, позволяющая манипулировать с отдельными битами 32-битного числа. Она менее гибка, чем BitArray, но, в отличие от него, позволяет манипулировать отдельными диапазонами битов как миниатюрными целочисленными значениями.
BitVector32.Section Используется совместно с BitVector32 для определения в последнем секций (наборов битов).
Таблица 4. Специализированные коллекции, входящие в FCL.

Большинство коллекций из пространства имен System.Collections.Specialized специфичны, и редко используются на практике. Исключение составляют NameObjectCollectionBase, StringCollection и StringDictionary. NameObjectCollectionBase удобна для создания собственных типизированных словарей, а StringCollection и StringDictionary – готовые строковые коллекции.

Интерфейс IEnumerable

Все коллекции в FCL реализуют интерфейс IEnumerable. Этот интерфейс позволяет перебрать элементы коллекции в цикле.

Интерфейс описывает всего один метод:

IEnumerator GetEnumerator();

Этот метод возвращает ссылку на интерфейс IEnumerator (перечислитель), при помощи которого можно осуществить перебор всех элементов коллекции.

Для одного экземпляра коллекции можно одновременно запросить несколько перечислителей. Поэтому такого понятия, как «текущий элемент», нет.

Интерфейс IEnumerator

Этот интерфейс предназначен для перебора значений коллекции. В состав этого интерфейса входят: MoveNext(), Reset() и свойство Current.

Reset() позволяет сбросить состояние перечислителя в начальное состояние. В этом состоянии перечислитель находится сразу после его создания, при этом переход к следующему элементу приведет к тому, что текущим элементом станет первый элемент коллекции.

Метод MoveNext() как раз и осуществляет переход к следующему элементу коллекции. Таким образом, MoveNext() нужно вызывать непосредственно перед обращением к первому или следующему элементу.

Свойство Current, как нетрудно догадаться, предоставляет доступ к текущему элементу.

Вот пример использования этого интерфейса:

IEnumerator enumerator = ((IEnumerable)someCollection).GetEnumerator();
while (enumerator.MoveNext())
{
  ElemType elem = (ElemType)enumerator.Current();
  // ... какие-то действия с элементом коллекции.
}

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

Если вам интересно, как устроена защита в коллекциях из System.Collections, полезно будет заглянуть во внутреннюю реализацию таких коллекций, как ArrayList, Stack и Queue. У этих коллекций есть специальное private-поле _version. Узнать значение этого поля невозможно (если, конечно, не прибегать к использованию reflection или к отладчику). Значение этого поля увеличивается на единицу при любом изменении коллекции и запоминается итератором при его создании. Помимо версии, во внутренних полях итератора создается ссылка на коллекцию. Если коллекция изменилась, версия перестает совпадать с сохраненной, и итератор возбуждает исключение.

Использовать связку IEnumerable/IEnumerator удобнее всего с помощью оператора foreach. Так, приведенный выше пример можно переписать следующим образом:

        foreach (ElemType elem in someCollection)
{
  // ... какие-то действия с элементом коллекции.
}

Коротко и ясно. Но не все прекрасно под луной...

Недостатком интерфейса IEnumerator является то, что при обращении к свойству Current элемент коллекции приводится к object, а перед использованием приводится обратно к исходному типу. Если коллекция хранит элементы ссылочного типа, такое преобразование стоит относительно недорого, но если элементы являются value-типами, происходит boxing и unboxing, а это уже довольно дорогая операция. Однако бывает и хуже. Иногда для реализации универсального алгоритма (generic-алгоритм) работы с массивами применяются методы GetValue и SetValue класса Array (базового класса всех встроенных массивов). Эти методы настолько медленны, что алгоритмы, реализованные на их основе, могут быть в 100 раз медленнее, чем аналогичные, работающие с массивом напрямую. В большинстве случаев даже такие медленные алгоритмы не заметны, так как обычно объемы данных, копируемых с помощью этих методов, невелики. Но если такие алгоритмы будут использованы в узких местах, последствия могут быть не очень приятными.

Единственным радикальным решением этих проблем было бы введение полноценных generic-ов (средств создания обобщенных алгоритмов и структур данных). Именно это и планирует сделать Microsoft в следующей версии .NET Framework. Однако попытки оптимизации были предприняты еще в первой версии. Первое – это возможность создавать типизированные перечислители. К сожалению, без generic-ов все подобные решения неполноценны. Решение, предложенное разработчиками C#, заключалось в том, что можно объявить у класса публичный метод с именем GetEnumerator(). Этот метод должен возвращать интерфейс, аналогичный интерфейсу IEnumerator, но типизированный.

Вторая попытка оптимизации заключается в том, что компилятор, встречая оператор foreach, который применяется к массиву, не бросается сломя голову использовать связку IEnumerable/IEnumerator, а генерирует код так, будто вместо foreach использовался обычный for. Таким образом, если в предыдущем примере someCollection является массивом, компилятор создаст примерно такой код:

        for(int I = 0; I < someCollection.Length; i++)
{
  ElemType elem = someCollection[i];
  // ... какие-то действия с элементом коллекции.
}

Естественно, в таком случае никаких потерь производительности нет. Так что не стоит избегать оператора foreach, надеясь, что это даст прирост производительности.

Интерфейс ICollection

Интерфейс ICollection наследуется от IEnumerable:

        public
        interface ICollection : IEnumerable

Он определяет свойство, при помощи которого можно получить число элементов коллекции:

        int Count {get;}

Помимо этого свойства, интерфейс определяет метод:

        void CopyTo(Array array, int index);

Задачей этого метода является копирование элементов коллекции в массив. Копирование производится начиная с элемента, индекс которого указан как второй аргумент метода. Ссылка на массив передается в качестве первого параметра. Размер массива должен быть достаточным для размещения копируемых элементов.

Свойство SyncRoot возвращает ссылку на объект, который должен использоваться для синхронизации доступа к объекту. Необходимость в таком объекте возникает при создании сложных коллекций. Они скрывают от пользователя детали реализации, и может оказаться, что внутри коллекции синхронизация делается по одному объекту, а вы будете делать ее по другому. Естественно, что такая синхронизация работать не будет. Вот пример использования свойства SyncRoot:

        lock (myCollection.SyncRoot)
{
  myCollection[0] = myCollection[1] + myCollection[2];
}

Для обеспечения корректной работы коллекции в многопоточной среде часто бывает удобно не делать синхронизацию вручную, а воспользоваться оберткой вокруг коллекции, обеспечивающей синхронизацию доступа к коллекции. Свойство IsSynchronized позволяет определить, нужна ли такая обертка имеющейся у вас ссылке на коллекцию, или она уже и так потокобезопасна.

Интерфейс IList

Описанные выше методы и свойства позволяют просто «гонять» итераторы от одного элемента коллекции к другому, и узнавать количество элементов коллекции. Если не будут реализованы собственные методы доступа к данным коллекции, коллекцией пользоваться не удастся. Так вот, интерфейс IList предоставляет полиморфный механизм манипуляции данными коллекции:

        public
        interface IList : ICollection, IEnumerable

В интерфейсе IList впервые встречается способ получить или присвоить какое-то значение элементу коллекции. Это делается с помощью индексатора:

        object
        this[int index] { get; set; }

Аргументом в данном случае является индекс элемента.

Чтобы добавить элемент в коллекцию, можно воспользоваться методом:

        int Add(object value);

Метод должен вернуть индекс добавленного элемента.

Если же необходимо вставить элемент в конкретное место коллекции, то можно использовать метод:

        void Insert(int index, object value);

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

Чтобы удалить элемент, имеющий конкретное значение, можно использовать метод:

        void Remove(object value);

Для удаления элемента по его индексу нужно воспользоваться методом:

        void RemoveAt(int index);

Очистить коллекцию можно при помощи метода:

        void Clear();

Если нужно просто узнать, присутствует ли в коллекции элемент с заданным значением, можно воспользоваться методом:

        bool Contains(object value);

Если же возникает задача узнать индекс объекта в коллекции, можно использовать метод IndexOf():

        int IndexOf(object value);

Свойство IsReadOnly позволяет узнать, предназначена ли коллекция только для чтения, то есть можно ли изменять число элементов коллекции и значения элементов. Свойство IsFixedSize помогает узнать, можно ли изменять число элементов коллекции после ее создания.

IDictionary

Этот интерфейс описывает методы, которые должны быть у реализаций абстракции «словарь» (ассоциативной коллекции – хранящей пары ключ/значение).

Свойство Описание
IsFixedSize Позволяет узнать, имеет ли данная реализация IDictionary фиксированный размер.
IsReadOnly Позволяет узнать, можно ли модифицировать коллекцию.
Keys Возвращает ссылку на коллекцию (ICollection), содержащую список ключей словаря.
Values Возвращает ссылку на коллекцию (ICollection), содержащую список значений словаря.
Таблица 5. Свойства интерфейса IDictionary.
Метод Описание
Add Позволяет добавить пару ключ/значение к словарю.
Clear Очищает содержимое коллекции.
Contains Позволяет определить, содержит ли коллекция элемент с заданным ключом.
GetEnumerator Возвращает ссылку на перечислитель словаря – интерфейс IDictionaryEnumerator.
Remove Позволяет удалить элемент с заданным ключом.
Таблица 6. Методы интерфейса IDictionary.

Реализации

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

Знание интерфейсов коллекций позволит проще изучать новые виды коллекций, так как они обычно реализуют стандартные интерфейсы.

Массивы

Несмотря на то, что массив находится не в пространстве имен System.Collections, а в пространстве System, можно сказать, что одним из базовых видов коллекций в .NET являются массивы. Массивы поддерживаются средой исполнения (CLR) и являются полноценными объектами во всех языках (кроме разве что MSIL), совместимых с .NET.

Все массивы в .NET считаются наследниками класса System.Array:

[Serializable]
publicabstractclass Array : ICloneable, IList, ICollection, IEnumerable

Любой экземпляр массива обладает свойствами и методами класса System.Array, а также позволяет пользоваться статическими методами этого класса для манипуляций с его содержимым. Так, чтобы узнать размер массива, можно воспользоваться свойством Length:

        int[] ary = newint[2];
Console.WriteLine(ary.Length); // Выведет 2.

Однако декларируемое наследование нельзя понимать так буквально. Невозможно создать наследника System.Array явно (в коде программы). Наследников Array могут создавать только компиляторы и система. Связано это с тем, что в реальности никакого наследования нет. Более того, простые одномерные массивы с нижней границей, равной нулю, поддерживаются непосредственно средой исполнения, и для манипуляции с ними в MSIL имеется специализированный набор инструкций. Например, приведенный выше код будет скомпилирован в следующие MSIL-инструкции:

.locals (int[] ary)
L_0000: ldc.i4.2// Загрузка в стек значения 2.
L_0001: newarr int// Создание массива целых чисел.
L_0006: stloc.0// Запись ссылки на массив в переменную ary.
L_0007: ldloc.0// Загрузка ссылки на массив в стек.
L_0008: ldlen// загрузка в стек количества элементов в массиве
L_0009: conv.i4// Приведение данных лежащих в стеке к int.
L_000a: call Console.WriteLine  // Печать значения.

Обратите внимание на выделенные красным строки. Это специализированные инструкции по работе с массивами, а не методы объекта.

Зачем все это нужно? Все очень просто. Красоты объектной ориентации нужны, чтобы программист мог проще излагать свои мысли. Но объектно-ориентированные изыски (изменение состояния объекта через свойств, методы и т.д.) негативно сказываются на производительности. Ведь массивы, по сути, являются просто областями памяти, и если работать с ними через универсальные объектно-ориентированные обертки, производительность будет настолько низкой, что многих это может отпугнуть. Поэтому компиляторы эмулируют для программиста идеально похожую на настоящую «объектноориентированность», но в то же время генерируют максимально эффективный код. Довершает работу JIT-компилятор, сводящий инструкции по работе с массивами в быстрый и компактный машинный код.

Над созданием ОО-идилии трудится не только JIT-компилятор. В этом процессе участвует и runtime.

Полиморфизм массивов

.NET допускает полиморфизм между массивами, если полиморфизм допустим между типами элементов этих массивов. Так, если есть класс B, производный от класса A, то ссылка на массив типа A (A[]) может быть использована для передачи/хранения ссылки на массив типа B (B[]) точно так же, как отдельная ссылка на объект типа A может быть использована для хранения ссылки на объект типа B. При этом runtime будет контролировать все манипуляции с массивами и не позволит некорректных присвоений. Вот пример, демонстрирующий полиморфное поведение массивов в C#:

          using System;

class A { }
class B : A { }

class Test
{
  staticvoid SetFirstElem(A[] ary, A a)
  {
    ary[0] = a;
  }

  staticvoid Main(string[] args)
  {
    A[] aryA = new A[2];
    B[] aryB = new B[2];

    // Обычное использование.
    SetFirstElem(aryA, new A());
    // Корректное полиморфное использование.
    SetFirstElem(aryB, new B());
    aryB[0] = null;
    // Некорректное использование. Тип элемента несовместим с массивом.// Этот вызов приведет к исключению System.ArrayTypeMismatchException.SetFirstElem(aryB, newA());
  }
}

Второй вызов функции SetFirstElem использует свойства полиморфизма массивов. Третий вызов (выделен в коде) приведет к генерации исключения:

An unhandled exception of type 'System.ArrayTypeMismatchException' occurred in ArrayPoly.exe
Additional information: Attempted to access an element as a type incompatible with the array.

Это происходит потому, что хотя при передаче ссылка на массив с элементами типа В и приводится к ссылке на массив с элементами типа А, но runtime-тип массива все равно остается прежним (т.е. B[]). Представьте, что будет, если поместить в массив с элементами типа В ссылку на экземпляр класса А. Компилятор, уверенный, что в массиве могут храниться только «правильные» элементы, казалось бы, имеет право при доступе к объекту, хранящемуся в массиве, не производить никаких дополнительных проверок. Это может вызвать, например, обращение к несуществующему (в классе А) члену. Чтобы предотвратить неопределенное поведение, runtime пресекает попытки присвоить ячейке массива значение, которое не может быть неявно приведено к типу элемента массива.

К сожалению, такие проверки не могут быть выполнены во время компиляции. Все три вызова функции SetFirstElem будут успешно скомпилированы. Ошибка же возникнет только во время выполнения приложения.

С одной стороны, полиморфизм массивов очень удобен, так как позволяет писать полиморфные алгоритмы, но с другой, это приводит к некоторым накладным расходам (ведь подобные проверки могут быть сделаны только во время исполнения). Подобные проверки делаются только для массивов ссылочных типов. Массивы value-типов ими не отягощаются. Так что если вам нужна скорость, стоит задуматься о массиве структур.

Все массивы в C# унаследованы от базового класса Array, следовательно, и сами реализуют интерфейсы этого класса. Это позволяет приводить ссылку на массив к ссылке на интерфейсы: IList, ICollection, IEnumerable. Это тоже увеличивает полиморфное применение массивов. Однако скорость работы при этом зачастую снижается (почему это происходит, будет сказано чуть позже).

Создание и инициализация массивов

Массивы являются ссылочными типами данных. Это означает, что они могут быть созданы исключительно в GC-хипе (GC – Garbage Collection), а стало быть, создать их можно только динамически. Так, запись

          int ary[2];

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

          int[] ary = newint[2];

При создании массива его можно проинициализировать значениями по умолчанию:

          int[] myArray = newint[]{ 1, 2, 345 };

Массивы простых встроенных типов можно инициализировать по упрощенной схеме:

          int[] myArray = { 1, 2, 345 };

Такая запись может ввести в заблуждение, так как она очень напоминает статическую инициализацию массива в C/C++. Однако на самом деле эта конструкция полностью аналогична предыдущей. Убедиться в этом могут помочь декомпиляторы (вроде Reflector for .NET - или Anakrino).

В отличие от С/С++, в С# скобки, указывающие, что тип данных является массивом, ставятся после типа данных, а не после имени массива. Это позволяет легко и просто описывать массив как тип данных, например:

          int[] GetIntArray();

Даже с первого взгляда понятно, что GetIntArray – это функция, которая возвращает массив целых.

Нижняя граница массивов в C# и VB.NET должна быть равна нулю. В принципе, с помощью методов класса Array можно создать и массив с ненулевой границей, но работать с таким массивом можно будет только с помощью методов этого класса, а это крайне неэффективно.

Массивы можно создать двумя способами. Первый – массив создается с помощью оператора new и квадратных скобок. Второй способ – с использованием методов CreateInstance, принадлежащих классу Array. На практике чаще всего массивы создаются через оператор new. CreateInstance используется, если язык не поддерживает некоторую функциональность (например, вложенных – jagged-массивов). CreateInstance можно использовать также, если необходимо создать массив с заранее неизвестным типом элемента.

Вот самый простой вариант этого метода:

          public
          static Array CreateInstance(Type elementType, int length);

Первым аргументом является тип элементов массива, вторым – количество элементов массива. Таким образом, для создания массива, состоящего, скажем, из пяти целых чисел, можно воспользоваться следующеми конструкциями:

          int[] ary = newint[5];
Array ary = Array.CreateInstance(typeof(Int32), 5);
int[] ary = (int[])Array.CreateInstance(typeof(Int32), 5);

Второй вариант порождает ссылку на абстрактный базовый класс Array. С помощью методов этого класса можно организовать полиморфную работу с массивами любого типа. Например, с помощью его методов GetValue/SetValue можно читать/изменять содержимое массива. Однако нужно всеми правдами и неправдами избегать этого. Дело в том, что скорость такого полиморфного кода будет очень низкой (по крайней мере на сегодня). Как уже говорилось выше, скорость алгоритмов, использующих методы GetValue/SetValue может быть в 100 раз меньше, чем аналогичных с использованием типизированных массивов. Это значительно медленнее, чем даже преобразование массива к массиву объектов:

          object[] objAry = someAry;
object obj = objAry[0];

и работа с ним. Кстати, благодаря свойству полиморфизма массивов такое преобразование возможно... но, к сожалению, не всегда. Такое пребразование возможно для массивов, элементами которых являются ссылочные типы. Так, код:

          object[] objAry = new String[]{ "123", "456" };
object obj = objAry[0];

скомпилируется и беспрепятственно выполнится, а код:

          object[] objAry = newint[] { 123, 456 };

даже не скомпилируется. С помщью явного приведения типа массива к Array можно заставить подобный код скомпилироваться:

          object[] objAry = (object[])(Array)newint[] { 123, 456 };
object obj = objAry[0];

но в момент выполнения runtime сгенерирует исключение «Specified cast is not valid.».

Такая непоследовательность является следствием того, что для value-типов наследование от object эмулируется компилятором. Честно говоря, разработчики .NET Framework и компилятора C# могли бы поглубже скрыть эти некрасивые «уши», но реальность такова, какова она есть, и с ней придется мириться.

Ссылку на Array, в том числе и если она реально указывает на массив value-типов, можно привести к исходному типу. Если массив хранит value-типы, то соответствие должно быть полным. Для массивов с элементами ссылочных типов работают правила полиморфизма.

Для ускорения работы с массивами value-типов вскоре можно будет воспользоваться generic-ами (которые появятся в .NET 1.2, планируемой к выпуску в 2004-ом году). Сейчас же можно делать специализированные версии. Второй подход, мягко говоря, не гибок. Он подразумевает создание специализированных версий кода для каждого поддерживаемого value-типа. Пример, приведенный ниже, демонстрирует описанный подход:

          static
          void ArrayPolymorfFunc(Array ary)
{
  object[] abjAry;
  int[] intAry;
  MyStruct[] myStructAry;
  if ((abjAry = ary asobject[]) != null)
    // Код для массива с элеметами ссылочных типов - abjAry...elseif ((intAry = ary asint[]) != null)
    // Код для массива целых - intAry...elseif ((myStructAry = ary as MyStruct[]) != null)
    // Код для массива MyStruct - myStructAry...else// Полиморфный код с использованием методов SetValue/GetValue...
}

В данном примере одинаковый по смыслу код дублируется четыре раза для массива ссылок, массива целых, массива структур MyStruct и для всех остальных типов. Причем первые 3 варианта выполняются относительно быстро, но не универсальны, а последний - медленный, но универсальный.

Подобным образом извращаться стоит только в тех случаях, когда код потенциально может выполняться в критичных к времени выполнения местах (например, если это библиотечный код). Если полиморфный код принципиально не может выполняться в таких местах (например, он должен срабатывать в ответ на действия пользователя, и всегда работает с небольшим числом элементов), лучше закрыть глаза на его неоптимальность.

Лучшим выбором в данном случае будет использование generic-ов или предопределенной системной функции (вроде Array.Sort или Array.Copy) ведь такие функции обычно оптимизируются для встроенных типов. Но, к сожалению не всегда можно найти подходящую системную функцию. Generic-и же еще не доступны публично. Подробнее о generic-ах будет рассказано в конце этой статьи.

Кроме всего прочего, необходимо заметить, что для создания массива необходимо жестко задать его размер. В дальнейшем размер массива изменен быть не может. Причем, как уже говорилось выше, языками, входящими в .NET, поддерживаются только массивы с верхней границей, равной нулю. Массивы с верхней границей, отличной от нуля, поддерживаются только на уровне runtime-а, методами класса Array.

Если нужно создать массив с ненулевой нижней границей (или многомерный массив, о которых будет сказано ниже), можно воспользоваться следующей формой метода CreateInstance:

          public
          static Array CreateInstance(Type elementType, 
  int[] lengths, int[] lowerBounds);

С помощью этого варианта функции CreateInstance можно создавать и обычные одномерные массивы с нулевой нижней границей. Такие массивы можно привести к типу, поддерживаемому языкм:

          int[] a = (int[])Array.CreateInstance(
   typeof(int), 
   newint[] { 2 }, // Список размеров измерений.newint[] { 0 }  // Нижняя граница для каждого измерения.
  );

Создать многомерный массив можно следующим образом:

Array myIntArray = Array.CreateInstance(typeof(Int32), newint[]{2, 3});

.NET-совместимые языки позволяют работать с многомерными массивами так же просто, как и с одномерными:

          int[,] myIntArray = newint[2, 3];

Однако эффективность работы с многомерными объектами не так высока, как при работе с одномерными массивами, так как доступ к значениям происходит с помощью функций доступа. Это не так ужасно медленно, как использование полиморфного варианта Array.GetValue/Array.SetValue, но все же менее эффективно, чем работа с одномерным массивом. К тому же для многомерных массивов не поддерживаются некоторые операции (например, массовое копирование элементов функцией Array.Copy).

Учитывая все это, лучше стараться избегать использования многомерных массивов. Вместо этого лучше воспользоваться новым (для языков семейства C++) типом массивов – вложенным (jagged). Jagged-array – это массив массивов. Описывается он следующим образом:

          int[][] jaggedArray;

Синтаксис определения вложенных массивов похож на синтаксис определения многомерных массивов в C/C++:

          int cppArray[x][y];

но это совершенно разные вещи. Вложенный массив C# является одномерным массивом, каждый элемент которого, в свою очередь, также является массивом. Отсюда и название «массив массивов». Такое положение дел становится возможным благодаря тому, что в C# (как, впрочем, и в самом .NET) массив стал полноценным типом данных (а не является указателем на первый элемент непрерывной области данных, как это было в C/C++).

Вложенные массивы гибче многомерных массивов, так как позволяют создавать вложенные массивы с различным количеством элементов. Более того, некоторые вложенные массивы вообще могут быть не заданы. В следующем примере создается массив массивов размером 3 элемента, первый вложенный массив которого содержит пять элементов, последний - два, а средний вообще не заполнен:

          int[][] jaggedArray = newint[3][] { newint[5], null, newint[2] };

Ближайшим аналогом вложенных массивов в C++ является использование указателя на указатель на некоторое значение. Вот C++-код аналогичный приведенному выше:

          int ** jaggedArray = newint*[3];

jaggedArray[0] = newint[5];
jaggedArray[1] = NULL;
jaggedArray[2] = newint[2];

Доступ к элементам вложенных массивов очень похож на доступ к элементам многомерных массивов в C++:

          // Получить значение по индексу 1 нулевого подмассива
          int i = jaggedArray[0][1];

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

          // Получаем подмассив с индексом 0...
          int[] tempArray = jaggedArray[0];
// ... Считываем значение по индексу 1 этого подмассива.int i = tempArray[1];

Если попытаться обратиться к неинициализированному подмассиву (в примере выше – это подмассив с индексом 1), то произойдет исключение.

Проинициализировать подмассив можно следующим образом:

jaggedArray[1] = newint[10];

Совершенно все равно, как инициализировать массив – статически (списком параметров) или динамически. Реально любая инициализация будет производиться во время исполнения, так что выиграть в скорости на этом практически невозможно. Однако статический список инициализации выглядит более «читабельно».

Многомерные массивы также можно инициализировать при декларации:

          int[,] array = newint[2, 2] { { 12, 23 }, { 33,44 } }; // Верноint[,] array = newint[2, 2] { new int{ 12, 23 }, { 33,44 } }; // Ошибка

VB.NET и C# имеют приблизительно одинаковые возможности работы с массивами (как вложенными, так и многомерными). Но кое-какие проблемы возникают при использовании MC++ (здесь и далее под MC++ будет пониматься «Managed Extensions for C++» - расширение C++ от Microsoft, позволяющее писать managed-приложения на C++). MC++ вообще не поддерживает вложенных массивов. А для многомерных массивов не подерживает их статической инициализации. Если второе ограничение не страшно, так как всегда можно произвести инициализацию в коде программы, то первое довольно неприятно, но тоже не смертельно. MC++ позволяет работать с вложенными массивами при помощи функций класса Array. Понятно, что это не увеличивает скорость, довольно неудобно и не всегда применимо... но на безрыбье...

Массив в качестве замены функций с переменным количеством параметров

Наверное, будет интересным еще один пример использования массивов. Те, кто писал на С++, наверняка помнят функции с переменным числом параметров, такие, например, как printf. К сожалению, у таких функций был одни существенный недостаток. Они не были типобезопасными. Попросту говоря, контроль над правильностью передачи аргументов ложился целиком на программиста. Причем не было практически никаких средств контроля над правильностью выполняемых действий. В C# эта проблема решена намного эстетичнее. Для создания функций с переменным числом параметров в С# существует ключевое слово params. Оно используется только в списке передаваемых методу параметров и является модификатором передаваемого аргумента. Применение этого модификатора означает, что за ним следует аргумент, представляющий собой массив. В этом массиве и содержится список параметров переменной длины. Количество параметров равно числу элементов массива. Модификатор params может применяться только к последнему аргументу функции. Массив (как и другие встроенные массивы C#) может содержать элементы только одного типа. Но то, что элемент любого типа может быть приведен к object, позволяет создавать функции с переменным числом параметров любого типа. Причем, в отличие от C/C++, код получается типобезопасным, так как тип object позволяет получить в runtime-е описание типа хранящегося в нем объекта.

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

Ниже приведен пример функции с переменным числом параметров (функции Print). Заметьте, что эта функция получает массив ссылок на базовый класс object. Это позволяет ей работать с элементами любого типа. Например, элементами массива при втором вызове функции являются целое число, два числа с плавающей точкой, символ и строка.

Итак, пример:

          using System;

namespace ArrayTest
{
  class Class1
  {
    staticvoid Print(params Object[] ary)
    {
      if (ary == null)
      {
        Console.WriteLine("Argument is null.");
        return;
      }

      if (ary.Length == 0)
      {
        Console.WriteLine("The number of arguments is 0.");
        return;
      }

      foreach (Object obj in ary)
      {
        if (obj is String || obj ischar)
          Console.Write("'{0}' ", obj);
        else
          Console.Write("{0} ", obj);
      }

      Console.WriteLine();
    }

    staticvoid Main(string[] args)
    {
      Print(1, 2, 7);
      Print(17, 5.25, 1.44, 'c', "rsdn.ru");

      int[] intArray = { 1, 2, 345 };
      Print(intArray);
      object[] objArray = { 1, 2, 345 };
      Print(objArray);

      Print();
      Print(null);

      Console.WriteLine("...");
      Console.ReadLine();
    }
  }
}

Ниже приведен результат работы этого примера:

1 2 7
17 5.25 1.44 'c' 'rsdn.ru'
System.Int32[]
1 2 345
The number of arguments is 0.
Argument is null.
...

Кроме того, еще одной особенностью, отличающей массивы в С# от привычных всем массивов, является возможность создания массивов с ненулевой нижней границей. К сожалению, создать такой массив при помощи оператора [] не удастся, нужно использовать метод CreateInstance. Ниже приведен пример создания массива с ненулевой нижней границей:

          int[] lengths = newint[] { 3, 5 };
int[] bounds  = newint[] { 2, 3 };
Array myCuctomBoundArray = Array.CreateInstance(typeof(String), 
  lengths, bounds);

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

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

Свойства и методы класса Array

Все массивы реализуют интерфейсы ICloneable, IList, ICollection, IEnumerable. Это, с одной стороны, позволяет работать с массивами полиморфно, а с другой, обеспечивает богатый набор методов, позволяющий манипулировать массивами. Наиболее часто используемым свойством является Length. Например, инициализировать все элементы массива в цикле можно следующим образом:

          for (int i = 0; I < ary.Length; i++)
  ary[i] = i * 2;

Перебрать содержащиеся в массиве значения можно с помощью оператора foreach:

          foreach (i in ary)
  Console.WriteLine(i);

Как уже говорилось в разделе, посвященном интерфейсу IEnumerable, для массивов подобный код не приводит к использованию этого интерфейса, а превращается компилятором в цикл на базе for.

Для манипуляций с содержимым массивов можно использовать как обычные свойства и методы, так и статические. В таблице 6 приведен список статических членов класса System.Array.

Метод Описание
BinarySearch Осуществляет поиск заданного значения в одномерном отсортированном массиве с использованием алгоритма бинарного поиска.
Clear Устанавливает значения элементов массива или заданного диапазона элементов в нуль (false или NULL, в зависимости от типа элемента).
Copy Копирует диапазон одного массива в другой. Осуществляет преобразование типов и боксинг при необходимости. Подобно функции memmove из CRT Copy корректно обрабатывает ситуацию с перекрытием областей памяти и может использоваться для копирования элементов в рамках одного массива. Copy – это самый эффективный способ копирования данных.
CreateInstance Позволяет динамически создать новую копию массива (объекта типа Array).
IndexOf Возвращает индекс первого вхождения значения в одномерном массиве или диапазоне значений. Поиск производится простым перебором.
LastIndexOf Возвращает индекс последнего вхождения значения в одномерном массиве или диапазоне значений. Поиск производится перебором.
Reverse Меняет порядок следования элементов массива или диапазона на обратный.
Sort Сортирует элементы в одномерном массиве (с помощью алгоритма QuickSort).
Таблица 7. Статические члены класса System.Array.

Большинство программистов считает, что методы системных библиотек и встроеных классов (к которым и относятся массивы в .NET) реализованы оптимально, и что используя их, можно рассчитывать на максимальную производительность. К сожалению, не всегда это так. Из перечисленных выше методов только к Copy нет нареканий по части производительности.

ПРИМЕЧАНИЕ

Напомню, что речь идет о .NET Framework версий от 1.0 до 1.2.30703 (версии .NET Framework, представленной на PDC 2003). Возможно, что в будущем ситуация изменится.

Без зазрения совести можно использовать также CreateInstance. Эта функция хотя и медленнее использования оператора new, но незначительно. Она всего лишь получает тип массива и передает управление runtime-у. Общая потеря в скорости CreateInstance по сравнению с использованием оператора new составляет 1.5-4 раза (в зависимости от размера массива и типа его элементов).

Остальные функции показывают разную производительность в зависимости от данных, хранимых в массиве, и некоторых других условий. Все эти функции выполнены по следующей схеме:

  1. Сначала производится проверка параметров. Эта операция отнимает совсем чуть-чуть времени, и на нее не стоит обращать внимания.
  2. Далее, если пользователем не задан специализированный интерфейс сравения – IComparer (если таковой может быть задан), вызывается специальная, реализованная на unmanaged C++, функция. Она имет имя, формируемое по схеме TrySZXxx (где Xxx – это имя функции, например, Sort, если дело происходит внутри функции Sort). Эта функция определяет, не является ли тип данных элементов массива встроенным (вроде int или double). Если является, процедура для выполнения операции вызывает специализированную (предназначенную для конкретного типа данных) unmanaged-версию функции. В случае успешного выполнения операции функция возвращает true. На этом работа функции Xxx завершается.
  3. Если TrySZXxx вернула false, производится попытка привести ссылку на массив к ссылке на массив объектов (object[]). Если это удается, необходимая операция производится над этим массивом. Как уже говорилось выше, к object[] можно привести ссылку на массивы, элементы которых являются ссылочными типами.
  4. Если на шагах 2 и 3 требуемую операцию произвести не удалось, операция производится с помощью методов Array.GetValue и Array.SetValue.

Функции TrySZXxx – это добротный C++-код, имеющий очень приличную производительность. Единственный их недостаток – множество лишних действий. Скорость этих функций, в зависимости от версии .NET Framework, в 1.4-3 раза меньше, чем может продемонстрировать аналогичная функция, написанная на C# «в лоб» (для конкретного типа с inline-проверками и сравнениями).

Скорость работы с массивами, которые можно привести к object[] (т.е. массивами с элементами ссылочных типов), тоже довольно высока. По сути, разница заключается только в том, что для сравнения элементов используется виртуальный вызов (Compare), производятся лишнее приведение типов и несколько лишних проверок. Все это влияет на производительность довольно слабо.

А вот если дело дошло до пункта 4, производительность страдает значительно сильнее. Вследствие использования Array.GetValue и Array.SetValue скорость работы не выдерживает никакой критики. В определенных обстоятельствах она может быть более чем в 100 раз (!) ниже, чем у «лобового» алгоритма, написанного на C#. Поэтому следует любыми путями избегать использования таких методов, если в массиве хранятся структуры, или если требуется нестандартный механизм сравнения. Естественно, что эти слова верны, только если код не вызывается в совершенно некритичных ко времени местах, и не работает с маленькими объемами данных.

Все статические методы класса System.Array принимают ссылку на массив, приведенную к System.Array.

У Array есть также несколько нестатических методов. Они перечислены в таблице 7.

Метод Описание
Clone Создает копию (клон) массива. При этом происходит так называемое неглубокое клонирование. Копируется только содержание самого массива. Если массив содержит элементы ссылочного типа, или структуры, содержащие ссылки, эти ссылки будут указывать на те же объекты, что и в основном массиве.
CopyTo Копирует все элементы текущего одномерного массива в указанный одномерный массив.
GetLength Возвращает число элементов в указанном измерении массива в виде 32-битного целого.
GetLongLength Возвращает число элементов в указанном измерении массива в виде 64-битного целого.
GetLowerBound Возвращает нижнюю границу указанного измерения.
GetUpperBound Возвращает верхнюю границу указанного измерения.
GetValue Возвращает значение указанного элемента массива. Индексы определяются как 32-битовые целые.
SetValue Позволяет установить значение указанного элемента массива.
Таблица 8. Нестатические методы класса System.Array.

Все перечисленные в таблице 14 методы (за исключением GetValue и SetValue) работают очень быстро. GetValue и SetValue работают крайне медленно. Трудно сказать, что конкретно тормозит их работу. Скорее всего, разработчики CLR не проявили должной заботы при реализации этих методов. Учитывая их важность и частоту применения в других методах класса System.Array, можно было уделить этим методам больше внимания. Возможно, не грех было бы даже вмонтировать их поддержку в JIT-компилятор. А пока что придется принять их медлительность как данное и постараться избегать их использования. Также стоит помнить, что эти методы могут быть вызваны и неявно. Вероятность этого увеличивается, если вы пользуетесь массивами структур.

В таблице 9 приведен список свойств класса System.Array.

Название Описание
Length Возвращает общее число элементов во всех измерениях массива в виде 32-битного целого.
LongLength Возвращает общее число элементов во всех измерениях массива в виде 64-битного целого.
Rank Возвращает количество измерений массива.
SyncRoot Возвращает объект, который может быть использован для синхронизации доступа к массиву. Для массивов – это сам массив.
Таблица 9. Свойства класса System.Array.

Скорость доступа к свойствам System.Array не вызывает нареканий.

Как уже было сказано выше, System.Array реализует интерфейс IList. Это позволяет использовать массивы везде, где требуется нередактируемая коллекция. Вследствие того, что при эмуляции IList приходится пользоваться средствами полиморфизма (приведением к object и методами GetValue/SetValue), скорость получается очень низкой.

Достоинства и недостатки массивов

К достоинствам массивов можно отнести высокую скорость доступа к их элементам по индексу и типизированность. Первое позволяет создавать код, почти не уступающий по скорости коду, созданному лучшими оптимизирующими компиляторами (такими, как VC++ 7.1 и Intel C++ 7.0). По адресу http://rsdn.ru/summary/590.xml можно найти серию статей, сравнивающих производительность различных средств разработки. Обратите внимание на тест QuickSort. В нем производится интенсивный доступ к массиву целых чисел. Причем благодаря тому, что массивы в CLR являются полноценными объектами, работать с ними значительно проще, чем с массивами в C++. Второе преимущество позволяет создавать надежный код. CLR контролирует выход за пределы массива и корректность обращения к его элементам. Подобную функциональность в C++ можно получить только при использовании классов-оберток вроде std::vector, CAtlArray или CArray (из MFC). Причем не все реализации таких оберток обеспечивают надлежащий контроль, а те, что обеспечивают, делают это обычно только в отладочном режиме. Еще одним достоинством типобезопасности при работе с массивами в CLR является то, что при этом используются только верифицируемые инструкции MSIL и отсутствует прямое использование адресной арифметики. Это позволяет не только обеспечить более надежную работу приложения, но и гарантирует, что работа с массивами не сможет стать лазейкой в системе безопасности (что так часто случалось в мире C/C++).

Однако нет совершенства в этом мире. Не являются им и массивы в CLR. Так, они не поддерживают динамического изменения размера (для этого придется занимать новый, больший или меньший, массив, и копировать в него элементы из старого), не поддерживаются ассоциативные массивы, да и вообще их прямое применение не всегда удобно. Для облегчения жизни разработчика в .NET были введены специальные классы коллекций. Все они размещаются в пространстве имен System.Collections. Собственно, о них уже говорилось выше. Настала пора познакомиться с ними поближе. Начнем с класса ArrayList.

ArrayList

Очень часто случается так, что размер массива неизвестен заранее. Именно в таких случаях удобно использовать класс ArrayList. ArrayList – это динамический одномерный массив, т.е. массив, позволяющий динамически менять свой размер. ArrayList реализует абстракцию «список» (интерфейс IList):

[Serializable]
publicclass ArrayList : IList, ICollection, IEnumerable, ICloneable

В качестве хранилища данных в ArrayList используется скрытый массив ссылок на object (object[]). Этот массив обычно имеет размер больший, нежели число хранящихся в ArrayList элементов. Реальное количество элементов, хранящихся в данный момент в ArrayList, можно узнать из свойства Count. По сути, оно аналогично свойству Length обыкновенных массивов. Получить доступ к элементам можно с помощью индексатора. И Count, и индексатор объявлены в интерфейсе IList и реализованы как публичные свойства. Собственно, все методы и свойства IList реализованы как публичные, так что их можно использовать, не производя приведение к IList. Это делает работу с ArrayList проще. IList уже был описан выше, поэтому я пропущу описание этих методов.

Кроме количества элементов, ArrayList оперирует понятием емкость (Capacity). Емкость – это реальный размер внутреннего массива, хранящего данные. Емкость не может быть меньше количества элементов. Пока емкости хватает, перезаем памяти под внутренний массив не производится. Если при вставке новых элементов емкости не хватает, происходит ее увеличение. Делается это путем присвоения свойству Capacity значения, вдвое большего, чем текущеее значение этого же свойства. При изменении значения свойства Capacity создается новый внутренний массив необходимого размера, и в него копируются данные из старого массива. Естествнно, все эти действия выполняются классом ArrayList автоматически.

Таким образом, если из ArrayList не производилось удалений, емкость всегда лежит в пределах от количества элементов до количества элементов * 2. Увеличение удвоением с одной стороны, минимизирует количество перезаемов памяти (это довольно медленная операция), а с другой - обеспечивает приемлемый расход памяти.

Если вам кажется, что объем памяти, занятой под внутренний массив, избыточен (например, вы произвели большое количество вставок, а потом удалили большое количество элементов), всегда можно уменьшить объем занятой памяти, вызвав метод TrimToSize(). Этот метод перезанимает память, делая емкость массива равной его размеру. Лучше не злоупотреблять этой возможностью, так как эта операция требует относительно большого времени, а GC все равно не освободит память до следующей сборки мусора. Вместо этого лучше при удобном случае пересоздать весь массив. В большинстве алгоритмов этот прием также позволяет упростить код.

Перед использованием ArrayList, как и в случае любого другого класса, нужно создать его экземпляр. Если в этот момент вам известно (хотя бы приблизительно), каков будет максимальный размер массива, то лучше всего указать емкость в качестве параметра конструктора:

ArrayList array = new ArrayList(100);

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

Если при создании ArrayList не задать емкость, при первой вставке она будет установлена в значение 16.

Если нужно скопировать элементы из другой коллекции, можно воспользоваться конструктором:

        public ArrayList(ICollection c);

При этом будет установлена емкость, равная количеству элементов. Это удобно, если ArrayList используется для массовых добавлений элементов или только для чтения. Если в массив планируется добавить пару-другую элементов, то это не лучший выход, так как первый же добавленый элемент увеличит емкость в двое. В целях экономии памяти в таких случаях лучше создать ArrayList, задав необходимую емкость, после чего скопировать элементы вызовом:

        public
        virtual
        void AddRange(ICollection c);

Этот метод, как и предыдущий конструктор, добавлет в ArrayList элементы из другой коллекции. Вот пример такой инициализации:

        string[] someList = newstring[]
{
  "Основной элемент 1",
  "Основной элемент 2",
  "Основной элемент 3",
  "Основной элемент 4",
  "Основной элемент 5",
  "Основной элемент 6",
};

// Следующая строка функционально аналогична двум// идущим за ней, но приводит к большему расходу памяти.//ArrayList arrayList = new ArrayList(someList);
ArrayList arrayList = new ArrayList(someList.Length + 3);
arrayList.AddRange(someList);

arrayList.Add("Дополнительный элемент 1");
arrayList.Add("Дополнительный элемент 2");
arrayList.Add("Дополнительный элемент 3");

// Выводим содержимое arrayList на консоль..for (int i = 0; i < arrayList.Count; i++)
  Console.WriteLine(arrayList[i]);

Console.WriteLine("Capacity={0}, Count={1}", 
  arrayList.Capacity, arrayList.Count);

Этот пример выведет на консоль:

Основной элемент 1
Основной элемент 2
Основной элемент 3
Основной элемент 4
Основной элемент 5
Основной элемент 6
Дополнительный элемент 1
Дополнительный элемент 2
Дополнительный элемент 3
Capacity=9, Count=9

Если заменить выделенные красным строки (раскомментировать первую и закомментировать две, идущие за ней), Capacity изменится на 12 (6 * 2).

Подобные приемы особенно полезны, если массив предназначен для долгого хранения, и исходная коллекция довольно велика, или если подобные операции производятся в цикле (ведь иначе память будет расходоваться понапрасну, и GC ничем не сможет вам помочь).

AddRange и конструктор, принимающий ссылку на ICollection, работают очень резво, так как используют для копирования данных функцию System.Array.Copy().

ПРИМЕЧАНИЕ

Метод Add является реализацией метода IList.Add. Методы интерфейса IList уже были описаны выше, поэтому я пропущу их описание.

Если требуется вставить содержимое коллекции в произвольное место, можно воспользоваться методом:

        public
        virtual
        void InsertRange(int index, ICollection c);

Чтобы удалить некоторый диапазон элементов, можно воспользоваться методом:

        public
        virtual
        void RemoveRange(int index, int count);

Если требуется переписать некоторый диапазон значений значениями из другой коллекции, лучше всего воспользоваться методом:

        public
        virtual
        void SetRange(int index, ICollection c);

Если количество элементов ArrayList меньше, чем сумма index и количества элементов в коллекции c, будет выдано исключение.

Получить значение элементов диапазона массива можно при помощи методов:

        public
        virtual ArrayList GetRange(int index, int count);

Иногда нужно передать список в метод, благонадежность которого не вызывает доверия. Чтобы обезопаситься, можно получить класс-обертку, предотвращающую добавление или удаление элементов из коллекции или вообще предотвращающую редактирование. Для этого предназначены статические функции:

        public
        static ArrayList FixedSize(ArrayList list);
publicstatic IList FixedSize(IList list);
publicstatic ArrayList ReadOnly(ArrayList list);
publicstatic IList ReadOnly(IList list);

Соотвественно FixedSize позволяют создать коллекцию-обертку, запрещающую изменять количество элементов, а ReadOnly – вообще запрещающую модификацию коллекции (заменять ее элементы). У обоих методов есть варианты, возвращающие обертки в виде IList и ArrayList.

В отличие от IList, у ArrayList есть множество удобных методов. Немудрено, что возникает желание заполучить эти методы для имеющейся ссылки на IList. Функция:

        public
        static ArrayList Adapter(IList list);

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

ArrayList реализует несколько вариаций метода CopyTo(), копирующих данные из ArrayList в некоторый массив. Одна является реализацией аналогичного метода интерфейса IList. Остальные позволяют производить копирование данных более гибко:

        public
        virtual
        void CopyTo(Array array);
publicvirtualvoid CopyTo(int index, Array array, int arrayIndex, int count);

Думаю, их описания говорят сами за себя.

Зачастую ArrayList используется в качестве промежуточного массива, в котором идет накопление элементов. После того, как заканчивается формирование массива, бывает удобно преобразовать его в типизированный массив. Это позволяет повысить типобезопасность и скорость. Сделать это можно двумя способами. Первый – воспользоваться методами CopyTo (о которых уже говорилось выше). Второй – воспользоваться методами:

        public
        virtual
        object[] ToArray();
publicvirtual Array ToArray(Type);

Оба они создают массив нужного размера и копируют туда элементы из внутреннего массива. Причем оба они делегируют работу методу Array.Copy. Разница между ними заключается в том, что первый массив всегда создает массив object[], а второй – массив с типом элемента, соотвествующим переданному типу (с помощью функции Array.CreateInstance). Пример использования этого метода можно найти в функции Parse из раздела «Пример использования класса Hashtable».

Если необходимо создать новый объект класса ArrayList и проинициализировать его элементы каким-то одним значением, можно воспользоваться методом:

        public
        static ArrayList Repeat(object value, int count);

Ничего интеллектуального этот метод не делает. Он просто создает экземпляр ArrayList и в цикле добавляет значение, переданное в параметре value. В общем, способ сэкономить пару строк кода.

Изменить порядок следования элементов на обратный можно с помощью методов:

        public
        virtual
        void Reverse();
publicvirtualvoid Reverse(int index, int count);

Второй вариант позволяет «перевернуть» диапазон элементов.

Получить индекс некоторого элемента по его значению можно с помощью методов:

        public
        virtual
        int IndexOf(object value);
publicvirtualint IndexOf(object value, int startIndex);
publicvirtualint IndexOf(object value, int startIndex, int count);

Методы LastIndexOf делают то же самое, что и IndexOf, но поиск производится в обратном направлении (начиная с конца):

        public
        virtual
        int LastIndexOf(object value);
publicvirtualint LastIndexOf(object value, int startIndex );
publicvirtualint LastIndexOf(object value, int startIndex, int count);

Если необходимо отсортировать массив, можно воспользоваться одним из трех методов:

        public
        virtual
        void Sort();
publicvirtualvoid Sort(IComparer comparer);
publicvirtualvoid Sort(int index, int count, IComparer comparer);

Параметр comparer позволяет задать объект, с помощью которого будет производиться сравнение элементов массива. Это позволяет изменять критерии сортировки, не изменяя код классов хранимых элементов. Например, для строк можно применять объекты, производящие сравнения, зависимые, или наоборот, независимые от регистра.

Если массив отсортирован, то для поиска какого-то значения в нем можно воспользоваться методами:

        public
        virtual
        int BinarySearch(object value);
publicvirtualint BinarySearch(object value, IComparer comparer);
publicvirtualint BinarySearch(int index,
                                int count,
                                object value,
                                IComparer comparer);
СОВЕТ

Методы: Reverse, IndexOf, LastIndexOf, Sort и BinarySearch просто делегируют вызов аналогичным методам класса System.Array, передавая им внутренний массив и производя необходимые вычисления индексов и т.п.

Если вам интересны особенности их работы, загляните в раздел, посвященный встроенным массивам.

Достоинства и недостатки ArrayList

К достоинствам ArrayList можно отнести:

  1. Возможность динамического изменения размера массива.
  2. Высокую скорость доступа по индексу.
  3. Высокую скорость добавления в конец и удаления последних элементов.
  4. Полиморфность. В массиве можно хранить элементы разных типов. Однако это достоинство очень спорно (см. список недостатков).

К недостаткам:

  1. Необходимость постоянного приведения типов при доступе к элементам. И как следствие, меньшую надежность и небольшое уменьшение производительности.
  2. Существенное снижение проивзодителоности при хранении value-типов вследствие необходимости boxing-а и unboxing-а при доступе к элементам.
  3. Низкую производительность в алгоритмах, производящих большое количество вставок и удалений в середину (не в конец) списка. Это происходит потому, что при вставке в середину необходимо производить смещение диапазона элементов, начинающегося с позиции вставки и заканчивающегося концом массива. Особенно неприятно этот недостаток проявляется при увеличении размера массива. В таких случаях нужно применять специальные варианты динамических массивов, хранящие данные в отдельных слотах. К сожалению, в FCL подобные коллекции не входят (об этом чуть позже).
  4. Необходимость перезаема памяти при привышении имеющейся емкости.

Пример использования ArrayList можно найти в функции Parse из раздела «Пример использования класса Hashtable».

Stack

Stack – это простая коллекция, реализующая идеологию LIFO (последним пришел – первым ушел). С ее помощью, например, удобно превращать рекурсивные алгоритмы в циклические. Так, при обходе дерева в нем можно хранить текущий путь обхода. Вот описание класса Stack:

[Serializable()]
publicclass Stack : ICollection, ICloneable

Как видите, он, так же, как ArrayList, реализует интерфейсы ICollection и ICloneable. Таким образом, Stack можно клонировать, а его содержимое можно скопировать во внешний массив.

Основные методы этой коллеции:

        public
        virtual
        void Push(Object obj);

Помещает объект на вершину стека.

        public
        virtual Object Pop();

Извлекает объект из стека и сдвигает внутренний указатель на предыдущий элемент.

        public
        virtual Object Peek();

Позволяет получить объект с вершины стека, но не изменять при этом внутренний указатель.

Как и ArrayList, Stack реализован на базе массива объектов (object[]). Как и ArrayList, Stack имеет три конструктора:

        public Stack();
public Stack(int initialCapacity);
public Stack(ICollection col);

Копирующий конструктор производит копирование по одному элементу, используя для перебора элементов исходной коллекции ее перечислитель (IEnumerable). Все плучаемые элементы помещаются в стек операцией Push. Это сделано для того, чтобы при копировании элементов исходной коллекции поменять порядок элементов на обратный. Пример, приведенный ниже, демонстрирует это поведение:

        static
        void Main()
{
  // Инициализируем стек значениями из массива целых чисел.
  Stack stack1 = new Stack(newint[] { 1, 2, 3, 4, 5 });
  Print("stack1", stack1); // Печатаем содержимое первого стека.// Инициализируем второй стек значениями из первого.
  Stack stack2 = new Stack(stack1);
  Print("stack2", stack2); // Печатаем содержимое второго стека.
}

// Процедура печати коллекции.staticvoid Print(string str, IEnumerable en)
{
  Console.Write("{0}:  ", str);
  foreach (object o in en)
    Console.Write("{0} ", o);
  Console.WriteLine();
}

Этот пример выводит на консоль следующие результаты:

stack1: 5 4 3 2 1
stack2: 1 2 3 4 5

Как видно, элементы выводятся в разном порядке. Подобное поведение можно использовать для переворота элементов коллекций. В разделе, посвященном BitArray, это поведение стека используется для переворота списка битов (в целях отображения битов справа налево).

Count – это реализация свойства ICollection.Count. Как и в ArrayList, все свойства и методы этого интерфейса реализованы как публичные и виртуальные. Метод ICollection.CopyTo реализован аналогично итератору, т.е. тоже меняет порядок элементов на обратный. Таким образом, следующий код:

Stack stack1 = new Stack(newint[] { 1, 2, 3, 4, 5 });
Print("stack1", stack1);
int[] ary = newint[stack1.Count];
stack1.CopyTo(ary, 0);
Print("ary", ary);

Выведет на консоль следующий результат:

stack1: 5 4 3 2 1
ary:    5 4 3 2 1

Следует избегать использования метода CopyTo, если используется массив value-типов, так как при этом для доступа к элементам массива будет применяться медленный метод Array.SetValue.

Если нужно проверить, содержит ли стек некоторое значение, можно воспользоваться методом:

        public
        virtual
        bool Contains(Object obj);

Как и в случае с ArrayList, для Stack-а можно получить его синхронизированную версию:

        public
        static Stack Synchronized(Stack stack);

Преобразовать содержимое стека в массив объектов (object[]) можно с помощью следующего метода:

        public
        virtual Object[] ToArray();

Queue

Queue (очередь) реализует другой принцип работы с коллекциями – FIFO (первым пришел – первым ушел). Очереди обычно используются там, где нужна последовательная обработка данных. Клиенты помещают данные (обычно их при этом называют сообщениями) в очередь, а обработчик извлекает и обрабатывает эти данные. Вот описание класса Queue:

[Serializable()]
publicclass Queue : ICollection, ICloneable

Как видите, очередь тоже реализует интерфейс коллекции и клонирования.

Интерфейс Queue является почти полной копией класса Stack, за исключением того, что вместо методов Push и Pop он реализует методы:

        public
        virtual
        void Enqueue(Object obj);

и:

        public
        virtual Object Dequeue();

Enqueue помещает значение в очередь, а Dequeue извлекает.

Думаю, никто не удивится, если я скажу, что и очередь в FCL реализована на базе массива. Но используется этот массив несколько иначе. В Queue используется так называемый кольцевой буфер, т.е. вместо того, чтобы все время помещать данные в конец внутреннего массива, в Queue заведены специальные указатели хвоста и головы очереди. Таким образом, вместо того, чтобы сдвигать данные при каждом помещении/извлечении данных, происходит смещение головы и хвоста. Если количества элементов во внутреннем массиве недостаточно для размещения новых элементов, происходит увеличение емкости. В отличие от стека, задать значение емкости для очереди можно только в момент ее создания. Зато класс Queue обладает (как и ArrayList) методом TrimToSize, обрезающим емкость по количеству элементов, находящихся в этот момент в очереди. Кроме того, Queue позволяет задать так называемый фактор расширения (growFactor), определяющий насколько будет домножаться текущее значение емкости при расширении внутреннего массива. По умолчанию значение фактора расширения является равным 2.0, т.е. происходит расширение удвоением. Это значение должно лежать в пределах от 1.0, до 10.0 (включительно).

BitArray

В отличие от C++, в C# и VB.NET отсутствуют структуры с битовыми полями. Поэтому средствами языка на уровне битов можно работать только с помощью битовых операций (&, |, ~, ^ в C# и And, Or, Not, Xor в VB.NET). К тому же даже наличие битовых полей не спасало C++-программистов, если нужно было работать с битовыми полями переменной длины. Чтобы упростить работу с наборами битов, в FCL был добавлен класс BitArray. Этот класс хорош тем, что позволяет работать с наборами битов переменного размера. Я использовал BitArray, когда мне нужно было создать алгоритм сериализации DataSet-а (если вы еще не знаете, что это такое, загляните в соответствующий раздел этой статьи). Некоторые поля строк DataSet-а могут содержать пустые значения. Чтобы не тратить драгоценного места на хранение null-значений, я решил записывать перед каждой строкой DataSet-а битовое поле, биты которого соответствуют колонкам DataSet-а. Если бит поднят –соотвествующие данные сериализуются. Если нет, данные не сериализуются. Так как количество колонок в разных DataSet-ах различаются, то и битовые поля должны были иметь разную длинну. Тут то и пригодился BitArray. Вот описание этого класса:

[Serializable()]
publicsealedclass BitArray : ICollection, ICloneable

Как и все коллекции, BitArray реализует интерфейсы ICollection и ICloneable. Однако семантика методов несколько отличается, но об этом чуть позже.

Физически массив битов хранится в массиве целых (int[]), т.е. первые 32 бита хранятся в первом элементе массива, вторые – во втором, и так далее.

Количество учитываемых битов хранится в BitArray отдельным полем и доступно на чтение/запись через свойство Length и на чтение через свойство Count (публичную реализацию ICollection.Count). Запись в элемент с индексом, превышающим размер массива, невозможна даже в том случае, если в последнем элементе массива-хранилица есть свободные биты. В случае выхода за пределы диапазона будет выдано исключение System.ArgumentOutOfRangeException.

У BitArray есть несколько конструкторов. Первый конструктор позволяет создать битовый массив заданной длины, при этом значение каждого бита будет false (биты будут установлены в 0):

        public BitArray(int length);

Второй конструктор также позволяет создать битовый массив заданной длины, но еще и позволяет определить начальное значение битов в создаваемом массиве (все биты устанавливаются в значение заданное параметром defaultValue):

        public BitArray(int length, bool defaultValue);

Чтобы задать значения для каждого бита битового массива можно воспользоваться следующими видми конструкторов:

        public BitArray(bool[] values);
public BitArray(int[] values);
public BitArray(byte[] bytes);

Первый конструктор устанавливает биты в соответствии со значениями ячеек массива values. Одно булево значение задает один бит. Первый элемент массива задет первый бит, второй – второй и т.д.

Второй и третий конструкторы производят побитовое копирование данных соотвественно из массива целых и байтов.

Применяя последние два вида конструкторов не трудно запутаться, так как биты обычно считаются справа налево. К тому же в целом (на процессорах Intel) байты располагаются в обратном порядке. Вот пример, демонстрирующий эти особенности:

        bool[] ary = newbool[] 
{
  true,  false,  true, false, false, false, false, false,
  false, false, false, false, false, false, false, false,
  false, false, false, false, false, false, false, false,
  false, false, false, false, false, false, false, false,

  false, false, false, false, false, false, false, false,
  false, false, false, false, false, false, false, false,
  false, false, false, false, false, false, false, false,
  false, false, false, false, false, false, false, true,
};

BitArray bits = new BitArray(ary);
Print(bits);

...

// Выводит на консоль содержимое массива битовstaticvoid Print(BitArray bits)
{
  // Выводим биты слева направо...
  PrintBits(bits, false);
  // ... и справа налево.
  PrintBits(bits, true);
  // Выводим содержимое коллекции bits в виде набора байтов.
  PrintBytes(bits);
  // Выводим содержимое коллекции bits в виде набора целых.
  PrintInts(bits);
}

// Выводит биты из bits в порядке слева направо, если// rightToLeft задан в false, и справа налево, если в true.staticvoid PrintBits(BitArray bits, bool rightToLeft)
{
  Console.WriteLine("биты {0}:", rightToLeft 
    ? "(справа налево, классический вид)" : "(как есть)");
  int cnt = 0;

  // Если требуется вывести биты справа налево, // переворачиваем список с помощью копирования его // в стек. Пользуемся полиморфизмом коллекций// для устранения различий между стеком и массивом битов.
  ICollection collection = rightToLeft
    ? (ICollection)new Stack(bits) : bits;

  // Значения отдельных битов BitArray-ем представляются // как значения типа bool.foreach (bool b in collection)
  {
    // Отделяем каждые 32 бита пробеломif (cnt != 0 && cnt % 32 == 0)
      Console.Write(" ");
    cnt++;
    // Выводим значение по одному биту.// В C# bool не приводится к int ни под каким соусом.// Поэтому приходится использовать оператор ? :
    Console.Write("{0}", b ? 1 : 0);
  }
  Console.Write("b");

  Console.WriteLine();
}

// Выводить содержимое bits в виде отдельных байтовstaticvoid PrintBytes(BitArray bits)
{
  Console.WriteLine("байты:");

  // Рассчитываем необходимый размер массива байтов и создаем массив.int size = bits.Length / 8;
  byte[] bytes = newbyte[size];
  // Копируем содержимое BitArray в новый массив.
  bits.CopyTo(bytes, 0);

  int cnt = 0;
  // Выводим значения по одному байту.foreach (byte bt in bytes)
  {
    // Отделяем каждые четыре байта (32 бита) отступом.if (cnt != 0 && cnt % 4 == 0)
      Console.Write("             ");
    cnt++;
    Console.Write("0x{0:x2} ", bt);
  }

  Console.WriteLine();
}

// Выводить содержимое bits в виде отдельных целых void PrintInts(BitArray bits)
{
  Console.WriteLine("целые:");

  // Рассчитываем необходимый размер массива целых и создаем массив.int size = bits.Length / 32;
  int[] ints = newint[size];
  // Копируем содержимое BitArray в новый массив.
  bits.CopyTo(ints, 0);

  // Выводим значения по 32 бита.foreach (int i in ints)
    Console.Write("0x{0:x8}                       ", i);

  Console.WriteLine();
}

В этом примере массив битов инициализируется массивом логических значений (bool[]). Затем содержимое битового массива выводится на консоль в виде списка битов, массива байтов и массива целых. Этот пример выводит на консоль:

биты (как есть):
10100000000000000000000000000000 00000000000000000000000000000001b
биты (справа налево, классический вид):
10000000000000000000000000000000 00000000000000000000000000000101b
байты:
0x05 0x00 0x00 0x00              0x00 0x00 0x00 0x80
целые:
0x00000005                       0x80000000

Обратите внимание на представление содержимого битового массива в байтах и целых! Красным подсвечены установленные биты. Сравните их с исходным массивом bool-значений. Все это не более, чем обман зрения, возникающий из-за особенностей отображения битов.

Если нужно создать копию массива битов, можно воспользоваться копирующим конструктором:

        public BitArray(BitArray bits);

или методом:

        public Object Clone(); // реализация ICloneable.Clone()

Чтобы установить значение всех битов массива уже после его создания, можно воспользоваться методом:

        public
        void SetAll(bool value);

Задать значение отдельного бита можно с помощью метода:

        public
        void Set(int index, bool value);

Соотвественно узнать значение некоторого бита можно с помощью метода:

        public
        bool Get(int index);

Прочитать и установить значения отдельных битов можно также с помощью индексатора:

        public
        bool
        this[int index] { get; set;  }

Слеюующий пример создает массив битов, состоящий из 6 бит, и устанавливает нулевой и пятый биты (верхний и нижний):

BitArray bits = new BitArray(6);
bits[0] = true;
bits.Set(5, bits[0]);

Над экземплярами BitArray можно производить битовые операции. Для этого используются следующие методы:

        public BitArray And(BitArray value) ;
public BitArray Or(BitArray value);
public BitArray Xor(BitArray value);
public BitArray Not();

Все эти операции производят модифицикацию текущего экземпляра BitArray, производя битовые операции над данными текущего массива и массива, полученного в качестве параметра. Операция Not просто производит инверсию собственного состояния. Все методы возвращают ссылку на себя же (на свой this). Это делается для того, чтобы операции можно было вкладывать друг в друга.

К сожалению, хотя BitArray написан на C# (как и практически вся FCL), для BitArray не создано перегруженных операторов. А ведь насколько выразительнее был бы код с их применением. Причем класс предусмотрительно помечен как sealed, так что добавить перегрузку бинарных операторов в его наследнике не выйдет.

Примеры, приведенные выше, являются «синтетическими». И хотя они демонстрируют некоторые особенности BitArray, продемонстрировать использование BitArray с их помощью трудно. Следующий пример является демонстрацией работы с BitArray. В нем производится примитивная шифрация данных путем наложения на данные ключа с помощью операции Xor. Стойкость такой шифрации годится для защиты только от тех, кому ваши данные и так не интересны. Зато работу с битовыми массивами программа демонстрирует.

ПРЕДУПРЕЖДЕНИЕ

Программа не создает копии файла, а шифрует его «на месте». Хотя алгоритм и не серьезен, настоятельно советую не экспериментировать над важными данным, или предварительно сделать их резервную копию. Если вы утеряете ключ, его придется подбирать, а сделать это без дополнительной программы не так то просто.

Программа принимает в первом параметре командной строки ключ, а во втором – путь к шифруемому файлу. Расшифровка файла происходит при повторном запуске программы с теми же параметрами.

        using System;
using System.Collections;
using System.IO;
using System.Text;

namespace ConsoleApplication2
{
  class Class1
  {

    int[] MyArray;

    // Возвращает путь к исполняемому файлу.staticstring GetExeName()
    {
      return System.Reflection.Assembly
        .GetExecutingAssembly().GetModules()[0].ToString();
    }

    // Переводит Unicode-строку в массив байтов.// Рамер получаемого массива байт может не совпадать// с размером входной строки (из-за разницы в размере символов).staticbyte[] StrToByte(string str)
    {
      Encoder enc = Encoding.UTF8.GetEncoder();
      char[] chrs = str.ToCharArray(0, str.Length);
      int strLenInBytes = enc.GetByteCount(chrs, 0, chrs.Length, false);
      byte[] buffer1 = newbyte[strLenInBytes];
      strLenInBytes = enc.GetBytes(chrs, 0, 
        chrs.Length, buffer1, 0, true);
      return buffer1;
    }

    staticvoid Main(string[] args)
    {
      // Если не задано двух параметров, выводим приглашение// и завершаем работу приложения.if(args.Length != 2)
      {
        Console.Write("Введите ключ и имя файла: \n{0}
                       qwertyuiop MyFile.txt", GetExeName());
        Console.ReadLine();
        return;
      }

      string key = args[0]; // Получаем значение ключа.string sourceFileName = args[1]; // Получаем имя шифруемого файла.// Инициализируем битовый массив ключа.try
      {
        // Преобразуем строку в массив байтов.byte[] bufferTmp = StrToByte(key);
        // Создаем буфер, в который будет читаться часть файла.// Размер буфера должен быть равен размеру ключа в // байтах или размеру шифруемого файла, если ключ// имеет больший размер, чем файл.byte[] buffer = newbyte[System.Math.Min(bufferTmp.Length, 
          (int)new FileInfo(sourceFileName).Length)];
        // Копируем данные из временного буфера в постоянный.
        Array.Copy(bufferTmp, 0, buffer, 0, buffer.Length);
        // Инициализируем битовый массив ключа.
        BitArray keyBites = new BitArray(buffer);

        // Начинаем шифрование...// Открываем файл для чтения.// using позволяет автоматически его закрыть при выходе из блока.using(FileStream fileStream = new FileStream(sourceFileName,
          FileMode.Open, FileAccess.ReadWrite, FileShare.None))
        {
          int bytesRead = 0; // Количество реально прочитанных байтов.// Читаем данные из файла.while((bytesRead = fileStream.Read(buffer, 0, buffer.Length)) != 0)
          {
            // Клонируем битовый массив.
            BitArray sourceBits = new BitArray(buffer);
            // Делаем XOR битовых массивов.
            sourceBits.Xor(keyBites);
            // Копируем измененные биты обратно в буфер.
            sourceBits.CopyTo(buffer, 0);
            // Перемещаемся на начало блока в файле.
            fileStream.Seek(-bytesRead, SeekOrigin.Current);
            // Перезаписываем изменения.
            fileStream.Write(buffer, 0, bytesRead);
          }
        }
        Console.WriteLine("Шифрация прошла успешно.";
      }
      catch (Exception ex)
      {
        // Не имеет смысла что-либо делать.
        Console.WriteLine(ex.Message); 
      }
    }
  }
}

Hashtable

Самой «нелинейной» в семействе коллекций .NET Framework является Hashtable. Hashtable – это реализация абстракции «словарь» (IDictionary, иногда эту абстракцию называют английским словом Map) на базе хэш-таблицы.

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

Таким образом, Hashtable является идеальной коллекцией, если нужен быстрый поиск значения по некоторому ключу или проверки существования ключа (при этом значение можно просто установить в null). Например, Hashtable замечательно подойдет для преобразования значений, если имеется некий набор строк, которым соответствуют некие целочисленные значения.

Скоростные характеристики

Хэш-таблицы удерживают почетное второе место после массивов с их прямым доступом по индексу. В лучшем случае скоростная характеристика поиска в хэш-таблице – O(1). В худшем – O(n). Hashtable в .NET написана так, что худшего случая можно добиться, если только расчет хэш-значений для ключей реализован из рук вон плохо (подробнее об этом см. раздел «Производительность и качество хэш-функции»). С некоторой натяжкой можно сказать, что независимо от того, что является ключом, скорость поиска будет почти одинакова для любого размера таблицы. С базовыми концепциями алгоритмов, используемых в хэш-таблицах, можно познакомиться у нас на сайте по адресу http://rsdn.ru/article/alg/bintree/hash.xml.

Есть смысл упомянуть, что уменьшить количество коллизий (от которых и зависит скорость поиска) можно, увеличив размер хэш-таблицы. Hashtable умеет сама увеличивать размер хэш-таблицы, причем можно влиять на политику перераспределения за счет задания параметра конструктора loadFactor. loadFactor – это число с плавающей точкой, определяющее коэффициент заполнения отдельного бакета хэш-таблицы. Единица считается разработчиками Hashtable оптимальным компромиссом между объемом занимаемой памяти и скоростью поиска по ключу. Значение loadFactor может лежать в пределах от 0.1 до 1. Меньшее значение ускоряет работу поиска и увеличивает расход памяти. Большее, соответственно, наоборот. Перераспределение (rehashing) само по себе медленная операция. И, хотя loadFactor позволяет значительно уменьшить количество перераспределений, они все равно остаются непроизводительными затратами. Если заранее известно количество хранимых элементов, есть смысл задать начальный размер таблицы, умножив количество элементов на 1.5. Задать начальный размер таблицы можно с помощью параметра конструктора capacity.

Если говорить о реальной скорости, то, хотя скоростные характеристики Hashtable и одинаковы с массивом, все же Hashtable будет работать значительно медленнее массивов (особенно типизированных). Дело в том, что для поиска в хэш-таблице нужно как минимум вычислить хэш-код и произвести некоторые операции по извлечению бакетов, а ведь еще бывают и коллизии. К тому же нельзя забывать про boxing и unboxing, если ключ или значение являются value-типами (ведь все данные хранятся как object).

Добавление пар

Итак, Hashtable позволяет ассоциировать одно значение с другим. Первое значение называется ключом, а второе – непосредственно значением. Добавить ассоциацию в Hashtable (пару ключ/значение) можно с помощью метода:

          void Add(Object key, Object value);

или индексатора:

Object this[Object key]

Использование Add:

Hashtable ht = Hashtable();
int someVal = 123;
ht.Add("Тестовый ключ", someVal);

Использование индексатора:

Hashtable ht = Hashtable();
int someVal = 123;
ht["Тестовый ключ"] = someVal;

Чем отличаются эти варианты? Отличия появляются, если хэш-таблица уже содержит элемент с ключом, равным добавляемому. Add в такой ситуации возбуждает исключение ArgumentException. Использование индексатора приводит к замене значения на новое. Исключение при этом не возбуждается. Таким образом если ключ уже имеется, просто меняется значение, ассоциированное с ним.

Удаление пар

Удалить вхождение (пару «ключ/значение») по ключу можно с помощью метода:

          void Remove(Object key);

Здесь все проще, чем не учить уроков. Передаете ключ вхождения, подлежащего удалению и... вуаля! Вот только может возникнуть одна засада. Дело в том, что если ключ отсутствует, метод не издаст ни звука. В исходных кодах Rotor-а в конце метода присутствует строчка:

          //throw new ArgumentException(
          //     Environment.GetResourceString("Arg_RemoveArgNotFound"));
        

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

ПРИМЕЧАНИЕ

Rotor – это кодовое имя проекта SS CLI. Практически это урезанные исходные коды .NET Framework. В них отсутствует код, связанный с оптимизатором JIT-компилятора, и многие не переносимые библиотеки вроде WinForms и ADO.NET.

Проверка наличия ключа

Если нужно просто определить, содержит ли хэш-таблица определенный ключ, можно воспользоваться методами Contains или ContainsKey. Оба метода идентичны, оба они принимают значение искомого ключа в качестве параметра и возвращают true, если ключ присутствует, или false – если отсуствует:

          bool Contains(Object key);

В качестве ключа можно использовать ссылку на любой объект, лишь бы у него были корректно реализованы методы сравнения и метод GetHashCode(). Хотя если использовать внешний провайдер хэш-кодов, то и корректное функционирование GetHashCode() не обязательно. В качестве значения может вообще использоваться все, на что можно получить ссылку. Что это может дать? Очень многое. Так, в качестве значения можно использовать делегаты и ссылки на интерфейсы. Это может позволить организовать ассоциацию данных с действиями. Таким способом можно, например, организовать расширяемый набор команд в GUI вашего приложения.

Перебор ключей и значений

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

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

Свойства Описание
Values Возвращает коллекцию (интерфейс ICollection) значений. Используя это свойство можно перебирать (например, оператором foreach) или копировать значения, содержащиеся в хэш-таблице, во внешний массив.
Keys Возвращает коллекцию (интерфейс ICollection) ключей. Используя это свойство, можно перебирать (например, оператором foreach) или копировать ключи, содержащиеся в хэш-таблице, во внешний массив.
GetEnumeratorИли просто запрос нумератора через интерфейс IEnumerable. Позволяет перебрать (например, оператором foreach) пары ключ/значение, хранимые в хэш-таблице. Это самый быстрый способ на сегодня, так как в текущей реализации только в нем создается нумератор, не копирующий данные в промежуточный массив с использованием очень медленных методов Array.SetValue. Метод GetEnumerator возвращает ссылку на IDictionaryEnumerator, с помощью которого можно перебирать структуры DictionaryEntry, содержащие пары ключ/значение.
Таблица 10. Свойства/методы хэш-таблицы, возвращающие коллекции или итераторы.

Можно воспользоваться методом CopyTo:

          void CopyTo(Array array, int arrayIndex);

С его помощью можно скопировать содержимое хэш-таблицы в массив DictionaryEntry или массив объектов.

К сожалению, все методы копирования и перебора, за исключением GetEnumerator (перечисления структур DictionaryEntry, содержащих пары ключ/значение), реализованы с использованием очень медленного метода Array.SetValue. Поэтому, если данная операция используется внутри критичного к времени выполнения участка кода, лучше пользоваться перебором DictionaryEntry, например:

Hashtable ht = new Hashtable();
ht["Мама"] = 123;
ht["Папа"] = 321;
ht["Я"]    = 789;

foreach (DictionaryEntry entry in ht)
  Console.WriteLine("key:{0} val:{1} ", entry.Key, entry.Value);

Откровенно говоря, совершенно неясно, почему не был сделан метод:

          void CopyTo(DictionaryEntry array, int arrayIndex);

так как это позволило бы избежать лишней пары boxing/unboxing, и тем самым увеличить скорость. Так же непонятно, почему в остальных случаях нельзя было обойтись без использования медленного метода Array.SetValue. Однако не стоит на этом зацикливаться, так как операции перебора и копирования содержимого хэш-таблиц производятся довольно редко.

Синхронизация

Хэш-таблица требует дополнительной синхронизации, если производится параллельная ее модификация (из другого потока). Синхронизированную версию хэш-таблицы (а вернее, обертку) можно получить с помощью статического свойства Synchronized. В общем-то, это стандартный подход в .NET, и даже не стоило бы про него упоминать отдельно, если бы не одна особенность. Дело в том, что, как сказано в документации, обертка хэш-таблицы поддерживает так называемый режим неблокирующего чтения, т.е. при доступе к обертке на чтение не происходит блокировки. Запись же производится последовательно (сериализуется). Это делает хэш-таблицу особенно привлекательной в многозадачных приложениях. Остается только надеяться, что разработчики не допустили никаких ошибок, так как при доступе на чтение (через индексатор) блокировки отсутствуют полностью.

Пример использования класса Hashtable

В качестве примера я приведу программу, подсчитывающую количество вхождений слов в текстовом файле. В ней сначала из текстового файла, путь к которому указывается в качестве параметра, текст загружается в строку. Затем в процедуре Parse производится разбор полученной строки на отдельные слова. Все слова помещаются в массив, который возвращается основному алгоритму. Далее производится попытка найти каждое слово в хэш-таблице. Если это не удается, в хэш-таблицу добавляется соответствующий ключ, с которым ассоциируется единица. Иначе полученное значение увеличивается на единицу и помещается обратно в хэш-таблицу. Таким образом, в конце процедуры Main мы получаем хэш-таблицу, в которой находится список уникальных слов из прочитанного файла, причем с каждым словом ассоциировано количество его вхождений.

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

          using System;
using System.Collections;
using System.IO;
using System.Text;

class Concordance
{  
  staticvoid Main(string[] args)
  {
    if (args.Length < 1)
    {
      Console.WriteLine("Введите имя файла в качестве параметра.");
      return;
    }

    Console.WriteLine("Обрабатывается файл: {0}", args[0]);

    // Создаем и инициализируем хэш-таблицу.
    Hashtable dictionary = new Hashtable(
      1000, // Начальный размен таблицы
      0.3F,  // loadFactornew CaseInsensitiveHashCodeProvider(), 
      new CaseInsensitiveComparer());

    using (StreamReader texFile = new StreamReader(args[0]))
    {
      PerfCounter perf = new PerfCounter(); 
      
      perf.Start(); // Замеряем время...// Считываем файл в строку и разбираем ее на слова...string[] ary = Parse(texFile.ReadToEnd());
      Console.WriteLine("Время парсинга: {0:### ###.000}", perf.Finish());
      
      perf.Start(); // Засекаем время подсчета слов...foreach (string word in ary)
      {
        object obj = dictionary[word];
        // Если слово еще не добавлялось, obj будет содержать null.if (obj == null)
          dictionary[word] = 1;
        else
          dictionary[word] = (int)obj + 1;
      }
      Console.WriteLine("Время подсчета слов: {0:### ###.000}", 
        perf.Finish());

      Console.WriteLine("Всего слов: {0}", dictionary.Count);

      Console.WriteLine("Готово...");
    }
  }

  staticstring[] Parse(string str)
  {
    StringBuilder sb = new StringBuilder(100);
    ArrayList ary = new ArrayList(1000);

    foreach (char ch in str.ToCharArray())
    {
      if (char.IsLetterOrDigit(ch))
        sb.Append(ch);
      elseif (sb.Length > 0)
      {
        ary.Add(sb.ToString());
        sb.Length = 0;
      }
    }

    // Преобразуем динамический массив (ArrayList) в string[].return (string[])ary.ToArray(typeof(string));
  }
}

На моей машине трехмегабайтный файл разбирается на слова за ~0.37 секунды, а подсчет количества слов занимает 0.35 секунды. Таким образом затраты на добавление элементов в Hashtable можно сравнить с посимвольной обработкой строки такого же размера.

Производительность и качество хэш-функции

Скорость поиска в хэш-таблице зависит от двух факторов: размера хэш-таблицы и качества хэш-функции. Под качеством хэш-функции понимается ее способность выдавать хэш-значения, дающие минимальное количество коллизий. В этой статье я не буду разбирать теоретические вопросы, если это вас интересует, обратитесь к ссылкам, приведенным выше. Но поговорить о качестве хэш-функции, наверное, стоит. Для встроенных типов (таких, как string, int, double) в .NET Framework имеются довольно качественные реализации хэш-функций (GetHashCode). Для классов реализация GetHashCode почти идеальна, с одной оговоркой. Функция GetHashCode для классов по «умолчанию» возвращает порядковый номер в таблице указателей, т.е. по сути порядковый номер класса. Это подразумевает, что два различных экземпляра класса не могут быть эквивалентны. Поэтому, если ваша логика подразумевает возможность наличия нескольких логически эквивалентных экземпляров класса, придется вручную реализовать GetHashCode, а также все функции сравнения, объявленные в классе object.

Самая неудачная реализация функции GetHashCode в .NET Framework – это реализация, используемая по умолчанию в структурах. Дело в том, что эта функция для структур делает следующее. Она с помощью рефлексии перебирает все поля и пытается получить хэш-код. Найдя первое поле, от которого можно получить хэш-код, функция завершает свою работу, возвращая это значение. В большинстве случаев она возвращает хэш-код первого попавшегося поля. Однако если структура состоит из ссылочных типов, и все они установлены в null, то функция по аналогии с классом возвращает порядковый номер объекта. Ниже приведена реализация этой функции из Rotor:

          public
          override
          int GetHashCode()
{
  // Note that for correctness, we can't use any field of the value type// since that field may be mutable in some way.  If we use that field// and the value changes, we may not be able to look up that type in a// hash table.  For correctness, we need to use something unique to// the type of this object.                             // HOWEVER, we decided that the perf of returning a constant value (such as// the hash code for the type) would be too big of a perf hit.  We're// willing to deal with less than perfect results, and people should // still be encouraged to override GetHashCode.
 
  BCLDebug.Correctness(!(thisis System.Collections.DictionaryEntry), 
    "Calling GetHashCode on DictionaryEntry is dumb and probably wrong.");
  BCLDebug.Perf(false, "ValueType::GetHashCode is not fast.  Perhaps "
    + this.GetType().FullName + " should override GetHashCode()");

  RuntimeType thisType = (RuntimeType)this.GetType();
  FieldInfo[] thisFields = thisType.InternalGetFields(
    BindingFlags.Instance | BindingFlags.Public 
    | BindingFlags.NonPublic, false);

  if (thisFields.Length>0)
  {
    for (int i = 0; i < thisFields.Length; i++)
    {
      Object obj = ((Object)(((RuntimeFieldInfo)thisFields[i])
        .InternalGetValue((Object)this, false)));
      if (obj != null)
        return obj.GetHashCode();
     }
  }
  // Using the method table pointer is about 4x faster than getting the// sync block index for the Type object.return GetMethodTablePtrAsInt(this);
}

У такого подхода есть два недостатка. Первое – такой хэш-код может оказаться и часто оказывается некорректным, так как по одному полю тяжело идентифицировать всю структуру. Во-вторых, из-за использования рефлексии этот способ далек от идеальной производительности. Поэтому при необходимости получения хэш-значений от структур, лучше реализовать соответствующие функции самостоятельно. Стандартным приемом является сложение хэш-значений ключевых полей структуры и соответствующая модификация функций сравнения. Главное – не забывать, что если функция сравнения признает два объекта эквивалентными, то их реализация метода GetHashCode должна возвращать одинаковые значения.

Иногда встречается ситуация, когда необходимо применять разные алгоритмы сравнения, а стало быть, и по-разному считать значение хэш-кода. Например, стандартная реализация GetHashCode и функции сравнения класса string сравнивает строки с учетом регистра. Иногда же требуется хранить в той же хэш-таблице значения, не учитывающие регистр. Для таких случаев придуманы интерфейсы IHashCodeProvider и IComparer, которые можно передать, например, хэш-таблице. В этом случае все сравнения будут производиться с помощью этих интерфейсов. Для тех же строк, например, существуют реализации этих интерфейсов, не чувствительные к регистру (классы CaseInsensitiveHashCodeProvider и CaseInsensitiveComparer). Для упрощения создания хэш-таблиц и сортированных списков можно воспользоваться специальным классом-помощником System.Collections.Specialized.CollectionsUtil. Для этих целей в его состав входят статические функции CreateCaseInsensitiveHashtable и CreateCaseInsensitiveSortedList.

SortedList

Как и Hashtable, SortedList является реализацией абстракции «словарь» (IDictionary), но, в отличие от хэш-таблицы, поддерживает упорядоченность данных. Достигается это за счет хранения ключей и данных в двух отсортированных массивах. Поиск элемента по ключу у этой коллекции происходит за время O(log2n). Вставка состоит из поиска и сдвижки элементов массивов, начиная от вставляемого и до конца массива. Так как сдвижка при больших размерах массива (десятки тысяч элементов) становится все медленнее, стоит стараться избегать использования этой коллекции, если требуются частные вставки-удаления. Совершенно не оправдано использование этой коллекции там, где нужен только поиск по ключу. В таких ситуациях намного лучше выбрать хэш-таблицу.

Пример из предыдущего раздела при замене реализации словаря с Hashtable на SortedList стал выполняться приблизительно за 1.4 секунды, т.е. в 4 раза медленнее.

Пользовательские типизированные коллекции

Если вы работали с компонентами в FCL, то должны были заметить, что большинство списков, предоставляемых через свойства компонентов, являются классами, реализующими интерфейс IList, и предоставляющими типизированный доступ к содержимому через типизированный индексатор. Такие коллекции можно редактировать в VS.NET (в PropertyGrid). В общем, вещь удобная и полезная. :)

Как же создать такие коллеции? В принципе, для реализации собственной типизированной коллекции достаточно создать класс, реализующий интерфейс IList, и индексатор, но это довольно сложно. А ведь большинствао коллекций основаны на линейных списках (массивах). Причем чаще всего такие коллекции создаются на основе ArrayList.

Чтобы упростить процесс создания таких колекций, в FCL были введены два класса:

[SerializableAttribute()]
publicabstractclass CollectionBase : IList, ICollection, IEnumerable

и:

[SerializableAttribute()]
publicabstractclass ReadOnlyCollectionBase : ICollection, IEnumerable

Оба класса используются в качестве базовых при создании собственных коллекций. Они реализуют основные методы интерфейсов IList и ICollection и предоставляют ряд виртуальных методов, которые можно перекрыть, чтобы из производного класса можно было вмешаться в процесс работы коллеции.

Вот пример простой readonly-коллекции:

        public
        class Attribute { ... }

publicclass AttributeCollection : ReadOnlyCollectionBase
{
  public AttributeCollection(ArrayList attributes)
  {
    if (attributes != null)
      InnerList.AddRange(attributes);
  }

  public Attribute this[int index]  
  {
    get { return (Attribute)InnerList[index]; }
    set { InnerList[index] = (object)value; }
  }

  publicint IndexOf(Attribute value)  
  {
    return(InnerList.IndexOf(value));
  }

  publicbool Contains(Attribute value)  
  {
    return(InnerList.Contains(value));
  }

}

В .NET принято давать классам коллекций имена, состоящие из имени элемента, хранящегося в коллекции, и суфикса Collection. Так, в примере, приведенном выше, коллекция хранит элементы типа Attribute и называется AttributeCollection. Инициализация коллекции происходит в конструкторе. Свойство InnerList позволяет получить доступ к ArrayList, хранящему элементы коллекции.

Немного сложнее (но тоже довольно просто) создать изменяемую коллекцию. Для этого нужно унаследовать коллекцию от CollectionBase и добавить типизированные аналоги методов, свойств и индексатора интерфейса IList (тех, что принимают в качестве параметров object). Внутри этих методов нужно передать управление аналогичным методам объекта, возвращаемого свойством List. Это свойство возвращает ссылку на интерфейс IList. Вот пример такой реализации:

        public
        void Add(ItemType value)
{
  List.Add(value);
}
publicvoid Remove(ItemType value);
{
  List.Remove(value);
}
bool Contains(ItemType value);
{
  return List.Contains(value);
}
...

Значение свойства List по сути всего лишь ссылка на реализацию IList данной коллекцией. Так что вместо обращения к этому свойству можно просто привести this к IList. Следующая реализация метода Contains аналогична приведенной выше:

        bool Contains(ItemType value);
{
  return ((IList)this).Contains(value);
}

Реализация этого интерфейса в CollectionBase в основном перенаправляет вызовы аналогичным методам внутреннего ArrayList доступного, как и в случае ReadOnlyCollectionBase, через свойство InnerList. В принципе, вместо обращения IList можно получить прямую ссылку на ArrayList и модифицировать его содержимое напрямую. Однако лучше так не делать, так как при этом не будет доступна функциональность уведомлений. Дело в том, что при модификации коллекции через интерфейс IList управление не просто передается аналогичным методам ArrayList. Перед и после модификации вызываются специальные виртуальные методы. Эти методы помечены модификатором protected, так что их можно переопределить в классе-наследнике. Вот список этих методов:

        protected
        virtual
        void OnSet(int index, object oldValue,
                        object newValue) ;
protectedvirtualvoid OnSetComplete(int index, object oldValue,
                        object newValue);
protectedvirtualvoid OnInsert(int index, object value);
protectedvirtualvoid OnInsertComplete(int index, object value);
protectedvirtualvoid OnClear();
protectedvirtualvoid OnClearComplete();
protectedvirtualvoid OnRemove(int index, object value);
protectedvirtualvoid OnRemoveComplete(int index, object value);
protectedvirtualvoid OnValidate(object value);

В таблице 10 приведены их описания.

Метод Описание
OnSet Вызывается перед изменением элемента коллекции.
OnSetComplete Вызывается после изменения элемента коллекции.
OnInsert Вызывается перед вставкой элемента коллекции.
OnInsertComplete Вызывается после вставки элемента коллекции.
OnClear Вызывается перед очисткой коллекции.
OnClearComplete Вызывается после очистки коллекции.
OnRemove Вызывается перед удалением элемента коллекции.
OnRemoveComplete Вызывается после удаления элемента коллекции.
OnValidate Вызывается перед любым изменением коллекции.
Таблица 11. Описание событийных методов класса CollectionBase.

Методы OnXxx вызываются перед некоторой операцией. Если в них возбудить исключение, операция не будет выполнена. Если этот метод не вызвал исключения, сразу после выхода из него производится модификация коллекции. Такое поведение делает методы OnXxx идеальным местом для контроля корректности модификации коллекции. Этому сопутствует то, что все эти методы получают исчерпывающую информацию об изменениях.

После окончания соответствующих операций модификации вызывается метод OnXxxComplete. Причем если в них вызвать исключение, то поведение будет уже не так предсказуемо, как в случае с OnXxx. Так, при вставке, добавлении или модификации исключение вызовет удаление вставленного элемента или откат к старому значению, а при удалении состояние коллекции не восстанавливается. Учитывая это, лучше выполнять в OnXxxComplete только операции, которые не могут привести к исключениям. Обычно это некоторые операции подсчета и т.п.

Метод OnValidate позволяет сделать проверку корректности данных. Он интересен тем, что вызывается перед любой операцией изменения коллекции. Однако это же делает его и несколько неудобным, так как проверка правильности данных при удалении – занятие, скажем так, очень странное. В основном этот метод стоит использовать для проверки корректности типов аргументов. Ведь при модификации коллекции через методы IList вполне возможно, что в качестве параметра будет передано значение, тип которого несовместим с типом элементов коллекции.

Что следует знать, берясь за реализацию собственных типизированных коллекций? В первую очередь стоит знать, что лучше всего в качестве типа элемента коллекции использовать ссылочные типы данных. Дело в том, что визуальные дизайнеры в основном не умеют изменять значение, если в коллекции хранятся value-типы. Связано это с тем, что большинство из них написано на C#, а в этом языке перед изменением value-типа, приведенного к object, сначала делается unboxing. При этом происходит модификация значения копии элемента, размещенной в стеке, а не элемента, хранящегося в коллекции. Чтобы вернуть это значение в коллекцию, его нужно заново присвоить этому элементу. Однако этого дизайнеры не делают. Еще одним фактором, говорящим не в пользу value-типов является то, что boxing и unboxing выливаются в довольно значительные накладные расходы. При этом все преимущества value-типа исчезают.

DataSet и DataTable

В FCL входят два очень интересных класса, которые тоже можно отнести к коллекциям. Это DataSet и DataTable из пространства имен System.Data. Они не входят в список стандартных коллекций, так как предназначены в первую очередь для работы с данными, выбираемыми из БД. Однако с ними можно полноценно работать и без БД. DataTable позволяет хранить список строк, каждая из которых состоит из набора ячеек. DataTable определяет набор ячеек (полей) для всех строк, входящих в DataTable. Таким образом, DataTable очень похож на таблицу БД. В DataTable даже можно создать индекс или отфильтровать данные по некоторому условию. Данные в DataTable хранятся практически оптимально. Так что память не будет расходоваться понапрасну.

DataSet является коллекцией DataTable-ов. В рамках DataSet-а можно определять связи между DataTable-ами. Т.е. DataSet аналогичен маленькой БД, хранящейся в памяти.

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

Generic-коллекции

Начиная с версии 1.2 .NET Framework будет поддерживать так называемые generic-коллекции и соответствующие generic-интерфейсы. Они размещаются в пространстве имен System.Collections.Generic. И те, и другие очень похожи на типы из пространства имен System.Collections. Отличия в основном проявляются в том, что generic-коллекции и интерфейсы строго типизированы, причем параметризация производится не конкретными типами, а с помощью нового механизма, введенного в этой версии CLR. Этот механизм получил название generics. Подробнее о нем можно прочесть в одной из статей этого номера. Почти все коллекции являются копиями одноименных коллекций из пространства имен System.Collections, но параметризованы generic-параметром (или двумя). Например, ICollection<T> – это типизированная версия ICollection. Единственным исключением является интерфейс IKeyComparer, хотя и он, в общем-то, является вариацией на тему IComparer.

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

ПРЕДУПРЕЖДЕНИЕ

Информация о generic-коллекциях основана на предварительной версии .NET Framework (1.2.30703), и многое еще может измениться. Не забывайте об этом.

В таблице 12 приведен список классов из пространства имен System.Collections.Generic.

Название Описание
Comparer<T> Обобщенная реализация интерфейса сравнения (IComparer<T>). Ее метод Compare пытается любыми доступными способами сравнить два элемента. Сначала он пытается сравнить ссылки. Затем он пытается получить от сравниваемых объектов ссылку на интерфейс IComparable<T>. Если все это не удается, пытается получить ссылку на обычный IComparable. Если же и это не удается, генерируется исключение.
Dictionary<T, U> Реализация абстрации IDictionary<T> на базе алгоритма хэш-таблицы. Аналогичен классу Hashtable, но позволяет обеспечить строгую типизацию ключей и значений.
List<T> Реализация абстракции IList<T> на базе массива. Аналогичен классу ArrayList, но позволяет обеспечить строгую типизацию элементов списка.
Queue<T> Аналогичен классу Queue, но позволяет обеспечить строгую типизацию элементов списка.
SortedDictionary<T, U> Реализация абстрации IDictionary<T> на базе алгоритма сортированных массивов. Аналогичен классу SortedList, но позволяет обеспечить строгую типизацию ключей и значений.
Stack<T> Аналогичен классу Stack, но позволяет обеспечить строгую типизацию элементов списка.
Таблица 12. Список классов из пространства имен System.Collections.Generic.

Чем generic-коллекции лучше реализованных в .NET Framework 1.1? В первую очередь типобезопасностью. Дело в том, что при работе с коллекциями, входящими в пространство имен System.Collections, постоянно приходится пользоваться приведением типов:

        int i = (int)arrayList[1];

а это заставляет компилятор отказаться от проверки типов во время компиляции. Это не приводит к столь печальным последствиям, как это было в C++, так как проверки все же осуществляются в runtime-е. Но надежность программ при этом снижается. Ведь некоторые участки кода (особенно обработчики ошибок) могут быть так ни разу и не запущены во время отладки программы, и сбой проявится только у заказчика. Generic-и позволяют избавиться от этой проблемы, если в коллекции хранятся однотипные элементы. Сравните два варианта кода. Обычный:

ArrayList ary = new ArrayList();
ary.Add(0);
ary.Add(1);
ary.Add("2"); // Прекрасно скомпилируются.int i1 = (int) ary [0]; // Обращение к элементу требует приведение типаint i2 = (int) ary [2]; // Скомпилируется, но вызовет исключению в runtime-е

И generic:

ArrayList<int> ary = new ArrayList<int>();
ary.Add(0);
ary.Add(1);
ary.Add("2"); // Не скомпилируются!int i1 = ary [0]; // Обращение не требует приведений!int i2 = ary [2];

Обратите внимание на комментарии. В первом примере допущена ошибка. В ArrayList добавляется элемент типа string, в то время как по задумке разработчика в ней должны были храниться только целые числа. Эта ошибка пропускается компилятором, так как строка приводится к object так же легко, как и int. Однако в runtime-е попытка доступа к элементу с индексом 2 приведет к исключению. В generic-варианте код с ошибкой попросту не скомпилируется. Причем программист получит доходчивое сообщение об ошибке.

Еще одним преимуществом является то, что generic-коллекции работают быстрее, чем обычные, так как не требуется приведений к типу object и обратно к базовому типу.

Однако тут не все так радужно. Дело в том, что текущая реализация коллекций сделана довольно примитивно. Большинство методов делегирует работу соответствующим методам класса Array, это, как я уже говорил выше, чревато потерями производительности (особенно если в массиве хранятся структуры).

Возможно, в окончательной версии Microsoft исправит эту недоработку и перепишет весь код generic-коллекций на C#. Но гарантировать этого нельзя. С другой стороны, можно точно гарантировать, что если этого не сделают программисты из Microsoft, то это сделает кто-нибудь из независимых программистов. Возможно даже, это будет кто-нибудь из RSDN-овцев ;).

Еще раз о производительности

О скорости работы коллекций FCL в этой статье было уже сказано немало. Но главное, что не было сказано – это то, что никакие советы и финты не уберегут вас от катастрофического замедления программ, если вы не умеете подбирать нужный тип коллекции. Дело в том, что ни одна самая быстрая реализации коллекции не может скомпенсировать разницу в алгоритмах. По поводу выбора подходящих алгоритмов написано немало статей. Так на www.optim.su есть две статьи:

В них подробно описаны основные алгоритмы и даны их временные характеристики.

Здесь же я могу изложить принципы, по которым нужно выбирать те или иные коллекции.

Если вам нужен быстрый поиск по ключу, то лучше всего воспользоваться хеш-таблицей (Hashtable или Dictionary<T, U>). Если кроме этого нужно сохранять упорядоченность или сортированность, то стоит или поместить элементы кроме хэш-таблицы еще и в массив (отсортировав его после добавления всех элементов, если это требуется). Если предполагается часто добавлять и удалять элементы, и при этом требуются упорядоченность и поиск по ключу, то лучше всего воспользоваться SortedList-ом. Однако нужно помнить, что скорость поиска по ключу у него ниже, а вставка и удаление – довольно дорогие операции.

Если вам просто требуется сохранять упорядоченность, то лучше всего выбрать массив или ArrayList. ArrayList лучше выбирать, если требуются массовые вставки и/или удаления. А простой массив – если нужно хранить относительно статичные данные. Если данные формируются в начале работы, а дальше не изменяются, то лучше всего сформировать список с использованием ArrayList, и по окончании скопировать данные в обычный массив. Это повысит типобезопасность и поднимет производительность.

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

Если алгоритм допускает хранение данных как в одном ArrayList, так и в нескольких, лучше стараться разнести данные по нескольким ArrayList, так как удаление и вставка в середину списка при этом будут происходить быстрее.

Если необходимо передать коллекцию вовне (возвратить из публичной функции и т.п.), лучше пользоваться типизированными коллекциями или (на худой конец) интерфейсами IList или ICollection (а так же их generic-вариациями). Это позволит избежать ошибок дизайна, а значит многих граблей, связанных с ним.

Если вам доступен .NET Framework 1.2 и выше, пользуйтесь generic-коллекциями вместо обычных. Это повысит производительность и безопасность кода.

Не ленитесь комбинировать коллекции. Помните, что панацей не бывает.

Коллекции, которых нет в .NET Framework

.NET Framework содержит минимальный набор коллекций, которого, тем не менее, хватает в 95% случаев. Однако кое-чего в FCL нет – вообще отсутствуют такие коллекции как:


Эта статья опубликована в журнале RSDN Magazine #6-2003. Информацию о журнале можно найти здесь
    Сообщений 25    Оценка 230 [+0/-1]         Оценить