Типы коллекций

С момента своего появления платформа .NET Framework включала множество типов коллекций, предназначенных для управления всем — от расширяемых массивов ArrayList, очередей Queue, стеков Stack и даже словарей — через класс HashTable. С годами новые версии .NET Framework расширили и усовершенствовали эти типы.

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

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

1
System.Collections и System.Collections.Specialized

в .NET 1.1. В MSDN доступна масса документации на эту тему.

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

1
System.Collections.Generic и System.Collections.ObjectModel.

Сравнение ICollection(T) и ICollection

Наиболее очевидные дополнения к типам коллекций, которые появились в .NET 2.0 Framework, являются типы, определенные внутри пространства имен System.Collections.Generic.

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

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

Ниже приведено его объявление:

public interface ICollection : IEnumerable, IEnumerable {
int Count { get; }
bool IsReadOnly { get; }
void Add ( T item ) ;
void Clear ();
bool Contains ( T item ) ;
void CopyTo ( T[] array, int arraylndex );
bool Remove ( T item ) ;
}

Для сравнения показано также определение необобщенного интерфейса ICollection:

public interface ICollection : IEnumerable {
int Count { get; }
bool IsSynchronized { get; }
object SyncRoot { get; }
void CopyTo ( Array array, int index );
}

Рассмотрим отличия между ними и то, что они означают для кода. Необобщенным коллекциям недостает универсального интерфейса управления содержимым коллекции. Например, оба необобщенных типа — Stack и Queue — имеют метод Clear для очистки своего содержимого.

Как и можно было ожидать, оба они реализуют интерфейс ICollection. Однако поскольку ICollection не содержит никаких модифицирующих методов, обычно полиморфно трактовать в коде экземпляры этих двух типов нельзя. Поэтому всегда приходится выполнять приведение переменной экземпляра к типу Stack, чтобы вызвать Stack.Clear, и приводить к типу Queue, чтобы вызвать Queue.Clear.

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

Для таких экземпляров вызовы методов Add, Clear и Remove приведут к генерации исключения InvalidOperationException. В интересах производительности рекомендуется, чтобы вызывающий код определял, разрешены ли такие операции, проверяя свойство IsReadOnly и таким образом вообще избегая исключений.

Разумеется, если конечным результатом IsReadOnly, возвращающего true, окажется генерация исключения, то никакого выигрыша не будет. Поскольку главное назначение ICollection — обеспечить более высокую безопасность типов, для ICollection имеет смысл предоставление собственной строго типизированной версии CopyTo.

В то время как методу ICollection.CopyTo известно, что его первым параметром является массив, при этом может приниматься ссылка на System.Array, ICollection.CopyTo в первом параметре передается конкретный тип массива.

Ясно, что методу ICollection.CopyTo можно передавать только одномерные массивы. Фактически необобщенный метод ICollection.CopyTo также принимает только одномерные массивы, но поскольку компилятор не может определить размерность типа System.Array во время компиляции, при передаче правильной реализации ICollection.CopyTo массива с более, чем одним измерением будет сгенерировано исключение времени выполнения Argument Exception.

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

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

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

Если не производится наследование от Collection, работа окажется более трудной, поскольку придется реализовать большую часть того, что уже реализовано в Collection.

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

Словари

В .NET 2.0 Framework появился тип IDictionary — обобщенный, а потому строго типизированный аналог IDictionary. Как обычно, конкретные типы, реализующие IDictionary, должны также реализовать IDictionary.

Между ними есть много перекрытий, но обобщенный интерфейс объявляет более безопасные в отношении типов версии некоторых свойств и методов, объявленных в IDictionary.

Однако в IDictionary присутствует также и новый метод по имени TryGetValue, который можно использовать для получения значений на основе заданных ключей. Этот метод возвращает значение в выходном параметре, а само возвращаемое значение говорит о том, присутствует ли элемент с таким ключом в словаре. Хотя того же можно добиться, используя операцию индекса и перехватывая исключение KeyNotFoundException, когда элемента в словаре нет, всегда более эффективным будет код, избегающий исключений, если известно, что искомого элемента может не оказаться в словаре.

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

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

При реализации обобщенных словарей существуют два варианта выбора, от чего наследовать реализацию. Для начала можно использовать SortedDictionary, который обеспечивает время доступа 0(log n) и реализует lDictionary в качестве интерфейса коллекции.

Однако вполне можно отдать предпочтение KeyedCollection из пространства имен System.Collections.ObjectModel. Хотя этот класс на самом деле не реализует интерфейсов словарей, он обеспечивает время доступа 0(1) в большинстве случаев.

Наборы

В NET 3.5 Framework появился еще один полезный класс коллекций по имени HashSet, который определен в пространстве имен System.Collections.Generic. Класс HashSet реализует типичные операции над множествами, которых можно было ожидать.

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

К другим полезным методам относятся IsSubsetOf, IsSupersetOf, ExceptWith, SymmetricExceptWith, Contains и т.д. Это лишь несколько из удобных методов, доступных в наборах.

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

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

По этой причине метод Add возвращает булевское значение, указывающее на то, удалась ли операция. Генерировать исключения в таких случаях было бы неэффективно, поэтому результат обозначается возвращаемым значением метода Add.

System.Collections.ObjectModel

При определении собственных типов коллекций наиболее удобными типами окажутся те, что определены в пространстве имен System.Collections.ObjectModel. По возможности реализации должны наследоваться от объектов из этого пространства имен. Оно содержит только пять типов, и сам факт существования такого пространства имен является предметом дискуссии. Было две главных причины вынести эти пять типов в отдельное пространство имен.

Во-первых, в среде Visual Basic уже есть тип Collection, реализованный в пространстве имен, импортируемом по умолчанию, и в команде Visual Basic предположили, что пользователи VB будут введены в заблуждение, увидев два типа с одинаковыми именами, но с совершенно отличающимся поведением, в окне IntelliSense.

Во-вторых, в команде, занимающейся разработкой библиотек базовых классов (Base Class Libraries — BCL), решили, что пользователям редко понадобятся типы из этого пространства имен. Со временем выяснится, так ли это. С другой стороны, эти типы исключительно полезны для написания библиотек кода, используемых другими. Одно из руководств Microsoft советует создавать подклассы этих типов при разработке коллекций, даже если только требуется предоставить более выразительное имя, описывающее коллекцию, и обеспечить удобное место для расширений.

Эти типы весьма удобны при определении собственных типов коллекций. Для получения поведения коллекции по умолчанию, включая реализации ICollection, IList и IEnumerable, необходимо унаследовать свой тип от Collection. В Collection также реализованы необобщенные интерфейсы ICollection, IList и IEnumerable.

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

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

Тем не менее, защищенные виртуальные методы, которые можно переопределять, все-таки показаны ниже:

1
2
3
4
5
6
7
8
public class Collection<t> : ICollection<t>, IList<t>, IEnumerable<t>,
ICollection, IList, IEnumerable
{
protected virtual void ClearltemsO ;
protected virtual void Insertltem( int index, T item );
protected virtual void RemoveItem( int index );
protected virtual void Setltem( int index, T item );
}

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

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

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

По идее, типу Collection не помешали бы и дополнительные конструкторы, принимающие IEnumerator и IEnumerable, чтобы обеспечить больше гибких способов наполнения коллекции. Эту задачу можно решить самостоятельно, добавив дополнительные конструкторы к типам, производным от Collection, как показано ниже:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
public class MyCollection<t> : Collection<t> {
public MyCollection ()  : base()  { }
public MyCollection ( IList<t> list )
: base(list)  { }
public MyCollection ( IEnumerable<t> enumerable )
: baseO  {
foreach ( T item in enumerable )  {
this.Add( item ) ;
}
}
public MyCollection ( IEnumerator<t> enumerator ) : base()  {
while( enumerator.MoveNext() )  {
this.Add( enumerator.Current );
}
}
}
public class EntryPoint {
static void Main()  {
MyCollection<int> coll =
new MyCollection<int>( GenerateNumbers() );
f oreach ( int n in coll ) {
Console.WriteLine ( n );
}
}
static IEnumerable<int> GenerateNumbers () {
for( int i = 4; i >= 0; -i )  {
yield return i;
}
}

В Main имеется экземпляр MyCollection, который создан передачей ему типа IEnumerable, возвращенного методом GenerateNumbers. Если ключевое слово yield в методе GenerateNumbers покажется незнакомым, это может объясняться тем, что данное средство появилось только в версии С# 2.0.

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

В конце концов, MyCollection является Collection. Кстати, конструкторы, принимающие необобщенные IEnumerable и IEnumerator, не предусмотрены просто потому, что предпочтение было отдано достижению более строгой безопасности в отношении типов.

Возможно, вы отметили присутствие List в пространстве имен System.Collections.Generic. Было бы соблазнительно использовать List в приложениях всякий раз, когда нужно предоставить потребителям обобщенный список. Однако вместо List подумайте о применении Collection.

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

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

Другим полезным типом из пространства имен System.Collections.ObjectModel является тип ReadOnlyCollection, который представляет собой оболочку, используемую для реализации коллекций, доступных только для чтения. Поскольку в С# отсутствует понятие ключевого слова const для выражения константности, как в языке С++, важно иметь возможность создавать при необходимости неизменяемые типы и передавать их методам в виде константных параметров.

Конструктор ReadOnlyCollection принимает тип параметра IList. Поэтому тип ReadOnlyCollection можно использовать в качестве оболочки для любого типа, реализующего IList, включая Collection. Естественно, если пользователь обратится к свойству ICollection.IsReadOnly, он получит в результате true. При каждой попытке вызова модифицирующего метода, такого как ICollection.Clear, будет сгенерировано исключение NotSupportedException.

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

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

Эффективность

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

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

Упаковка — определенно более дорогая операция, чем распаковка, поскольку требует выделения памяти в куче, а распаковка — нет. Рико Мариани (Rico Mariani) указывает на многие другие узкие места эффективности в своем блоге Rico Mariani’s Performance Tidbits. Он подчеркивает, что команды разработчиков тратят массу времени на решение проблем производительности, и упрощение всегда помогает в этом.

Он приводит один блестящий пример, доказывающий, что List существенно быстрее, чем ArrayList, когда используется много операций foreach. Однако повышенная скорость объясняется не очевидными причинами, связанными с отсутствием упаковки/распаковки, а скорее тем, что ArrayList использует “бесплатный” набор виртуальных методов — особенно во время перечислений. ArrayList.GetEnumerator является виртуальным методом, а вложенный тип перечисления ArrayListEnumeratorSimple также виртуально реализует метод MoveNext и свойство Current.

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

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

Если нет абсолютной уверенности в наличии причин, по которым кто-то пожелает выполнить наследование от класса, ориентироваться следует на создание герметизированных (sealed) классов. Не имея веских причин, не оставляйте класс открытым для наследования только потому, что считаете, что такая необходимость может возникнуть в будущем.

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

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

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

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

Поэтому, если обобщение содержит поле вроде такого:

1
2
3
4
public class MyGeneric<t>
{
public static int staticField;
}

то MyGeneric.staticField и MyGeneric.staticField будут ссылаться на разные места в памяти. Мораль этой истории в том, что необходимо учитывать инженерные компромиссы. Хотя обобщения помогают избежать упаковки/распаковки и обычно порождают более эффективный код, они также увеличивают размер рабочего набора приложения.

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

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100