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

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

Существует два основных типа коллекций — универсальные и неуниверсальные коллекции. Универсальные коллекции являются строго типизированными во время компиляции. Таким образом, универсальные коллекции обычно обеспечивают более высокую производительность. Универсальные коллекции принимают параметр типа во время создания и не требуют приведение в тип Object и из него при добавлении или удалении элементов. Кроме того, большая часть универсальных коллекций поддерживается в приложениях Microsoft Store. Неуниверсальные коллекции хранят такие элементы, как Object, требуют приведения. Большая их часть не поддерживается для разработки приложений Microsoft Store. Однако неуниверсальные коллекции можно наблюдать в старом коде.

Начиная с .NET Framework 4, коллекции пространства имен System.Collections.Concurrent предоставляют эффективные потокобезопасные операции для доступа к элементам коллекции из нескольких потоков. Неизменяемые классы коллекций в пространстве имен System.Collections.Immutable (пакет NuGet) являются потокобезопасными, так как операции выполняются с копией исходной коллекции, а исходная коллекция неизменяемая.

Общие возможности коллекций

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

• Возможность перечисления коллекции

  Чтобы обеспечить итерацию по коллекции, коллекции .NET реализуют System.Collections.IEnumerable или System.Collections.Generic.IEnumerable<T>. Перечислитель может рассматриваться как перемещаемый указатель на любой элемент в коллекции. Foreach, in statement и the For Each... Следующая инструкция использует перечислитель, предоставляемый методомGetEnumerator, и скрывает сложность управления перечислителем. Кроме того, любая коллекция, реализующая System.Collections.Generic.IEnumerable<T>, считается запрашиваемым типом, и к ней можно создавать запросы LINQ. Запросы LINQ предоставляют общий шаблон для доступа к данным. Обычно они являются более четкими и удобочитаемыми, чем стандартные циклы foreach, и предлагают возможности фильтрации, упорядочения и группировки. LINQ запросы также могут повысить производительность. Дополнительные сведения см. в разделах LINQ to Objects (C#), LINQ to Objects (Visual Basic), Parallel LINQ (PLINQ), Введение в запросы LINQ (C#) и Базовые операции с запросами (Visual Basic).

• Возможность копирования содержимого коллекции в массив

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

Кроме того, во многих классах коллекций реализованы следующие возможности.

• Свойства "Емкость и количество элементов"

  Емкость коллекции — это число элементов, которое она может содержать. Количество элементов коллекции — это число элементов, которое она реально содержит. В некоторых коллекциях емкость или количество элементов скрыты.

  Большинство коллекции автоматически увеличивают емкость, если количество элементов достигает предела. Происходит перераспределение памяти, и элементы копируются из старой коллекции в новую. Это уменьшает объем кода, необходимого для использования коллекции. Однако производительность при работе с такой коллекцией может ухудшиться. Например, если Count меньше Capacity, для List<T> добавление элемента является операцией O(1). Если емкость нужно увеличить для размещения нового элемента, добавление элемента становится операцией O(n), где n — это Count. Наилучший способ избежать потерь производительности, вызванных множественными перераспределениями, — это установить начальную вместимость, равную предполагаемому размеру коллекции.

  BitArray является особым случаем; его емкость совпадает с его длиной, которая совпадает с количеством элементов.

• Согласованная нижняя граница

  Нижняя граница коллекции — это индекс ее первого элемента. Все индексированные коллекции в пространствах имен System.Collections имеют нижнюю границу, равную нулю. Класс Array по умолчанию имеет нижнюю границу, равную нулю, но при создании экземпляра класса Array с помощью Array.CreateInstance может быть задана другая нижняя граница.

• Синхронизация для доступа из нескольких потоков (только классы System.Collections).

  Неуниверсийные типы коллекций в System.Collections пространстве имен обеспечивают некоторую безопасность потоков с синхронизацией; обычно предоставляется через SyncRoot элементы и IsSynchronized элементы. Эти коллекции не являются потокобезопасными по умолчанию. Если требуется масштабируемый и эффективный многопотоковый доступ к коллекции, используйте один из классов в пространстве имен System.Collections.Concurrent или рассмотрите возможность использования неизменяемой коллекции. Дополнительные сведения см. в разделе Потокобезопасные коллекции.

Выбор коллекции

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

Действие	Возможности универсальной коллекции	Возможности неуниверсальной коллекции	Возможности потокобезопасной или неизменяемой коллекции
Хранение элементов в виде пар "ключ-значение" для быстрого поиска по ключу	Dictionary<TKey,TValue>	Hashtable (Коллекция пар "ключ-значение", которые упорядочены по хэш-коду ключа.)	ConcurrentDictionary<TKey,TValue> ReadOnlyDictionary<TKey,TValue> ImmutableDictionary<TKey,TValue>
Доступ к элементам по индексу	List<T>	Array ArrayList	ImmutableList<T> ImmutableArray
Использование элементов по принципу FIFO	Queue<T>	Queue	ConcurrentQueue<T> ImmutableQueue<T>
Использование данных по принципу LIFO	Stack<T>	Stack	ConcurrentStack<T> ImmutableStack<T>
Последовательный доступ к элементам	LinkedList<T>	Рекомендации отсутствуют	Рекомендации отсутствуют
Получение уведомлений при удалении элементов из коллекции или добавлении элементов в коллекцию. (реализует INotifyPropertyChanged и INotifyCollectionChanged)	ObservableCollection<T>	Рекомендации отсутствуют	Рекомендации отсутствуют
Отсортированная коллекция	SortedList<TKey,TValue>	SortedList	ImmutableSortedDictionary<TKey,TValue> ImmutableSortedSet<T>
Набор для математических функций	HashSet<T> SortedSet<T>	Рекомендации отсутствуют	ImmutableHashSet<T> ImmutableSortedSet<T>

Алгоритмическая сложность коллекций

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

Изменяемый	Амортизационный анализ	Худший случай	Неизменяемые	Сложность
Stack<T>.Push	O(1)	O(n)	ImmutableStack<T>.Push	O(1)
Queue<T>.Enqueue	O(1)	O(n)	ImmutableQueue<T>.Enqueue	O(1)
List<T>.Add	O(1)	O(n)	ImmutableList<T>.Add	O(log n)
List<T>.Item[Int32]	O(1)	O(1)	ImmutableList<T>.Item[Int32]	O(log n)
List<T>.Enumerator	O(n)	O(n)	ImmutableList<T>.Enumerator	O(n)
HashSet<T>.Add, поиск	O(1)	O(n)	ImmutableHashSet<T>.Add	O(log n)
SortedSet<T>.Add	O(log n)	O(n)	ImmutableSortedSet<T>.Add	O(log n)
Dictionary<T>.Add	O(1)	O(n)	ImmutableDictionary<T>.Add	O(log n)
Dictionary<T>, поиск	O(1)	O(1) — или строго O(n)	ImmutableDictionary<T>, поиск	O(log n)
SortedDictionary<T>.Add	O(log n)	O(n log n)	ImmutableSortedDictionary<T>.Add	O(log n)

List<T> можно эффективно перечислить с помощью цикла for или foreach. Но в случае с ImmutableList<T> использовать цикл for неэффективно, так как время для индексатора составляет O(log n). Перечисление ImmutableList<T> с помощью цикла foreach является эффективным, так как ImmutableList<T> использует двоичное дерево для хранения своих данных вместо простого массива, который использует List<T>. Массив можно быстро проиндексировать, тогда как двоичное дерево обрабатывается до тех пор, пока не будет найден узел с нужным индексом.

Кроме того, SortedSet<T> имеет ту же сложность, что и ImmutableSortedSet<T>. Это обусловлено тем, что в обоих случаях используются двоичные деревья. Существенная разница заключается в том, что ImmutableSortedSet<T> использует неизменяемое двоичное дерево. Так как ImmutableSortedSet<T> также предлагает класс System.Collections.Immutable.ImmutableSortedSet<T>.Builder, который допускает изменения, обеспечивается как неизменяемость, так и производительность.

См. также

Заголовок	Описание
Выбор класса коллекции	Описывает различные коллекций и содержит сведения по выбору коллекции, соответствующей сценарию пользователя.
Часто используемые типы коллекций	Описывает часто используемые типы универсальных и неуниверсальных коллекций, таких как System.Array, System.Collections.Generic.List<T> и System.Collections.Generic.Dictionary<TKey,TValue>.
Когда следует использовать универсальные коллекции	Рассматривает использование типов универсальных коллекций.
Сравнение и сортировка в коллекциях	Описывает использование проверок равенства и сортировки в коллекциях.
Отсортированные типы коллекций	Описывает производительность и характеристики отсортированных коллекций.
Типы коллекций Hashtable и Dictionary	Описывает возможности универсальных и неуниверсальных типов словарей на основе хэша.
Потокобезопасные коллекции	Описывает типы коллекций, такие как System.Collections.Concurrent.BlockingCollection<T> и System.Collections.Concurrent.ConcurrentBag<T>, поддерживающие безопасный и эффективный одновременный доступ из нескольких потоков.
System.Collections.Immutable	Приводятся вводные сведения о неизменяемых коллекциях и ссылки на типы коллекций.

Справочник

System.Array System.Collections System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable