为 .NET 设计的通用 Set 类型
4.79/5 (13投票s)
2004年10月31日
7分钟阅读
111176
566
提供一个通用的集合 Set。
引言
新的 System.Collections.Generic 命名空间包含最常用数据结构的泛型版本，例如列表和字典。但不幸的是，它不包含通用的 Set 类型。本文附带的项目提供了一个通用的 Set 类型来填补这一空白。
为什么需要另一个 Set 类型？
是的，我知道你在想什么。为什么需要另一个 Set 类型？此网站上已经发布了几个 Set 集合，例如 这个 和 那个。嗯，首先，这是一个通用的 Set 实现，所以它会更方便使用，而且比前面提到的非通用 Set 类型快得多。实现一个通用的集合类也是了解 .NET generics 工作原理的好方法。
接口
由于此 Set 类型旨在填补 System.Collections.Generic 命名空间中的一个空白，因此它的编码风格与之相似，以便轻松集成。它还努力提供与其他集合类型的良好互操作性。
我试图提供与 System.Collections.Generic 命名空间中其他集合的名称和功能相似的方法。例如，我实现了非常有用的 ConvertAll、TrueForAll、FindAll 和 ForEach 方法，与 List<T> 类中的完全相同。当然，我还实现了通用和非通用版本的 IEnumerable 和 ICollection。所以，希望在使用 Set<T> 类时不会有意外。
实现
Set 类的要求非常简单：Add、Remove 和 Contains 方法应该尽可能快。幸运的是，System.Collections.Generic 命名空间已经包含了一个具有这些特性的集合，即 Dictionary<K,V> 类型。Dictionary<K,V> 类型是 System.Collections.HashTable 类的强类型版本。
Dictionary<K,V> 中的键是唯一的。并且只要存储类型 K 提供了良好的 GetHashCode() 实现，在 Dictionary<K,V> 中添加、删除或查找键就会很快。因此，为了避免代码重复，使用 Dictionary<K,V> 在内部存储 Set 元素是有意义的。
继承或组合
由于 Dictionary<K,V> 不是密封的，理论上可以让 Set<T> 继承自 Dictionary<T,V>。这实际上将是实现由 HashTable 支持的 Set 的最有效方法，但我因为几个原因决定不这样做：首先，Dictionary<K,V> 包含许多与 Set 无关的方法和属性，它们会不必要地弄乱 Set<T> 类并使您感到困惑。其次，Set<T> 类使用 Dictionary<K,V> 实现这一事实是一个实现细节，对于类的用户来说应该是不可见的。如果我决定自己编写 Set<T> 实现而不是将所有工作委托给 Dictionary<K,V>，我可以在不破坏 API 兼容性的情况下这样做。
因此，我决定使用一个私有字段来存储 Dictionary<K,V> 而不是继承自 Dictionary<K,V>，即使这意味着创建了一个额外的对象。
效率？
正如我们所见，HashTable 的键可以用来模拟 Set。但值呢？我们不需要它们，所以我们可以为它们使用任意值。这是非通用 .NET 编程中常用的方法。
这个小的代码片段演示了如何使用非通用的 HashTable 来使 int[] 中的值唯一。由于我们存储在 HashTable 中的值是任意的，并且我们希望避免不必要的装箱，所以我们使用 null，即使它看起来有点奇怪。
int[] values=new int[] {1,1,2,2,3,3,3,4,6,6,7,8,9,9,9,9,9,9};
Hashtable temp=new Hashtable();
foreach(int i in values)
temp[i]=null;
int[] uniquevalues=new int[temp.Count];
temp.Keys.CopyTo(uniquevalues,0);
上面的代码可以工作并且效率相当高，但有几个地方效率不是最优的。由于非通用的 HashTable 类在内部使用对象引用作为键和值，因此每次我们将一个 int 添加到 HashTable 时，它都会被装箱并放在堆上。而且，即使我们不关心存储的值的引用，我们仍然需要存储它的空间。
Generics 显神通
当使用值类型作为类型参数实例化泛型类型时，CLR 会为该特化生成特殊的 IL 代码。因此，泛型类型与值类型的结合可以完全消除装箱开销。考虑到这一点，我们可以使用泛型版本的 HashTable 来重写上面的代码。
int[] values=new int[] {1,1,2,2,3,3,3,4,6,6,7,8,9,9,9,9,9,9};
Dictionary<int,object> temp=new Dictionary<int,object>();
foreach(int i in values)
temp[i]=null;
int[] uniquevalues=new int[temp.Count];
temp.Keys.CopyTo(uniquevalues,0);
这段代码比非通用版本快得多，因为向临时字典添加新键不再有任何装箱开销。但仍然存在我们永远不需要的值的引用这种不必要的负担。
零大小结构体？
我曾认为可以通过使用零大小的 struct 来消除这个开销，但事实证明，当前的 .NET 运行时即使对于零大小的 struct 也会保留一些内存。
这在未来有望改变，因为有相当多的 巧妙技巧 可以利用零大小的 struct。
这是我尝试过的方法：由于我们不关心值，我们可以给它任何我们想要的类型。显然，我们想要最小的类型。最小的原生类型是 byte，它只有 1 字节（废话），但通常会根据打包大小占用 4 到 8 字节。但通过定义自己的零大小的虚拟类型，我们可以做得更好。
struct Dummy {};
Dummy dummy=new Dummy();
int[] values=new int[] {1,1,2,2,3,3,3,4,6,6,7,8,9,9,9,9,9,9};
Dictionary<int,Dummy> temp=new Dictionary<int,Dummy>();
foreach(int i in values)
temp[i]=dummy;
int[] uniquevalues=new int[temp.Count];
temp.Keys.CopyTo(uniquevalues,0);
可惜它没有按预期工作。
替代实现
使用 Dictionary<T,X> 存储 Set<T> 数据是相当有效的。但由于未使用的字典值，它有一些内存开销。我目前正在开发一个由按哈希码排序的 List<T> 支持的 Set<T>。这在许多情况下会更快、更节省空间。当我对代码满意后，我将把它发布到下面提到的网站。它将具有与此实现完全相同的公共方法，因此您可以使用它作为即插即用替换。
Set 操作
除了常规的集合操作外，Set<T> 类型还支持各种 Set 特定的操作。这是一个概述。
| 方法 | 运算符 | 描述 |
a.Union(b) |
a|b | a 或 b 中的所有元素 |
a.Difference(b) |
a-b | a 中不存在于 b 的所有元素 |
a.SymmetricDifference(b) |
a^b |
(a^b)=(a-b)|(b-a) |
a.Intersection(b) |
a&b | a 和 b 中都存在的元素 |
a.Equals(b) |
a==b | a 和 b 包含完全相同的元素 |
| - | a<b | b 包含 a 中的所有元素以及一些附加元素 |
| - |
a<=b |
b 包含 a 中的所有元素，可能还有一些附加元素 |
运算符方法和非运算符方法之间存在细微差别。运算符方法都要求参数为 Set，而非运算符方法通常使用 IEnumerable<T> 作为参数。我这样做是为了在调用运算符时避免意外转换为 Set<T>。
结论
我认为新的 System.Collections.Generic 命名空间用起来非常方便。对于值类型，它速度更快，因为它消除了装箱开销。许多有用的方法，如前面提到的 ConvertAll、TrueForAll、FindAll 和 ForEach，可以消除大多数循环。唯一缺少的是 Set 类型。但现在不再是了。
如果您可以使用 .NET 2.0 的功能，那么无论您是否需要类型安全，都应该使用 System.Collections.Generic 命名空间。例如，您应该使用 List<object> 而不是 ArrayList。
关于代码
随附的项目包含所描述的 Set<T> 类型，以及一个小型演示程序，该程序对 Set 执行一些性能和正确性测试。代码是在 BSD 许可证下发布的，因此您可以随意将其用于您自己的项目。