.NET 4 BCL の新機能 (3) : SortedSet

.NET 4 BCL にはユニークな要素を保持するコレクション SortedSet が追加される。.NET 3.5 で追加された HashSet のようなものだが、SortedSet の方は名前からも想像がつく通り、各要素はソートされた状態でコレクション内に保持される。

赤黒木 (原文では self-balancing red-black tree。なお、赤黒木についてはざっと検索した限りこのページが詳しく書いてある) で実装されているので、挿入、削除、検索の計算量は O(log n)。一方、HashSet は O(1)。ということで、通常は HashSet を使った方がいいようだ。ただし、

• コレクション内の要素をソート状態にしておきたい
• 特定の範囲のサブセットを取り出したい
• 最小、最大の要素を取り出したい

などの要求がある場合は SortedSet を使うとよいとのこと。

 

コードサンプル

// これで set1 の中身は 1, 2, 4, 5, 6, 8 になります。
// 2 を２回追加していますが、２度目の追加は無視されます。
var set1 = new SortedSet<int>() { 2, 5, 6, 2, 1, 4, 8 };
 
// プロパティで最小、最大要素を取り出せます。
var min = set1.Min;
var max = set1.Max;
 
// サブセットの取り出しも可能です。subset1 の中身は 2, 4, 5, 6 です。
var subset1 = set1.GetViewBetween(2, 6);

 

補足

GetViewBetween メソッドで得られるサブセットは面白い性質を持っている。オリジナルの「ビュー」なので、サブセットを変更するとオリジナルにも変更が反映されるのだ。また、境界外のデータを追加しようとすると例外が発生する (上のサンプルの場合は 2 から 6 の範囲でサブセットを取得しているので、例えば 9 を追加すると例外が発生する)。