孜孜不倦的程式師

.NET 收集：C5 入門

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 （由-現在無處不在）安裝套裝軟體命令，只需通過鍵入"安裝套裝軟體 C5"。請注意 C5 編寫成可用於 Visual Studio 和單聲道，當 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 關注他。

衷心感謝以下技術專家對本文的審閱：防盜 Landwerth

共用方式為