.NET Coreのソースを読む！第一回 List<T> パート4

# はじめに

以下の続きです。

- [.NET Coreのソースを読む！第一回 List<T> パート1](https://qiita.com/kutarou197/items/48416013dff136f2587e)

- [.NET Coreのソースを読む！第一回 List<T> パート2](https://qiita.com/kutarou197/items/a493458d16b05bf8ebbb)

- [.NET Coreのソースを読む！第一回 List<T> パート3](https://qiita.com/kutarou197/items/ab91636831aa3d28f124)

# ソースリンク

https://github.com/dotnet/corefx/blob/master/src/Common/src/CoreLib/System/Collections/Generic/List.cs

# ソースを読む！

## インスタンスメソッド

```csharp
        // Searches a section of the list for a given element using a binary search
        // algorithm. Elements of the list are compared to the search value using
        // the given IComparer interface. If comparer is null, elements of
        // the list are compared to the search value using the IComparable
        // interface, which in that case must be implemented by all elements of the
        // list and the given search value. This method assumes that the given
        // section of the list is already sorted; if this is not the case, the
        // result will be incorrect.
        //
        // The method returns the index of the given value in the list. If the
        // list does not contain the given value, the method returns a negative
        // integer. The bitwise complement operator (~) can be applied to a
        // negative result to produce the index of the first element (if any) that
        // is larger than the given search value. This is also the index at which
        // the search value should be inserted into the list in order for the list
        // to remain sorted.
        // 
        // The method uses the Array.BinarySearch method to perform the
        // search.
        // 
        public int BinarySearch(int index, int count, T item, IComparer<T> comparer)
        {
            if (index < 0)
                ThrowHelper.ThrowIndexArgumentOutOfRange_NeedNonNegNumException();
            if (count < 0)
                ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.count, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
            if (_size - index < count)
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_InvalidOffLen);

            return Array.BinarySearch<T>(_items, index, count, item, comparer);
        }

        public int BinarySearch(T item)
            => BinarySearch(0, Count, item, null);

        public int BinarySearch(T item, IComparer<T> comparer)
            => BinarySearch(0, Count, item, comparer);
```

BinarySearchは、二分検索だから当然ですが、ソート済みでないと正しい結果返ってきません。（本来は存在するのに、存在しないという結果になるんでしょうね。）
存在しない場合は、マイナスが帰ってくるそうです。
.NET Coreのソースは、大事なことをコメントに書いてくれていますね。

1件だけ探し出すときは、LINQのFirstとかFirstOrDefalutとかが簡単なので、LINQで実装してしまいがちですが、もし、性能を求められたときは、BinarySearchも選択枠に入れるべきですね。
ICompareは、List<T>にあるSortメソッドでも使えるので、同じICompareでSortしてBinarySearchってやれば良いかと思います。ただ、検索するのに並び順を変えてしまってもよいかどうかは、注意が必要ですね。

完全に余談ですが、初心者の頃に、ICompare<T>のようなものでSortが出来ることを理解したときは感動しました。（確かJavaのComparator<T>だったと思います。）初心者の頃は、引数や戻り値には何かしらのデータを渡すということしか理解できていなかったのですが、「どのように比較するか？」という概念を、引数で渡して、ソートをお任せするなんていうのが出来ることを知って、色々可能性が増えたような気がします。

```csharp
        // Clears the contents of List.
        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public void Clear()
        {
            _version++;
            if (RuntimeHelpers.IsReferenceOrContainsReferences<T>())
            {
                int size = _size;
                _size = 0;
                if (size > 0)
                {
                    Array.Clear(_items, 0, size); // Clear the elements so that the gc can reclaim the references.
                }
            }
            else
            {
                _size = 0;
            }
        }
```

リストの中身を空にします。
ただ単に、内部で保持している配列を新たに作り直せば簡単なのだけど、さすが標準ライブラリですね。色々考えているようです。

[MethodImpl(MethodImplOptions.AggressiveInlining)]で、コンパイル時にインライン化になりやすくしています。やっぱり、どういう時にこれを指定すべきかのか、私にはまだよくわかりません。

「_version++;」は、マルティスレッド対策のようですね。例えば、ForEachメソッドの中では、ループ中にバージョンが変わったら例外が投げられるようになっていますね。

「RuntimeHelpers.IsReferenceOrContainsReferences<T>()」では、Listで保持しているT型が参照型の値、もしくは、参照型の値を持っている（構造体がクラス型を持つってことのようです）場合はtrueになります。
以下のテストソースを見るとよくわかります。

https://github.com/dotnet/corefx/blob/59915687bb261efeae70565d0ca8990ac45ceb9c/src/System.Runtime/tests/System/Runtime/CompilerServices/RuntimeHelpersTests.netcoreapp.cs#L74

Listで保持しているT型に参照型のものがあれば、Array.ClearでちゃんとGCレベルで開放されるようにするようです。
私は英語が苦手なので、正確に理解できていませんが、以下のissueでこの処理に変わったようです。

https://github.com/dotnet/corefx/issues/14047

ここで、なんか気持ち悪いとおもったところが、「RuntimeHelpers.IsReferenceOrContainsReferences<T>()」がfalseになったら、_sizeを0にしているだけで、T型のインスタンスを保持している_itemsは初期化していないところです。Listは順次アクセスしかできない（0から順番にしかAdd出来ない）から、_itemsは初期化しなくとも安全なようです。参照型ではないものは、メモリをあまり消費しないから、そのまま保持していても問題なく、それよりも、配列を使いまわした方が効率が良いということでしょうか。
試しに、デバックしてみたら、確かにClearした後も値は保持し続けていました。今後、デバックするときに、騙されないようにしないといけませんね。

![1.png](https://qiita-image-store.s3.amazonaws.com/0/254172/6c365c9c-5c98-7135-83ab-80486816f6ff.png)

今回は、Clearメソッドがヘビーだったので、ここまで。

たった、数行のメソッドでもとても勉強になりますね。

# ライセンス

色々ソースを載せているので、念のためライセンスへリンクしておきます。

https://github.com/dotnet/corefx/blob/master/LICENSE.TXT