C#Listの実装 #2 Remove編

前編はこちら

• プログラミング/C-Listの実装-Add編

中身をのぞいて見る

毎度、ここから。

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

public bool Remove(T item) {
    int index = IndexOf(item);
    if (index >= 0) {
        RemoveAt(index);
        return true;
    }

    return false;
}

• このコードは単純で、T型のitemを引数にとる。
• IndexOfは線形探索で、itemの要素があった場合、最初のインデックスを返す。
• indexが0以上の値だった場合は、RemoveAt()メソッド用いて削除する。

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

public void RemoveAt(int index) {
    if ((uint)index >= (uint)_size) {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    Contract.EndContractBlock();
    _size--;
    if (index < _size) {
        Array.Copy(_items, index + 1, _items, index, _size - index);
    }
    _items[_size] = default(T);
    _version++;
}

• 上部は例外系。
• 要素が一個削除されるので、_sizeから1を引いている。
• 引数のindexの番号が、_sizeよりも大きいかチェックする。
• 大きかった場合は、index + 1から最後の要素までを、indexを先頭にコピーしている。つまり、削除される要素の1個後ろの要素からすべての要素を1個前に詰めている。要素数が多い場合は、計算量が増える。さらに言えば、後ろの要素を削除するより、先頭の方の要素を削除する方が、コストが大きい。
• 使用しなくなった_items[_size]にはT型の規定値を代入する。

今回のまとめ

• RemoveAt()メソッドは、かなりコストが大きい。
• 消す必要がない、かつ順番が関係ないのであれば、使用しない要素を一番後ろの要素と入れ替える方法もある。
• あくまで使用中の要素をコピーするので、capacityに大きな値を指定したからと言ってRemoveのパフォーマンスには影響しない。（要素自体は確保されているので、メモリは使用されるが）