C#List<T>の実装 #1 Add編

概要

C#のList<T>はデータ構造としてのリストではなく、使い方としてのリストを実現している。内部実装は配列リストと呼ばれる方法で実装している。

リストのデータ構造

リストのデータ構造としては、アドレス上の連続空間にはなく、要素は次の要素へのアドレスをもっているだけである。アドレスを使用してのアクセスにより、途中への値の挿入、削除がアドレスを書き換えるだけなのでO(1)と高速に行えるのがメリット。デメリットとしては、要素nへのアクセスがO(n)になってしまう点などあがあげられる。（リストについて詳しくはセルフで）

中身をのぞいて見る

今回はここをのぞいた。必要な部分のみを抜き出しているから、完全なソースコードではない。

List<T>宣言

public class List<T> : IList<T>, System.Collections.IList, IReadOnlyList<T>
{
    private const int _defaultCapacity = 4;

    private T[] _items;
    [ContractPublicPropertyName("Count")]
    private int _size;
    
    static readonly T[]  _emptyArray = new T[0];

リストで使用されるデータはT[] _itemsに格納される。
_sizeは保存されているデータの要素数。
_emptyArrayは要素数が0の時に使用される空配列。

List<T>コンストラクター

    public List() {
        _items = _emptyArray;
    }

    public List(int capacity) {
        if (capacity < 0) 
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.capacity, ExceptionResource.ArgumentOutOfRange_NeedNonNegNum);
        Contract.EndContractBlock();

        if (capacity == 0)
            _items = _emptyArray;
        else
            _items = new T[capacity];
    }

引数無しのコンストラクターは、内部配列に空配列を代入するだけ。
int引数ありのコンストラクターは、capacityを引数にとる。この値は、Listの内部配列の最大要素数。
内部配列の要素数はあくまで固定長の為、利用する最大要素数に予想がついているのであれば、指定したほうが、よりパフォーマンスが良くなる。

List<T>.Add()メソッド

よく使用するであろうAdd()メソッドを見てみる。

if (_size == _items.Length) EnsureCapacity(_size + 1);
    _items[_size++] = item;
}

T型のitemを引数にとる。
内部配列の使用中要素数である_sizeの数が、内部配列の要素数である_items.Lengthと等価になった場合はEnsureCapacity()メソッドが実行される。
その後、_size + 1の要素番号（使用中の最後の要素番号 + 1）の要素にitemを格納する。

List.EnsureCapacity()

次にAdd()内で実行されるEnsureCapacity()を見てみる。

private void EnsureCapacity(int min) {
    if (_items.Length < min) {
        int newCapacity = _items.Length == 0? _defaultCapacity : _items.Length * 2;
        if ((uint)newCapacity > Array.MaxArrayLength) newCapacity = Array.MaxArrayLength;
        if (newCapacity < min) newCapacity = min;
        Capacity = newCapacity;
    }
}

int型のminを引数にとる。
内部配列の要素数が、minの値より小さかった場合、if内が実行される。
内部配列の要素数が0だった場合は、newCapacityは_defaultCapacityである、4になる。
要素数が0ではなかった場合は、newCapacityは現在の要素数の2倍の値になる。
4行目では、newCapacityの値がArray.MaxArrayLengthの値を超えてないかチェックしている。
Array.MaxArrayLengthの値は、0X7FEFFFFFなので、事実上最大要素数は、2146435071ということになる。
ここら辺については、Array Classを読むことを推奨。
最終的にnewCapacityの値が決定され、Capacityに代入される。
事実上、このメソッドが実行された場合、Array.MaxArrayLength以下の範囲で、要素数が2倍になる。

List.Capacityプロパティ

EnsureCapacity()内で使用されるCapacityについて見る。今回はsetterのみ。

public int Capacity {
    set {
        if (value < _size) {
            ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        }
        Contract.EndContractBlock();

        if (value != _items.Length) {
            if (value > 0) {
                T[] newItems = new T[value];
                if (_size > 0) {
                    Array.Copy(_items, 0, newItems, 0, _size);
                }
                _items = newItems;
            }
            else {
                _items = _emptyArray;
            }
        }
    }
}

上部は例外系。
valueに内部配列の要素数以外の0以上の値が代入された場合、代入された要素数を持つ配列を作成し、現在保存しているデータを新規配列にコピーする。
その後、_itemsを新規配列に書き換える。
もし、値が0未満だった場合は、空配列に書き換える。
ということは、Capacityが増えるたびに、配列のコピーが発生する。

今回のまとめ

List<T>は、内部配列によって値を保存している。
内部配列の要素数以上の値を保存しようとすると、現在の要素数の2倍の要素数が確保される。
もし、使用する要素数がある程度わかるのであれば、インスタンス生成時にcapacityとして渡してあげることで、パフォーマンスが向上する。

Published 19 Jun 2019

カテゴリ

タグ