最近翻譯完了《Advanced Swift》中文版「集合」章節。這本書質量極高、講解細緻,但也因此篇幅偏長,前面學到的知識點讀到後面容易串不起來。加上它偏重講解,個人覺得總結還不夠透徹。我們不妨先拋出幾個問題:
數組類型(_ArrayType)、集合(Collection)、序列(Sequence)、生成器(Generator)、元素(Element)、下標(Index)等類型(協議)各自扮演什麼角色?
數組是如何借助上述類型實現各種方法的?
map、reduce、filter 等方法有何作用,又是如何實現的?
只有數組才具備这些方法嗎?如果不是,什麼樣的類型才有?
若要實現一個自定義集合類型,該從何入手?
而這些問題恰恰是我們過去未曾重視、甚至無從下手的。因為在 OC 裡,NSArray 封裝得過於完美,加之單純的 iOS 開發對數組的理解要求不深,我們很少去深究它背後的實現原理。
其實答案就散落在《Advanced Swift》中文版「集合」章節的如前所述各篇文章裡。本文將通過剖析 Swift 數組的實現來回答上述問題,並嘗試建構一套完整的知識體系。受限於篇幅,本文不會堆砌冗長源碼,而重在提煉總結。
參考文章
Advanced Swift——數組可變性:主要介紹數組的值語義
Advanced Swift——數組變換:介紹 map、reduce、filter 的用法與原理
Advanced Swift——字典與集合:介紹字典與集合類型的使用
Advanced Swift——集合協議:介紹數組相關的三種協議
Advanced Swift——集合:通過實現隊列,介紹 CollectionType 的使用
Advanced Swift——下標:實現自定義鏈表,介紹數組下標知識
相關類型簡介
我們從零出發,依據集合最本質的特點逐步抽象。
元素(Element)
任何集合本質上都是一種用來存放數據的數據結構。我們在代碼中常見的 Element,代表的就是最底層數據類型的別名。由於集合這種泛型類型並不關心具體存的是什麼,便用通用的 Element 代指,例如:
let array: Array = [1, 2, 3]
這無異於告訴數組:此時 Element 具體化為 Int 了。
生成器(Generator)
集合通常還需提供遍歷能力。可怎麼把它設計成可遍歷呢?別指望 for 循環——此刻我們什麼都沒有,既無數組概念,也無下標概念。有句名言說:「任何編程問題都可以通過增加一個中間層來解決。」於是我們抽象出 Generator 的概念,將它聲明為一個協議,要求實現者提供一個 next 方法,返回集合中的下一個元素:
protocol GeneratorType {
typealias Element
mutating func next() -> Element?
}可以想見,實現了 GeneratorType 的類,就能隱藏具體元素信息,通過不斷調用 next 拿到所有元素——比如用它持續生成斐波那契數列。總之,生成器讓我們得以遍歷所有元素。
序列(Sequence)
生成器雖能不斷吐出新元素,但已生成過的再也取不回來。比如在斐波那契數列中用 3 和 5 得到 8 後,這個生成器永遠不會再產生 3,下一個是 13。也就是說,對生成器而言,訪問過的元素無法再次獲取。
然而集合的元素總是客觀存在的。為支持多次遍歷,我們抽象出 Sequence 的概念,它封裝了 Generator 對象的創建過程:
protocol SequenceType {
typealias Generator: GeneratorType
func generate() -> Generator
}相比單純的 Generator,Sequence 讓「反復遍歷」成為可能,此時我們已能用 for 循環而非手動 next 來遍歷所有元素。
集合(Collection)
對比現有的 Sequence 與數組,會發現它還差一個關鍵特性——下標。
回顧 Generator 與 Sequence,它們只解決了遍歷,卻沒規定怎麼遍歷。也就是說,只要 Generator 設計「得當」,哪怕只有 1 和 2 兩個元素,也能陷入「1 的 next 是 2、2 的 next 又是 1」的死循環——這顯然不符合我們對數組的認知。歸根結底,是 Sequence 無法確定元素位置,也就無法保證不重複訪問。
基於此,我們抽象出 Collection 的概念:集合中每個元素都有確切位置,因而有明確的起止。給定一個位置就能找到對應元素。Collection 在 Sequence 基礎上實現了 Indexable 協議:
public protocol CollectionType : Indexable, SequenceType {
public var startIndex: Self.Index { get }
public var endIndex: Self.Index { get }
public subscript (position: Self.Index) -> Self._Element { get }
}當然,CollectionType 的內容遠不止這些,這裡列出來的只是為了體現其核心特性。
下標(Index)
我們用數組時,下標總是從 0 開始逐個遞增,但下標未必非得是從 0 遞增的整數——a、b、c…… 同樣可以當下標。下標類型的關鍵在於:能根據當前下標推斷出下一個下標(比如整數的下一個就是當前值加 1)。其協議大致如下:
public protocol ForwardIndexType : _Incrementable {
/// ...
}
public protocol _Incrementable : Equatable {
public func successor() -> Self
}下標類型必須實現 successor() 方法,同時得是 Equatable 的,否則無從判斷某個位置是否已被訪問。
數組簡介
有了以上鋪墊,就可以研究 Swift 數組的實現了。
基本定義
我們大概早已領教過 Swift 數組的強大:下標腳本既能讀取也能修改元素,能用字面量初始化,還能通過 appendContentsOf 從別的數組追加元素,甚至我們都沒細想過為何能用 for number in array 這樣的語法。
首先要明確:數組這些豐富強大的特性,絕非 Array 這一個類型所能獨力提供,主要功勞在於協議。用 OC 寫 iOS 時,協議幾乎是「代理」的代名詞;而在 Swift 中,協議的能力被空前強化。數組通過實現協議,以及協議的嵌套與擴展,獲得了諸多特性。它背後交織着錯綜複雜的協議、方法與擴展。
下面是數組的定義:
public struct Array : CollectionType, MutableCollectionType, _DestructorSafeContainer {
public var startIndex: Int { get }
public var endIndex: Int { get }
public subscript (index: Int) -> Element
public subscript (subRange: Range) -> ArraySlice
}數組是一個結構體,實現了三個協議,擁有兩個變量和兩個下標腳本,此外還有大量擴展。
數組擴展
數組的大量功能都在擴展中完成。由於擴展眾多,這裡不逐一貼出完整代碼,僅做梳理。數組一共擴展了四類協議:
ArrayLiteralConvertible:為支持 let a: Array = [1,2,3] 這樣的字面量語法,實現它很簡單,只需提供一個自定義初始化方法:
public init(arrayLiteral elements: Element...)
_Reflectable:用於處理反射相關內容,此處不展開。
CustomStringConvertible 與 CustomDebugStringConvertible:便於調試,與數組自身功能無關。
_ArrayType:這是數組最關鍵的部分。在实现它之前,數組只是個普通集合類型,僅具備下標、可重複遍歷而已;實現 _ArrayType 後,它便能在指定位置增刪一個或多個元素,並有了自己的 count 屬性。
這一點或許顛覆了我們此前的認知:一個集合類型,本不能增刪元素,而數組通過 _ArrayType 提供了這種能力。但這也好理解——集合的本質在於「收集元素」,而非「改變元素」。
_ArrayType 還給了我們一個重要啟示:若你想實現自己的數據結構(比如棧),就應該實現對應的 _StackType 協議。這種協議要充分考量數據結構自身特點,從而定義合適的方法。比如棧只能從棧頂 push/pop,不可能往某個特定位置插入若干元素,所以 _StackType 裡不會有 append、appendContentsOf,而應定義 pop 與 push。
SequenceType
接下來搞清楚 CollectionType 的原理。在此之前,先看看 SequenceType 的一些細節,畢竟 CollectionType 繼承自它。
有了 Generator,我們已能在 while 循環裡用 next 遍歷所有元素;而 SequenceType 讓「多次遍歷」成為可能。
注意,僅僅是「成為可能」。若遍歷細節完全由 Generator 掌控,多次遍歷自然沒問題;但在極少數情況下,若遍歷依賴 SequenceType 自身某個會變化的屬性,就無法保證多次遍歷。
SequenceType 協議本身極其簡單,只有一個封裝了 Generator 創建過程的 generate() 方法。
而一旦有了遍歷概念,SequenceType 立刻衍生出大量擴展,列舉幾個關鍵的:
forEach:讓我們能用 for 循環遍歷集合(for item in sequence)
dropFirst(n:) 與 dropLast(n:):返回除去前(後)n 個元素之外的 Sequence。由於此時還沒有下標概念,其實現頗為複雜。
prefix(maxLength:) 與 suffix(maxLength:):返回前(後)maxLength 個元素,實現同樣不簡單。
elementsEqual、contains、minElement、maxElement 等,都是針對元素的判斷與挑選。
map、flatMap、filter、reduce 等,則是針對所有元素的變換。
SequenceType 的擴展實在多不勝數,但歸納起來不外乎兩點:
因為能多次遍歷元素,我們得以對元素做各種比較、處理、篩選,這些派生方法極大地強化了 SequenceType 的能力。
由於 SequenceType 自身局限——無法保證一定可多次遍歷、又缺乏下標與位置概念,某些方法的實現不夠高效。
帶着這份遺憾,我們來看最關鍵的 CollectionType 是如何實現的。
細談 CollectionType
前面說過,CollectionType 是在 SequenceType 基礎上實現了 Indexable 協議。出於協議繼承,任何實現 CollectionType 的類型,都必須實現 Indexable 規定的 startIndex、endIndex 兩個參數,以及一個下標腳本 subscript (position:) -> _Element { get }——即便這三項要求在 CollectionType 中沒有直接標出。
回顧數組定義的前三行,恰好滿足了這三項要求。再看 CollectionType,它不僅重載了 Indexable 的一個下標腳本,還額外提供了一個用於訪問「某一段元素」的下標腳本,返回類型是切片(Slice)——這正是數組定義的第四行所實現的內容。
細心的讀者可能注意到,CollectionType 還定義了 prefixUpTo、suffixFrom、isEmpty、first 等諸多屬性和方法,但數組並未逐一實現它們。
事實上,這非但不是設計的敗筆,反而正是 Swift 協議的強大之處:Swift 可通過協議擴展,為計算屬性和方法提供默認實現。因此數組不寫一行代碼就具備了這些方法,而任何實現 CollectionType 的類型也同樣受益。
觀察 CollectionType 的其他擴展,大多數其實是重寫了 SequenceType 中的實現。前面提到 SequenceType 沒有下標概念,而像 dropFirst 這樣的方法,借助下標便极易實現。除了重寫已有方法,CollectionType 還新增了一些基於下標的方法,如 indexOf() 等。
套用官方文檔對 CollectionType 的概括就是:
A multi-pass sequence with addressable positions
也就是說,CollectionType 是一個「可多次遍歷、元素可定位」的 SequenceType。
總結
Element、Generator、SequenceType、CollectionType、Array 自下而上,共同構成了數組背後的層次結構,其關係如圖所示:

Swift 數組層次結構
若我們想定義自己的數據結構(比如鏈表),首先可明確它要實現 CollectionType 協議,與 Array 處於同一層次;隨後再定義一個 _ListType 協議(對應數組的 _ArrayType),依據鏈表自身特點定義方法。
如果覺得 CollectionType 甚至 SequenceType 都不滿足需求,你也可以自行實現對應類型。難度不會太大,因為它們雖看似龐雜,但大多方法已有默認實現,只需重寫關鍵邏輯即可。
最後要說明的是,Swift 對集合的實現實在過於複雜,若逐一詳析,怕是能寫成一本書。希望讀完本文後,讀者能舉一反三,自行翻閱源碼去解決相關問題。