カテゴリ

タグ

C#Listの実装 #3 Indexer編

前編はこちら

中身をのぞいて見る

毎度、ここから。

List<T>Indexer

public T this[int index] {
    get {
        if ((uint) index >= (uint)_size) {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        Contract.EndContractBlock();
        return _items[index]; 
    }

    set {
        if ((uint) index >= (uint)_size) {
            ThrowHelper.ThrowArgumentOutOfRangeException();
        }
        Contract.EndContractBlock();
        _items[index] = value;
        _version++;
    }
}

ずっと不思議に思っていたことがある。リストの要素nへのアクセスはO(n)であるが、なぜC#のリストはO(1)でアクセスできるのだろうと。 C#のリストについて調べる気になったこの問題だがこのコードですべてが解決した。

  • getter
  • インデックス番号を受け取り、内部配列内の指定されたインデックス番号の要素を返す。
  • 配列へのアクセスなのでO(1)である。
  • setter
  • 指定されたインデックス番号に指定された要素を格納する。
  • 上書きなので、コピーなどの処理はない。

総まとめ

  • List<T>は、内部配列によって値を保存している。
  • 内部配列の要素が最大になると、配列のコピー処理が発生する。
  • RemoveAt(),Remove()は、配列を前に詰める処理があるので多少重い。

感想

配列と違って、要素数を全任せできるのがリストの良い部分かな。

Published 25 Jun 2019