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

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

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

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

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

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

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 System.Collections.Concurrent System.Collections.Generic System.Collections.Specialized System.Linq System.Collections.Immutable