ADVENT CALENDAR 2019

C#でジェネリックコレクションを作ろう

December 12, 2019

アドベントカレンダー2019 CSharp

はじめに

Amusement Creators の Funny_Silkie です。
アドカレの時期となり，何を書こうかと考えた結果，ジェネリックコレクションの作り方とか色々習得できるしいいのでは？と思いこの題材にしました。
この記事は，C#でインターフェイスとかコレクション知ってるけどコレクションの作り方分からんと言う人向けです。

ジェネリックコレクションとは

ジェネリックコレクションとは，ジェネリック(任意の型にできるもの)の要素を格納できるコレクションを表します。

ジェネリックコレクションの例

コレクション名	説明
`List<T>`	インデックスで要素を取得・設定できる，所謂`ArrayList`のジェネリック版。検索機能が豊富で，コレクションだったら基本的にこれを使う。
`Dictionary<TKey, TValue>`	キーと値を結び付ける。`HashTable`のジェネリック版。よく使う。
`LinkedList<T>`	連結リストとも呼ばれ，双方向から要素の追加・削除ができる。要素の追加と削除をメインにしたい場合使う。
`Queue<T>`	後入れ先出し型のコレクション。`Queue`のジェネリック版。
`Stack<T>`	後入れ先出し型のコレクション。`Stack`のジェネリック版。
`SortedDictionary<T>`	キーと値を結び付けるコレクションで，キーをもとに自動的にソートされる。キーや値のコレクションはインデックス検索できない。要素の追加・削除が速め。
`SortedList<T>`	キーと値を結び付けたコレクションで，キーの値をもとに自動的に並び替えられる。キーまたは値のコレクションはインデックスを使って検索できる。SortedListのジェネリック版。
`HashSet<T>`	要素の重複を許さないコレクション。
`SortedSet<T>`	要素が自動的にソートされる`HashSet<T>`。

ジェネリックコレクションを作ると学べる事

ジェネリックコレクションを作ると，快適なC#プログラミングにおける仕様をいろいろ学ぶ事が出来ます。

interface周り

インターフェイスの制約や，明示的実装と普通の実装の違いなど

IEnumerable<T>周り

コレクションに必要な要素であるIEnumerable<T>インターフェイスや，foreach構文について

インデクサ周り

[]を使った要素の検索について(使うときと使わない時あり)

例外処理

コレクションは例外ぶん投げるorぶん投げられることが多いので，例外の投げ方や投げられないような処理の仕方を学べる

ジェネリックコレクションのメソッド

自分で作ってみることで，他のジェネリックコレクションにあるメソッドのやろうとしていることの意味が分かる

実際に作ってみる

ではジェネリックコレクションを一つ作ってみようとなります。インデクサなど色々使うコレクションという事で，List<T>を自作してみましょう。
一部で簡単のためにSystem.Collections.Generic.List<T>の実際のソースコードと異なるところがあります。
今回実装するのは一部の主要なメソッドですが，興味があればソースコードとにらめっこしながら実装してみてもいいと思います。

最初の準備

まずは以下のようにC#のクラスを新しく立てます。

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyList
{
    public class List<T>
    {

    }
}

ここでListとクラス定義している右に<T>がありますね。
この記述で， “このクラスはTというジェネリックを使用する” という宣言をしているわけです。 usingステートメントとしてはコレクション作成に重要な3つを記述します。

実装インターフェイスの選択

次に実装するインターフェイスを選択してみましょう。

コレクションに関わるインターフェイス一覧

コレクションの実装に関係するインターフェイスは以下の通り，非ジェネリック・ジェネリックと沢山あります。

インターフェイス名	説明	実装
IEnumerator	非ジェネリックな反復処理をサポートする。	各コレクション内部
IEnumerator`<T>`	ジェネリックな反復処理をサポートする。	各ジェネリックコレクション内部
IEnumerable	非ジェネリックな列挙可能オブジェクトを表す。foreach構文で必要。	各コレクション
IEnumerable`<T>`	ジェネリックな列挙可能オブジェクトを表す。foreach構文やLINQで必要。	各ジェネリックコレクション
ICollection	非ジェネリックなコレクションを表す。全てのコレクションの元となる。	各コレクション
ICollection`<T>`	ジェネリックなコレクションを表す。大抵のジェネリックコレクションの元となる。	各ジェネリックコレクション
IList	インデックスでアクセス可能な非ジェネリックコレクションを表す。	配列，`ArrayList`，`List<T>`
IList`<T>`	インデックスでアクセス可能なジェネリックコレクションを表す。	ジェネリック配列，`List<T>`
IDictionary	キーと値のペアからなる非ジェネリックコレクションを表す。	`HashTable`，`SortedList`，`Dictionary<TKey, TValue>`，`SortedList<TKey, TValue>`，`SortedDictionary<TKey, TValue>`
IDictionary`<TKey, TValue>`	キーと値のペアからなるジェネリックコレクションを表す。	`Dictionary<TKey, TValue>`，`SortedList<TKey, TValue>`，`SortedDictionary<TKey, TValue>`
ISet`<T>`	重複不可能な集合としてのジェネリックコレクションを表す。	`HashSet<T>`，`SortedSet<T>`
IReadOnlyCollection`<T>`	値が読み取り専用なジェネリックコレクションを表す。	各ジェネリックコレクション
IReadOnlyList`<T>`	値が読み取り専用なインデックスアクセス可能なジェネリックコレクションを表す。	ジェネリック配列，`List<T>`
IReadOnlyDictionary`<TKey, TValue>`	値が読み取り専用なキーと値のペアのジェネリックコレクションを表す。	`Dictionary<TKey, TValue>`，`SortedList<TKey, TValue>`，`SortedDictionary<TKey, TValue>`

この3つのインターフェイスはコレクション自体のためというより内部処理のための物です。

インターフェイス名	説明	実装
IDisposable	破棄可能なオブジェクトを表す。(後述の`Enumerator`作成に使用)	各ジェネリックコレクション内の`Enumerator`
ISerializable	シリアル化・逆シリアル化の設定。(一部コレクションで使用)	`Dictionary<TKey, TValue>`，`SortedList<TKey, TValue>`，`SortedDictionary<TKey, TValue>`，`HashSet<T>`，`SortedSet<T>`
IDeserializationCallback	逆シリアル化時の実装の設定。	`Dictionary<TKey, TValue>`，`SortedList<TKey, TValue>`，`SortedDictionary<TKey, TValue>`，`HashSet<T>`，`SortedSet<T>`

どのインターフェイスを実装すればよいか

インターフェイス選びで重要なのは，まずどのようなコレクションを作成するかです。
インデックスでアクセスさせるならIList<T>，キーと値のペアにしたいならIDictionary<TKey, TValue>，重複不可能な集合にしたかったらISet<T>といった感じです。それらのうち作成したいジェネリックコレクションのタイプのインターフェイスを実装して，それと一緒に 読み取り専用ジェネリックコレクションのインターフェイスと非ジェネリック型のインターフェイスも実装 します。
上記の三つのうちどのタイプでもない(Stack<T>やQueue<T>など)場合はどれも実装する必要はありません。
後は，どのコレクションでも実装されているICollectionインターフェイスもお忘れなく。
ICollection<T>やIEnumerable<T>，IEnumerableインターフェイスは，IList<T>，IDictionary<TKey, TValue>，ISet<T>の三つのインターフェイスで，IReadOnlyCollection<T>はIReadOnlyList<T>やIReadOnlyDictionary<TKey, TValue>で実装することが強制されているので自分で書く必要はありません。

今回はListの実装なので，IList<T>とIReadOnlyList<T>，IListの実装をします。(ICollectionはIListにて実装が強制されている)クラスの継承をする感覚でこの3インターフェイスを実装するとこんな感じ。

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyList
{
    public class List<T> : IList<T>, IList, IReadOnlyList<T>
    {

    }
}

この段階だとインターフェイス実装してないんだけど！って怒られています。後々実装していきましょう。

フィールドの実装

まずは内部処理に必要なフィールド変数を実装していきましょう。
ジェネリックコレクションは基本的に内部にジェネリックTの配列を持っていて，メソッドなどで要素を追加するごとにその大きさを自動的に調整しています。必要なフィールド変数を以下に示していきます。

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyList
{
    public class List<T> : IList<T>, IList, IReadOnlyList<T>
    {
        //内部の配列
        private T[] _array;
        //リストのバージョン
        private int version = 0;
    }
}

フィールド変数の解説をしていきましょう。
_arrayは，先述の通り要素を格納していく配列です。後々実装するAddメソッドなどで要素数が変更されていきます。
versionは，このList<T>のインスタンスのバージョンを表します。要素の追加や削除をするたびに変化していきます。一見無意味に見えますが，後々に説明していきます。

プロパティの実装

ここからはプロパティの実装に移っていきます。
プロパティのほとんどはインターフェイスにより強制されているものです。
では順を追って解説していきましょう。

using System;
using System.Collections;
using System.Collections.Generic;

namespace MyList
{
    public class List<T> : IList<T>, IList, IReadOnlyList<T>
    {
        //内部の配列
        private T[] _array;
        //リストのバージョン
        private int version = 0;
        //リスト内の要素数
        public int Count { get; private set; } = 0;
        //リストに格納できる最大要素数
        public int Capacity 
        {
            get => _array.Length;
            set
            {
                if (value < Count) throw new ArgumentOutOfRangeException();
                if (_array.Length != value)
                {
                    var newArray = new T[value];
                    for (int i = 0; i < _array.Length; i++)
                        newArray[i] = _array[i];
                    _array = newArray;
                }
            }
        }
        //アクセスが同期されているかどうか
        bool ICollection.IsSynchronized => false;
        //アクセスを同期する為に使用するオブジェクト
        object ICollection.SyncRoot
        {
            get
            {
                // lock(hoge)
                // {
                //     if (_syncRoot == null) _SyncRoot = new object();
                // }
                // と同じ
                if (_syncRoot == null) System.Threading.Interlocked.CompareExchange<object>(ref _syncRoot, new object(), null);
                return _syncRoot;
            }
        }
        private object _syncRoot;
        //読み取り専用かどうか
        bool ICollection<T>.IsReadOnly => false;
        //サイズが固定されているかどうか
        bool IList.IsFixedSize => false;
        //読み取り専用かどうか
        bool IList.IsReadOnly => false;
    }
}

Count：内部に格納されている要素数を返す。_array.Lengthとは異なるので，別々の値を設定したい。そのためprivate setも付けておきます。
Capacity：_arrayの長さを取得または設定する。値はCount以上でなければならないため，Count未満の値が代入されそうなときはArgumentOutOfRangeExceptionを投げるようにする。
値の設定時は同じ要素を持つ新たな配列を作成して_arrayに代入する。(Array.Copyメソッドを使ってもよい。)
IsSynchronized：マルチスレッド用のプロパティ。マルチスレッドを想定してオブジェクトが作成されているかどうかを表す。ここではfalse。
SyncRoot：マルチスレッド用のプロパティ。マルチスレッド時に同期させるオブジェクトを返す。
マルチスレッド時の動作を補助するSystem.Threading.Interlockedクラスで実装。
IsReadOnly：コレクションが読み取り専用かどうかを返す。インデクサやメソッドで値の設定ができるのでここではfalse。
IsFixedSize：コレクションのサイズを固定するかどうかを返す。ここでは要素数に応じて自動調整するのでfalse。

ここでよくわからない記述が出てきますね。

bool ICollection.IsSynchronized
object ICollection.SyncRoot
bool ICollection<T>.IsReadOnly
bool IList.IsFixedSize
bool IList.IsReadOnly

これは インターフェイスの明示的実装 と言います。 publicをくっつける普通の実装との違いを以下にまとめました。

実装方法	呼び出し	実装回数
普通の実装	普通に呼び出せる	一回で複数インターフェイス分まとめて可
明示的実装	キャスティングしてから	インターフェスごとに実装する必要あり

明示的実装はプロパティだけではなくメソッドでも可能です。明示的実装では以下のように通常実装と混ぜて使うこともできます。

public interface IExample1
{
    int Number { get; set; }
}
public interface IExample2
{
    int Number { get; }
}
public class ExampleClass : IExample1, IExample2
{
    public int Number { get; set; }
    int IExample2.Number => Number;
}

この方法では，ExampleClassのインスタンス名.Numberで呼び出されるのはIExample1としてのNumberだけで，IExample2のNumberを呼び出したいときは((IExample2)ExampleClassのインスタンス名).Numberと記述する必要があります。

インデクサの実装

インデクサは，配列やDictionary<TKey, TValue>の値検索の様に，[]内に特定の型の値を代入して，その値に結びつけられた要素を返したり設定できたりするやつのことです。
では早速実装してみましょう。get，setなど書き方はプロパティとほぼ同じですが，返り値の型 this[インデックスの型]といった形で定義します。

public T this[int index]
{
    get
    {
        //不正なインデックスの値で例外スロー
        if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException();
        //配列の指定インデックスの値をリターン
        return _array[index];
    }
    set
    {
        //不正なインデックスの値で例外スロー
        if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException();
        //値の割り当て
        _array[index] = value;
        version++;
    }
}
object IList.this[int index]
{
    get
    {
        //不正なインデックスの値で例外スロー
        if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException();
        //配列の指定インデックスの値をリターン
        return _array[index];
    }
    set
    {
        //不正なインデックスの値で例外スロー
        if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException();
        try
        {
            //値の割り当て
            _array[index] = (T)value;
        }
        catch (InvalidCastException)
        {
            //割り当てようとした型が違ったら例外スロー
            throw new ArgumentException();
        }
        version++;
    }
}

IList<T>の方の通常実装では，インデックスの範囲がまず配列の管理範囲内かどうかを判定します。配列の管理範囲外だった場合は例外をスローします。値の設定の場合は，配列内の要素が変更されるのでversionを一つ進めます。
IListの明示的実装の方では，object型で定義されているので，値の設定時はキャストする必要があります。キャスト時の例外はキャッチして，引数由来の例外である，ArgumentExceptionとして投げ直します。

Enumeratorの実装

Enumeratorは，ジェネリックコレクションの内部に定義される，IEnumerator<T>を実装する構造体です。
本体コレクションのGetEnumeratorメソッドで呼び出され，列挙処理を行います。

Enumerable実装の準備

まずは下の様にList<T>クラスの内部にEnumeratorを実装します。

public class List<T> : IList<T>, IList, IReadOnlyList<T>
{

    ・・・中略・・・

    public struct Enumerator : IEnumerator<T>
    {
        //マスターとなるリストのインスタンス
        private readonly List<T> list;
        //初期化当時のリストのバージョン
        private readonly int version;
        //処理時のリストのインデックス
        private int index;
    }
}

list：呼び出し元のList<T>のインスタンスへの参照。
version：コンストラクタ(後で実装)で初期化時現在のList<T>のバージョン。
index：列挙操作時の現在インデックス。

プロパティ・コンストラクタの実装

次にプロパティ，コンストラクタの実装をします。

public struct Enumerator : IEnumerator<T>
{
    //マスターとなるリストのインスタンス
    private readonly List<T> list;
    //初期化当時のリストのバージョン
    private readonly int version;
    //処理時のリストのインデックス
    private int index;
    //列挙中の現在要素を返す。
    public T Current { get; private set; }
    //列挙中の現在要素を返す。
    object IEnumerator.Current
    {
        get
        {
            if (index == 0 || index > list.Count) throw new InvalidOperationException();
            return Current;
        }
    }
    //コンストラクタ
    internal Enumerator(List<T> list)
    {
        this.list = list;
        index = 0;
        version = list.version;
        Current = default;
    }
}

Currentでは列挙作業中のlist中の現在の要素を返します。明示的実装では，インデックスの値がlistの配列の範囲外になったときに例外を返すようにします。
コンストラクタでは上記のフィールドとCurrentの初期化を行います。Currentは取り敢えずデフォルトの値を仮に設定しておきます。(列挙時にはちゃんと割り当てられる。) コンストラクタのアクセシビリティがinternalなのは，継承先や外部プロジェクトでわざわざそのコンストラクタを使ってインスタンスを生成しなくても，GetEnumeratorメソッドを使えばいいじゃないかという事です。

MoveNext，Reset，Disposeの実装

ではいよいよIEnumerator<T>のメソッドについて説明します。

bool MoveNext：現在のindexやversionの状態から，コレクションの列挙を次に進めるかどうかを判定します。
void Reset：フィールドやプロパティの値を初期化します。
void Dispose：IEnumerator<T>を実装するとなぜかくっついてくるやつ。foreach構文終了時に呼び出される。中身は何も書かなくていい。

では実際にコードにしてみましょう。

//列挙終了時に実行
public void Dispose() { }
//要素を次に進める
public bool MoveNext()
{
    //バージョンが変更されていたら例外をスロー
    if (version != list.version) throw new InvalidOperationException();
    //インデックスがlistの範囲内の場合はCurrentを設定してindexを進めtrueを返す。
    if (index < list.Count)
    {
        Current = list._array[index];
        index++;
        return true;
    }
    //それ以外の場合は終了操作を行う。
    else
    {
        Current = default;
        index = list.Count + 1;
        return false;
    }
}
//変数・プロパティの初期化を行う。
void IEnumerator.Reset()
{
    //バージョンが変更されていたら例外をスロー
    if (version != list.version) throw new InvalidOperationException();
    Current = default;
    index = 0;
}

ざっくりやってることをまとめると

Dispose：何も書かない。
MoveNext：インデックスの状態で判定し，それによって次の要素に進めるか操作を中断するかを返す。
Reset：変数の初期化です。 version変数が変えられたときに例外をスローするのは，要素の状態が返られると列挙中にインデックスがズレたりする可能性が出てくるからです。
Resetが明示的実装なのは，外部から勝手に呼ばれると列挙処理が乱されるからです。明示的実装には隠蔽的な意味合いも含まれています。

GetEnumeratorの実装

Enumerableを実装したので，メインのList<T>に話を戻していきましょう。列挙可能であるオブジェクトを表すIEnumerable<T>は，唯一GetEnumeratorメソッドの実装を強制しています。これは列挙処理に必要なIEnumerator<T>を呼び出すものです。IEnumerator<T>なら先程Enumeratorとして実装したので，これでこのメソッドは実装できそうなので書いてみましょう。

public class List<T> : IList<T>, IList, IReadOnlyList<T>
{

    ・・・中略・・・

    //Enumeratorの呼び出し
    public Enumerator GetEnumerator() => new Enumerator(this);
    //Enumeratorの呼び出し
    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
    //Enumeratorの呼び出し
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    public struct Enumerable : IEnumerator<T>
    {
        ・・・省略・・・
    }
}

Enumerableを呼び出すメソッドとしてGetEnumeratorを用意し，IEnumerable<T>及びIEnumerableのGetEnumeatorは明示的実装をしています。なんでIEnumerator<T> GetEnumerator()としないかと言うと，GetEnumeratorを実行時にList<T>.Enumerator()が呼び出されるという事を明示してコードの可読性を図るためです。

要素の追加メソッドの作成

コレクションに重要な要素を大体実装してきました。これで漸くリストっぽいメソッドの実装が始まります。
ここではAdd，Insertメソッドとその派生メソッドを実装します。
これらの操作ではコレクションの状態を変化させるのでversion変数を進めます。

配列の大きさを変更するメソッド

まずは_arrayの大きさを変更するメソッドを作りましょう。_array大きさ変更は今後重複するためメソッドにまとめて共通化した方が良いです。

//配列のサイズ変更
private void ChangeArraySize()
{
    //配列長が0だったら4に，それ以外では2倍にしたい
    var ns = _array.Length == 0 ? 4u : (uint)_array.Length * 2u;
    //上記のnsがint.MaxValueを超過する場合はその値に丸める
    var newSize = ns > int.MaxValue ? int.MaxValue : (int)ns;
    Capacity = newSize;
}

_arrayのサイズの変更について，なぜ2倍にするかと言うと，単に等差数列的に足していく場合は増やす値が小さいとAddRangeなどで一括して要素を増やすときに処理が何度も行われる必要があり，増やす値が大きいと小サイズのデータ管理でいい場合にメモリの無駄が増えてしまいます。そのため倍ずつに増やしていけば適宜対応できるのです。
また，int型のオーバーフローを避けるために一旦uintとして設定した後オーバーフローするかどうかを確かめて修正します。

Add

それではAddメソッドを実装しましょう。 Addメソッドでの流れは，

_arrayに新たな要素を格納する場所が無かったら配列を大きくする
_arrayのCount番目に新たな要素を代入する
versionを進める
IListのものの場合は要素を追加したところのインデックスを返す

となります。

これを実装するとこうなります。

//末尾に要素を追加する
public void Add(T item)
{
    //新たな要素を格納する場所が無かったら確保する
    if (Count + 1 > _array.Length) ChangeArraySize();
    //末尾の要素を指定した要素にして，Countを1増やす
    _array[Count++] = item;
    //バージョン更新
    version++;
}
//末尾に要素を追加し，挿入場所のインデックスを返す
int IList.Add(object value)
{
    //null非許容の型にnullが指定されていたら例外スロー
    if ((T)default != null && value == null) throw new ArgumentNullException();
    try
    {
        //キャストしてAddする
        Add((T)value);
    }
    catch (InvalidCastException)
    {
        //キャストできなかったら例外をスロー
        throw new ArgumentException();
    }
    //上のAddでCountが進んでいるので進む前の値を返す。
    return Count - 1;
}

IListの明示的自走の方ではobject型の引数をキャストする必要があります。また，Add((T)value)を実行した地点でCountは増えているので，返り値はCount - 1となります。

AddRange

次はAddRangeメソッドを実装します。 AddRangeメソッドは，単に引数の列挙可能オブジェクトを全てAddしていけばいいので，Addメソッドを実装した今は余裕ですね。

//要素を一括で追加する
public void AddRange(IEnumerable<T> collection)
{
    foreach (var item in collection)
        Add(item);
}

このように，ただforeach構文で片っ端から持ってきてAddすればいいのです。

Insert

次はInsertメソッドを実装しましょう。 Insertメソッドでは指定したインデックスに要素を挿入するものです。道筋としては

引数の挿入位置を表すインデックスが適正な値かどうかを判定
_arrayに新たな要素を格納する場所が無かったら配列を大きくする
要素を挿入できるように_arrayの要素をずらす
指定した場所に要素を代入
要素数を増やす
versionを進める

となります。では実装してみましょう。

//要素を挿入
public void Insert(int index, T item)
{
    //インデックスの値が不正だったら例外をスロー
    if (index < 0 || index > Count) throw new ArgumentOutOfRangeException();
    //サイズが不足していたら配列を拡張
    if (Count + 1 > _array.Length) ChangeArraySize();
    //_array内の要素をずらす
    if (index < Count) Array.Copy(_array, index, _array, index + 1, Count - index);
    //要素を追加
    _array[index] = item;
    //要素数を増やす
    Count++;
    //バージョンを進める
    version++;
}
//要素を挿入
void IList.Insert(int index, object value)
{
    //null非許容の型にnullが指定されていたら例外スロー
    if ((T)default != null && value == null) throw new ArgumentNullException();
    try
    {
        //キャストしてInsert実行
        Insert(index, (T)value);
    }
    catch (InvalidCastException)
    {
        //キャストに失敗したら例外スロー
        throw new ArgumentException();
    }
}

ここでは配列の要素をずらすためにArray.Copyメソッドを使用しています。
for文で代用することも可能です。

InsertRange

次はInsertRangeメソッドの実装です。
これもAdd-AddRangeのような感じで実装すればよいのですが，挿入は一つずつずらしていかなければなりません。 (もしInsert(index, item)で繰り返すと引数として提供された追加される要素の順序が逆転してしまう)
そのため，一工夫が必要です。

//要素をまとめて挿入
public void InsertRange(int index, IEnumerable<T> collection)
{
    foreach (var item in collection)
        Insert(index++, item);
}

ここで見てわかる通り，実行するInsertメソッドの引数がindexではなくindex++になっています。これによって挿入する位置を右にずらしながらInsertを実行する事が出来，collectionの順序を守ったまま実行する事が出来ます。

コンストラクタの実装

要素を追加するメソッドを実装できたのでコンストラクタを実装できます。
コンストラクタでは主に_arrayの初期化を行います。

public List() : this(0) { }
public List(int capacity)
{
    //capacityの値が0未満の時に例外スロー
    if (capacity < 0) throw new ArgumentOutOfRangeException();
    //_arrayの初期化
    _array = new T[capacity];
}
public List(IEnumerable<T> collection)
{
    //collectionがnullのとき例外スロー
    if (collection == null) throw new ArgumentNullException();
    //_arrayの初期化
    _array = new T[0];
    //collectionの追加
    AddRange(collection);
}

真ん中のコンストラクタでは引数で指定された値で_arrayを初期化します。
上のコンストラクタではcapacity = 0として_arrayを初期化します。
下のコンストラクタではcollectionのnullチェックを行った後，AddRangeで初期要素として追加します。

インデックス検索メソッドの作成

要素の追加メソッドを作ったのだから次は削除メソッドだと行きたいところですが，要素を削除するにはインデックスの検索が必要なことが多いです。そのためまずはインデックスを検索するメソッドを作成していきます。

IndexOf

まずはIndexOfメソッドの実装です。
このメソッドでは引数として指定された要素と一致する要素のうち先頭の要素のインデックスを返すものです。方針としては，for文で要素を最初から回していき，該当要素に当たったらそのインデックスを返すという感じです。
このメソッドにはオーバーロードがあり，それぞれで下の表の通りの検索範囲になります。

メソッド	最初のインデックス	最後のインデックス
IndexOf(object value)	0	Count - 1
IndexOf(T item)	0	Count - 1
IndexOf(T item, int index)	index	Count - 1
IndexOf(T item, int index, int count)	index	index + count - 1

こんな感じなので， IndexOf(T item, int index, int count) を実装して，残り3つはそのメソッドをうまく引数を合わせて呼び出せばいいと考えられます。では実装してみましょう。

public int IndexOf(T item) => IndexOf(item, 0);
int IList.IndexOf(object value)
{
    try
    {
        //キャストしてIndexOfを実行
        return IndexOf((T)value);
    }
    catch (InvalidCastException)
    {
        //キャストできなかったら例外スロー
        throw new ArgumentException();
    }
}
public int IndexOf(T item, int index) => IndexOf(item, index, Count - index);
public int IndexOf(T item, int index, int count)
{
    //引数の値が不正だった場合は例外スロー
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //ジェネリックの二つの要素を比較する比較子
    var eq = EqualityComparer<T>.Default;
    //最初から要素を検索する
    for (int i = index; i < index + count; i++)
        if (eq.Equals(_array[i], item))
            return i;
    return -1;
}

ここで気になるのはEqualityComparer<T>だと思います。なぜこんな回りくどいやり方をして等しいかどうかを比較しているかと言うと，ジェネリックにおいて==は定義されていない からです。そのため，EqualityComparer<T>を用いて比較するか，object型にキャストしてから比較するしかないのです。

LastIndexOf

次はLastIndexOfメソッドを実装します。 IndexOfメソッドで返されるインデックスが要素と一致する先頭の物のインデックスなのに対し，LastIndexOfメソッドでは末尾の物のインデックスを返します。実装方法としては，IndexOfで行ったfor文による検索を逆方向に行うという事です。実際に実装してみるとこんな感じ。

public int LastIndexOf(T item) => LastIndexOf(item, 0);
public int LastIndexOf(T item, int index) => LastIndexOf(item, index, Count - index);
public int LastIndexOf(T item, int index, int count)
{
    //引数の値が不正だったら例外スロー
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //検索開始インデックス
    var firstIndex = index + count - 1;
    //index == count == 0の時
    if (firstIndex == -1)
        return -1;
    else
    {
        //ジェネリックを比較する比較子
        var eq = EqualityComparer<T>.Default;
        //IndexOfとは逆向きに検索
        for (int i = firstIndex; i >= index; i--)
            if (eq.Equals(_array[i], item))
                return i;
        return -1;
    }
}

このように，for文の開始地点，終了地点，加算減算を逆転させて場逆方向に検索すれば良いのです。不等号の=有無には気を付けてください。

FindIndex，FindLastIndex

次はFindIndexメソッドです。 FindIndexメソッドではPredicate<T>で指定された条件の要素のうち最初の要素のインデックスを返します。
実装においてはEqualityComparer<T>で比較していたものをPredicate<T>.Involke(T)にするだけです。 FindLastIndexもLastIndexOfを改造すれば簡単に作れます。
実装するとこんな感じになります。

public int FindIndex(Predicate<T> match) => FindIndex(0, match);
public int FindIndex(int index, Predicate<T> match) => FindIndex(index, Count - index, match);
public int FindIndex(int index, int count, Predicate<T> match)
{
    //引数の値が不正だった場合は例外スロー
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //matchがnullの時に例外スロー
    if (match == null) throw new ArgumentNullException();
    //最初から要素を検索する
    for (int i = index; i < index + count; i++)
        if (match.Invoke(_array[i]))
            return i;
    return -1;
}
public int FindLastIndex(Predicate<T> match) => FindLastIndex(0, match);
public int FindLastIndex(int index, Predicate<T> match) => FindLastIndex(index, Count - index, match);
public int FindLastIndex(int index, int count, Predicate<T> match)
{
    //引数の値が不正だったら例外スロー
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //matchがnullの時に例外スロー
    if (match == null) throw new ArgumentNullException();
    //検索開始インデックス
    var firstIndex = index + count - 1;
    //index == count == 0の時
    if (firstIndex == -1)
        return -1;
    else
    {
        //FindIndexとは逆向きに検索
        for (int i = firstIndex; i >= index; i--)
            if (match.Invoke(_array[i]))
                return i;
        return -1;
    }
}

ここで注意なのは，matchはnullになる可能性があるので，nullチェックをしてArgumentNullExceptionをスローさせるのが大事です。
nullチェック⇒例外スローの流れはよくあるので覚えておきましょう。

要素削除メソッドの作成

インデックス検索メソッドを実装できたので要素削除メソッドを作成できます。

RemoveAt

最初はRemoveAtメソッドの実装が良いです。 RemoveメソッドはRemoveAtを基に実装されるからです。方法としては，indexの範囲チェックをしてから，削除されて空く場所に対して_array内の要素を一つずつ前にずらす感じです。
では実装してみましょう。

public void RemoveAt(int index)
{
    //引数の値が不正だった場合は例外スロー
    if (index < 0 || index > Count) throw new ArgumentOutOfRangeException();
    if (index < Count - 1)
    {
        //削除場所に対して要素をずらしていく
        Array.Copy(_array, index + 1, _array, index, Count - index - 1);
    }
    //末尾に既定値を代入
    _array[Count - 1] = default;
    Count--;
    version++;
}

ここで注意することは，_array[Count - 1]に既定値を代入して，末尾の要素の重複を防ぐ必要がある事です。

Remove

次はRemoveメソッドの実装です。 IndexOfでインデックスを検索してそのインデックスでRemoveAtを行うだけです。実装するとこんな感じ。

public bool Remove(T item)
{
    //インデックスの検索
    var index = IndexOf(item);
    //インデックスが見つかったらRemoveAt
    if (index >= 0)
    {
        RemoveAt(index);
        return true;
    }
    //見つからなかったらfalseを返す
    return false;
}
void IList.Remove(object value)
{
    //キャスト可能であるならRemove実行
    if (value is T || ((T)default == null && value == null)) Remove((T)value);
}

IList<T>.Removeは返り値がboolなので，インデックスが見つかったかどうかで返り値を決定します。

RemoveRange

RemoveRangeメソッドでは指定した範囲の要素を一括で削除するメソッドです。
実装は

引数の範囲チェック
要素を削除する分ずらす
後ろの余分な要素を削除する
Countとversionを調整する

といった感じになります。
では実装してみましょう。

public void RemoveRange(int index, int count)
{
    //引数の値が不正だった場合は例外スロー
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //要素を削除分ずらす
    Array.Copy(_array, count + index, _array, index, Count - count - index);
    //後ろの余った要素を潰す
    for (int i = index + count; i < Count; i++)
        _array[i] = default;
    //要素数を減らす
    Count -= count;
    //バージョンを進める
    version++;
}

RemoveAll

RemoveAllは引数のPredicate<T>の条件を満たす要素を全て削除するというものです。
このメソッドは多少複雑ですが，RemoveAtとFindIndexを組み合わせれば実装可能です。
手順は，

引数のPredicate<T>のnullチェック
FindIndexで条件を満たす要素のインデックスを求める
RemoveAtでその要素を削除する
FindIndexの結果が-1になるまで繰り返す
削除した要素数を返す

といった感じになります。
version変数はRemoveAtを実行するたびに変化しているので変える必要はありません。

public int RemoveAll(Predicate<T> match)
{
    //matchがnullのとき例外スロー
    if (match == null) throw new ArgumentNullException();
    //match検索の結果インデックス
    var index = FindIndex(match);
    //一致する要素が1つもなかったらそこで終了
    if (index == -1) return 0;
    //削除した要素数
    var count = 0;
    //matchに該当する要素がある限り実行
    while (index != -1)
    {
        //要素を削除
        RemoveAt(index);
        //削除した要素数を増やす
        count++;
        //次のインデックスを検索
        index = FindIndex(match);
    }
    return count;
}

Clear

次は全ての要素を削除するClearメソッドです。
このメソッドはfor文を回すだけでとても簡単に実装可能です。

public void Clear()
{
    for (int i = 0; i < Count; i++)
        _array[i] = default;
    version++;
}

要素検索メソッドの作成

次は要素を直接検索するメソッドを作成します。

Find，FindLast

Findメソッドでは引数Predicate<T>を満たす要素のうち先頭の物を返す，FindIndexの要素版です。
すでにFindIndexを実装しているので，それを使えばすぐ実装できます。
FindLastも同じ要領で実装できます。

public T Find(Predicate<T> match)
{
    //matchのnullチェック
    if (match == null) throw new ArgumentNullException();
    //index検索
    var index = FindIndex(match);
    //検索に引っかからなかったら既定値，それ以外で_arrayを検索
    return index == -1 ? default : _array[index];
}
public T FindLast(Predicate<T> match)
{
    //matchのnullチェック
    if (match == null) throw new ArgumentNullException();
    //index検索
    var index = FindLastIndex(match);
    //検索に引っかからなかったら既定値，それ以外で_arrayを検索
    return index == -1 ? default : _array[index];
}

FindAll

FindAllメソッドでは引数のPredicate<T>を満たす要素を全て，新しいList<T>のメソッドに追加して返します。
こちらでは新しいList<T>インスタンスを生成して，条件を満たす要素をAddしていく方針で実装します。

public List<T> FindAll(Predicate<T> match)
{
    //matchのnullチェック
    if (match == null) throw new ArgumentNullException();
    //リターンするリストを定義
    var list = new List<T>();
    for (int i = 0; i < Count; i++)
    {
        //matchを満たす要素をlistに追加
        if (match.Invoke(_array[i]))
            list.Add(_array[i]);
    }
    return list;
}

存在の有無を表すメソッドの作成

ここでは指定した条件の有無を返すメソッドを実装していきます。

Contains

Containsメソッドでは指定した要素が存在するかどうかを返します。
実装はIndexOf(またはLastIndexOf)を使えばすぐできます。
IndexOfの結果が-1の時は存在しないのでfalse，それ以外でtrueなので1行ですね。

public bool Contains(T item) => IndexOf(item) != -1;
bool IList.Contains(object value)
{
    //キャスト可能ならContains実行
    if (value is T || ((T)default == null && value == null)) return Contains((T)value);
    //それ以外でfalse
    return false;
}

Exists

Existsメソッドでは引数のPredicate<T>を満たす要素がList<T>インスタンス内に存在するかどうかを返します。
こちらもFindIndex(またはFindLastIndex)ですぐに実装できます。

public bool Exists(Predicate<T> match) => FindIndex(match) != -1;

TrueForAll

TrueForAllでは，List<T>インスタンス内の全ての要素が引数のPredicate<T>を満たすかどうかを返します。
Existより条件を厳しくした感じです。全て一致という形なのでFindIndexを使った横着はできない感じですね。黙ってfor文を回していきましょう。

public bool TrueForAll(Predicate<T> match)
{
    //matchのnullチェック
    if (match == null) throw new ArgumentNullException();
    for (int i = 0; i < Count; i++)
    {
        //matchを満たさない場合は即falseを返す
        if (!match.Invoke(_array[i]))
            return false;
    }
    return true;
}

要素をコピーするメソッドの作成

CopyTo

CopyToメソッドでは指定した配列にList<T>のインスタンスの要素をコピーするものです。
オーバーロードによってコピー範囲が以下のように異なります。

メソッド	コピー元のコピー開始インデックス	コピー元のコピー終了インデックス	コピー先の上書き開始インデックス
Copy(T[] array)	0	Count - 1	0
Copy(T[] array, int arrayIndex)	0	Count - 1	arrayIndex
Copy(int index, T[] array, int arrayIndex, int count)	index	index + count - 1	arrayIndex
Copy(Array array, int index)	0	Count - 1	index

実装時は例外チェックを行た後，for文で代入していくか，Array.Copyメソッドでコピーしていきます。

public void CopyTo(T[] array) => CopyTo(array, 0);
public void CopyTo(T[] array, int arrayIndex) => CopyTo(0, array, arrayIndex, Count);
public void CopyTo(int index, T[] array, int arrayIndex, int count)
{
    //indexとcountの範囲チェック
    if (index < 0 || index + count > Count || arrayIndex < 0 || count < 0) throw new ArgumentOutOfRangeException();
    //arrayのnullチェック
    if (array == null) throw new ArgumentNullException();
    //arrayの要素数がコピーできるだけあるかチェック
    if (array.Length < arrayIndex + count) throw new ArgumentException();
    //要素をコピー
    for (int i = index; i < index + count; i++)
        array[arrayIndex++] = _array[i];
}
void ICollection.CopyTo(Array array, int index)
{
    //indexの範囲チェック
    if (index < 0) throw new ArgumentOutOfRangeException();
    //arrayのnullチェック
    if (array == null) throw new ArgumentNullException();
    //arrayの要素数がコピーできるだけあるかチェック
    if (array.Length < index + Count) throw new ArgumentException();
    //arrayの次元チェック
    if (array.Rank != 1) throw new ArgumentException();
    //arrayのインデックスが0から始まるかチェック
    if (array.GetLowerBound(0) != 0) throw new ArgumentException();
    try
    {
        //コピー実行
        Array.Copy(_array, 0, array, index, Count);
    }
    catch (ArrayTypeMismatchException)
    {
        //配列に誤った型が代入されそうになったら例外を再スロー
        throw new ArgumentException();
    }
}

GetRange

GetRangeメソッドではList<T>の指定範囲の要素を新しいList<T>インスタンスにコピーして返します。
実装はCopyToとほぼ同じで，for文を回すかArray.Copyメソッドで写します。

public List<T> GetRange(int index, int count)
{
    //indexとcountの範囲チェック
    if (index < 0 || count < 0 || index + count > Count) throw new ArgumentOutOfRangeException();
    //新しいインスタンス生成
    var list = new List<T>();
    //コピー実行
    Array.Copy(_array, index, list._array, 0, count);
    //リストを返す
    return list;
}

他のコレクションの内部実装の紹介

Dictionary<TKey, TValue>では内部的にはKeyValuePair<TKey, TValue>の配列を持っていて，インデックスを検索するメソッドを使用しながら実装しています。
ソースコードを見てみるとint[] bucketやらstruct Enrtyやらで頭から白煙が上がり~~悟りを開き~~そうになります。
Stack<T>とQueue<T\>ではかなり似通ったメソッドを持っていますが，Queueの方がフィールドが多くコードが複雑です。
ISet<T>ではメソッドの実装にポインタを使っていたりするので闇です。一回実装しようとして挫折した記憶があります…

基本的に非ジェネリックコレクションのインターフェイスによって実装が強制されているプロパティやメソッドは，明示的実装によって隠蔽されていることが多いです。
明示的実装によってキャスティングしないと使用できないので，objectのキャストミスや返り値の違いなどあるため使いづらいメソッドを隠す事が出来るのです。

ジェネリックコレクションを自作するときはこれらのコードのうち自分が実装したいものに近いものを参考にしていくといいと思います。キーが2つのディクショナリなど，複数のジェネリックが関わるコレクションを実装するときは，それらをまとめる構造体やインターフェイスの自作するという事も視野に入れてもいいかもしれません。

最後に

長々と語ってしまいましたが，これを読めばジェネリックコレクションを自作するノウハウがある程度身に付いたと思います(多分)。
C#のプログラミングライフを自分で充実させるために新しいジェネリックコレクションを生み出して使ってみましょう。
ジェネリックコレクションを作らないにしても，インデクサやインターフェイスの仕様なども解説していったので他の事項に関しても役に立つんじゃなかなぁと思います。

リンク集

Microsoft Docs

ソースコード

SHARE THIS POST