通用集合数据结构

• 下载源代码文件 - 21.5 Kb
• 下载演示项目 - 5.32 Kb

引言

最近，我的一位同事（一位刚从 Java 转到 .NET 的新手）挑战我，让我给他推荐一个等同于 java.util.Set 类的东西。

考虑到框架中数据结构的广度，我失望地发现 .NET 框架 1.1 版本中没有对集合的原生支持。我也意识到可以很快地编写一个。CodeProject 上已经有几个集合项目，但它们更侧重于特定的场景，如内存使用效率或特定类型的存储，并没有像我下面那样探索集合操作，或者它们更庞大且难以理解。

本项目面向初学者，旨在解释基本集合迭代和运算符重载的实现。

游戏、集合、比赛

什么是集合，为什么你需要它？Java 文档中 java.util.Set 将集合定义为不包含重复元素的集合。集合类似于框架中的 enum（枚举），不同之处在于 enum 是在编译时定义的（静态）构造（忽略 Reflection.Emit 命名空间的高级技巧）。枚举是一个特定数据类型的已定义值列表。特定常量存在于枚举中（是集合的成员），或者不存在。集合与枚举不同之处在于，枚举成员具有名称和值。集合只有值。

集合通常这样表示：{1, 2, 5, 8, 9}。它们经常是数值的，但其他“事物”的集合也并不难想象，而且同样有用。你可以有一个包含三位喜剧演员的集合 {Larry, Moe, Curly}，或者一个包含行星的集合 {Mercury, Venus, Earth, Mars, Jupiter, Saturn, Uranus, Neptune, Pluto}，或者任何其他东西。它们是用于分组和表示逻辑上相似事物的机制。

如果你想以比队列、堆栈、字典或集合更合理的方式存储数据，你就会想要一个集合。这是一个递归定义，但有些数据作为集合更有意义。

基本集合操作

除了能够迭代成员的基本集合要求外，你必须能够向集合添加新成员（并强制执行唯一性约束），你应该能够清除集合中的值，并且我将允许客户端类通过索引器访问集合的成员。集合还支持一些基本的逻辑函数以及相等性测试。

如果你还记得小学数学，你可能用维恩图学习过集合。考虑以下两个集合：集合“A” {1, 2, 3, 4, 5} 和集合“B” {3, 5, 7, 8, 9}。它们可以这样画出来

你可以看到 A 中有独有的成员，B 中有独有的成员，还有它们共同拥有的成员。两个集合共有的成员称为两个集合的“交集”，两个集合的所有成员合在一起称为两个集合的“并集”。

交集、并集和相等性是这个类将要实现的运算。

代码

Set 类的基本内部存储单元是 ArrayList。ArrayList 在大小和容纳不同数据类型成员的能力方面都具有令人满意的动态性。

Set 类实现了 IEnumerable，因此可以迭代集合的内容，并且实现了 IDisposable，因为我希望我所有的类在关闭时都能以一致的方式运行。

public class Set : System.Collections.IEnumerable, System.IDisposable

实现 IEnumerable 非常简单，只需要一个方法

public IEnumerator GetEnumerator() {
   return new SetEnumerator(this);
}

SetEnumerator 对象是定义在 Set.cs 文件底部的一个 private（私有）类

private class SetEnumerator : System.Collections.IEnumerator { 
   private Set _set = null;
   private Int32 _position = -1;

   public SetEnumerator(Set set) {
      _set = set;
   } 

   public void Reset() { 
      _position = -1; 
   }

   public object Current { 
      get {return _set[_position];} 
   } 

   public bool MoveNext() { 
      if (_position < _set.Length - 1) {
         _position++; 
         return true; 
      } else 
         return false; 
   } 
}

枚举器的 Current 属性利用了我通过索引器（直接连接到底层的 ArrayList）暴露了集合的成员这一事实。如果我们不这样做，我们就必须提供其他机制来实现相同的功能，以便对象可枚举。

现在我们已经满足了在 foreach(){} 结构中迭代成员的要求，我们必须编写一些其他方法来获取数据并对其进行操作。

公共方法

我编写了两个构造函数。第一个是无参数的简单构造函数。第二个接受一个 Set 对象数组，并基于所有数组元素的并集创建一个新的集合。我最初有一个接受单个 Set 对象作为参数并复制它的构造函数，但后来意识到 Set[] 构造函数可以轻松处理这种情况，所以我将其从库中删除了。

Add() 方法实现如下

public void Add(object member) {
   for(Int32 i = 0; i < _members.Count; i++)
      if (_members[i].Equals(member))
         if (_behaviour == BadBehaviourResponses.BeAggressive)
            throw new ArgumentException(...);
         else
            return;

   _members.Add(member);
}

前六行搜索现有成员以查找要添加的成员。如果它已存在于集合中，则方法在将新成员添加到 ArrayList 之前返回。

BadBehaviourResponses.BeAggressive 枚举是一个工具，允许方法根据它是被内部方法还是外部客户端调用而以不同的方式工作。如果外部客户端调用 Add() 并且发现要添加的成员已在集合中，我希望抛出一个 ArgumentException（与字典添加重复键时抛出的异常相同），以强制客户端处理重复数据。但是，如果内部方法调用 Add()，我希望能够跳过异常抛出。捕获异常在计算上非常昂贵，尤其是当你确切知道你只是要忽略错误时。

尽管只有两种状态 BeAggressive（激进）和 BeCool（冷静），但我将其实现为枚举。我尝试用布尔值实现相同的功能，但代码的可读性确实受到了影响。

大多数其他方法都相当不言自明，并且易于编写。Clear()、IsEmpty()、Contains() 和 Remove() 都相当简单。我添加了 ToArray()，因为我可以轻松地从底层 ArrayList 获取它，而且我还实现了显式转换运算符来从数组创建 Set 对象（稍后讨论），ToArray() 是该转换的补充。Length 属性和索引器都与底层 ArrayList 的相应属性相关联。

重写了 ToString() 方法，以在大括号 {} 包围并用逗号分隔的内容显示集合的内容，这对调试很有帮助。

重载运算符

Set 对象允许的逻辑运算符更有趣。由于“交集”在概念上与按位“与”相当，所以我这样重载了 & 运算符

public static Set operator & (Set s1, Set s2) {
   Set result = new Set();
   result.DuplicateDataResponse = BadBehaviourResponses.BeCool;
   if (s1.Length > s2.Length) {
      foreach (object o in s1)
         if (s2.Contains(o))
            result.Add(o);
   } else {
      foreach(object o in s2)
         if (s1.Contains(o))
            result.Add(o);
   }
   result.DuplicateDataResponse = BadBehaviourResponses.BeAggressive;
   return result;
}

重载 & 运算符允许客户端代码如下所示

Set s3 = s2 & s1; // s3 is the intersection of s1 and s2

算法上，该方法确定哪个集合更大，然后迭代较大集合的成员。如果较大集合中的任何成员也存在于较小集合中，则将它们添加到新创建的 Set 对象中。在方法结束时，结果对象中的任何成员都是两个输入 Set 对象共有的成员。

设置私有属性以控制重复数据添加行为，确保我们在这些循环中不必捕获异常，并在返回新对象之前将行为设置回 BeAggressive，这意味着该对象的消费者仍然必须为后续异常捕获异常。

与交集情况类似，“并集”类似于“或”，我重载了按位或运算符 | 如下

public static Set operator | (Set s1, Set s2) {
   return new Set(new Set[2] {s1, s2});
}

它直接使用了我之前讨论过的构造函数，该构造函数接受现有 Set 对象数组，并返回一个新的集合，其中包含输入的 Set 对象并集在一起

public Set(Set[] sources) {
   _behaviour = BadBehaviourResponses.BeCool;

   foreach(Set initialSet in sources)
      foreach(object o in initialSet)
         this.Add(o);

   _behaviour = BadBehaviourResponses.BeAggressive;
}

我再次记得在创建 Set 实例后，将错误引发行为恢复到默认操作 BeAggressive。无论 Set 实例是如何创建的，无论是通过客户端显式实例化还是通过重载运算符隐式创建，我都希望它在完全创建后抛出异常。

实现相等运算符（==）的重载是所有重载运算符中最简单的。

public static bool operator == (Set s1, Set s2) {
   if (s1.Length != s2.Length)
      return false;

   foreach(object o in s1)
      if (!s2.Contains(o))
         return false;

   return true;
}

如果两个被比较的集合长度不相等，该方法会快速返回。如果长度相等，循环会查找集合成员之间的不匹配。如果找到一个不匹配，则返回 false。如果没有找到不匹配项，则返回 true。由于我们不关心集合是否已排序，因此被比较的集合成员不必处于相同的位置；如果一个集合的所有成员也是第二个集合的成员，则它们相等。

要重载的最后一个运算符是从数组显式转换，因此客户端代码可以如下所示

Int32[]  intArray1 = new Int32[] {1, 4, 5, 7, 8, 9};
Set s5 = (Set)intArray1;

重载 Set 转换运算符的代码也相当直接

public static explicit operator Set(Array array) {
   Set s = new Set();

   foreach(Object o in array) {
      try {
         s.Add(o);
      } catch (ArgumentException e) {
         throw new InvalidCastException(…, e);
      }
   }

   return s;
}

更短的方法是跳过 try/catch 块，只依赖于 s.Add(o) 生成的任何重复异常冒泡回客户端，但这会导致 ArgumentException 而不是 InvalidCastException，在这种情况下的准确性更高。

结论

该类可以存储任何数据类型，包括 Int32 和 System.String 等内在类型，异常和数据库连接等复杂类型，或任何其他用户定义类型。它可以存储和操作任何可以通过评估其 Equals() 方法来区分的类型的实例。

你拥有的数据结构永远不会嫌多。对于那些需要集合而不是哈希表、队列、堆栈或其他集合的情况，你可以使用并扩展此代码来获得所需的灵活性。我包含了一个示例项目来练习该库，以及 NDoc 创建的 MathLib.chm 文件，用于文档目的。

修订历史

• 2005 年 6 月 26 日 – 初始修订。