您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發基礎

深入探究 Swift 數組背後的協議、方法與擴展

編輯:iOS 開發基礎

最近翻譯完了《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 的擴展實在多不勝數,但歸納起來不外乎兩點:

  1. 因為能多次遍歷元素,我們得以對元素做各種比較、處理、篩選,這些派生方法極大地強化了 SequenceType 的能力。

  2. 由於 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 對集合的實現實在過於複雜,若逐一詳析,怕是能寫成一本書。希望讀完本文後,讀者能舉一反三,自行翻閱源碼去解決相關問題。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved