はじめに
List<T>クラスについて、あれやこれや書きたいと思います。
「普段何気なく使ってるけど、言われてみれば中身とか全然知らんわ。」
「でも改めて考えると、すごく気になってきた。」
っていうちょっと変わった人向けです。
ほぼ全部独学で書いたので、間違ってたら指摘してください。
List<T>とは
CからC#に移って来た人間が一番最初に感動するやつ__(私が証明です)__
ざっくり言うと、サイズの管理をしなくてもいい配列__(多少の語弊あり)__
C#でそれなりの規模のプログラムを組んでいれば絶対に1度はお世話になる__(はず)__
定義はどこにあるの?
mscorlib.dll → System.Collections.Generic名前空間の下にあります。
ソースコードは↑でも見れるし、デコンパイルしても見れるよ。
List<T>のあれやこれや
その前に<T>ってなに?
ジェネリクス(ジェネリック)と呼ばれている凄いヤツです。
__型だけ違っていて、中身は同じ__であるような一連の処理があったときに、型をパラメータにとり、さまざまな型に対応したクラスや関数を作るためのものになります。
List<string>
とかList<int>
とかList<MyClass>
とかやると思いますが、このstring
とかint
とかMyClass
とかが__型をパラメータにとり__の部分。
どれも複数の値をまとめるものなので、型だけ違っていて、中身は同じ。
Listの中身ってどうなってるの?
配列です。private T[] _items
で中身を管理してます。
なのに簡単に要素を増やせるし、減らせる。素晴らしいですね。
配列なのにサイズの管理をしなくてもいいの?
厳密に言えば__しなくていい訳ではない__です。__List側で勝手にやって__ます。
なので、利用者はあまり気にすることなく使えます。
具体的には_items.Length
と private int _size
とpublic int Capacity
の3つの要素でサイズを管理しています。
Countってのがあった気がするけど?
Listを使うときによく使うCount(プロパティ)ですが、
public int Count
{
get
{
return _size;
}
}
となっているので、_sizeと同じです。
ちなみにCountメソッドってのもありますが、Listクラスに定義は存在しません。
__拡張メソッド__と呼ばれる機能を使って、Enumerable
クラスに定義されてます。
こいつの話をしだすと、IEnumerable<T>
とか、Func
デリゲートとか、ラムダ式とか、LINQとか、色々話が広がりすぎるので今回は割愛します。
ソースコードは、System.Core.dll → System.Linq名前空間の下にいます。
こっちはGitHubにおいてあります。
要素の取得ってどうなってるの?
[]で要素を取得・設定する処理のコードです。
public T this[int index]
{
get
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
return _items[index];
}
set
{
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
_items[index] = value;
_version++;
}
}
このメソッド自体は__インデクサー__と呼ばれるC#で用意されている機能です。
indexがsizeより大きい場合や0以下の場合、ArgumentOutOfRangeException
が発生します。
要素の追加ってどうなってるの?
要素追加用メソッドAdd
です。こいつは4段階の構成になっています。
public void Add(T item)
{
if (_size == _items.Length)
{
EnsureCapacity(_size + 1);
}
_items[_size++] = item;
_version++;
}
private void EnsureCapacity(int min)
{
if (_items.Length < min)
{
int num = (_items.Length == 0) ? 4 : (_items.Length * 2);
if ((uint)num > 2146435071u)
{
num = 2146435071;
}
if (num < min)
{
num = min;
}
Capacity = num;
}
}
public int Capacity
{
[__DynamicallyInvokable]
get
{
return _items.Length;
}
[__DynamicallyInvokable]
set
{
if (value < _size)
{
ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
}
if (value != _items.Length)
{
if (value > 0)
{
T[] array = new T[value];
if (_size > 0)
{
Array.Copy(_items, 0, array, 0, _size);
}
_items = array;
}
else
{
_items = _emptyArray;
}
}
}
}
4段階目のArray.Copy
は、配列をコピーするメソッドです。
後で詳しく説明しますので、この段階ではそんなもんかと思っていてください。
-
Add
呼び出し時に_size
と_items.Length
が同じだった場合、EnsureCapacity
を呼び出す。 -
EnsureCapacity
呼び出し時に_items.Length
の2倍と引数min
を比較し、大きい方をCapacity
に設定。 -
Capacity
のSetterで_items.Length
と設定値value
を比較し、配列の新規作成と既存部分のコピーを行う。
つまりListは__「サイズを無視して要素を追加できる配列」ではなく、「サイズが足りなくなったら自動で作り直してくれる配列」__なんです。実に優秀なお方ですね。
パフォーマンス測ってみた
上記の理由から、Addを大量に呼び出す場合は、あらかじめCapacity
を自分で設定しておいたほうがパフォーマンスに優れます。(配列の新規作成や要素のコピーには時間がかかる)
というわけで、早速測ってみました。
BenchmarkDotNet=v0.11.3, OS=Windows 10.0.15063.1508 (1703/CreatorsUpdate/Redstone2)
Intel Core i7-4770 CPU 3.40GHz (Haswell), 1 CPU, 8 logical and 4 physical cores
Frequency=3312643 Hz, Resolution=301.8738 ns, Timer=TSC
[Host] : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
DefaultJob : .NET Framework 4.7.2 (CLR 4.0.30319.42000), 32bit LegacyJIT-v4.7.3260.0
public class Tests
{
private int num = 100_000_000;
public Tests()
{
ListTest1();
ListTest2();
}
[Benchmark]
public void ListTest1()
{
//特に何もしない。
var a = new List<int>();
for (int i = 0; i < num; i++)
{
a.Add(i);
}
}
[Benchmark]
public void ListTest2()
{
// コンストラクタの引数であらかじめCapacityを設定できる。
var b = new List<int>(num);
for (int i = 0; i < num; i++)
{
b.Add(i);
}
}
}
Method | Mean | Error | StdDev |
---|---|---|---|
ListTest1 | 550.7 ms | 4.740 ms | 4.434 ms |
ListTest2 | 336.4 ms | 1.259 ms | 1.116 ms |
リストに0から1億個数字を追加した時の差がこれくらいでした。
これを大きいと見るか、小さいと見るかは人それぞれですが、個人的にはそんなに大きくないと思います。
1億もデータがあったらもっと遅い処理がどこかにあるはずなので、誤差レベルじゃないかと。
ですが、シビアなパフォーマンスを求められる局面に出会ったら思い出してください。
要素の削除ってどうなってるの?
要素削除用メソッドRemoveAt
です。こいつの構成は2段階です。
public void RemoveAt(int index)
{
// (1)
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
// (2)
_size--;
if (index < _size)
{
Array.Copy(_items, index + 1, _items, index, _size - index);
}
// (3)
_items[_size] = default(T);
_version++;
}
public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
{
Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, false);
}
internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);
ぱっと見て、分かりにくい処理です。
(1)から順に追っていきましょう。
// (1)
if ((uint)index >= (uint)_size)
{
ThrowHelper.ThrowArgumentOutOfRangeException();
}
ここは特に言うこともありません。
indexがsizeより大きい場合や0以下の場合、ArgumentOutOfRangeException
が発生します。
// (2)
_size--;
if (index < _size)
{
Array.Copy(_items, index + 1, _items, index, _size - index);
}
_size--
でListのサイズを1つ小さくします。
問題はその次です。
Array.Copyの中身はCopyですが、このCopyの中身は見ることができません。
こいつはC++で書かれてるDLLを参照しています。
仕方がないので、皆大好きMicrosoft公式リファレンスにて、Array.Copyの仕様を調べます。
Copy(Array, Int32, Array, Int32, Int32)
Copies a range of elements from an Array starting at the specified source index and pastes them to another Array starting at the specified destination index. The length and the indexes are specified as 32-bit integers.
指定されたコピー元インデックスから始まる配列から要素の範囲をコピーし、指定されたコピー先インデックスから始まる別の配列にそれらを貼り付けます。 長さとインデックスは32ビット整数として指定されます。
Parameters
sourceArray
The Array that contains the data to copy.
sourceIndex
A 32-bit integer that represents the index in the
sourceArray
at which copying begins.
destinationArray
The Array that receives the data.
destinationIndex
A 32-bit integer that represents the index in the
destinationArray
at which storing begins.
length
A 32-bit integer that represents the number of elements to copy.
パラメーター
sourceArray
アレイ
コピーするデータを含む配列。sourceIndex
Int32
コピーが開始されるsourceArray内のインデックスを表す32ビット整数。destinationArray
アレイ
データを受け取る配列。destinationIndex
Int32
保存が始まるdestinationArray内のインデックスを表す32ビット整数。長さ
Int32
コピーする要素の数を表す32ビット整数。
日本語部分がGoogle翻訳にぶん投げた結果です。
つまり_items
の index + 1
インデックス目から_size - index
個の要素を、_items
のindex
インデックス目を開始位置としてコピーする処理ってことですね。
// (3)
_items[_size] = default(T);
_version++;
そして最後に、隙間をdefaultで埋めて終わりです。
全く理解が追いつかないのだが?
表を使って詳しく説明します。
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
a | b | c | d | e | f |
List<string>の中身だと思ってください。この時_size
は6です。
このListからcを消したいと思います。
RemoveAt(2)
を実行します。index
は2です。
index < _size
なので(1)で例外は発生しません。
(2)の最初で_size
が5になります。
よって、
index+1
=> 3
_size - index
=> 3
となるので、_items
の3インデックス目から3個の要素を、_items
の2インデックス目を開始位置としてコピーします。
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
a | b | d | e | f | f |
このままでは最後に不要なデータが残ってしまうので、一番最後をdefault(string)、空文字で埋めます。
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
a | b | d | e | f |
無事に、cを消すことができました。
ちなみに(2)でif (index < _size)
と判定してます。
これはindex
と_size
が同じ(=一番最後の要素を削除したい)場合、一番最後をdefault(T)で埋めるだけでいいからです。
メモリ的な話
ここで1つ大事(かもしれない)事です。
要素を削除した時、配列のサイズは変わらないんです。
なので、大量の要素を削除した時、配列の後ろに大量の空の部分が出来上がります。
中身は空でもメモリは消費するので、気をつけてください。
今どきそれほどシビアなメモリ管理が必要なことはあまり無いとは思いますが。
例外ってどうなってるの?
System.ArgumentOutOfRangeException
System.ArgumentNullException
System.InvalidOperationException
System.ArgumentException
System.OutOfMemoryException
Listクラス内で発生する可能性のある例外たちです。
出現頻度は、1 >= 2 > 3 >>>> 4 >>>> 5です。(当社調べ)
ここでは出現頻度の低い4,5は割愛します。
1.ArgumentOutOfRangeException
要素の取得時や削除時に、_size
より大きな値や0未満の値を設定すると発生します。
よく初心者が「要素が6なんだから最後は6番目やん、list[6]
っと」と言って踏み抜くやつです。
2.ArgumentNullException
引数にnullを設定して一部のメソッドを呼び出すと、発生します。
「いちいちAdd
なんてやってられんわ、AddRange
使ったろ」と言ったときに、引数を初期化し忘れて踏むことがあります。
3.InvalidOperationException
上2つはそのままですが、こいつは少しややこしいです。
直訳すると「無効な操作による例外」です。無効な操作ってなんやねん。
良く見るパターンはこんな感じのやつです。
var listStr = new List<string>() { "aaa", "abc", "bbc", "aba", "cbc", "bcc" };
foreach (var item in listStr)
{
if (!item.Contains("a"))
{
listStr.Remove(item);
}
}
foreach
の中でListに手を加えてしまったパターンです。
”コレクションが変更されました。列挙操作は実行されない可能性があります。”と言われてしまいます。
列挙操作、つまり1つ1つ数え上げている途中で変えられてしまうと、どこまで処理を行ったか分からなくなってしまいます。
もしこれを許可してしまった場合、
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | abc | bbc | aba | cbc | bcc |
未 | 未 | 未 | 未 | 未 | 未 |
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | abc | bbc | aba | cbc | bcc |
済→残 | 未 | 未 | 未 | 未 | 未 |
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | abc | bbc | aba | cbc | bcc |
済 | 済→残 | 未 | 未 | 未 | 未 |
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | bbc | bbc | aba | cbc | bcc |
済 | 済 | 済→削 | 未 | 未 | 未 |
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | bbc | aba | cbc | bcc | |
済 | 済 | 未 | 済→削 | 未 | 未 |
0 | 1 | 2 | 3 | 4 | 5 |
---|---|---|---|---|---|
aaa | bbc | aba | bcc | ||
済 | 済 | 未 | 未 | 済→完 | 未 |
このように確認されない部分が出てしまいます。
これでは困るので、foreach
の中では要素の変更ができないようになっています。
コレクションの変更ってどうなってるの?
InvalidOperationExceptionの説明の中に、”コレクションが変更されました。列挙~”とありました。
コレクションの変更をどうやって管理してるのかもついでに解説します。
とはいえ、実は答えの半分は既に出ていたりします。
要素の取得・追加・削除の解説内に_version++
という処理がありました。
こいつを使っています。
public void ForEach(Action<T> action)
{
if (action == null)
{
ThrowHelper.ThrowArgumentNullException(ExceptionArgument.match);
}
//ここと
int version = _version;
for (int i = 0; i < _size; i++)
{
//ここと
if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
{
break;
}
action(_items[i]);
}
//ここ
if (version != _version && BinaryCompatibility.TargetsAtLeast_Desktop_V4_5)
{
ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumFailedVersion);
}
}
ForEach
メソッドです。一般的に広く使われているforeach
とは別物になります。
色々と分からない箇所があるとは思いますが、コメントのすぐ下の行だけ見てください。
- 最初に現在の
_version
を取得し、version
としておく。 -
_item
に対して反復処理をかける際に、都度_version
とversion
を比較。 - 不一致だったら
for
から抜けて、例外を出力。
これによりAdd
やRemoveAt
等が実行されると_version
とversion
にズレが生じる仕組みになっております。
foreach
も似たようなことをやっています。(詳細を解説しようとすると長くなるので割愛)
2019/01/15 この辺について書いて見ました。
「Enumerator構造体ってなに?」の辺りで触れています。
おわりに
ここまで大量に書いておいてなんですが、C#でプログラミングする上で、ここに書いてあることの9割は不要です。
プログラミング言語ってのは、「何か」を作るための道具の1つです。
道具の仕組みを知らなくても、使い方さえ知っていればその「何か」は作れるわけです。
ボールペンからインクが出る原理がわからなくても字は書けるし、どうやって電話が音を伝えているか知らなくても遠くの誰かとお話できるわけです。
ちなみにこの考え方はオブジェクト指向でよく出てくるカプセル化と呼ばれるものです。
複雑なもの(配列の長さの管理等)は中に隠し、外に見えるのは簡単な操作(取得・追加・削除等)のみにすることで誰でも利用可能になっています。
もちろん知っておいて損することはありません。
シビアなメモリ管理やパフォーマンスを求められた場合に役立つ可能性はありますし、こうやって長々と記事を書いて暇を潰すことも出来ます。
ただ費用対効果に見合っているかと言われると......疑問ですね。
なぜこんな物を書いたのか
よくプログラミングの世界では「おまじない」とか「動いてるからよし」とか「そういうものです」とか言われることがあります。
自作の機能だとマズいですが、C#にはじめから用意されている機能だったらそれでいいと思います。
でも中には「いや、そんな事言われても納得できんぞい。」と考える変わり者がいてもいいでしょう。
そんな変わり者が僕以外にいるかどうかはわかりませんが、「いたら嬉しいなぁ」というのが動機です。
人は生まれながらに、知ることを欲する。 アリストテレス(古代ギリシア)
かっこつけてアリストテレスとか言ってますが、元ネタはトリビアの泉です。
もし次回以降があれば、今回割愛したIEnumerable<T>
とか、Func
デリゲートとか、ラムダ式とか、LINQとかその変の話もしたいと思ってます。