コレクションとデータ構造体Collections and Data Structures

多くの場合、類似するデータはコレクションとして格納および操作すると、より効率的に処理できます。Similar data can often be handled more efficiently when stored and manipulated as a collection. System.Array クラスまたは System.CollectionsSystem.Collections.GenericSystem.Collections.Concurrent、および System.Collections.Immutable 名前空間のクラスを使用して、コレクションの個々の要素または一定の範囲の要素を追加、削除、および変更できます。You can use the System.Array class or the classes in the System.Collections, System.Collections.Generic, System.Collections.Concurrent, and System.Collections.Immutable namespaces to add, remove, and modify either individual elements or a range of elements in a collection.

主要なコレクションの型として、ジェネリック コレクションと非ジェネリック コレクションの 2 つがあります。There are two main types of collections; generic collections and non-generic collections. ジェネリック コレクションはコンパイル時にタイプ セーフです。Generic collections are type-safe at compile time. このため、通常、ジェネリック コレクションの方がパフォーマンスが高くなります。Because of this, generic collections typically offer better performance. ジェネリック コレクションは構築時に型パラメーターを受け取りますが、項目をコレクションに追加またはコレクションから削除するときに Object 型との間でキャストする必要はありません。Generic collections accept a type parameter when they are constructed and do not require that you cast to and from the Object type when you add or remove items from the collection. また、ほとんどのジェネリック コレクションが Windows ストア アプリでサポートされています。In addition, most generic collections are supported in Windows Store apps. 非ジェネリック コレクションは、項目を Object として格納し、キャストが必要であり、ほとんどが Windows ストア アプリの開発でサポートされていません。Non-generic collections store items as Object, require casting, and most are not supported for Windows Store app development. ただし、以前のコードに非ジェネリック コレクションが含まれている場合があります。However, you may see non-generic collections in older code.

.NET Framework 4 より、System.Collections.Concurrent 名前空間のコレクションによって、複数のスレッドからコレクション項目にアクセスするための効率的なスレッドセーフ操作が可能になります。Starting with .NET Framework 4, the collections in the System.Collections.Concurrent namespace provide efficient thread-safe operations for accessing collection items from multiple threads. System.Collections.Immutable 名前空間の変更できないコレクション クラス (NuGet パッケージ) は、操作が元のコレクションのコピーで実行され、元のコレクションは変更不可能なため、本質的にスレッドセーフです。The immutable collection classes in the System.Collections.Immutable namespace (NuGet package) are inherently thread-safe because operations are performed on a copy of the original collection and the original collection cannot be modified.

一般的なコレクションの機能Common collection features

すべてのコレクションに、コレクション内の項目を追加、削除、または検索するためのメソッドが用意されています。All collections provide methods for adding, removing, or finding items in the collection. また、ICollection インターフェイスまたは ICollection<T> インターフェイスを直接または間接的に実装するすべてのコレクションで、次の機能を共有しています。In addition, all collections that directly or indirectly implement the ICollection interface or the ICollection<T> interface share these features:

また、多くのコレクション クラスに次の機能が含まれています。In addition, many collection classes contain the following features:

  • 容量とカウントのプロパティCapacity and Count properties

    コレクションの容量とは、そこに含むことのできる要素の数です。The capacity of a collection is the number of elements it can contain. コレクションのカウントとは、実際に含まれている要素の数です。The count of a collection is the number of elements it actually contains. コレクションによっては、容量またはカウント、あるいはその両方を内部で処理する場合があります。Some collections hide the capacity or the count or both.

    ほとんどのコレクションで、現在の容量に達すると自動的に容量が拡張されます。Most collections automatically expand in capacity when the current capacity is reached. メモリが再割り当てされ、要素は古いコレクションから新しいコレクションにコピーされます。The memory is reallocated, and the elements are copied from the old collection to the new one. これにより、コレクションを使用するために必要なコードが削減されます。ただし、コレクションのパフォーマンスに悪影響を及ぼす可能性があります。This reduces the code required to use the collection; however, the performance of the collection might be negatively affected. たとえば、List<T> では、CountCapacity 未満の場合、項目の追加は O(1) 操作になります。For example, for List<T>, if Count is less than Capacity, adding an item is an O(1) operation. 容量を増やして新しい要素を格納する必要がある場合、項目の追加は O(n) 操作になります。ここで、nCount です。If the capacity needs to be increased to accommodate the new element, adding an item becomes an O(n) operation, where n is Count. 複数の再割り当てによるパフォーマンスの低下を回避するには、初期容量をコレクションの見積もりサイズに設定しておくことが最善の方法です。The best way to avoid poor performance caused by multiple reallocations is to set the initial capacity to be the estimated size of the collection.

    BitArray は特殊なケースで、その容量はその長さと同じで、長さはそのカウントと同じです。A BitArray is a special case; its capacity is the same as its length, which is the same as its count.

  • 一貫した下限A consistent lower bound

    コレクションの下限とは、最初の要素のインデックスです。The lower bound of a collection is the index of its first element. System.Collections 名前空間のすべてのインデックス付きコレクションの下限がゼロです。つまり、インデックスがゼロから始まります。All indexed collections in the System.Collections namespaces have a lower bound of zero, meaning they are 0-indexed. Array の下限は既定でゼロですが、Array.CreateInstance を使用して Array クラスのインスタンスを作成する場合には、別の下限を定義できます。Array has a lower bound of zero by default, but a different lower bound can be defined when creating an instance of the Array class using Array.CreateInstance.

  • 複数のスレッドからのアクセスの同期 (System.Collections クラスのみ)。Synchronization for access from multiple threads (System.Collections classes only).

    System.Collections 名前空間の非ジェネリック コレクション型では、同期によるスレッド セーフが提供され、通常、SyncRoot メンバーと IsSynchronized メンバーを介して公開されます。Non-generic collection types in the System.Collections namespace provide some thread safety with synchronization; typically exposed through the SyncRoot and IsSynchronized members. 既定では、これらのコレクションはスレッド セーフではありません。These collections are not thread-safe by default. 拡張性が高く効率的な、コレクションへのマルチスレッド アクセスが必要な場合は、System.Collections.Concurrent 名前空間のいずれかのクラスを使用するか、変更できないコレクションを使用することを検討します。If you require scalable and efficient multi-threaded access to a collection, use one of the classes in the System.Collections.Concurrent namespace or consider using an immutable collection. 詳しくは、「スレッド セーフなコレクション」を参照してください。For more information, see Thread-Safe Collections.

コレクションの選択Choose a collection

通常は、ジェネリック コレクションを使用します。In general, you should use generic collections. 次の表では、一般的なコレクションのシナリオとこれらのシナリオに使用できるコレクション クラスについて説明します。The following table describes some common collection scenarios and the collection classes you can use for those scenarios. ジェネリック コレクションに対する知識がない場合、このテーブルは、タスクに最適なジェネリック コレクションを選択するのに役立ちます。If you are new to generic collections, this table will help you choose the generic collection that works the best for your task.

やりたいことI want to… ジェネリック コレクションのオプションGeneric collection options 非ジェネリック コレクションのオプションNon-generic collection options スレッド セーフまたは変更できないコレクションのオプションThread-safe or immutable collection options
キーによるクイック検索用のキー/値のペアとして項目を保存するStore items as key/value pairs for quick look-up by key Dictionary<TKey,TValue> Hashtable

(キーのハッシュ コードに基づいて編成された、キーと値のペアのコレクション。)(A collection of key/value pairs that are organized based on the hash code of the key.)


インデックスで項目にアクセスするAccess items by index List<T> Array


先入れ先出し (FIFO) で項目を使用するUse items first-in-first-out (FIFO) Queue<T> Queue ConcurrentQueue<T>

後入れ先出し (LIFO) でデータを使用するUse data Last-In-First-Out (LIFO) Stack<T> Stack ConcurrentStack<T>

項目に順次アクセスするAccess items sequentially LinkedList<T> 推奨しませんNo recommendation 推奨しませんNo recommendation
項目がコレクションから削除またはコレクションに追加されるときに通知を受け取る。Receive notifications when items are removed or added to the collection. (INotifyPropertyChangedINotifyCollectionChanged を実装する)(implements INotifyPropertyChanged and INotifyCollectionChanged) ObservableCollection<T> 推奨しませんNo recommendation 推奨しませんNo recommendation
並べ替えられたコレクションA sorted collection SortedList<TKey,TValue> SortedList ImmutableSortedDictionary<TKey,TValue>

数学関数のセットA set for mathematical functions HashSet<T>

推奨しませんNo recommendation ImmutableHashSet<T>


コレクションのアルゴリズムの複雑さAlgorithmic complexity of collections

コレクション クラスを選択する際は、パフォーマンスの潜在的なトレードオフを考慮する必要があります。When choosing a collection class, it is worth considering potential tradeoffs in performance. アルゴリズムの複雑さについては、次の表を使用して、さまざまな変更可能なコレクション型とそれに対応する変更できないコレクション型を比較できます。Use the following table to reference how various mutable collection types compare in algorithmic complexity to their corresponding immutable counterparts. 変更できないコレクション型は多くの場合、パフォーマンスは劣りますが、不変性が提供され、これは、比較時に有効なメリットになることが多いです。Often immutable collection types are less performant but provide immutability - which is often a valid comparative benefit.

変更可能Mutable 分散Amortized 最悪のケースWorst Case 変更不可Immutable 複雑さComplexity
Stack<T>.Push O(1)O(1) O(n)O(n) ImmutableStack<T>.Push O(1)O(1)
Queue<T>.Enqueue O(1)O(1) O(n)O(n) ImmutableQueue<T>.Enqueue O(1)O(1)
List<T>.Add O(1)O(1) O(n)O(n) ImmutableList<T>.Add O(log n)O(log n)
List<T>.Item[Int32] O(1)O(1) O(1)O(1) ImmutableList<T>.Item[Int32] O(log n)O(log n)
List<T>.Enumerator O(n)O(n) O(n)O(n) ImmutableList<T>.Enumerator O(n)O(n)
HashSet<T>.Add, lookupHashSet<T>.Add, lookup O(1)O(1) O(n)O(n) ImmutableHashSet<T>.Add O(log n)O(log n)
SortedSet<T>.Add O(log n)O(log n) O(n)O(n) ImmutableSortedSet<T>.Add O(log n)O(log n)
Dictionary<T>.Add O(1)O(1) O(n)O(n) ImmutableDictionary<T>.Add O(log n)O(log n)
Dictionary<T>lookupDictionary<T> lookup O(1)O(1) O(1) –厳密には O(n)O(1) – or strictly O(n) ImmutableDictionary<T>lookupImmutableDictionary<T> lookup O(log n)O(log n)
SortedDictionary<T>.Add O(log n)O(log n) O(n log n)O(n log n) ImmutableSortedDictionary<T>.Add O(log n)O(log n)

List<T> は、for ループまたは foreach ループを使用して効率的に列挙できます。A List<T> can be efficiently enumerated using either a for loop or a foreach loop. ただし、ImmutableList<T> では、インデクサーの O(log n) 時間が原因で、for ループ内のジョブは適切に実行されません。An ImmutableList<T>, however, does a poor job inside a for loop, due to the O(log n) time for its indexer. foreach ループを使用した ImmutableList<T> の列挙は、ImmutableList<T> では、List<T> のような単純な配列ではなく、バイナリ ツリーを使用してデータを格納するため、効率的です。Enumerating an ImmutableList<T> using a foreach loop is efficient because ImmutableList<T> uses a binary tree to store its data instead of a simple array like List<T> uses. 配列は、簡単にインデックスを付けることができます。一方、バイナリ ツリーは、目的のインデックスを持つノードが見つかるまで下に移動する必要があります。An array can be very quickly indexed into, whereas a binary tree must be walked down until the node with the desired index is found.

さらに、SortedSet<T> の複雑さは ImmutableSortedSet<T> と同じです。Additionally, SortedSet<T> has the same complexity as ImmutableSortedSet<T>. これらは両方ともバイナリ ツリーを使用するからです。That's because they both use binary trees. もちろん、大きな違いは、ImmutableSortedSet<T> では、変更できないバイナリ ツリーが使用されることです。The significant difference, of course, is that ImmutableSortedSet<T> uses an immutable binary tree. ImmutableSortedSet<T> には、変更を許可する System.Collections.Immutable.ImmutableSortedSet<T>.Builder クラスも用意されているため、不変性とパフォーマンスの両方を備えることができます。Since ImmutableSortedSet<T> also offers a System.Collections.Immutable.ImmutableSortedSet<T>.Builder class that allows mutation, you can have both immutability and performance.

TitleTitle 説明Description
コレクション クラスの選択Selecting a Collection Class さまざまなコレクションについて説明し、いずれかのシナリオを選択できるよう支援します。Describes the different collections and helps you select one for your scenario.
一般的に使用されるコレクション型Commonly Used Collection Types System.ArraySystem.Collections.Generic.List<T>System.Collections.Generic.Dictionary<TKey,TValue> などの一般的に使用されるジェネリックと非ジェネリック コレクション型について説明します。Describes commonly used generic and nongeneric collection types such as System.Array, System.Collections.Generic.List<T>, and System.Collections.Generic.Dictionary<TKey,TValue>.
ジェネリック コレクションを使用する状況When to Use Generic Collections ジェネリック コレクション型の使用について説明します。Discusses the use of generic collection types.
コレクション内での比較と並べ替えComparisons and Sorts Within Collections コレクションでの等価比較と並べ替え比較の使用について説明します。Discusses the use of equality comparisons and sorting comparisons in collections.
Sorted コレクション型Sorted Collection Types 並べ替えられたコレクションのパフォーマンスと特性について説明しますDescribes sorted collections performance and characteristics
Hashtable コレクション型と Dictionary コレクション型Hashtable and Dictionary Collection Types ジェネリックと非ジェネリックのハッシュをベースにしたディクショナリ型の機能について説明します。Describes the features of generic and non-generic hash-based dictionary types.
スレッドセーフなコレクションThread-Safe Collections 複数のスレッドからの安全で効率的な同時アクセスをサポートする System.Collections.Concurrent.BlockingCollection<T>System.Collections.Concurrent.ConcurrentBag<T> などのコレクション型について説明します。Describes collection types such as System.Collections.Concurrent.BlockingCollection<T> and System.Collections.Concurrent.ConcurrentBag<T> that support safe and efficient concurrent access from multiple threads.
System.Collections.ImmutableSystem.Collections.Immutable 変更できないコレクションを導入し、コレクション型へのリンクを提供します。Introduces the immutable collections and provides links to the collection types.


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