孜孜不倦的程序员

  • 项目

.NET 集合： C5 入门

Ted Neward

 

Ted Neward我有事要坦白。

我在白天是 Neudesic LLC 这家咨询公司的一个温良恭谨的 .NET 开发人员。但到了晚上，妻儿熟睡之后，我就会拿起笔记本电脑悄悄溜出房门，来到我秘密的藏身之处：第 148 街上的 Denny's，然后开始编写 Java 代码。

是的，朋友们，我过着双重生活，一边是 .NET 开发人员，一边是 Java（或更准确地说，Java 虚拟机 (JVM)）开发人员。这样的双重生活有趣的意外好处之一，是我可以看到 Microsoft .NET Framework 中一些可以带回 JVM 中的很好的理念。其中一个理念就是自定义属性，JVM 在 Java5 中采用了它（大约在 2005 年），其名称为“注解”。但反过来也是如此： 实际上 JVM 做到了 CLR 和 .NET 基类库 (BCL) 并没有做到（您要是觉得被冒犯，那么我至少可以说，它做得不够好）的一些事情。这样的一个方面体现在 .NET BCL 的中心： 集合。

集合： 一个可批判之处

.NET 集合中的一部分缺陷是 BCL 团队不得不将毫无意义的东西编写两次： 在推出泛型功能之前为 .NET Framework 1.0/1.1 的发布编写一次，在泛型成为 CLR 的一部分之后又为 .NET Framework 2.0 编写了一次，因为没有强类型版本的集合就是毫无意义。这自然意味着，必然要废弃其中一次编写的集合，而保留对于库的任何增强或增加的功能。（Java 实质上是通过用泛型化的版本“替换”非泛型化的版本来逃避这个问题的，这种方法只是因为 Java 处理泛型的方式才能得以实现，但我在此处并不会深入谈论这个问题。） 并且，除去通过 Visual Studio 2008 和 C# 3.0 中的 LINQ 提供的增强功能之外，集合库在 2.0 版本之后从未真正得到过太多青睐，它本身或多或少仅仅是将 System.Collections 类在强类型版本的一个新的命名空间（System.Collections.Generic，简称 SCG）中重新实现而已。

更重要的是，.NET 集合的设计似乎更多地将重点放在将一些实用而有用的东西作为 1.0 版本的一部分切割开来，而不是试着去深入思考集合的设计以及它们可以如何扩展。这是 .NET Framework 真正与 Java 世界类似的一个方面（虽然我无意如此怀疑）。Java 1.0 随附一系列基本的实用集合。但是这些集合有几个设计上的缺陷（最富恶名的一个缺陷便是引入 Stack 类这一个设计决策，这是一种后进先出集合，它直接扩展 Vector 类，而后者基本上就是 ArrayList）。Java 1.1 发布后，Sun Microsystems 的几位工程师辛勤工作，重新编写了这些集合类，使之成为著名的 Java 集合，并在 Java 1.2 中推出。

总之，.NET Framework 已成为过去，其集合类应该进行改进，理想情况下，至少应该在很大程度上实现与现有 SCG 类兼容。幸运的是，丹麦哥本哈根信息技术大学的研究员已针对 SCG 类创建了富有价值的后续类和补充类： 他们称为“C# 哥本哈根全面集合类”（简称 C5）的一个库。

C5 支持信息

如果您想了解有关 C5 的版本历史或获取相关书籍 (PDF) 的链接（虽然这本书已经发行几个版本了），可在 Web 上的 itu.dk/research/c5 上找到 C5，开始进行了解。或者，C5 可通过 NuGet 使用 Install-Package 命令（目前是非常常用）获得，您只需要键入“Install-Package C5”即可。请注意，C5 是为 Visual Studio 和 Mono 编写的，当 NuGet 安装软件包时，它会添加对 C5.dll 程序集和 C5Mono.dll 程序集的引用。两者之间存在冗余，因此请删除您不需要的一个。为了通过一系列探索测试来探索 C5 集合，我创建了一个 Visual C# 测试项目并将 C5 添加到了该项目。除此之外，对于该代码唯一值得注意的更改是两条“using”语句，C5 文档中也有相同假设：

using SCG = System.Collections.Generic;
using C5;

使用别名的原因很简单： C5“重新实现”在 SCG 版本中具有相同名称的几个接口和类，因此对旧的东西使用别名能使其对我们可用，又只需要添加非常简短的前缀即可（例如 IList<T> 表示 C5 版本，而 SCG.IList<T> 则表示来自 SCG 的“经典”版本。）

顺便消除一下律师可能有的疑问：C5 使用 MIT 许可证，是开源代码，因此比起 GNU 通用公共许可证 (GPL) 或 GNU 较宽松通用公共许可证 (LGPL)，您具有更大余地修改或增强一些 C5 类。

C5 设计概述

我们看看 C5 设计方法，从集合分解为两个“层级”来看，它似乎与 SCG 风格类似： 一个是接口层，描述一个给定集合的接口和期望行为，一个是实现层，提供一个或多个接口所需的实际支持代码。 SCG 类很接近这个理念，但是在某些情况下，它们并不能非常好地遵循这一点，例如，我们在实现 SortedSet<T> 时完全没有灵活性可言（这意味着，基于数组、基于链表或基于哈希，这每一种选择的插入和遍历等操作的性能具有不同特征）。 在某些情况下，SCG 类就是缺少某些集合类型，比如说循环队列（队列中最后一项遍历完成时，迭代就再次“折回”到队列开头）或简单的“包”集合（只包含项，不提供任何功能，从而避免不必要的排序和索引等开销）。

诚然，对于普通 .NET 开发人员来说，这似乎并不算是太大的损失。 但在很多应用中，随着性能开始成为重中之重，选择正确的集合类来解决具体的问题就变得至关重要。 这个集合会创建一次就频繁遍历吗？ 还是会频繁添加或移除但很少遍历？ 如果此集合是某个应用功能（或者是应用本身）的中心，则这两种情况之间的区别可能导致完全不同的反应：“哇！此应用真是太棒了！”和“还好，用户喜欢它，但觉得速度未免太慢了。”

此外，C5 的一个核心准则是，开发人员应该“在编码时注重接口，而不是实现”，同时还要提供至少十多个描述底层集合必须提供的功能的不同接口。 ICollection<T> 是一切的基础，能保证基本集合行为，但是通过它，我们一开始能找到 IList<T>、IIndexed<T>、ISorted<T> 和 ISequenced<T>。 以下是完整的接口列表，它们与其他接口的关系以及它们整体保证具有的特性：

  • SCG.IEnumerable<T> 可以枚举其项。 所有集合和字典都是可枚举的。
  • IDirectedEnumerable<T> 是可枚举的，也可以反转，因此可以相反的顺序反向枚举其中的项。
  • ICollectionValue<T> 是集合值。 它不支持修改，可枚举，知道自身包含的项数，并且可将这些项复制到数组。
  • IDirectedCollectionValue<T> 是集合值，可反转为反向集合值。
  • IExtensible<T> 是可向其中添加项的集合。
  • IPriorityQueue<T> 是可扩展集合，其中最小和最大的项都可非常高效地找到（和移除）。
  • ICollection<T> 可以扩展，其中的项可以移除。
  • ISequenced<T> 是以特定顺序（由插入顺序或项排序确定）显示项的集合。
  • IIndexed<T> 是排序集合，其中的项可通过索引进行访问。
  • ISorted<T> 是排序集合，其中的项按升序出现；项顺序通过对各项进行比较来确定。 对于给定项，可以非常高效地找到其在集合中的前一项或后一项。
  • IIndexedSorted<T> 是编制了索引并经过排序的集合。 它可以非常高效地确定有多少项大于或等于给定项 x。
  • IPersistentSorted<T> 是排序集合，可以非常高效地为其制作快照，也就是将保持不变、不受对原始集合的更新影响的只读副本。
  • IQueue<T> 是先进先出 (FIFO) 队列，并且支持索引。
  • IStack<T> 是后进先出 (LIFO) 堆栈。
  • IList<T> 是创建了索引的集合，因此是有序集合，其中的项顺序由插入和删除操作确定。 它由 SCG.IList<T> 派生而来。

从实现上说，C5 有好几种形式，包括循环队列、数组支持列表和链表支持列表，此外还有哈希数组列表和哈希链表、包装数组、排序数组、基于树的集合和包等等。

C5 编码风格

好在 C5 不需要在编码风格上有重大转变，它还支持所有 LINQ 操作（因为它基于 SCG 接口构建，而 SCG 接口的 LINQ 扩展方法是断开的），因此在某些情况下，您可以在构造时对 C5 集合进行简单的访问，而不更改其周围的任何代码。 请参见图 1 了解相应示例。

图 1 C5 入门

// These are C5 IList and ArrayList, not SCG
IList<String> names = new ArrayList<String>();
names.AddAll(new String[] { "Hoover", "Roosevelt", "Truman",
  "Eisenhower", "Kennedy" });
// Print list:
Assert.AreEqual("[ 0:Hoover, 1:Roosevelt, 2:Truman, 3:Eisenhower," +
  " 4:Kennedy ]", names.ToString());
// Print item 1 ("Roosevelt") in the list
Assert.AreEqual("Roosevelt", names[1]);
Console.WriteLine(names[1]);
// Create a list view comprising post-WW2 presidents
IList<String> postWWII = names.View(2, 3);
// Print item 2 ("Kennedy") in the view
Assert.AreEqual("Kennedy", postWWII[2]);
// Enumerate and print the list view in reverse chronological order
Assert.AreEqual("{ Kennedy, Eisenhower, Truman }",
  postWWII.Backwards().ToString());

即使您没有阅读过 C5 文档，也很容易看明白这些示例中执行了哪些操作。

C5 对 SCG 集合实现

以上只不过是 C5 的冰山一角。 在我的下一期专栏文章中，我会介绍使用 C5 而不是 SCG 集合实现的一些实用示例，以及这样做会给我们带来的一些好处。 建议您不要等待： 使用 NuGet，实践 C5，开始独自探索，您会在其中发现非常多的乐趣。

祝您工作愉快！

Ted Neward 是 Neudesic LLC. 的体系结构顾问。 他曾写过 100 多篇文章，独自撰写或与人合著过十几本书，包括《Professional F# 2.0》（Wrox，2010 年）。 他是 F# 领域最优秀的专家之一和著名的 Java 专家，在全球 Java 和 .NET 会议上演讲。 他定期担任顾问和导师，如果您有兴趣请他参与您的团队工作，请通过 ted@tedneward.com 或 Ted.Neward@neudesic.com 与他联系。 他的博客网址是 blogs.tedneward.com，您也可以通过 Twitter 地址 twitter.com/tedneward 关注他。

衷心感谢以下技术专家对本文的审阅： Immo Landwerth