概要
C# 動的配列 List とは、動的にサイズを増減できる便利な配列クラスだぞ。
※ 以前は ArrayList というクラスがあったらしいが、問題があったようで、現在は List の使用が推奨されているようだ。
通常の配列では使用前にサイズを指定する必要があり、アプリ実行中の状況に応じて必要なサイズが増減するような場合は、 どの程度のサイズを指定しておいたらいいか困ってしまう。少ないと足りなくなりにっちもさっちもいかなくなるし、 十分大きなサイズを指定するとメモリの無駄で、場合によってはそれによってパフォーマンスが低下することもある。
その点、動的配列である List を使っておけば、アプリ実行中必要に応じて配列のサイズを増減させることができ安心だ。
i 番目の要素は [i] で参照できるので、使い方も通常の配列とほとんど違わず、必要最低限のことだけ覚えれば、便利な配列として十分使えるぞ。
パフォーマンス的には、C++ の std::vector と同じで、ランダムアクセス O(1)、末尾への要素追加・末尾要素の削除は O(1) と高速で、
途中への要素追加・途中要素の削除は O(N) となっている。
※ O(1) は処理時間がデータサイズに依存しないことを、O(N) はデータサイズに比例することを示す。
準備
※ 注意： 本稿で示すコードは C# コンソールアプリケーション用のものである。
Unity スクリプト内に書いて実行することも可能だが、素直に C# コンソールアプリを作ってそこで確かめることを強く勧める。
List を使用するには、プログラムの先頭付近に「using System.Collections.Generic;」を記述する。
C# コンソールアプリケーション プロジェクトを作成した場合、上記の using 文は自動的に生成される。
Unity の C# スクリプトの場合は自動的に生成されないので、自分で記述するのを忘れないようにしよう。
初期化
要素の型を T とすると、その動的配列型は「List<T>」と表記する。
例えば int 型の要素を持つ動的配列は以下のように宣言する。
List<int> v;
C++ では、変数を宣言するだけで、デフォルトコンストラクタがコールされ初期化されるが、 C# では new でオブジェクトの初期化が必要だ。
List<int> v = new List<int>();
new による初期化を行わないと、v には null が入っている。
List<int> v = new List<int>(123); // 容量（capacity）指定。サイズではないので注意
上記のように、コンストラクタ引数に数値を指定すると、容量（capacity）指定となる。 C++ の std::vector 等のコンテナクラスでは、サイズ指定なので、C++er は間違えないよう要注意だ。
なお、現時点で（C++ コンテナクラスの resize(size_t) の様に）動的配列の要素数を指定することは不可能のようだ。
列挙データで動的配列を初期化したい場合は、下記のように丸括弧の部分をデータをカンマで区切り波括弧で囲んだもので置き換える。
List<int> v = new List<int>{1, 2, 3};
要素型がクラスの場合、下記のように各要素を new で生成する必要がある。
List<Vector3> v3 = new List<Vector3>{new Vector3(0,0,0), new Vector3(1,1,1)};
このような冗長な書き方は C++ に慣れている筆者にとっては正直まどろっこしいと感じる。 将来的には new List<Vector3>, new Vector3 を省略できる糖衣構文（シンタックスシュガー）が実装されるのではないかと期待する。
演習問題：
- float 型の動的配列 lstf を宣言し、初期化しなさい。
- 32 の容量を持つ int 型の動的配列 lst を宣言し、初期化しなさい。
- {3, 1, 4, 1} の要素を持つ int 型の動的配列 lst を宣言・初期化しなさい。
List<float> lstf = new List<float>();
List<int> lst = new List<int>(32);
List<int> lst = new List<int>{3, 1, 4, 1};
プロパティ
Count で要素数を、Capacity でメモリを再確保しなくても格納できる総要素数を返す。これらは関数ではなく、読み出し専用のメンバ変数なので、 末尾に () を付加しないし、値を代入することも出来ない。
List<int> lst = new List<int>();
Console.WriteLine("lst.Count = {0}", lst.Count);
Console.WriteLine("lst.Capacity = {0}", lst.Capacity);
List<int> lst2 = new List<int>(7); // 容量（Capacity）に 7 を指定
Console.WriteLine("lst2.Count = {0}", lst2.Count);
Console.WriteLine("lst2.Capacity = {0}", lst2.Capacity);
List<int> lst3 = new List<int>{3, 1, 4};
Console.WriteLine("lst3.Count = {0}", lst3.Count);
Console.WriteLine("lst3.Capacity = {0}", lst3.Capacity);
List<int> lst = new List<int>();
lst.Count = 12; // エラー
lst.Capacity = 34; // エラー
C# の通常配列で要素数を取得するのは Count ではなく Length プロパティだ。これは（筆者が）よく間違えることなので、読者も注意しよう（自戒）。
演習問題：
- 上記の最初のコードを実際にビルド・実行し、Count, Capacity の値を確認しなさい。
- 上記の２番めのコードをビルドし、エラーが発生することを確認しなさい。
要素を参照
通常の配列と同様に 変数名[インデックス] でインデックス番目の要素を参照できる。なお、インデックスは C/C++ 同様に 0 から始まる。
下記のように、右辺値で要素の値が参照でき、左辺に書けば値を修正することができる。
[インデックス] による参照の処理時間は O(1) で、要素数に依らず高速である。
List<int> lst = List<int>{3, 1, 4, 1, 5};
Console.WriteLine(lst[2]); // 4 が表示される
lst[2] = 123; // 値を修正
Console.WriteLine(lst[2]); // 123 が表示される
全要素を表示する場合は、下記のように for 文で Count 回ループすればよい。
for (int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // i 番目の要素を表示
}
要素を全部表示する場合は、下記のように foreach を使用して簡潔に記述することもできる。
foreach (int n in lst) {
Console.WriteLine(n); // 要素を順に表示
}
List の ForEach(アクション) を使って、全要素を参照することもできる。引数にはデリゲートやラムダ式を指定することができる。
// デリゲートを使った場合
lst.ForEach (delegate(int n) {
Console.WriteLine(n); // 要素を順に表示
});
// ラムダ式を使った場合
lst.ForEach ((n) => {
Console.WriteLine(n); // 要素を順に表示
});
演習問題：
- int 型で {3, 1, 4} の要素を持つ動的配列 lst を作り、for文、foreach文、ForEach メソッドを使い要素を順に表示しなさい。
- int 型で {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5} の要素を持つ動的配列 lst を作り、for文、foreach文、ForEachメソッドのどれかを使い要素の合計を求め、表示しなさい。
List<int> lst = new List<int>{3, 1, 4};
for (int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // i 番目の要素を表示
}
foreach (int n in lst) {
Console.WriteLine(n);
}
lst.ForEach ((n) => {
Console.WriteLine(n);
});
List<int> lst = new List<int>{3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int sum = 0; // 合計
lst.ForEach ((n) => {
sum += n; // 合計に足し込む
});
Console.WriteLine("sum = {0}", sum); // 合計表示
要素を追加
Add(要素) で要素を最後に追加することができる。処理速度は O(1) と高速だ。
C++ STL の std::push_back(要素) 相当。
List<int> lst = new List<int>();
lst.Add(1); // 末尾に 1 を追加
lst.Add(3); // さらに末尾に 3 を追加、{1, 3} となる
Insert(インデックス, 要素) でインデックスで指定する位置に要素を挿入することができる。
List<int> lst = new List<int>();
lst.Insert(0, 1); // 先頭に 1 を挿入
lst.Insert(0, 3); // 先頭に 3 を挿入、{3, 1} となる
Insert() の処理速度は O(N) なので、乱用はパフォーマンス的に危険だ。
演習問題：
- 空の list<int> lst を作成し、for文で 0, 1, ... 9 を Add() で末尾に追加した後、lst の中身を表示して確認しなさい。
- 空の list<int> lst を作成し、for文で 0, 1, ... 999999 を末尾に追加するのに要する時間をミリ秒単位で計測しなさい。
時間計測方法は C# 処理時間計測 入門 を参照。 - ループ回数を適当に変えてみて、Add() の処理時間が O(N) であることを確認しなさい。
- C++ でも同様の処理を記述し、速度比較してみなさい。
- 空の list<int> lst を作成し、for文で 0, 1, ... 99999 を順に先頭に挿入するのに要する時間をミリ秒単位で計測しなさい。
- ループ回数を適当に変えてみて、Insert(0, 値) をfor文で回した場合の処理時間が O(N^2) であることを確認しなさい。
List<int> lst = new List<int>();
for (int i = 0; i < 10; ++i) {
lst.Add(i); // 末尾に追加
}
for(int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // 要素を表示
}
List<int> lst = new List<int>();
var sw = new Stopwatch(); // ストップウォッチオブジェクト生成
sw.Start(); // 時間計測開始
for (int i = 0; i < 1000000; ++i) {
lst.Add(i);
}
sw.Stop(); // 時間計測終了
var el = sw.Elapsed; // 経過時間取得
Console.WriteLine("elapsed = {0}", el.TotalMilliseconds); // ミリ秒単位で経過時間を表示
List<int> lst = new List<int>();
var sw = new Stopwatch(); // ストップウォッチオブジェクト生成
sw.Start(); // 時間計測開始
for (int i = 0; i < 100000; ++i) {
lst.Insert(0, i);
}
sw.Stop(); // 時間計測終了
var el = sw.Elapsed; // 経過時間取得
Console.WriteLine("elapsed = {0}", el.TotalMilliseconds); // ミリ秒単位で経過時間を表示
要素を削除
Clear() で、全要素を削除できる。
なお、要素は削除され Count プロパティは 0 になるが、Capacity プロパティは変化しない。
List<int> lst = new List<int>{3, 1, 4}; // 要素数3のリスト生成
lst.Clear(); // 全要素をクリア
Remove(要素) で、指定要素と同じ最初の要素を削除できる。
要素を削除した場合は true を、指定要素が List に含まれない場合は、何もおこらず、false が返る。
List<int> lst = new List<int>{3, 1, 4, 1};
lst.Remove(1); // 最初の要素1を削除 → {3, 4, 1} となる
for(int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // 要素を表示
}
上記の例は最初の要素1を削除し、結果を表示するもの。
RemoveAt(インデックス) で、指定位置の要素を削除できる。
List<int> lst = new List<int>{3, 1, 4, 1};
lst.RemoveAt(2); // インデックス2の要素を削除 → {3, 1, 1} となる
for(int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // 要素を表示
}
上記の例は3番目の要素である4を削除し、結果を表示するもの。
RemoveRange(インデックス, 要素数) で、指定位置から指定要素数を削除できる。
List<int> lst = new List<int>{1, 2, 3, 4, 5};
lst.RemoveRange(1, 2); // インデックス1から2つの要素を削除 → {1, 4, 5} となる
for(int i = 0; i < lst.Count; ++i) {
Console.WriteLine(lst[i]); // 要素を表示
}
上記の例は2, 3番目の要素を削除し、結果を表示するもの。
Remove, RemoveAt, RemoveRange の処理速度は O(N) なので、乱用はパフォーマンス的危険だ。
ただし、末尾の削除は O(1) である。
末尾要素の削除は使用頻度が高いので、C++ STL の pop_back() に対応するメソッドを何故用意しなかったのは謎だ。
が、以下のように記述すれば事足りる。
lst.RemoveAt(lst.Count-1); // 最後の要素を削除
演習問題：
- {3, 1, 4} の要素を持つ動的配列 lst を宣言し、要素数・キャパシティを表示した後、Clear() で全要素を削除した後、再度、要素数・キャパシティを表示してみなさい。
- {3, 1, 2, 2, 1, 2, 3, 3, 2} の要素を持つint型動的配列 lst を生成し、Remove(2) を使って要素 2 をすべて削除し、lst の内容を表示しなさい。 ただし、配列初期値に依存するようなコードは不可とする。
- {1, 2, 3, ... 10} の要素を持つint型動的配列 lst を生成し、RemoveAt(ix) を使って、偶数番目の要素（2, 4, ... 10）を全部削除し、結果を表示しなさい。
- {1, 2, 3, ... 10} の要素を持つint型動的配列 lst を生成し、RemoveRange(ix) を使って、3番目の要素から4つの要素を削除し、結果を表示しなさい。
List<int> lst = new List<int> { 3, 1, 4 };
Console.WriteLine("Count = {0}", lst.Count);
Console.WriteLine("Capacity = {0}", lst.Capacity);
lst.Clear();
Console.WriteLine("Count = {0}", lst.Count);
Console.WriteLine("Capacity = {0}", lst.Capacity);
List<int> lst = new List<int> { 3, 1, 2, 2, 1, 2, 3, 3, 2 };
while( lst.Remove(2) ) { } // 要素2をすべて削除するまでループ
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
List<int> lst = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
for(int i = 9; i > 0; i -= 2) // 先頭から消すと要素位置がずれるので末尾の方から消していく
lst.RemoveAt(i); // 偶数番目の要素をすべて削除
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
List<int> lst = new List<int> { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
lst.RemoveRange(3, 4); // 3番目の要素から4つの要素を削除
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
要素を検索
ある値がリストに含まれるかどうかを判定するには Containts(値) を使用する。処理速度は O(N) だ。
List<int> lst = new List<int> {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
if( lst.Contains(2) ) { // 2 が含まれるか？
Console.WriteLine("Contains(2)");
}
含まれるかどうかだけでなく、どの位置かを知りたい場合は IndexOf(値) を使用する。
マッチする要素が無い場合、IndexOf(値) は -1 を返すぞ。
List<int> lst = new List<int> {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int i = lst.IndexOf(4); // 要素4のインデックス、この場合は 2 を返す
IndexOf(値) は最初の要素インデックスを返す。指定値の要素が複数存在する場合、IndexOf(値) だけでは2番め以降の要素を見逃してしまう。
マッチする要素をすべてのインデックスを取得したい場合は、以下のように IndexOf(値、検索開始インデックス) を使うといいぞ。
List<int> lst = new List<int> {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int i = -1; // 検索開始位置のひとつ前
while( (i = lst.IndexOf(5, i+1)) >= 0 ) { // i の次から検索
Console.WriteLine(i); // 要素5のインデックスをすべて表示
}
逆順に検索したい場合は LastIndexOf(値) を使用する。
マッチする要素が無い場合、LastIndexOf(値) は -1 を返すぞ。
List<int> lst = new List<int> {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int i = lst.LastIndexOf(3); // 最後の要素3のインデックス、この場合は 9 を返す
途中から逆順に検索したい場合は LastIndexOf(値, 位置) を使用する。検索は指定位置から行われる。
例えば、lst が {1, 2, 3, 4, 5} の場合、LastIndexOf(x, 3) はインデックス3の位置、すなわち要素4の場所から検索を開始する。
List<int> lst = new List<int> {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int i = lst.Count; // 検索開始位置のひとつ後
while( (i = lst.IndexOf(5, i-1)) >= 0 ) { // i の次から検索
Console.WriteLine(i); // 要素5のインデックスをすべて表示
}
IndexOf(), LastIndexOf() の処理時間は O(N) なので、大量のデータに対して何度も繰り返し検索する場合はパフォーマンス的に好ましくない。
そのような場合は、次節で説明する Sort() でデータを昇順に並べ替え、さらにその次で説明する二分探索を行った方がよいかもしれない。
演習問題：
- int 型の {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 } を持つ動的配列を作り、IndexOf(要素、位置) を使って、要素5を全て探し、値を -5 に書き換えなさい。
- int 型の {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 } を持つ動的配列を作り、２番め以降の 5 をすべて削除しなさい。結果は {3, 1, 4, 1, 5, 9, 2, 6, 3 } となる。
List<int> lst = new List<int> { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int p = -1;
while ((p = lst.IndexOf(5, p + 1)) >= 0) { // p の次から検索
lst[p] = -5; // -5 に書き換え
}
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
List<int> lst = new List<int> { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
int ix = lst.IndexOf(5); // 最初の 5 の位置
if( ix >= 0 ) { // 要素 5 が存在する場合
++ix; // 次の位置から検索するためにインクリメント
while( (ix = lst.IndexOf(5, ix)) >= 0 ) // ix 番目から5を検索
lst.RemoveAt(ix); // 発見した5の位置を削除
}
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
ソート
List には Sort 関数が用意されており、要素型が比較関数が予め用意されているもの（例えば int）であれば、単に Sort() を呼ぶだけでソートを行ってくれる。
List<int> lst = List<int>{3, 1, 4, 1, 5};
lst.Sort(); // 昇順にソートされる
引数にラムダ式の比較関数を渡すこともできるぞ。例えば、降順にソートしたい場合は以下のように記述できる。
List<int> lst = List<int>{3, 1, 4, 1, 5};
lst.Sort((lhs, rhs) => rhs - lhs); // 降順にソートされる
比較関数は lhs < rhs ならはマイナスの値を、lhs > rhs ならばプラスの値を、lhs == rhs なら 0 を返すようにするんだぞ。
List の要素が、独自に定義した構造体などで、比較関数が定義されていない場合は、比較関数を明示的に指定する必要があるぞ。
struct SItem {
public int m_v1;
public int m_v2;
public SItem(int v1, int v2) {
m_v1 = v1;
m_v2 = v2;
}
};
.....
List<SItem> lst = new List<SItem>();
lst.Add(new SItem(10, 5));
lst.Add(new SItem(3, 2));
lst.Add(new SItem(4, 20));
lst.Sort((lhs, rhs) => lhs.m_v1 - rhs.m_v1); // m_v1 をキーにして昇順にソート
演習問題：
- string 型の {"M", "I", "T"} を要素に持つ動的配列を作り、Sort を使って昇順にソートし、結果を表示しなさい。
- int 型の動的配列 lst を作り、[0, 100) の範囲の乱数を10個末尾に追加し、昇順にソートした後、表示しなさい。
※ C# 乱数は Random rnd = new System.Random(); で、乱数オブジェクトを作成し、rnd.Next(100) で、[0, 100) の乱数を生成できる。 - int 型の動的配列 lst を作り、[0, 100) の範囲の乱数を10個末尾に追加し、降順にソートした後、表示しなさい。
※ C# 乱数は Random rnd = new System.Random(); で、乱数オブジェクトを作成し、rnd.Next(100) で、[0, 100) の乱数を生成できる。 - int 型の {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 } を持つ動的配列を作り、Sort() を１回だけ使い、偶数を配列の前半に、奇数を配列の後半に移動し、それぞれ昇順にソートしなさい。 ※ 結果は {2, 4, 6, 1, 1, 3, 3, 5, 5, 5, 9} となる。
List<string> lst = new List<string> { "M", "I", "T" };
lst.Sort();
foreach(string str in lst)
Console.WriteLine(str);
List lst = new List();
Random rnd = new System.Random(); // ランダムオブジェクト
for (int i = 0; i < 10; ++i) {
lst.Add(rnd.Next(100));
}
lst.Sort();
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
List lst = new List();
Random rnd = new System.Random(); // ランダムオブジェクト
for (int i = 0; i < 10; ++i) {
lst.Add(rnd.Next(100));
}
lst.Sort((lhs, rhs) => rhs - lhs); // 比較を反転
// 別解として、昇順にソートした後、Reverse() で反転するという方法もある
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
List<int> lst = new List<int> { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 };
lst.Sort((lhs, rhs) =>
lhs % 2 == 0 && rhs % 2 != 0 ? -1 : // lhs が偶数、rhs が奇数の場合
lhs % 2 != 0 && rhs % 2 == 0 ? 1 : // lhs が奇数、rhs が偶数の場合
lhs - rhs);
for (int i = 0; i != lst.Count; ++i)
Console.WriteLine(lst[i]);
二分探索
配列がソート済みであれば、２分探索を使うことで O(log N) と高速に検索することができる。
その他
まとめ
