.NETのGenericコレクションの使い方サンプル（計算量付き）
C#(.NET)コレクションの使い分けヒント の続き
List<T>
内部データ構造は配列。
var list = new List<string>();
// 追加 : O(1)
list.Add("item");
// 取得 : O(1)
var item = list[0];
// 検索 : O(n)
int index = list.IndexOf("item");
bool contains = list.Contains("item");
var finditem = list.Find(_ => _.StartsWith("it"));
// ソート : O(n log n)
list.Sort();
// 列挙 : O(1) ※GetEnumerator()のみ。foreachを含めたらO(n)
foreach (var element in list)
{
Console.WriteLine(element);
}
// 削除 : O(n)
bool removed = list.Remove("itemmmm");
list.RemoveAt(0);
LinkedList<T>
内部データ構造は連結リスト。
var llist = new LinkedList<string>();
// 追加 : O(1)
LinkedListNode<string> addedNode = llist.AddLast("value");
LinkedListNode<string> addedNode2 = llist.AddAfter(addedNode, "value2");
// 検索 : O(n)
bool contains = llist.Contains("value");
// 検索と取得 : O(n)
LinkedListNode<string> findNode = llist.Find("value");
var value = findNode.Value;
// 列挙 : O(1)
foreach (var element in llist)
{
Console.WriteLine(element);
}
// 削除(要素指定) : O(n)
bool removed = llist.Remove("value");
// 削除(ノード指定) : O(1)
llist.Remove(addedNode2);
llist.RemoveFirst();
Queue<T>
内部データ構造は循環配列。
var queue = new Queue<string>();
// エンキュー : O(1)
queue.Enqueue("item");
// 検索 : O(n)
bool contains = queue.Contains("item");
// ピーク : O(1)
var item = queue.Peek();
// デキュー : O(1)
var item2 = queue.Dequeue();
Stack<T>
内部データ構造は配列。
var stack = new Stack<string>();
// プッシュ : O(1)
stack.Push("item");
// 検索 : O(n)
bool contains = stack.Contains("item");
// ピーク : O(1)
var item = stack.Peek();
// ポップ : O(1)
var item2 = stack.Pop();
Dictionary<TKey, TValue>
内部データ構造はハッシュテーブル。
var dict = new Dictionary<string, string>();
// 追加 : O(1)
dict.Add("key", "value");
// 検索 : O(1)
bool containsKey = dict.ContainsKey("key");
// 取得 : O(1)
var value = dict["key"];
// 削除 : O(1)
bool removed = dict.Remove("key");
※備考
O(1)になるには下記の条件が必要。そうでない場合はO(n)に近づく。
- CountがCapacityより十分少ない
- TKey（またはIEqualityComparer<TKey>）のGetHashCode()が偏りのないハッシュを返す
SortedDictionary<TKey, TValue>
内部データ構造は二分探索木。
var sdict = new SortedDictionary<string, string>();
// 追加：O(log n)
sdict.Add("key2", "value2");
sdict.Add("key", "value");
// 検索：O(log n)
bool contains = sdict.ContainsKey("key");
// 取得：O(log n)
var value = sdict["key"];
// 列挙：O(log n)
foreach (var element in sdict)
{
Console.WriteLine($"Key={element.Key}, Value={element.Value}");
}
// 削除：O(log n)
bool removed = sdict.Remove("key");
SortedList<TKey, TValue>
内部データ構造は（ソートされた）配列。
var slist = new SortedList<string, string>();
// 追加：O(n)
slist.Add("key", "value");
slist.Add("key2", "value");
// 検索：O(log n)
bool containsKey = slist.ContainsKey("key");
int indexKey = slist.IndexOfKey("key");
// 取得：O(log n)
var value = slist["key"];
// 取得(インデックス使用)：O(1)
var keybyindex = slist.Keys[0];
var valuebyindex = slist.Values[0];
// 列挙：O(1)
foreach (var element in slist)
{
Console.WriteLine($"Key={element.Key}, Value={element.Value}");
}
// 削除：O(n)
bool removed = slist.Remove("key");
slist.RemoveAt(0);
HashSet<T>
内部データ構造はハッシュテーブル。
var set = new HashSet<string>();
// 追加：O(1)
bool added = set.Add("item");
// 検索：O(1)
bool contains = set.Contains("item");
// 集合演算：O(n) ~ O(n+m)
set.UnionWith(new[] { "otheritem" });
set.IntersectWith(new[] { "item" });
// 列挙：O(1)
foreach (var element in set)
{
Console.WriteLine(element);
}
// 削除：O(1)
bool removed = set.Remove("item");
// 削除(条件指定)：O(n)
int removedCount = set.RemoveWhere(_ => _.StartsWith("it"));
※備考
O(1)になるには下記の条件が必要。そうでない場合はO(n)に近づく。
- CountがCapacityより十分少ない
- TKey（またはIEqualityComparer<TKey>）のGetHashCode()が偏りのないハッシュを返す
SortedSet<T>
内部データ構造は二分探索木。
var sset = new SortedSet<string>();
// 追加：O(log n)
bool added = sset.Add("item");
sset.Add("item2");
sset.Add("item4");
sset.Add("item3");
// 検索：O(log n)
bool contains = sset.Contains("item");
// 集合演算：O(n) ~ O(n+m)
sset.UnionWith(new[] { "otheritem" });
// 列挙：O(log n)
foreach (var element in sset)
{
Console.WriteLine(element);
}
// 削除：O(log n)
bool removed = sset.Remove("item");
// 削除（条件指定）：O(n)
int removedCount = sset.RemoveWhere(_ => _.StartsWith("it"));