概要

集合類(lèi)型對(duì)任何一門(mén)現(xiàn)代化編程語(yǔ)言都至關(guān)重要，它們?cè)谠S多可見(jiàn)或者不可見(jiàn)的地方，影響著代碼質(zhì)量與執(zhí)行效率。Swift 在集合類(lèi)型的設(shè)計(jì)和實(shí)現(xiàn)上，進(jìn)行了諸多的考量，讓它兼具易用性、高性能以及擴(kuò)展性，但同時(shí)也增加了集合的復(fù)雜性。很多時(shí)候我們都在說(shuō) Swift 會(huì)比 OC 更快，但它到底快在哪里呢？對(duì)于名 Swifter 來(lái)說(shuō)，單純的數(shù)據(jù)統(tǒng)計(jì)分析的結(jié)果無(wú)說(shuō)服力的，我們要知其然，同時(shí)更要知其所以然，那么本系列文章將圍繞著 Swift 是如何實(shí)現(xiàn)高性能的集合類(lèi)型來(lái)展開(kāi)。

起點(diǎn) Sequence

在 Swift 中，集合是一個(gè)復(fù)雜的類(lèi)型家族，是由許多 Protocol 組成的，其中 Sequence 是 Swift 整個(gè)集合類(lèi)型體系中的起點(diǎn)，它抽象了一個(gè)集合最原始的協(xié)議。僅表示一系列類(lèi)型相同的元素，而不對(duì)這一系列元素的性質(zhì)有任何額外的約定。它只約定一個(gè)動(dòng)作，就是可以從序列的當(dāng)前位置讀取下一個(gè)元素，也即表示序列需要對(duì)外提供一個(gè)迭代器來(lái)實(shí)現(xiàn)對(duì)外的訪(fǎng)問(wèn)。

Sequence 的實(shí)現(xiàn)

我們可以在 Sequence.swift 文件中查看到 Sequence 協(xié)議的實(shí)現(xiàn)方法（在前言篇中在已經(jīng)講述過(guò)如何編譯和查看 Swift 的源碼，系列文章將不作重復(fù)說(shuō)明）：

public protocol Sequence {
  associatedtype Element
  associatedtype Iterator : IteratorProtocol where Iterator.Element == Element
  __consuming func makeIterator() -> Iterator    
}

Sequence 協(xié)議中定義了大量的輔助函數(shù)，大部分都已通過(guò) Protocol Extension 實(shí)現(xiàn)了，不一一列舉，這里的事例代碼只保留了 Sequence 協(xié)議最核心代碼。從上面源碼可以看出，序列的實(shí)現(xiàn)思路非常簡(jiǎn)單：

• Element：表示序列中元素的類(lèi)型；
• Iterator：表示 IteratorProtocol 并且 Iterator 的 Element 與序列的 Element 相同；
• makeIterator()：返回一個(gè) Iterator，Iterator 迭代器提供了訪(fǎng)問(wèn)序列中下一個(gè)元素的能力，它的具體實(shí)現(xiàn)如下：

public protocol IteratorProtocol {
  associatedtype Element
  mutating func next() -> Element?
}

• Element：表示 next() 返回的元素類(lèi)型，如上面所述，Element 的類(lèi)型與相應(yīng)的序列的 Element 保持一致；
• next()：方法是問(wèn)序列下一個(gè)元素的接口，如果沒(méi)有下一個(gè)元素則返回 nil;

IteratorProtocol 協(xié)議與 Sequence 協(xié)議是一對(duì)緊密相連的協(xié)議。序列通過(guò)創(chuàng)建一個(gè)提供對(duì)其元素進(jìn)行訪(fǎng)問(wèn)的迭代器，它通過(guò)跟蹤迭代過(guò)程并在調(diào)用 next() 時(shí)返回一個(gè)元素。

在我們使用 for-in 來(lái)訪(fǎng)問(wèn)序列或者集合時(shí)， Swift 實(shí)質(zhì)在底層通過(guò)迭代器來(lái)循環(huán)遍歷數(shù)組，正常我們通過(guò) for-in 來(lái)遍歷一個(gè)數(shù)組的用法：

let colors = ["red", "white", "black"]
for color in colors {
    print(color)
}

實(shí)質(zhì)上 Swift 在底層通過(guò) Sequence 的 Iterator 能力，做了如下轉(zhuǎn)換：

let colors = ["red", "white", "black"]
var iterator = colors.makeIterator()
while let color = iterator.next() {
    print(color)
}

這兩種方式訪(fǎng)問(wèn)序列的效果是等同的，只是一種簡(jiǎn)單的語(yǔ)法轉(zhuǎn)換，所以所有基于 Sequence 的協(xié)議，除了可以通過(guò)過(guò) for 來(lái)訪(fǎng)問(wèn)元素外，還可以通過(guò)迭代器來(lái)序列元素。

自定義序列

我了解 Sequence 的具體實(shí)現(xiàn)后，我們來(lái)嘗試實(shí)現(xiàn)自己的序列，下面我們來(lái)實(shí)例一個(gè)輸出 1…n 的平方數(shù)的序列。

首先我們需要先實(shí)現(xiàn)一個(gè) SquareIterator 的迭代器來(lái)遍歷平方數(shù)序列：

struct SquareIterator: IteratorProtocol {
    typealias Element = Int
    var state = (curr: 0, next: 1)
    mutating func next() -> SquareIterator.Element? {
        let curr = state.curr
        let next = state.next
        state = (curr: next, next: next + 1)
        if curr == 0 {
            return 1
        }
        return curr * curr
    }
}

通過(guò)在迭代器中定義一個(gè) state 來(lái)記錄當(dāng)前迭代過(guò)程的狀態(tài)信息，實(shí)現(xiàn)了該迭代器后，我們就需要實(shí)現(xiàn) Square 序列的 Sequence 協(xié)議：

struct Square: Sequence {
    typealias Element = Int
    func makeIterator() -> SquareIterator {
        return SquareIterator()
    }
}

通過(guò)實(shí)現(xiàn)了 Sequence 與 IteratorProtocol 兩個(gè)協(xié)議，那么一個(gè)簡(jiǎn)單的 Square 序列即開(kāi)發(fā)完畢，我們可以嘗試去執(zhí)行它：

let square = Square()
var iterator = square.makeIterator()
while let num = iterator.next(), num <= 100 {
    print(num) // 1,1,3,9,16,25,36,49,64,81,100
}

到這里我們已經(jīng)完成一個(gè)自定義的序列，它支持通過(guò)迭代器來(lái)遍歷序列的所有元素，但是沒(méi)有辦法通過(guò)下標(biāo)的方式來(lái)訪(fǎng)問(wèn)序列元素，至于如何實(shí)現(xiàn)下標(biāo)訪(fǎng)問(wèn)，這其中又涉及到另一個(gè)協(xié)議：Collection，接下來(lái)我們就來(lái)談?wù)?Collection Protocol。

Collection

Collection 是一個(gè)繼承于 Sequence 序列，是一個(gè)元素可以反復(fù)遍歷并且可以通過(guò)索引的下標(biāo)訪(fǎng)問(wèn)的有限集合。集合在標(biāo)準(zhǔn)庫(kù)中廣泛使用，當(dāng)我們?cè)谑褂脭?shù)組、字典和其他集合時(shí)，大多將受益于 Collection 協(xié)議聲明和實(shí)現(xiàn)的操作。 除了集合從 Sequence 協(xié)議繼承的操作之外，最大的不同點(diǎn)是可以訪(fǎng)問(wèn)依賴(lài)于訪(fǎng)問(wèn)集合中特定位置的元素的方法。

Collection 的實(shí)現(xiàn)

源碼

我們可以在 Collection.swift 查看到 Collection 的具體實(shí)現(xiàn)：

public protocol Collection: Sequence {
  override associatedtype Element
  associatedtype Index : Comparable
  var startIndex: Index { get }
  var endIndex: Index { get }
  associatedtype Iterator = IndexingIterator<Self>
  override __consuming func makeIterator() -> Iterator

  associatedtype SubSequence: Collection = Slice<Self>
  where SubSequence.Index == Index,
        Element == SubSequence.Element,
        SubSequence.SubSequence == SubSequence
  
  @_borrowed
  subscript(position: Index) -> Element { get }
  subscript(bounds: Range<Index>) -> SubSequence { get }

  associatedtype Indices : Collection = DefaultIndices<Self>
    where Indices.Element == Index, 
          Indices.Index == Index,
          Indices.SubSequence == Indices
       
  var indices: Indices { get }
}

• Element、makeIterator：重寫(xiě) Sequence 的 Element、makeIterator；
• startIndex、endIndex：非空集合中第一個(gè)、最后一個(gè)元素的位置；
• subscript：下標(biāo)訪(fǎng)問(wèn)集合元素，例如 collection[i]、collection[0...i]；
• indices: 集合的索引

通過(guò)源碼，我們可以發(fā)現(xiàn) Collection 與 Sequence 最大的不同點(diǎn)是提供了索引能力，以此基礎(chǔ)上提供了通過(guò)下標(biāo)訪(fǎng)問(wèn)元素的能力。 Collection 的自定義了迭代器：IndexingIterator，接下來(lái)我們了解下 What is IndexingIterator。

IndexingIterator

Collection 的迭代器使用 IndexingIterator，從名字的字面意思來(lái)看，這就是與下標(biāo)位置有關(guān)的迭代器，我們先來(lái)看下它的具體實(shí)現(xiàn)：

public struct IndexingIterator<Elements : Collection> {
  internal let _elements: Elements
  internal var _position: Elements.Index
  
  init(_elements: Elements) {
    self._elements = _elements
    self._position = _elements.startIndex
  }
  init(_elements: Elements, _position: Elements.Index) {
    self._elements = _elements
    self._position = _position
  }
}
extension IndexingIterator: IteratorProtocol, Sequence {
  public typealias Element = Elements.Element
  public typealias Iterator = IndexingIterator<Elements>
  public typealias SubSequence = AnySequence<Element>
  
  public mutating func next() -> Elements.Element? {
    if _position == _elements.endIndex { return nil }
    let element = _elements[_position]
    _elements.formIndex(after: &_position)
    return element
  }
}

• _elements：需要迭代的集合，類(lèi)型為 Collection；
• _position：記錄遍歷時(shí)的位置信息；

IndexingIterator 的作用主要是在迭代器執(zhí)行 next() 方法時(shí)，記錄了 position，通過(guò) position 記錄索引的同時(shí)，還可以與 elements.endIndex 比較來(lái)判斷是否有下一個(gè)元素。

Slice

Collection 協(xié)議中，通過(guò)閉包去訪(fǎng)問(wèn)多個(gè)元素時(shí)，返回了一個(gè) Slice<Self>，這里的 Slice 是一個(gè)可以獲取集合的元素的子序列。切片存儲(chǔ)的只是集合的開(kāi)始和結(jié)束索引，所以它不會(huì)將集合中的元素復(fù)制一份，因此創(chuàng)建切片具有O（1）復(fù)雜度。Collection 中通過(guò) Slice 來(lái)截取子序列，具體可以看下 Slice 到底做了些什么：

public struct Slice<Base: Collection> {
  public var _startIndex: Base.Index
  public var _endIndex: Base.Index
  internal var _base: Base

  public init(base: Base, bounds: Range<Base.Index>) {
    self._base = base
    self._startIndex = bounds.lowerBound
    self._endIndex = bounds.upperBound
  }
  public var base: Base {
    return _base
  }
}
extension Slice: Collection {
  public typealias Index = Base.Index
  public typealias Indices = Base.Indices
  public typealias Element = Base.Element
  public typealias SubSequence = Slice<Base>
  public typealias Iterator = IndexingIterator<Slice<Base>>

  public var startIndex: Index {
    return _startIndex
  }
  public var endIndex: Index {
    return _endIndex
  }
  public subscript(index: Index) -> Base.Element {
    get {
      _failEarlyRangeCheck(index, bounds: startIndex..<endIndex)
      return _base[index]
    }
  }
  public subscript(bounds: Range<Index>) -> Slice<Base> {
    get {
      _failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex)
      return Slice(base: _base, bounds: bounds)
    }
  }
}

Slice 實(shí)質(zhì)上僅且修改 Collection 的索引，從而達(dá)到獲取子序列的效果。

Custom Collection

在了解了 Collection 及其相關(guān)的一些協(xié)議 后，我們來(lái)嘗試自己實(shí)現(xiàn)一個(gè)簡(jiǎn)單的 Collection，這個(gè)集合包含 1 ~ 10 的 Int 類(lèi)型的元素，并支持下標(biāo)訪(fǎng)問(wèn)和多次遍歷：

struct SquareCollection: Collection { 
    typealias Element = Int
    typealias Index = Int
    typealias Indices = Range<Int>
    let contents = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    var indices: Range<Int> = 0..<10
    
    public func index(after i: Int) -> Int {
        return i + 1
    }
    public var startIndex: Int {
        get {
            return indices.startIndex
        }
    }
    public var endIndex: Int {
        get {
            return indices.endIndex
        }
    }
    public subscript(index: Int) -> Element {
        get {
            return contents[index]
        }
    }
}

我們?cè)?SquareCollection 實(shí)現(xiàn)了 Collection 協(xié)議，提供了索引功能，然后通過(guò) subscript 方法就可以達(dá)到通過(guò)下標(biāo)訪(fǎng)問(wèn)元素的效果：

let collection = SquareCollection()
print(collection[1])  // 2
print(collection[3])  // 4

這個(gè)自定義的集合，有點(diǎn)類(lèi)似一個(gè)寫(xiě)死的數(shù)組，它擁有 Sequence 與 Collection 協(xié)議的所有已實(shí)現(xiàn)的方法，比如：

let newCollection = collection.dropLast()
print(newCollection.count) // 9

當(dāng)然這離真正的數(shù)組還有很遠(yuǎn)的距離，比如設(shè)置初始化元素、越界判斷、通過(guò)下標(biāo)修改元素值，關(guān)于通過(guò)下標(biāo)修改元素，Swift 中通過(guò) MutableCollection 協(xié)議來(lái)實(shí)現(xiàn)，可以看下 MutableCollection 的核心代碼：

public protocol MutableCollection: Collection
where SubSequence: MutableCollection
{
  override subscript(position: Index) -> Element { get set }
  override subscript(bounds: Range<Index>) -> SubSequence { get set }
}

extension MutableCollection {
  public subscript(bounds: Range<Index>) -> Slice<Self> {
    get {
      _failEarlyRangeCheck(bounds, bounds: startIndex..<endIndex)
      return Slice(base: self, bounds: bounds)
    }
    set {
      _writeBackMutableSlice(&self, bounds: bounds, slice: newValue)
    }
  }
}

最核心的是重寫(xiě)了 subscript 方法，提供了對(duì)外的 set 方法，當(dāng)然集合家族中，還有非常的輔助協(xié)議，用來(lái)提高集合家族的效率與性能，這里暫不深入講解，后面內(nèi)容涉及到的話(huà)再詳細(xì)介紹。

集合與算法

集合大家族中， 除了定義相關(guān)的數(shù)據(jù)結(jié)構(gòu)外，還提供了大量的算法實(shí)現(xiàn)，以提高 Swift 的便捷性與高性能，以 Sequence 為例，我們可以看下 SequenceAlgorithms.swift 內(nèi)容：

public func enumerated() -> EnumeratedSequence<Self>
public func min() -> Element?
public func max() -> Element?
public func starts<PossiblePrefix: Sequence>(
    with possiblePrefix: PossiblePrefix
  ) -> Bool
public func elementsEqual<OtherSequence: Sequence>
...
...

SequenceAlgorithms 實(shí)現(xiàn)了大量的基礎(chǔ)算法，其具體的實(shí)現(xiàn)就不展示討論，當(dāng)然 CollectionAlgorithms 也是類(lèi)似的，目的就是讓開(kāi)發(fā)者更便捷地使用集合的同時(shí)又保證它的性能穩(wěn)定。如果我們開(kāi)發(fā)組件或者開(kāi)源庫(kù)的時(shí)候，這是一種值得參考的思路，在功能完善的同時(shí)，我們還要保證使用者的便捷與接口的高性能，當(dāng)然這是題外話(huà)了，就不過(guò)多去討論。

Lazy

What is Lazy

Lazy 惰性加載，最典型的用例是懶加載，定義時(shí)聲明具體操作，但只有在第一次使用時(shí)才去真正創(chuàng)建：

// 僅聲明了 titleLabel，并沒(méi) UILabel 對(duì)象
lazy var titleLabel : UILabel = {
    let label = UILabel()
    return label
}() 
// 訪(fǎng)問(wèn) titleLabel 時(shí)會(huì)去創(chuàng)建 UILabel 對(duì)象
self.titleLabel

通過(guò)這么一個(gè)簡(jiǎn)單的例子，初步了解 Swift 的 Lazy 是什么意思，當(dāng)然懶加載只是其中的一種用法，下面我們來(lái)了解下集合中的 Lazy 作用。

LazySequence

在 Sequence 和 Collection 中已經(jīng)了很多類(lèi)似 map 和 filter 這些高階函數(shù)，它們的思路是將一些通用的算法封裝成簡(jiǎn)單的單行函數(shù)。但是有些時(shí)候我們并不需要立馬執(zhí)行這些輔助數(shù)，我們希望是的使用時(shí)再去執(zhí)行輔助函數(shù)，定義時(shí)只做聲明，這個(gè)時(shí)候就需要使用到 lazy，舉個(gè)例子：

let allUser = [0, 1, 0, 1, 0, 2, 3, 4, 2, 1]
// 定義時(shí)直接執(zhí)行 filter 方法，如果 agents 沒(méi)有被使用，則浪費(fèi)了資源
let agents = allUser.filter { $0 == 1 }

// 使用時(shí)才執(zhí)行 filter 方法，如果不使用也不會(huì)浪費(fèi)資源
let lazyAgents = allUser.lazy.filter { $0 == 1 }

Swift Sequences 和 Collections 給我提供通過(guò) lazy 的方式來(lái)執(zhí)行輔助函數(shù)，目的是為了給開(kāi)發(fā)者提供便捷的輔助函數(shù)并又保持其高性能。那么這里來(lái)看下 Sequences 是怎么實(shí)現(xiàn) lazy 的。

我們可以通過(guò)查看 LazySequence.swift 了解具體實(shí)現(xiàn)，核心代碼如下：

public protocol LazySequenceProtocol : Sequence {
  associatedtype Elements: Sequence = Self where Elements.Element == Element
  var elements: Elements { get }
}
extension LazySequenceProtocol where Elements == Self {
  public var elements: Self { return self }
}
extension LazySequenceProtocol {
  public var lazy: LazySequence<Elements> {
    return elements.lazy
  }
}
extension LazySequenceProtocol where Elements: LazySequenceProtocol {
  public var lazy: Elements {
    return elements
  }
}
public struct LazySequence<Base : Sequence> {
  internal var _base: Base
  internal init(_base: Base) {
    self._base = _base
  }
}

從源碼角度來(lái)看，非常有意思的是 LazySequence 并沒(méi)有做任何的額外事情，只是新定義了一種類(lèi)型。那么它具體是怎么實(shí)現(xiàn)，這個(gè)我們需要看具體的輔助方法，比如 Filter，我們可以從 Filter.swift 中找到以下代碼：

extension LazyFilterSequence.Iterator: IteratorProtocol, Sequence {
  public typealias Element = Base.Element
  public mutating func next() -> Element? {
    while let n = _base.next() {
      if _predicate(n) {
        return n
      }
    }
    return nil
  }
}

Lazy 的功能，實(shí)質(zhì)上是通過(guò) extension 方法，在迭代器執(zhí)行 next() 方法時(shí)，對(duì)獲取到的元素執(zhí)行 filter() 后再進(jìn)行返回，從而實(shí)現(xiàn)了 lazy 惰性執(zhí)行的效果。當(dāng)然其它的 map()、flatMap() 等方法 lazy 實(shí)現(xiàn)也是一樣的，這里就不一一列舉了。

總結(jié)

在這一章內(nèi)容中，介紹 Collection 大家族中幾個(gè)重要的協(xié)議，初步了解它們是如何去實(shí)現(xiàn)與工作的。 但是，它們?cè)?Collection 大家族中，不過(guò)是冰山一角，還有更多的內(nèi)容等待我們?nèi)ド钊胪诰?，我們可以嘗試通過(guò)解決下面幾個(gè)問(wèn)題去加深對(duì)集合類(lèi)型的了解：

• 有幾種不同形式的 Sequence 與 Collection，它們的作用是什么？
• 為什么 Iterator、LazySequence 等使用的是值類(lèi)型，這樣的目的是為了什么？
• Sequence 與 Collection 有哪些高階函數(shù)，他們是如何去實(shí)現(xiàn)的？

如果能答對(duì)上面的問(wèn)題，估計(jì)會(huì)對(duì) Swift 的集合類(lèi)型有更深入的了解，下一篇我們會(huì)從 Array、Dictionary、Set 的具體實(shí)現(xiàn)來(lái)深入了解 Swift 的集合家族，同時(shí)也會(huì)嘗試去實(shí)現(xiàn)我們自定義的功能齊全的集合類(lèi)型。

更多內(nèi)容，請(qǐng)關(guān)注我的公眾號(hào)：

關(guān)注公眾號(hào)