List<T>について本気出して調べてみた

# はじめに

List＜T＞クラスについて、あれやこれや書きたいと思います。

「普段何気なく使ってるけど、言われてみれば中身とか全然知らんわ。」

「でも改めて考えると、すごく気になってきた。」

っていう~~ちょっと変わった~~人向けです。

ほぼ全部独学で書いたので、間違ってたら指摘してください。

# List＜T＞とは

CからC#に移って来た人間が一番最初に感動するやつ__(私が証明です)__

ざっくり言うと、サイズの管理をしなくてもいい配列__(多少の語弊あり)__

C#でそれなりの規模のプログラムを組んでいれば絶対に1度はお世話になる__(はず)__

## 定義はどこにあるの？
mscorlib.dll → System.Collections.Generic名前空間の下にあります。

https://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

ソースコードは↑でも見れるし、デコンパイルしても見れるよ。



# List＜T＞のあれやこれや

## その前に＜T＞ってなに？

ジェネリクス（ジェネリック）と呼ばれている凄いヤツです。

__型だけ違っていて、中身は同じ__であるような一連の処理があったときに、__型をパラメータにとり__、さまざまな型に対応したクラスや関数を作るためのものになります。

`List<string>`とか`List<int>`とか`List<MyClass>`とかやると思いますが、この`string`とか`int`とか`MyClass`とかが__型をパラメータにとり__の部分。

どれも複数の値をまとめるものなので、__型だけ違っていて、中身は同じ__。

## Listの中身ってどうなってるの？

配列です。`private T[] _items`で中身を管理してます。

なのに簡単に要素を増やせるし、減らせる。素晴らしいですね。

## 配列なのにサイズの管理をしなくてもいいの？

厳密に言えば__しなくていい訳ではない__です。__List側で勝手にやって__ます。

なので、利用者はあまり気にすることなく使えます。

具体的には`_items.Length`と `private int _size`と`public int Capacity`の3つの要素でサイズを管理しています。

### Countってのがあった気がするけど？

Listを使うときによく使うCount(プロパティ)ですが、

```C#
public int Count
{
    get
    {
        return _size;
    }
}
```

となっているので、_sizeと同じです。

ちなみにCountメソッドってのもありますが、__Listクラスに定義は存在しません。__

__拡張メソッド__と呼ばれる機能を使って、`Enumerable`クラスに定義されてます。

こいつの話をしだすと、`IEnumerable<T>`とか、`Func`デリゲートとか、ラムダ式とか、LINQとか、色々話が広がりすぎるので今回は割愛します。

ソースコードは、System.Core.dll → System.Linq名前空間の下にいます。

こっちはGitHubにおいてあります。

https://github.com/dotnet/corefx/blob/master/src/System.Linq/src/System/Linq/Count.cs

## 要素の取得ってどうなってるの？

[]で要素を取得・設定する処理のコードです。

```c#
public T this[int index]
{
    get
    {
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        return _items[index];
    }
    set
    {
        if ((uint)index >= (uint)_size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        _items[index] = value;
        _version++;
    }
}
```

このメソッド自体は__インデクサー__と呼ばれるC#で用意されている機能です。

indexがsizeより大きい場合や0以下の場合、`ArgumentOutOfRangeException`が発生します。

## 要素の追加ってどうなってるの？

要素追加用メソッド`Add`です。こいつは4段階の構成になっています。

```C#
public void Add(T item)
{
    if (_size == _items.Length)
    {
        EnsureCapacity(_size + 1);
    }
    _items[_size++] = item;
    _version++;
}
```

```C#
private void EnsureCapacity(int min)
{
    if (_items.Length < min)
    {
        int num = (_items.Length == 0) ? 4 : (_items.Length * 2);
        if ((uint)num > 2146435071u)
        {
            num = 2146435071;
        }
        if (num < min)
        {
            num = min;
        }
        Capacity = num;
    }
}
```

```C#
public int Capacity
{
    [__DynamicallyInvokable]
    get
    {
        return _items.Length;
    }
    [__DynamicallyInvokable]
    set
    {
        if (value < _size)
        {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }
        if (value != _items.Length)
        {
            if (value > 0)
            {
                T[] array = new T[value];
                if (_size > 0)
                {
                    Array.Copy(_items, 0, array, 0, _size);
                }
                _items = array;
            }
            else
            {
                _items = _emptyArray;
            }
        }
    }
}
```

4段階目の`Array.Copy`は、配列をコピーするメソッドです。

後で詳しく説明しますので、この段階ではそんなもんかと思っていてください。

1. `Add`呼び出し時に`_size`と`_items.Length`が同じだった場合、`EnsureCapacity`を呼び出す。
2. `EnsureCapacity`呼び出し時に`_items.Length`の2倍と引数`min`を比較し、大きい方を`Capacity`に設定。
3. `Capacity`のSetterで`_items.Length`と設定値`value`を比較し、配列の新規作成と既存部分のコピーを行う。

つまりListは__「サイズを無視して要素を追加できる配列」__ではなく、__「サイズが足りなくなったら自動で作り直してくれる配列」__なんです。実に優秀なお方ですね。

### パフォーマンス測ってみた

上記の理由から、Addを大量に呼び出す場合は、あらかじめ`Capacity`を自分で設定しておいたほうがパフォーマンスに優れます。(配列の新規作成や要素のコピーには時間がかかる)

というわけで、早速測ってみました。

``` ini
BenchmarkDotNet=v0.11.3, OS=Windows 10.0.15063.1508 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
Frequency=3312643 Hz, Resolution=301.8738 ns, Timer=TSC
  [Host]     : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
  DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
```

```C#
public class Tests
{
    private int num = 100_000_000;
    public Tests()
    {
        ListTest1();
        ListTest2();
    }

    [Benchmark]
    public void ListTest1()
    {
        //特に何もしない。
        var a = new List<int>();
        for (int i = 0; i < num; i++)
        {
            a.Add(i);
        }
    }

    [Benchmark]
    public void ListTest2()
    {
        // コンストラクタの引数であらかじめCapacityを設定できる。
        var b = new List<int>(num);
        for (int i = 0; i < num; i++)
        {
            b.Add(i);
        }
    }
}
```

| Method    |     Mean |    Error |   StdDev |
| --------- | -------: | -------: | -------: |
| ListTest1 | 550.7 ms | 4.740 ms | 4.434 ms |
| ListTest2 | 336.4 ms | 1.259 ms | 1.116 ms |

リストに0から1億個数字を追加した時の差がこれくらいでした。

これを大きいと見るか、小さいと見るかは人それぞれですが、個人的にはそんなに大きくないと思います。

1億もデータがあったらもっと遅い処理がどこかにあるはずなので、誤差レベルじゃないかと。

ですが、シビアなパフォーマンスを求められる局面に出会ったら思い出してください。

## 要素の削除ってどうなってるの？

要素削除用メソッド`RemoveAt`です。こいつの構成は2段階です。

```c#
public void RemoveAt(int index)
{
    // (1)
    if ((uint)index >= (uint)_size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    // (2)
    _size--;
    if (index < _size)
    {
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    // (3)
    _items[_size] = default(T);
    _version++;
}
```

```C#
public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
{
    Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, false);
}

internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);
```

ぱっと見て、分かりにくい処理です。

(1)から順に追っていきましょう。

```c#
// (1)
if ((uint)index >= (uint)_size)
{
    ThrowHelper.ThrowArgumentOutOfRangeException();
}
```

ここは特に言うこともありません。

indexがsizeより大きい場合や0以下の場合、`ArgumentOutOfRangeException`が発生します。

```C#
// (2)
_size--;
if (index < _size)
{
    Array.Copy(_items, index + 1, _items, index, _size - index);
}
```

`_size--`でListのサイズを1つ小さくします。

問題はその次です。

Array.Copyの中身はCopyですが、このCopyの中身は見ることができません。

こいつはC++で書かれてるDLLを参照しています。

仕方がないので、皆大好きMicrosoft公式リファレンスにて、Array.Copyの仕様を調べます。

> Copy(Array, Int32, Array, Int32, Int32)
>
> Copies a range of elements from an [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2) starting at the specified source index and pastes them to another [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2) starting at the specified destination index. The length and the indexes are specified as 32-bit integers.
>
> 指定されたコピー元インデックスから始まる配列から要素の範囲をコピーし、指定されたコピー先インデックスから始まる別の配列にそれらを貼り付けます。 長さとインデックスは32ビット整数として指定されます。

> #### Parameters
>
> - sourceArray
>
>   [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2)
>
> The [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2) that contains the data to copy.
>
> - sourceIndex
>
>   [Int32](https://docs.microsoft.com/en-us/dotnet/api/system.int32?view=netframework-4.7.2)
>
> A 32-bit integer that represents the index in the `sourceArray` at which copying begins.
>
> - destinationArray
>
>   [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2)
>
> The [Array](https://docs.microsoft.com/en-us/dotnet/api/system.array?view=netframework-4.7.2) that receives the data.
>
> - destinationIndex
>
>   [Int32](https://docs.microsoft.com/en-us/dotnet/api/system.int32?view=netframework-4.7.2)
>
> A 32-bit integer that represents the index in the `destinationArray` at which storing begins.
>
> - length
>
>   [Int32](https://docs.microsoft.com/en-us/dotnet/api/system.int32?view=netframework-4.7.2)
>
> A 32-bit integer that represents the number of elements to copy.
>
> パラメーター
> sourceArray
> アレイ
> コピーするデータを含む配列。
>
> sourceIndex
> Int32
> コピーが開始されるsourceArray内のインデックスを表す32ビット整数。
>
> destinationArray
> アレイ
> データを受け取る配列。
>
> destinationIndex
> Int32
> 保存が始まるdestinationArray内のインデックスを表す32ビット整数。
>
> 長さ
> Int32
> コピーする要素の数を表す32ビット整数。

日本語部分がGoogle翻訳にぶん投げた結果です。

つまり`_items`の `index + 1`インデックス目から`_size - index`個の要素を、`_items`の`index`インデックス目を開始位置としてコピーする処理ってことですね。

```C#
// (3)
_items[_size] = default(T);
_version++;
```

そして最後に、隙間をdefaultで埋めて終わりです。

### 全く理解が追いつかないのだが？

表を使って詳しく説明します。

| 0    | 1    | 2     | 3    | 4    | 5    |
| ---- | ---- | ----- | ---- | ---- | ---- |
| a    | b    | **c** | d    | e    | f    |

List＜string＞の中身だと思ってください。この時`_size`は6です。

このListからcを消したいと思います。

`RemoveAt(2)`を実行します。`index`は2です。

`index < _size`なので(1)で例外は発生しません。

(2)の最初で`_size`が5になります。

よって、

`index+1` => 3

`_size - index` => 3

となるので、`_items`の3インデックス目から3個の要素を、`_items`の2インデックス目を開始位置としてコピーします。

| 0    | 1    | 2        | 3       | 4       | 5    |
| ---- | ---- | -------- | ------- | ------- | ---- |
| a    | b    | ***ｄ*** | ***e*** | ***f*** | f    |

このままでは最後に不要なデータが残ってしまうので、一番最後をdefault(string)、空文字で埋めます。

| 0    | 1    | 2    | 3    | 4    | 5    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| a    | b    | ｄ   | e    | f    |      |

無事に、cを消すことができました。

ちなみに(2)で`if (index < _size)`と判定してます。

これは`index`と`_size`が同じ(=一番最後の要素を削除したい)場合、一番最後をdefault(T)で埋めるだけでいいからです。

### メモリ的な話

ここで1つ大事(かもしれない)事です。

**要素を削除した時、配列のサイズは変わらない**んです。

なので、大量の要素を削除した時、配列の後ろに**大量の空の部分**が出来上がります。

中身は空でもメモリは消費するので、気をつけてください。

今どきそれほどシビアなメモリ管理が必要なことはあまり無いとは思いますが。


## 例外ってどうなってるの？

1. `System.ArgumentOutOfRangeException`
2. `System.ArgumentNullException`
3. `System.InvalidOperationException`
4. `System.ArgumentException`
5. `System.OutOfMemoryException`


Listクラス内で発生する可能性のある例外たちです。

出現頻度は、1 >= 2 > 3 >>>> 4 >>>> 5です。**(当社調べ)**

ここでは出現頻度の低い4,5は割愛します。

### 1.ArgumentOutOfRangeException

要素の取得時や削除時に、`_size`より大きな値や0未満の値を設定すると発生します。

よく初心者が「要素が6なんだから最後は6番目やん、`list[6]`っと」と言って踏み抜くやつです。

### 2.ArgumentNullException

引数にnullを設定して一部のメソッドを呼び出すと、発生します。

「いちいち`Add`なんてやってられんわ、`AddRange`使ったろ」と言ったときに、引数を初期化し忘れて踏むことがあります。

### 3.InvalidOperationException

上2つはそのままですが、こいつは少しややこしいです。

直訳すると「**無効な操作**による例外」です。**無効な操作**ってなんやねん。

良く見るパターンはこんな感じのやつです。

```c#
var listStr = new List<string>() { "aaa", "abc", "bbc", "aba", "cbc", "bcc" };
foreach (var item in listStr)
{
    if (!item.Contains("a"))
    {
        listStr.Remove(item);
    }
}
```

`foreach`の中でListに手を加えてしまったパターンです。

”コレクションが変更されました。列挙操作は実行されない可能性があります。”と言われてしまいます。

列挙操作、つまり1つ1つ数え上げている途中で変えられてしまうと、どこまで処理を行ったか分からなくなってしまいます。

もしこれを許可してしまった場合、

| 0    | 1    | 2    | 3    | 4    | 5    |
| ---- | ---- | ---- | ---- | ---- | ---- |
| aaa  | abc  | bbc  | aba  | cbc  | bcc  |
| 未   | 未   | 未   | 未   | 未   | 未   |

| 0     | 1    | 2    | 3    | 4    | 5    |
| ----- | ---- | ---- | ---- | ---- | ---- |
| aaa   | abc  | bbc  | aba  | cbc  | bcc  |
| 済→残 | 未   | 未   | 未   | 未   | 未   |

| 0    | 1     | 2    | 3    | 4    | 5    |
| ---- | ----- | ---- | ---- | ---- | ---- |
| aaa  | abc   | bbc  | aba  | cbc  | bcc  |
| 済   | 済→残 | 未   | 未   | 未   | 未   |

| 0    | 1    | 2     | 3    | 4    | 5    |
| ---- | ---- | ----- | ---- | ---- | ---- |
| aaa  | bbc  | bbc   | aba  | cbc  | bcc  |
| 済   | 済   | 済→削 | 未   | 未   | 未   |

| 0    | 1    | 2    | 3     | 4    | 5    |
| ---- | ---- | ---- | ----- | ---- | ---- |
| aaa  | bbc  | aba  | cbc   | bcc  |      |
| 済   | 済   | 未   | 済→削 | 未   | 未   |

| 0    | 1    | 2    | 3    | 4     | 5    |
| ---- | ---- | ---- | ---- | ----- | ---- |
| aaa  | bbc  | aba  | bcc  |       |      |
| 済   | 済   | 未   | 未   | 済→完 | 未   |

このように確認されない部分が出てしまいます。

これでは困るので、`foreach`の中では要素の変更ができないようになっています。

## コレクションの変更ってどうなってるの？

InvalidOperationExceptionの説明の中に、”コレクションが変更されました。列挙～”とありました。

コレクションの変更をどうやって管理してるのかもついでに解説します。

とはいえ、実は答えの半分は既に出ていたりします。

要素の取得・追加・削除の解説内に`_version++`という処理がありました。

こいつを使っています。

```c#
public void ForEach(Action<T> action)
{
    if (action == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
    }
    //ここと
    int version = _version;
    for (int i = 0; i < _size; i++)
    {
        //ここと
        if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
        {
            break;
        }
        action(_items[i]);
    }
    //ここ
    if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
    {
        ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
    }
}
```

`ForEach`メソッドです。一般的に広く使われている`foreach`とは別物になります。

色々と分からない箇所があるとは思いますが、コメントのすぐ下の行だけ見てください。

1. 最初に現在の`_version`を取得し、`version`としておく。
2. `_item`に対して反復処理をかける際に、都度`_version`と`version`を比較。
3. 不一致だったら`for`から抜けて、例外を出力。

これにより`Add`や`RemoveAt`等が実行されると`_version`と`version`にズレが生じる仕組みになっております。

`foreach`も似たようなことをやっています。(詳細を解説しようとすると長くなるので割愛)

2019/01/15 [この辺について書いて見ました。](https://qiita.com/NCT48/items/d8394d587e9fee969ca9)

「Enumerator構造体ってなに？」の辺りで触れています。

# おわりに

ここまで大量に書いておいてなんですが、C#でプログラミングする上で、ここに書いてあることの**9割は不要**です。

プログラミング言語ってのは、「何か」を作るための**道具の1つ**です。

道具の仕組みを知らなくても、使い方さえ知っていればその「何か」は作れるわけです。

ボールペンからインクが出る原理がわからなくても字は書けるし、どうやって電話が音を伝えているか知らなくても遠くの誰かとお話できるわけです。

ちなみにこの考え方はオブジェクト指向でよく出てくる**カプセル化**と呼ばれるものです。

複雑なもの(配列の長さの管理等)は中に隠し、外に見えるのは簡単な操作(取得・追加・削除等)のみにすることで誰でも利用可能になっています。

もちろん知っておいて損することはありません。

シビアなメモリ管理やパフォーマンスを求められた場合に役立つ可能性はありますし、こうやって長々と記事を書いて暇を潰すことも出来ます。

ただ費用対効果に見合っているかと言われると......疑問ですね。

## なぜこんな物を書いたのか

よくプログラミングの世界では「おまじない」とか「動いてるからよし」とか「そういうものです」とか言われることがあります。

自作の機能だとマズいですが、C#にはじめから用意されている機能だったらそれでいいと思います。

でも中には「いや、そんな事言われても納得できんぞい。」と考える変わり者がいてもいいでしょう。

そんな変わり者が僕以外にいるかどうかはわかりませんが、「いたら嬉しいなぁ」というのが動機です。

> 人は生まれながらに、知ることを欲する。　アリストテレス(古代ギリシア)

~~かっこつけてアリストテレスとか言ってますが、元ネタはトリビアの泉です。~~

もし次回以降があれば、今回割愛した`IEnumerable<T>`とか、`Func`デリゲートとか、ラムダ式とか、LINQとかその変の話もしたいと思ってます。