为 .NET 添加“集合”支持

• 下载源代码文件 - 19 Kb
• 下载演示项目 - 24.7 Kb
• 下载文档 - 289 Kb

引言

.NET Framework 中的 System.Collections 命名空间提供了许多在内存中操作数据时非常有用的集合类型。然而，System.Collections 中却有一个明显的缺失类型：Set。

Set 是一种不包含重复元素的集合。它松散地模仿了数学中的“集合”概念。此实现基于 Java 的 Set 接口定义，因此如果您也是 Java 程序员，这可能会让您感到熟悉。主要区别在于，此库不使用接口，并且提供了一些 Java 库未包含的“标准”Set 运算符。

当 Array 或 List 不完全符合要求时，Set 就派上用场了。 .NET 中的数组具有固定长度，添加和删除元素很麻烦。列表可以轻松添加新对象，但您可能拥有大量重复元素，这对于某些类型的问题是不希望的。对于大型数据集，在 Arrays 或 Lists 中搜索元素效率低下，需要线性搜索。您可以保持数组排序并使用二分搜索，但这通常是费力不讨好（尤其是因为此库和 .NET Framework 已经为您提供了更好的、已编写好的方法）。

使用集合，添加元素、删除元素和检查元素是否存在都快速而简单。您可以使用支持的数学集合运算符混合搭配不同集合中的元素：union（并集）、intersection（交集）、exclusive-or（异或）和 minus（差集）。有关更多信息，请参阅下面的示例。

您将在此库的不同 Set 实现中看到一些有趣的副作用，具体取决于底层的搜索算法。例如，如果您选择基于排序的 Set，当您使用 foreach 进行迭代时，元素将按排序顺序输出。如果您使用基于哈希的 Set，元素将按任意顺序输出，但在处理大型数据集时，包含检查将最快。如果您使用基于列表的 Set，当您迭代时，元素将按放入顺序输出。此外，列表类集合对于非常小的数据集（最多约 10 个元素）最快，但随着包含的元素数量的增加，其速度会迅速下降。为了兼顾两者，该库提供了一种 Set 类型，它对小型数据集使用列表，并在数据集大到足以支持时切换到基于哈希的算法。

使用代码

Iesi.Collections 库具有以下对象层次结构

• Set - 所有其他集合的抽象基类。
  • DictionarySet - 一个抽象类，允许您基于 IDictionary 的任意实现创建新的 Set 类。
    • HashedSet - 基于 HashTable。
    • SortedSet - 基于 SortedList。
    • ListSet - 基于 ListDictionary。
    • HybridSet - 基于 HybridDictionary。
  • ImmutableSet - 其他 Set 的包装器，使其变为只读。
  • SynchronizedSet - 其他 Set 的包装器，使其（大部分）线程安全。

您可能会发现 HashedSet 和 HybridSet 是最有用的实现。它们可以包含任何不可变、可以使用 Equals() 进行比较且具有有效 GetHashCode() 实现的对象。所有常规值类型和许多对象已经满足这些要求，因此对于大多数数据类型，HashedSet 和 HybridSet 都能正常工作。使用它们的唯一缺点是您无法预测迭代顺序。

如果您对 Set 的迭代顺序感兴趣，SortedSet 会很有用，但它会带来一些不同的要求，而且通常更难满足。除了不可变性之外，SortedSet 中的元素还必须实现 IComparable。此外，它们必须实际可比较而不会引发异常。因此，您无法将 string 值和 int 值放入同一个 Set 实例中。

ListSet 对非常小的数据集很有用。当 ListSet 包含的元素少于 10 个时，它的速度实际上会比任何其他实现都要快。然而，一旦超过 10 个元素，许多集合操作的运行时间就会随着数据大小的平方而增加。因此，包含 1,000 个元素的 ListSet 上的操作大约会比包含 10 个项目的 ListSet 上的操作慢 10,000 倍。

ImmutableSet 和 SynchronizedSet 是专门的包装器。它们包含其他集合，这些集合会执行所有实际工作。ImmutableSet 包装内部的 Set 以使其变为只读。SynchronizedSet 包装内部 Set 的所有函数以对其进行同步。这允许 Set 被多个线程使用。有关这方面的信息，请参阅文档，因为在使用多线程集合时存在特殊注意事项。

如果您有兴趣创建自己的 Set 类型，此库支持该功能。如果您想从头开始，可以扩展 Set 并实现所有抽象函数。如果您想基于现有的 IDictionary 实现创建新的 Set 类型，请扩展 DictionarySet。如果您只想为现有的、正常工作的 Set 实现添加一些新功能，请选择 HashedSet、HybridSet、ListSet 或 SortedSet 进行扩展。

下面的示例演示了如何创建新集合并使用集合运算符对其进行操作。当前支持的集合运算符在下表中简要描述

集合运算符

名称	符号	描述
Union()	|	A | B 返回一个包含来自两个输入集合的所有元素的 Set。
Intersect()	&	A & B 返回一个包含 A 和 B 中所有元素的 Set。
ExclusiveOr()	^	A ^ B 返回一个包含 A 或 B 中存在但并非两者都存在的元素的 Set。
Minus()	-	A - B 返回一个包含 A 的所有元素，并从中移除 B 的元素的 Set。
Equals()		您可以使用 Equals() 来比较两个 Set 实例是否相等。也就是说，如果 A 和 B 包含完全相同的元素，则 A.Equals(B) 为 true。'==' 和 '!=' 运算符并非设计为被重载。

该示例使用 Set 实例来表示美国西南部各州。每个 Set 保存该州主要河流的名称。然后，它使用基本的州-河流信息来推导出关于这些河流的各种有趣事实。

using System;
using Iesi.Collections;
namespace RiverDemo
{    
class Rivers
{
   [STAThread]
   static void Main(string[] args)
   {
     //Use Arrays (which are ICollection objects) to quickly initialize.
     Set arizona   
        = new SortedSet(new string[] {"Colorado River"});
     Set california
        = new SortedSet(new string[] {"Colorado River", "Sacramento River"});
     Set colorado
          = new SortedSet(new string[] {"Arkansas River", 
                      "Colorado River", "Green River", "Rio Grande"});
     Set kansas
            = new SortedSet(new string[] {"Arkansas River", "Missouri River"});
     Set nevada
            = new SortedSet(new string[] {"Colorado River"});
     Set newMexico
         = new SortedSet(new string[] {"Rio Grande"});
     Set utah
              = new SortedSet(new string[] {"Colorado River", "Green River", 
                              "San Juan River"});
     //Rivers by region.
     Set southWest = colorado | newMexico | arizona | utah;
     Set midWest = kansas;
     Set west = california | nevada;
     //All rivers (at least for the demo).
    Set all = southWest | midWest | west;
    Print("All rivers:", all);
    Print("Rivers in the southwest:", southWest);
    Print("Rivers in the west:", west);
    Print("Rivers in the midwest:", midWest);
    Console.WriteLine();

    //Use the '-' operator to subtract the rivers in Colorado from 
    //the set of all rivers.
    Print("Of all rivers, these don't pass through Colorado:",all - colorado);

   //Use the '&' operator to find rivers that are in Colorado AND in Utah.
   //A river must be present in both states, not just one.
   Print("Rivers common to both Colorado and Utah:", colorado & utah);

   //use the '^' operator to find rivers that are in Colorado OR Utah,
   //but not in both.
   Print("Rivers in Colorado and Utah that are not shared by both states:",
          colorado ^ utah);

   //Use the '&' operator to discover which rivers are present in Arizona, 
   // California,Colorado, Nevada, and Utah.  The river must be present in 
   // all states to be counted.
   Print("Rivers common to Arizona, California, Colorado, Nevada, and Utah:", 
         arizona & california & colorado & nevada & utah);
   //Just to prove to you that operators always return like types, let's do a
   //complex Set operation and look at the type of the result:
   Console.WriteLine("The type of this complex operation is: " + 
   ((southWest ^ colorado & california) | kansas).GetType().FullName);
}
    private static void Print(string title, Set elements)
    {
       Console.WriteLine(title);
       foreach(object o in elements)
       {
           Console.WriteLine("\t" + o);
           Console.WriteLine();
       }    
    }
}

尽管库中还有其他类型的集合可用，但示例始终使用 SortedSet。这对于示例来说很好，因为所有内容都会按字母顺序整齐地打印出来。但您可能想知道，当您对两个 Set 实例进行“union”（并集）、“intersect”（交集）、“exclusive-or”（异或）或“minus”（差集）运算时，会返回哪种类型的 Set。该库始终返回与左侧 Set 相同类型的 Set，除非左侧操作数为 null，在这种情况下，它将返回右侧 Set 的类型。

这意味着，由于我们使用的是 SortedSet 实例，当我们在二进制运算符组合集合时，我们总是会得到 SortedSet 实例。因此，我们示例中的输出将始终按字母顺序排序，正如您所期望的那样。

以下是运行示例的输出

All rivers:
	Arkansas River
	Colorado River
	Green River
	Missouri River
	Rio Grande
	Sacramento River
	San Juan River

Rivers in the southwest:
	Arkansas River
	Colorado River
	Green River
	Rio Grande
	San Juan River

Rivers in the west:
	Colorado River
	Sacramento River

Rivers in the midwest:
	Arkansas River
	Missouri River

Of all rivers, these don't pass through Colorado:
	Missouri River
	Sacramento River
	San Juan River

Rivers common to both Colorado and Utah:
	Colorado River
	Green River

Rivers in Colorado and Utah that are not shared by both states:
	Arkansas River
	Rio Grande
	San Juan River

Rivers common to Arizona, California, Colorado, Nevada, and Utah:
	Colorado River

The type of this complex operation is: 
	Iesi.Collections.SortedSet
Press any key to continue

文档中还包含了一个额外的示例和更多技术信息。源代码也非常易于理解。所有搜索和排序的繁重工作都由 .NET Framework 中已有的类执行，因此没有任何代码特别困难或棘手。如果您有文档未涵盖的问题，通过阅读代码应该只需要 5 到 10 分钟即可找到答案。

尽情享用！