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

Связанные данные могут обрабатываться более эффективно, если они объединены в коллекцию. Для добавления, удаления и изменения отдельных элементов или диапазона элементов коллекции можно использовать класс 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 и For Each...Next Statement использует итератор, предоставляемый методом 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