29

C＃で利用できるさまざまな種類のリストと、それらの使用法が適切な場合を簡潔に説明するための優れたリソースを知っている人はいますか？

たとえば、リスト、ハッシュテーブル、辞書など。

いつ何を使うべきかよくわかりません。

4

10 に答える 10

32

これらはすべてコレクションですが、すべてがリストというわけではありません。ここに簡単な要約があります。

非ジェネリック コレクション (API はobject. 値の型はボックス化されています。

これらは主にSystem.Collections名前空間にあります。

  • ArrayList : 配列に基づくアイテムのリスト。高速ランダム読み取り/書き込みアクセス。バッファーのサイズ変更が必要ない場合は、末尾にすばやく追加します。
  • Hashtable : キーから値へのマップ。キーは一意ですが、値は一意である必要はありません。GetHashCode メソッドを使用して、O(1) に近い読み取り/書き込みアクセスを実現します (すべてのアイテムが同じハッシュを持つ場合や、バッキング ストアの再構築が必要な場合を除きます)。キーと値のペアを反復処理すると、順序が予測できなくなります。（まあ、事実上予測不可能です。）
  • SortedList : Hashtable と同様ですが、エントリは常にキーでソートされた順序で返されます。キーと値のペアのリストとして保存されます。
  • スタック: 後入れ先出しコレクション
  • Queue : 先入れ先出しコレクション
  • Array : 固定サイズの O(1) ランダム アクセス。非ジェネリックですが、強く型付けされたフォームもあります

ジェネリック コレクション。(厳密に型指定された API は、値の型をボックス化しません (適切な T を想定)。

これらは主にSystem.Collections.Generic 名前空間にあります。

おそらく最も重要なコレクションインターフェイスはIEnumerable (およびIEnumerable<T> ) です。これは、ストリームがバイトのシーケンスを表すのと同じように、アイテムのシーケンスを表します。ランダムアクセスはなく、前方読み取りのみです。LINQ to Objects はこれに基づいており、ほぼすべてのコレクション型がこれを実装しています。

于 2008-10-13T16:13:09.733 に答える
7

tobsen の以前の回答を詳しく説明すると、C5 Generic Collection Library には多数のコレクションがあります。ここでそれらのいくつかについて説明します。

キュー/スタック

  • CircularQueue<T>: このクラスは厳密にキューおよびスタック機能を提供します。同様に、スタック/キュー内の任意のアイテムへの効率的なO (1) アクセスは、インデクサーを使用して利用できますcq[0](0 は最も古いアイテムで、次にデキューされ、最後にポップされます)。

リスト

注:また、Queue/Stacks としても機能しますArrayList。LinkedList

  • ArrayList<T>: , の対応するものと同様にSystem.Collections.Generic (SCG)、List<T>これは配列によって支えられており、O (1) のインデックス付けが保証されていますが、最悪の場合はO ( n ) の挿入が保証されています。O ( n ) アイテムを検索します。
  • LinkedList<T>：対応するものと同様SCG.LinkedList<T>。二重リンク リストを使用すると、O (1) の挿入が保証されますが、最悪の場合はO ( n ) のインデックス付けが保証されます (実際には、リストの先頭または末尾からの距離に比例します)。また、 O ( n ) でアイテムを検索します。ソートには、安定した Merge Sort が使用されます。
  • HashedArrayList<T>:ArrayList<T>上記と同様ですが、重複は許可されません。その見返りとして得られる利点は、アイテムとそのインデックスを見つける時間がO (1) に短縮されることです。
  • HashedLinkedList<T>:LinkedList<T>上記と同様ですが、重複は許可されません。以前と同様に、アイテムを見つける時間はO (1) に短縮されますが、そのインデックスを見つける時間はO ( n ) のままです。
  • WrappedArray<T>: とかなり似ていますがArrayList<T>、これは を実装する配列のラッパーとして機能しますC5.IList<T>が、コレクションを変更しようとすると例外がスローされます (IsFixedSizeは true でありAdd、RemoveはInsert機能しません。ただし、 はSort機能Shuffleしません。Reverseインプレース操作)。

リストは、基になるリストのセグメントを表す「ビュー」機能も提供し、ローカル操作を実行できるようにします。C5 ブックで提供されているパターンを使用すると、配列と連結リストの両方で効率的なビューを使用して操作を実行できます。ビューに対して任意のリスト操作を実行することもでき、その効果は基になるリストのサブセットに制限されます。

ソートされたコレクション

  • SortedArray<T>ArrayList<T>:アイテムのソートを維持し、重複を許可しない点を除いて、 に似ています。このコレクションでのランダムな挿入と削除は遅いことに注意してください。このコレクションは、アイテムの数が少ないかほとんど変更されないが、アイテムのインデックスまたは値によって頻繁にアクセスされる場合に最適です。
  • TreeSet<T>: 赤黒のツリー構造を使用してアイテムを並べ替えます。セットですので、重複はできません。インデックスまたは項目値によるアクセスと挿入/削除はO ( log n ) かかります。
  • TreeBag<T>: 赤黒ツリーを使用して、アイテムをソートします。バッグとして、重複を許可しますが、重複をツリーに保存せず、カウントすることで重複を保持します。

と の両方が、 O (1) でツリーの「スナップショット」または永続的なコピーを効率的に作成する機能を提供しTreeSet<T>、基になるツリーを変更しながらスナップショットを反復処理できます。ツリーの各スナップショットは、ツリーへの更新にパフォーマンスのペナルティを追加しますが、これらの影響はスナップショットが破棄されるとなくなることに注意してください。TreeBag<T>

ハッシュ コレクション

  • HashSet<T>: ストレージに単純なハッシュ テーブルを使用するコレクション。項目値によるアクセスはO (1) かかります。セットですので、重複はできません。BucketCostDistribution()アイテムのハッシュコード関数の効率を判断するのに役立つ関数を提供します。
  • HashBag<T>: に似てHashSet<T>いますが、バッグのセマンティクスがあります。つまり、重複は許可されますが、重複はカウントによってのみ格納されます。

プライオリティ キュー

  • IntervalHeap<T>: プライオリティ キューを提供します。最大値と最小値を見つけるのはO (1) 回の操作であり、最大値、最小値の削除、追加、および更新はO ( log n ) 回の操作です。(カウントではなく) 明示的に格納することにより、重複を許可します。

辞書

  • HashDictionary<H,K>: と同様に、O (1)SCG.Dictionary<H,K>でエントリへのアクセス、挿入、および削除を提供します。上記のような機能も提供します。特定の列挙順序を保証するものではありません。BucketCostDistribution()HashSet<T>
  • TreeDictionary<H,K>: と同様に、SCG.SortedDictionary<H,K>赤黒木を使用して永続的にソートされたディクショナリを提供します。エントリへのアクセス、挿入、および削除はO ( log n ) で行われます。ディクショナリの列挙が、キー比較子によって指定された順序に従うことを保証します。

保護されたコレクション

同様に、C5 は「保護された」コレクションも提供します。これは、読み取り専用ラッパーとして効果的に機能し、コレクションが変更されるのを防ぎます。コレクション内のアイテムは引き続き変更できますが、アイテムをコレクションに追加、削除、または挿入することはできません。

長い答えですが、C5 ライブラリのさまざまなコレクションを自由に使用できます。私は C5 ライブラリが優れていることを発見し、自分のコードでよく使用して、一般的な C# ヘッダーを次のように置き換えます。

using C5;
using SCG = System.Collections.Generic;
于 2008-10-16T17:42:11.817 に答える
6

基本的なデータ構造に関する本を手に取る必要があります。言語に関係なく同じ理論です。

簡単な説明:

  • Array: (例のようにint[] myArray) - コレクションが変更されない場合に使用できる静的配列 (アイテムを追加または削除することはできませんが、個々のアイテムの値を変更することはできます)
  • ArrayList: 比較的高速な列挙と直接アクセスを可能にする汎用配列/リスト。このリストは、アイテムを追加すると自動的に大きくなりますが、 を格納するだけなので、Objectパフォーマンスとタイプ セーフの問題からめったに使用しないでください。
  • List<T>: 上記の ArrayList の汎用バージョン。パフォーマンスと柔軟性のバランスが取れているため、アイテムの動的なフラット リストがある場合は、ほとんど常に使用する必要があります。(.NET 2.0 の新機能)
  • Hashtable: フラット リストのように機能しますが、整数でインデックスを付ける代わりに、任意のオブジェクトを使用してインデックスを付けることができます。注目に値するのは、ハッシュ テーブルには「順序」がないことです。
  • Dictionary<T>: Hashtable の汎用バージョン。上記の ArrayList と List と同じ理由で、Hashtable の代わりに .NET 2.0 以降でこれを使用します。
  • Stack<T>: 先入れ後出しタイプのリストを提供します。最後に追加したアイテムは、何かを選択したときに最初に受け取るアイテムになります。
  • Queue<T>: 先入れ先出しリストを提供します。これは、一方の端にアイテムを挿入し、もう一方の端から取り出すチューブと考えてください。通常、スレッド間などでメッセージを渡すために使用されます。

一般に、.NET 2.0 以降で行うほとんどすべての操作にジェネリック コレクションを使用する必要があります。(ArrayList や HashTable などと比較して) 完全な型安全性が得られ、値の型 (整数、構造体、浮動小数点数など) については、非汎用的なものと比較してはるかに高速です。

決して変更されないアイテムのリストがある場合、または柔軟性が必要ない/必要ない場合List<T>は、もちろん配列を使用できます。これは、それらすべてのオーバーヘッドが最も少ないためです。

パブリック メソッドまたはパブリック プロパティからコレクションを返すときの推奨事項は、柔軟性の低いインターフェイスにキャストすることです。したがって、返される List がある場合は、それを にキャストできIEnumerable<int>ます。これは、消費者が項目を追加できないことを意味します (もちろん、それをキャストし直さない限り、それでもユーザーへの指示です)。キャストすると、API の安定性を維持しながら、基になるデータ構造を後で変更する柔軟性も得られます。ICollection<int>またはIList<int>、もう少し機能を公開することもできますが、実際のデータ構造は非表示のままにします。

于 2008-10-13T16:11:58.940 に答える
5

ハッシュマップ

  • 辞書
  • ハッシュテーブル (非ジェネリック)

これは、キーと値のペアを保持できるデータ構造です。順序付けの何らかの方法を持つ Key を指定すると、Value を挿入できます。簡単な例は、キーが学生 ID で、値が学生の名前である学生のリストです。

ランダム アクセス リスト

  • リスト
  • ArrayList (非ジェネリック)

ランダム アクセス リストは、ランダムにアクセスされるオブジェクトの長いリストを格納するために使用されます (つまり、O(1) 時間で n 番目の要素にアクセスしたい場合)。リストの途中で要素を挿入/削除したい場合は、リスト全体をシャッフルする必要があり、時間がかかる可能性があるため、適切ではありません。

リンクされたリストなど

  • リンクされたリスト
  • 列
  • スタック

リンクされたリストは、O(N) 時間かかるため、途中の要素にアクセスしたくない場合に最適です。いくつかのポインターを変更するだけなので、途中で要素を挿入/削除したい場合に最適です。

キューとスタックは、FIFO と FILO の動作 (それぞれ先入れ先出しと先入れ先出し) 用に最適化されているという点で、少し特殊化されています。

于 2008-10-13T16:11:29.877 に答える
2

これまでのすばらしい回答に加えて、 C5 GenericCollectionLibraryから入手できるコレクションがいくつかあります。ドキュメント（サイトにもあります）は、要件に応じて何を使用するかを決定する際に役立つ場合があります。

于 2008-10-13T19:07:34.967 に答える
2

System.CollectionsのMSDNDocoから始める場合は、個々のコレクションタイプにドリルダウンして、それらの「リスト」とその使用方法の詳細を確認できます。たとえば、のドコHashtableは、「キーのハッシュコードに基づいて編成されたキー/値のペアのコレクションを表します」と述べています。

ジェネリックスの理解におけるSystem.Collections.Genericについての素晴らしい議論もあります。

于 2008-10-13T15:59:44.940 に答える
2

List<T> は並べ替え可能ですが、公開することはお勧めしません。

Collection<T> は基本的な飾り気のないコレクションです。

Dictionary<T> は、キーと値のペアのコレクションです (古いハッシュテーブルによく似ていますが、現在は汎用です)。

KeyedCollection<T> は、値からキーを決定できる辞書です (これは抽象であるため、それを継承して GetKey 関数をサポートする必要があります)。

ReadOnlyCollection<T> は、内容を変更できない特別なコレクションです。

ArrayList と HashTable は、.NET 2.0 以降では基本的に廃止されています。

于 2008-10-13T16:05:56.817 に答える
1

MSDN には、 Selecting a Collection Classという記事があり、特定の状況で使用するコレクションの種類を把握しようとするときに非常に役立つと思います。

于 2009-05-04T14:59:41.813 に答える
0

これらは、さまざまなタイプの一般的なデータ構造の例です。これらのデータ構造は、ソフトウェアエンジニアリングの至る所で使用されています。

于 2008-10-13T16:00:59.230 に答える
-3

System.collections.Generic.コードウィンドウに入力するだけで、Intellisenseはそれぞれの簡単な説明を表示します。末尾の期間を忘れないでください。ああ、そしてもありSystem.Collections.ObjectModel.ます。そこから、MSDNから有望に見えるものについての詳細情報を取得できるはずです。

于 2008-10-13T16:00:10.620 に答える