コレクションとデータ構造体

多くの場合、類似するデータはコレクションとして格納および操作すると、より効率的に処理できます。 System.Array クラスまたは System.CollectionsSystem.Collections.GenericSystem.Collections.Concurrent、および System.Collections.Immutable 名前空間のクラスを使用して、コレクションの個々の要素または一定の範囲の要素を追加、削除、および変更できます。

主要なコレクションの型として、ジェネリック コレクションと非ジェネリック コレクションの 2 つがあります。 ジェネリック コレクションはコンパイル時にタイプ セーフです。 このため、通常、ジェネリック コレクションの方がパフォーマンスが高くなります。 ジェネリック コレクションは構築時に型パラメーターを受け取りますが、項目をコレクションに追加またはコレクションから削除するときに Object 型との間でキャストする必要はありません。 また、ほとんどのジェネリック コレクションが Windows ストア アプリでサポートされています。 非ジェネリック コレクションは、項目を Object として格納し、キャストが必要であり、ほとんどが Windows ストア アプリの開発でサポートされていません。 ただし、以前のコードに非ジェネリック コレクションが含まれている場合があります。

.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 ステートメント では、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 メソッドを使ってすべてのコレクションを配列にコピーできます。ただし、新しい配列の要素の順序は、列挙子が返す順序に基づきます。 結果の配列は、常に下限がゼロの 1 次元です。

また、多くのコレクション クラスに次の機能が含まれています。

  • 容量とカウントのプロパティ

    コレクションの容量とは、そこに含むことのできる要素の数です。 コレクションのカウントとは、実際に含まれている要素の数です。 コレクションによっては、容量またはカウント、あるいはその両方を内部で処理する場合があります。

    ほとんどのコレクションで、現在の容量に達すると自動的に容量が拡張されます。 メモリが再割り当てされ、要素は古いコレクションから新しいコレクションにコピーされます。 これにより、コレクションを使用するために必要なコードが削減されます。ただし、コレクションのパフォーマンスに悪影響を及ぼす可能性があります。 たとえば、List<T> では、CountCapacity 未満の場合、項目の追加は O(1) 操作になります。 容量を増やして新しい要素を格納する必要がある場合、項目の追加は O(n) 操作になります。ここで、nCount です。 複数の再割り当てによるパフォーマンスの低下を回避するには、初期容量をコレクションの見積もりサイズに設定しておくことが最善の方法です。

    BitArray は特殊なケースで、その容量はその長さと同じで、長さはそのカウントと同じです。

  • 一貫した下限

    コレクションの下限とは、最初の要素のインデックスです。 System.Collections 名前空間のすべてのインデックス付きコレクションの下限がゼロです。つまり、インデックスがゼロから始まります。 Array の下限は既定でゼロですが、Array.CreateInstance を使用して Array クラスのインスタンスを作成する場合には、別の下限を定義できます。

  • 複数のスレッドからのアクセスの同期 (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> 推奨しません 推奨しません
項目がコレクションから削除またはコレクションに追加されるときに通知を受け取る。 (INotifyPropertyChangedINotifyCollectionChanged を実装する) 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, lookup 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>lookup O(1) O(1) –厳密には O(n) ImmutableDictionary<T>lookup 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> では、インデクサーの O(log n) 時間が原因で、for ループ内のジョブは適切に実行されません。 foreach ループを使用した ImmutableList<T> の列挙は、ImmutableList<T> では、List<T> のような単純な配列ではなく、バイナリ ツリーを使用してデータを格納するため、効率的です。 配列は、簡単にインデックスを付けることができます。一方、バイナリ ツリーは、目的のインデックスを持つノードが見つかるまで下に移動する必要があります。

さらに、SortedSet<T> の複雑さは ImmutableSortedSet<T> と同じです。 これらは両方ともバイナリ ツリーを使用するからです。 もちろん、大きな違いは、ImmutableSortedSet<T> では、変更できないバイナリ ツリーが使用されることです。 ImmutableSortedSet<T> には、変更を許可する System.Collections.Immutable.ImmutableSortedSet<T>.Builder クラスも用意されているため、不変性とパフォーマンスの両方を備えることができます。

Title 説明
コレクション クラスの選択 さまざまなコレクションについて説明し、いずれかのシナリオを選択できるよう支援します。
一般的に使用されるコレクション型 System.ArraySystem.Collections.Generic.List<T>System.Collections.Generic.Dictionary<TKey,TValue> などの一般的に使用されるジェネリックと非ジェネリック コレクション型について説明します。
ジェネリック コレクションを使用する状況 ジェネリック コレクション型の使用について説明します。
コレクション内での比較と並べ替え コレクションでの等価比較と並べ替え比較の使用について説明します。
Sorted コレクション型 並べ替えられたコレクションのパフォーマンスと特性について説明します
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