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

はじめに

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

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

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

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

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

List＜T＞とは

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

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

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

定義はどこにあるの？

mscorlib.dll → System.Collections.Generic名前空間の下にあります。

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

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(プロパティ)ですが、

public int Count
{
    get
    {
        return _size;
    }
}

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

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

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

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

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

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

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

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

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段階の構成になっています。

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

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;
    }
}

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を自分で設定しておいたほうがパフォーマンスに優れます。(配列の新規作成や要素のコピーには時間がかかる)

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

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

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段階です。

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++;
}

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)から順に追っていきましょう。

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

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

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

// (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 starting at the specified source index and pastes them to another Array starting at the specified destination index. The length and the indexes are specified as 32-bit integers.

指定されたコピー元インデックスから始まる配列から要素の範囲をコピーし、指定されたコピー先インデックスから始まる別の配列にそれらを貼り付けます。 長さとインデックスは32ビット整数として指定されます。

Parameters

• sourceArray

Array

The Array that contains the data to copy.

• sourceIndex

Int32

A 32-bit integer that represents the index in the sourceArray at which copying begins.

• destinationArray

Array

The Array that receives the data.

• destinationIndex

Int32

A 32-bit integer that represents the index in the destinationArray at which storing begins.

• length

Int32

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インデックス目を開始位置としてコピーする処理ってことですね。

// (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つはそのままですが、こいつは少しややこしいです。

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

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

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++という処理がありました。

こいつを使っています。

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 この辺について書いて見ました。

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

おわりに

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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