最近翻譯完了《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方法就可以獲得所有元素了。比如你可以用一個生成器，不斷生成斐波那契數列的下一個數字。

總的來說，生成器(Generator)允許我們遍歷所有的元素。

• 序列(Sequence)

生成器不斷生成下一個元素，但是已經生成過的元素就無法再獲取到了。比如在斐波那契數列中通過3和5得到了8，那麼這個生成器永遠也不會再生成元素3了，下一個生成的元素是13。也就是說對於生成器來說，已經訪問過的元素就無法再次獲取到。

然而對於集合來說，它所包含的元素總是客觀存在的。為了能夠多次遍歷集合，我們抽象出了序列(Sequence)的概念。Sequence封裝了Generator對象的創建過程：

protocol SequenceType {
  typealias Generator: GeneratorType
  func generate() -> Generator
}

序列(Sequence)相比於單純的Generator，使反復遍歷集合中的元素成為可能。這時候，我們已經可以通過for循環而不是Generator來遍歷所有元素。

• 集合(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中的內容遠遠不止這些。這裡列出的僅僅是為了表示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時，協議幾乎就是代理的代名詞(可能是我對OC不甚精通，目光短淺)，但毋庸置疑的是在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協議。這種協議要充分考慮數據結構自身的特點，從而提供對應的方法。比如我們不可能向棧的某個特定位置添加若干個元素(只能向棧頂添加一個)。所以_StackType協議中不會定義append、appendContentsOf這樣的方法，而是應該定義pop和push方法。

SequenceType

接下來的任務是搞清楚ColectionType的原理了。不過在此之前，我們先來看看SequenceType的一些細節，畢竟CollectionType協議是繼承了SequenceType協議的。

在有了Generator之後，我們已經可以在while循環中用Generator的next方法遍歷所有元素了。之前也說過，SequenceType使對元素的多次遍歷成為可能。

注意，僅僅是成為可能而已。如果遍歷的細節由Generator控制，那麼多次遍歷是沒有問題的。在極個別情況下，但如果遍歷的細節依賴於SequenceType自身的某個屬性，而且這個屬性會發生變化，那麼就不能多次遍歷所有元素了。

SequenceType協議的基本部分非常簡單，只有一個generator()方法，封裝了Generator的創建過程。

一旦有了遍歷元素的概念，SequenceType立刻就有了非常多的拓展。這裡簡單列舉幾個比較關鍵的：

• forEach：這個拓展使得我們可以用for循環遍歷集合了：for item in sequence

• dropFirst(n: Int)和dropLast(n: Int)：這兩個方法返回的是除了前(後)n個元素之外的Sequence。需要提一下的是，由於此時的SequenceType還沒有下標的概念，這兩個方法的實現是非常復雜的。

• prefix(maxLength: Int)和suffix(maxLength: Int)：和剛剛兩個方法類似，這兩個方法返回的是前(後)maxLength個元素，實現也不簡單。

• elementsEqual、contains、minElement、maxElement等，這些都是針對元素的判斷和選擇。

• map、flatMap、filter、reduce這些方法是針對所有元素的變換。

SequenceType的拓展實在是太多了，但總結來看不外乎兩點：

1. 由於可以多次遍歷元素了，我們可以對元素進行各種比較、處理、篩選等等操作。這些派生出來的方法和函數極大的強化了SequenceType的功能。

2. 由於SequenceType自身的局限性，不能保證一定可以多次遍歷所有元素，還沒有下標和元素位置的概念，因此某些方法的實現還不夠高效，

帶著這樣的遺憾，我們來看看最關鍵的CollectionType是如何實現的。

細談CollectionType

之前我們說過CollectionType協議是在SequenceType的基礎上實現了Indexable協議。由於協議的繼承關系，任何實現了CollectionType協議的類，必須實現Indexable協議規定的兩個參數：startIndex和endIndex，以及一個下標腳本：subscript (position: Self.Index) -> Self._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的協議，這個協議對應數組的_ArrayList協議，根據數據結構自身的特性定義一些方法。

如果覺得CollectionType甚至是SequenceType不滿足我們的需求，我們還可以自己實現對應的類型。難度不會很大，因為它們雖然負責，但大多數方法已有默認實現，我們只要重寫一些關鍵的邏輯即可。

最後需要說明的是，Swift中對集合的實現實在是太復雜了，如果每個都詳細分析，怕是可以寫一本書。希望讀完這篇文章後，讀者可以舉一反三，自行閱讀源碼解決相關問題。