C#: Array,List,Collection,Dictionary,HashSet,Queue,Stack,IEnumerable

# リストの種類多すぎ！？

C#初学者に必要以上に混乱を与える要素として、リスト／コレクションクラス多すぎ問題が知られています。

初学者への進言としては、とりあえず `List<T>` 使っとけーで、だいたいの局面は乗り切れるかなとも思いますが、C#を生業とするならば、ちゃんと各クラスの特徴を知った上で正しく使いわけられるようになりたいところ。

この記事では、コレクション使い分けの指針をいくらか共有できればと思います。

# 使わないもの

## System.Collections名前空間

`ArrayList` , `IList` , `ICollection` , `Hashtable` 等、C#にジェネリックが導入される以前の遺産である非ジェネリックなコレクションのクラス／インターフェースがSystem.Collections名前空間に存在します。

が、もはやこれらを直接使う必要性はほぼ無いと考えて良いでしょう。

本ページでもこれ以降触れることはありません。

# 主要インターフェース

## IEnumerable&lt;T&gt;

すべてのリスト・コレクションの基本となる、「列挙できる」ことを表すインターフェースです。

foreach文やLINQメソッドを適用できる最も抽象的なインターフェースであるため、公開メソッドの引数はとりあえず `IEnumerable<T>` にしとけ的なコードを見かけることがありますが、以下のような点に注意する必要があります。

### 有限である保証がない

`IEnumerable<T>` というインターフェースは、要素数が有限であることを保証しません。

例として、以下のメソッドは要素数が無限なコレクション（ `{0,0,0,0,0,...}` ）を返します。

```C#
public IEnumerable<int> EnumerateZero()
{
    while(true)
    {
        yield return 0;
    }
}
```

このようなコレクションをCount()で数えようとしたり、ToArray()で配列化しようとした瞬間にOverflow／OutOfMemoryで落ちます。

### 列挙のコストがわからない

`IEnumerable<T>` インターフェースは遅延評価をサポートします。
この実体が式である場合、必要になったタイミングで初めて評価されます。

メソッドの引数などで外部からこのインターフェースを受け取ると、列挙に伴うコストを予測することができません。

```C#
public void PrintNums(IEnumerable<int> nums)
{
    for (int i = 0; i < nums.Count(); i++)
    {
        var num = nums.ElementAt(i);
        Console.WriteLine(num);
    }
}
```

上のコードは一見なんの問題もないように見えますが、例えば以下のEnumerateNumsメソッドにより返される値を渡して実行した場合、

```C#
public IEnumerable<int> EnumerateNums()
{
    //1秒くらいかかる重い処理をしながら1,2,3,4を返す
    Thread.Sleep(1000);
    yield return 1;
    Thread.Sleep(1000);
    yield return 2;
    Thread.Sleep(1000);
    yield return 3;
    Thread.Sleep(1000);
    yield return 4;
}
```

```C#
var nums = EnumerateNums();
PrintNums(nums);
```

上記コードは、実行に **30秒** もかかります。[^1]

[^1]: nums.Count()が5回走るので4秒×5、nums.ElementAt(0)～nums.ElementAt(3)にそれぞれ1,2,3,4秒を要するので、20+1+2+3+4=30

このように要素数をCountする必要がある場合などは、引数をオブジェクト化された `List<T>` や `IReadOnlyList<T>` などの形で受け取るか、最初にオブジェクト化して、評価が1度しか走らないようにするべきです。

```C#
public void PrintNums(IEnumerable<int> nums)
{
    //ここで式が確定する（※ただし要素が有限である前提）
    var array = nums.ToArray();

    //もちろんforeachでも良い
    for (int i = 0; i < array.Length; i++)
    {
        var num = array[i];
        Console.WriteLine(num);
    }
}
```

上記コードなら4秒で実行されます。

もちろん、この遅延評価の性質は、使いどころを間違えなければ効率の良い処理の実装に役立つものです。
たとえば前述の `EnumerateNums()` の結果が1つ以上の要素を持つかどうかだけを知りたい場合、オブジェクト化して `EnumerateNums().ToArray().Length > 0` とやれば同様に4秒かかりますが、式のまま `EnumerateNums().Any()` と調べれば、最初の要素が返されるところまでしか評価されず、実行に1秒しかかかりません。

## ICollection&lt;T&gt;, IList&lt;T&gt;

`ICollection<T>` は要素数が有限であるコレクションを表すインターフェースです。

`IList<T>` は `ICollection<T>` を継承するインターフェースで、 `ICollection<T>` との違いは、インデクサプロパティと、Insert, RemoveAtといった、インデクスを指定して要素にアクセスできるメソッドを持つ点です。

`ICollection<T>` 、`IList<T>` には1つ罠があり、Add, Removeのようなメソッドが定義されているにもかかわらず、 **コレクションが編集可能であることを保証しません。**

代表的な例として、配列も `IList<T>` インターフェースを実装していますが、配列に対しAddメソッドを呼ぶと、NotSupportedExceptionがスローされます。

```C#
IList<int> ilist = new int[] { };
ilist.Add(1);  //throws NotSupportedException
```

このインターフェースを持つコレクションは、IsReadOnlyプロパティがFalseであることを確認してから編集を行うのが正しい使い方とされています。

## IReadOnlyCollection&lt;T&gt;, IReadOnlyList&lt;T&gt;

いちいちIsReadOnlyなんて見てられるか！ということで、待ち望まれていた、読み取り専用であることを表すインターフェースが .NET Framework 4.5で追加されました。

配列や `List<T>` をはじめ、ほとんどのコレクションクラスがこれらを実装しており、非常に使い勝手の良いインターフェースです。

メソッド内で変更する必要のないコレクションを引数として受け取る場合や、変更されたくないコレクションをプロパティとして公開する場合、 `IReadOnlyList<T>` を第一選択肢とするのが良いでしょう。


# 主要な実装クラス

## 配列

サイズ固定のコレクションクラスです。

`var array = new[] { 1, 2, 3 };` のように最もシンプルに宣言・初期化することができ、LINQ式の `IEnumerable<T>` をToArray()で簡単に配列化することもできるので、局所的な使用機会は少なくないでしょう。

ただし、サイズこそ固定ですが、格納値が不変となるわけではないところに注意が必要。手軽さゆえに安易に広いスコープで使われてバグの元となるケースをまま見かけます。

特に、以下のような配列の公開プロパティはアンチパターンとされています。

```C#
public int[] NumArray { get; private set; }
```

たとえsetterをprivateにしていたとしても、この配列の値を外から `NumArray[0] = 1` のように変更することができてしまいます。通常これはコーダーの意図に反していることが多いでしょう。

ほかに配列で留意すべき点として、 **連続したメモリ領域を必要とする** ことが挙げられます。

巨大なサイズの配列を作成する場合、たとえOSの空きメモリに余裕があったとしても、連続するメモリ空間としてそのサイズが確保できなければ、OutOfMemoryになってしまいます。

## List&lt;T&gt;

もっとも汎用的で使い勝手の良いクラスです。

LINQ式からもToList()で簡単にリスト化することができます。

パフォーマンスも決して悪くなく、それほど要素の多くならないコレクションでは、とりあえず `List<T>` にしておけばほぼ困ることはありません。
特にコレクションを返すメソッドでは、迷ったら `List<T>` で返す形にしておけば不便はないでしょう。

LINQ使いにとって特筆すべきは、[ForEach](https://msdn.microsoft.com/ja-jp/library/bwabdf9z(v=vs.110).aspx)メソッドを持っていること。
LINQ式につなげて書きやすいという理由でわざわざToList()してForEachを使うコードや、自前で `IEnumerable<T>` に対する拡張メソッドとして同等のForEachを定義しているコードなどもよく見かけます。

## Collection&lt;T&gt;

`ICollection<T>` の実装クラスです。

`List<T>` に比べると使用頻度は多くないと思いますが、特徴として、他のコレクションをラップするコンストラクタを持っています。

他のコレクションを読み取り専用のコレクションとしてラップして扱う `ReadOnlyCollection<T>` クラスもあり、先述の `IReadOnlyList<T>` が登場する前は特に活躍しました。

また、 `List<T>` クラスは、継承してサブクラスを作るような使われ方を想定していないらしく、そのような用途では `List<T>` よりも `Collection<T>` を基底クラスに使用するのが良いとされています。

## HashSet&lt;T&gt;, Dictionary&lt;TKey, TValue&gt;

`Dictionary<TKey, TValue>` は、キーと値の対応付けで要素を保持するコレクションです。

特徴として、キーの値は重複が許可されず、既に存在するキーをAddしようとすると例外がスローされます。

`HashSet<T>` は、Dictionaryのキーのみのようなコレクションで、重複のない一意の値を保持します。

どちらも内部的にハッシュコードによって管理・検索されており、単純なリストと比較すると、キーの検索は圧倒的に速いです。

大量のレコードから特定の要素を探したい場合には積極的にDictionaryを利用するのが良いでしょう。

HashSetは、要素の有無のみを調べたい際にはDictionary同様にハイパフォーマンスを期待できるほか、値に重複がないことを保証するコレクションとして使い勝手が良いです。

注意点として、どちらも **要素の格納順が保証されません。**

実は単純に要素を追加していく分にはその順番が保持されてしまうのですが、現状たまたまそうなっているだけですので、将来的に内部実装が変わる可能性はあります。

また、以下のように中身を抜いてからAddしたりしてみると、現在の実装でも順番が保持されないのがわかるかと思います。

```C#
var dic = new Dictionary<int, string>();
dic.Add(1, "");
dic.Add(2, "");
dic.Add(3, "");
dic.Remove(2); //key=2を削除
dic.Add(4, "");

//1, 4, 3 の順で出力される
dic.ToList().ForEach(p => Console.WriteLine(p.Key));
```

要素の順番を保持しつつDictionaryを使いたい場合は、

* `SortedDictionary<TKey, TValue>` を使う
* `List<T>` 等で保持しておいて、必要なときにToDictionary()して使う
* 要素を追加順で保持するDictionaryクラスを自作する

といった方法を検討します。

# 特殊なコレクション

その他のコレクションクラスにもちょっとだけ触れておきます。

## Concurrentなコレクション

System.Collections.Concurrent名前空間には、 `ConcurrentDictionary<TKey, TValue>` , `ConcurrentBag<T>` といった、スレッドセーフなコレクションクラスが用意されています。

複数のスレッドで共有する資源を管理するコレクションには、自前で `lock` による排他を行っても良いですが、これらのConcurrentなコレクションの利用も検討すると良いでしょう。

## Queue&lt;T&gt;, Stack&lt;T&gt;

`Queue<T>` と `Stack<T>` はどちらも、要素を1つずつ取り出して1度だけ使用する目的で利用されるコレクションです。

キューはいわゆるFIFO（先入れ先出し）で、最初にコレクションに入れたものから順番に取り出すためのデータ構造です。
レジの順番待ちに並ぶ人が、先頭から順にレジを通って列をぬけていくイメージです。

スタックはその反対で、LIFO（後入れ先出し）となります。
上に積み重ねていった座布団が、上から順に使われていくイメージです。

いずれも、 `List<T>` を使えば同等の操作は可能ですが、これらのクラスは **コレクションの使用意図** を表現するために使用するのが良いかと思います。
ある変数が `Queue<T>` になっていれば、これは先に入れたものから順に取り出して使用されるんだな、というのが一目瞭然になります。

逆にいうと、これらの用途に一致しない使い方をすると、読む人にとって混乱のもとになります。
Queueなのに最後に入れた値にアクセスしようとしたり、Stackなのに全要素から条件に一致する値を探そうとしたりしていることに気づいたら、これらの使用はやめて、おとなしく `List<T>` などに置き換えるのが良いでしょう。

## ObservableCollection&lt;T&gt;

`ObservableCollection<T>` は、 `INotifyCollectionChanged` インターフェースを実装し、コレクションに変更が生じたことを検知するためのコレクションクラスです。

主には、Binding機構をもつWPF等のフレームワークで、モデルのデータリストからビューの一覧へ変更を通知する目的で使用されます。
もちろん、`ObservableCollection<T>` 自体は特別なフレームワークに依存するクラスではないので、GUIアプリに限らず、コードからCollectionChangedイベントを購読して使うこともできます。

なお、最高に意味のわからないコレクションとして、 `ReadOnlyObservableCollection<T>` というのもあります。

変更されないのに何をObserveするんだよと思ってしまうところですが、これは `ObservableCollection<T>` をラップして扱うクラスになります。
このクラスに対して外部から変更を加えることはできませんが、もとになるObservableCollectionに変更が加えられた際には、このクラスにも変更が反映されます。

```C#
var obs = new ObservableCollection<int>();
var roObs = new ReadOnlyObservableCollection<int>(obs);

//roObs.Add(123); できない
obs.Add(123);

Console.WriteLine(obs.Count);   // 1
Console.WriteLine(roObs.Count); // 1
```

ですが、このReadOnlyObservableCollectionクラスでは、CollectionChangedイベントがprotectedに隠蔽されているため、なんと、このクラスに対して外から直接CollectionChangedを購読することはできません。

なので、通常はReadOnlyなコレクションとしてラップしたい場合は、`ReadOnlyCollection<T>` を使えば事足りるかと思います。

# 使い分けの指針まとめ

* 評価を遅延させたいI/Fでは `IEnumerable<T>` を使う
* 変更しない／させないことを表すI/Fでは `IReadOnlyList<T>` を使う
* 配列は局所的な利用に留める
* 汎用的なメソッドでは `List<T>` を返しておく
* 別のコレクションをラップして扱うときは `Collection<T>` , `ReadOnlyCollection<T>` を使う
* 要素検索のパフォーマンスを求めるときは `Dictionary<TKey, TValue>` を使う
* 値に重複がないことを保証したいときは `HashSet<T>` を使う

以上になります。