SortedSet 集合类在 .NET 4.0 中

目录

• 引言
• SortedSet<T> 集合的默认行为
• 获取 SortedSet<T> 集合的子集
• 从 SortedSet<T> 集合中移除元素
• SortedSet<T> 集合的最大值和最小值
• 并集 (U)、交集 (∩) 和差集 (-) 操作
• 合并两个 SortedSet<T> 集合
• SortedSet<T> 集合的 CopyTo 方法
• 总结
• 历史

引言

.NET 4.0 在 System.Collections.Generic 中提供了一个新的集合类型，名为 SortedSet<T>。SortedSet<T> 是一个包含唯一元素的集合，并且会自动将元素保持排序状态。它通过一个自平衡红黑树实现，在插入、删除和查找操作上具有O(log n) 的性能复杂度。它用于保持元素有序、获取特定范围内的元素子集，或获取集合中的最小值或最大值元素。

SortedSet<T> 集合的默认行为

让我们创建一个 SortedSet<T> 集合实例，并用整数初始化它，不进行任何特定排序，最后使用 foreach 循环打印。另外请注意，我们添加了两次“1”和三次“2”。

var elements = new SortedSet<int>() { 5, 9, 2, 11, 2, 1, 4, 1, 2 };

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element));

输出 1 2 4 5 9 11

正如我们所见，所有元素都按排序顺序排列，并且没有重复的元素。即使我们在运行时添加一个元素，SortedSet<T>集合也会再次维护集合的排序顺序。你可以通过以下代码片段看到这一点：

bool result = elements.Add(17);

foreach (int element in elements)  
           Console.Write(string.Format(" {0}", element)); 

输出 1 2 4 5 9 11 17

基本上，Add 方法的返回类型是 bool，可以用来判断元素是否成功添加（true）或未成功添加（false）。如果返回 false，则表示该集合已包含该元素。

获取 SortedSet<T> 集合的子集

您还可以获取给定 SortedSet<T> 中特定范围的子集。

var subSet = elements.GetViewBetween(2, 9);

foreach (int element in subSet)  
           Console.Write(string.Format(" {0}", element));

输出 2 4 5 9

请注意，GetViewBetween 方法返回的是原始集合的视图，也就是说，对视图所做的任何更改都会反映在原始集合中。例如，如果我们向 subSet 添加 7，那么它实际上是添加到了原始集合元素中。

var subSet = elements.GetViewBetween(2, 9);

bool result = subSet.Add(7);

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element)); 

输出 1 2 4 5 7 9 11

但是，您不能向视图中添加超出指定范围的项，即，如果我们尝试向 subSet（其指定范围为 2 到 9）添加超出范围的 21，我们将收到 ArgumentOutOfRangeException 异常。

var subSet = elements.GetViewBetween(2, 9);

bool result = subSet.Add(21);

foreach (int element in elements)  
   Console.Write(string.Format(" {0}", element)); 

从 SortedSet<T> 集合中移除元素

您可以从给定的 SortedSet<T> 中移除任何特定元素。

 elements.Remove(1);

 foreach (int element in elements)
    Console.Write(string.Format(" {0}", element)); 

输出 2 4 5 9 11

Remove 方法在成功移除时返回 true，否则返回 false。

您还可以使用 RemoveWhere 方法从给定的 SortedSet<T> 中移除多个匹配谓词的元素。

elements.RemoveWhere(P => P % 2 == 0);

 foreach (int element in elements)
    Console.Write(string.Format(" {0}", element));

输出 1 5 9 11

谓词（P => P % 2 == 0）会从给定的整数 SortedSet<T> 中移除偶数元素。

RemoveWhere 方法返回从给定 SortedSet<T> 中删除的总元素数。

int totalRemoved = elements.RemoveWhere(P => P % 2 == 0);

Console.Write(string.Format("Total Elements Removed: {0}", totalRemoved)); 

已移除的总元素数 2

SortedSet<T> 集合的最大值和最小值

我们还可以按如下方式获取 SortedSet<T> 的最大值和最小值：

Console.Write(string.Format("Max: {0}, Min: {1}", elements.Max, elements.Min)); 

输出： Max: 11, Min: 1

并集 (U)、交集 (∩) 和差集 (-) 操作

您可以轻松地对给定的 SortedSet<T> 集合应用 并集(U)、交集(∩) 和 差集(-) 集合操作。让我们考虑两个集合 A 和 B：

var A = new SortedSet<int>() { 1, 2, 3, 4, 5, 11, };
var B = new SortedSet<int>() { 6, 7, 8, 9, 10, 11 };

您可以通过 Union 方法获取 A 和 B 的并集，如下所示：

var union = A.Union(B);

foreach (int element in union)
   Console.Write(string.Format(" {0}", element));

输出 (A U B) 1 2 3 4 5 11 6 7 8 9 10

您可以通过 Intersect 方法获取 A 和 B 的交集，如下所示：

var intersection = A.Intersect(B);

foreach (int element in intersection)
   Console.Write(string.Format(" {0}", element));

输出 (A ∩ B) 11

您可以通过 Except 方法获取 A 和 B 的差集，如下所示：

var difference = A.Except(B);

foreach (int element in difference)
   Console.Write(string.Format(" {0}", element));

输出 (A - B) 1 2 3 4 5

合并两个 SortedSet<T> 集合

您可以通过 Zip 方法，使用指定的谓词函数来合并两个 SortedSet<T> 集合。

var merged = A.Zip(B, (P, Q) => P + Q);

foreach (int element in merged)
   Console.Write(string.Format(" {0}", element));

输出 7 9 11 13 15 22

SortedSet<T> 集合的 CopyTo 方法

这是一个非常有用的方法。它有三个构造函数：CopyTo(T())、CopyTo(T(), Int32) 和 CopyTo(T(), Int32, Int32)。

CopyTo(T())：它将完整的 SortedSet<T> 复制到一个兼容的一维数组中，从目标数组的开头开始。

var target = new SortedSet<int>() {13, 2, 4, 10, 1, 7 };

int[] array = new int[10];

target.CopyTo(array);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

输出
索引：0，值：1
索引：1，值：2
索引：2，值：4
索引：3，值：7
索引：4，值：10
索引：5，值：13
索引：6，值：0
索引：7，值：0
索引：8，值：0
索引：9，值：0

CopyTo(T(), Int32): 它将完整的 SortedSet<T> 复制到一个兼容的一维数组中，从指定的数组索引开始。

target.CopyTo(array, 3);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

输出
索引：0，值：0
索引：1，值：0
索引：2，值：0
索引：3，值：1
索引：4，值：2
索引：5，值：4
索引：6，值：7
索引：7，值：10
索引：8，值：13
索引：9，值：0

CopyTo(T(), Int32, Int32)：它将 SortedSet<T> 中指定数量的元素复制到一个兼容的一维数组中，从指定的数组索引开始。

target.CopyTo(array, 3, 4);

for (int n = 0; n < array.Length; ++n)
   Console.Write(string.Format("Index: {0}, Value: {1}<br />", n, array[n]));

输出
索引：0，值：0
索引：1，值：0
索引：2，值：0
索引：3，值：1
索引：4，值：2
索引：5，值：4
索引：6，值：7
索引：7，值：0
索引：8，值：0
索引：9，值：0

如果兼容的一维数组没有足够的空间来容纳 SortedSet<T> 集合的元素，您将遇到 ArgumentException 异常。

总结

因此，我们已经看到，它是 .NET 4.0 基础类库 (BCL) 中一个非常有用的补充。

历史

• 2010 年 6 月 23 日 -- 文章更新（修改了目录，并添加了有关 CopyTo 方法的信息）
• 2010 年 6 月 22 日 -- 文章更新（修改了目录，添加了有关并集、交集和差集操作以及合并两个集合的信息）
• 2010 年 6 月 16 日 -- 文章更新（修改了目录，格式化了文章，并添加了有关移除元素的信息）
• 2010 年 6 月 10 日 -- 文章更新（添加了目录）
• 2010 年 6 月 10 日 -- 发布了原始版本