Swift底層原理-Sequence與Collection

• Sequence協(xié)議來說拙绊，表達(dá)的是既可以是一個(gè)有限的集合呐萌，也可以是一個(gè)無限的集合弊予，而它只需要提供集合中的元素和如何訪問這些元素的接口即可翼岁。
• Collection協(xié)議是建立在Sequence協(xié)議之上的悦析，為有限的序列提供下標(biāo)訪問的能力寿桨，同時(shí)增加了count屬性，自定義索引等特性

[圖片上傳失敗...(image-e4a786-1684654022077)]

Sequence

• Sequence作為swift集合類協(xié)議擴(kuò)展方法强戴，為集合提供了一系列的序列迭代能力亭螟。

for in本質(zhì)

• Sequence是通過Iterator來訪問元素的挡鞍。Iterator是一個(gè)迭代器，我們來看一段代碼预烙，如下：

let nums = [1, 2, 3, 4, 5];
for element in nums {
    print(element)
}

• 在Swift中的 for in 其實(shí)是一個(gè)語法糖墨微，那么它的本質(zhì)是什么呢，我們把它編譯成sil的代碼來看一下

// main
sil [ossa] @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  alloc_global @$s4main4numsSaySiGvp              // id: %2
  // 省略部分代碼
  %49 = alloc_stack $Array<Int>                   // users: %53, %52, %50
  store %48 to [init] %49 : $*Array<Int>          // id: %50
  %51 = witness_method $Array<Int>, #Sequence.makeIterator : <Self where Self : Sequence> (__owned Self) -> () -> Self.Iterator : $@convention(witness_method: Sequence) <τ_0_0 where τ_0_0 : Sequence> (@in τ_0_0) -> @out τ_0_0.Iterator // user: %52
  %52 = apply %51<[Int]>(%47, %49) : $@convention(witness_method: Sequence) <τ_0_0 where τ_0_0 : Sequence> (@in τ_0_0) -> @out τ_0_0.Iterator
  dealloc_stack %49 : $*Array<Int>                // id: %53
  br bb1                                          // id: %54

bb1:                                              // Preds: bb3 bb0
  %55 = alloc_stack $Optional<Int>                // users: %61, %60, %58
  %56 = begin_access [modify] [unknown] %47 : $*IndexingIterator<Array<Int>> // users: %59, %58
  %57 = witness_method $IndexingIterator<Array<Int>>, #IteratorProtocol.next : <Self where Self : IteratorProtocol> (inout Self) -> () -> Self.Element? : $@convention(witness_method: IteratorProtocol) <τ_0_0 where τ_0_0 : IteratorProtocol> (@inout τ_0_0) -> @out Optional<τ_0_0.Element> // user: %58
  %58 = apply %57<IndexingIterator<Array<Int>>>(%55, %56) : $@convention(witness_method: IteratorProtocol) <τ_0_0 where τ_0_0 : IteratorProtocol> (@inout τ_0_0) -> @out Optional<τ_0_0.Element>
  end_access %56 : $*IndexingIterator<Array<Int>> // id: %59
  %60 = load [trivial] %55 : $*Optional<Int>      // user: %62
  dealloc_stack %55 : $*Optional<Int>             // id: %61
  switch_enum %60 : $Optional<Int>, case #Optional.some!enumelt: bb3, case #Optional.none!enumelt: bb2 // id: %62

• 我們可以看到在%51行扁掸，調(diào)用了Sequence.makeIterator方法翘县，創(chuàng)建一個(gè)Iterator，把數(shù)組傳給迭代器也糊。
• 在%57行炼蹦，調(diào)用IteratorProtocol.next方法，將數(shù)組元素遍歷出來狸剃。

Sequence與IteratorProtocol

• 我們來Sequence.swift這個(gè)文件掐隐，查看Sequence定義

public protocol Sequence {
  // 可在協(xié)議實(shí)現(xiàn)后確定協(xié)議類型
  associatedtype Element

  associatedtype Iterator: IteratorProtocol where Iterator.Element == Element
  
  // 獲取一個(gè)迭代器
  /// Returns an iterator over the elements of this sequence.
  __consuming func makeIterator() -> Iterator

  // 省略其他方法
}

• 在該協(xié)議中，最重要的就是創(chuàng)建了一個(gè)迭代器

• 查看一下IteratorProtocol定義

public protocol IteratorProtocol {
    /// The type of element traversed by the iterator.
    associatedtype Element

    mutating func next() -> Self.Element?
}

• 它有一個(gè)next方法钞馁，可以通過調(diào)用next方法來返回元素虑省。
• 所以我們每次在使用 for..in 的時(shí)候，其實(shí)都是 通過sequence創(chuàng)建一個(gè)迭代器僧凰，用這個(gè)集合的迭代器來遍歷當(dāng)前集合或者序列當(dāng)中的元素

自己定義一個(gè)遵循Sequence的結(jié)構(gòu)體

• 自定義可迭代結(jié)構(gòu)體

struct TestSequence: Sequence {
    typealias Element = Int
    typealias Iterator = TestIterator
    let count: Int
    
    // MARK: - initialization
    init(count: Int) {
        self.count = count
    }
    
    func makeIterator() -> TestIterator {
        return TestIterator(sequece: self)
    }
}

struct TestIterator: IteratorProtocol {
    typealias Element = Int
    let sequece: TestSequence
    var count = 0
    
    // MARK: - initialization
    init(sequece: TestSequence) {
        self.sequece = sequece
    }
    
    mutating func next() -> Int? {
        guard count < sequece.count else {
            return nil
        }
        count += 1
        return count
    }
}

let seq = TestSequence(count: 5)
for element in seq {
    print(element)
}

打印結(jié)果：

1

2

3

4

5

Collection

• Collection協(xié)議實(shí)現(xiàn)了Sequence協(xié)議探颈，為有限的序列提供下標(biāo)訪問的能力，同時(shí)增加了count屬性训措，自定義索引等特性伪节。

• Collection是一個(gè)序列，其元素可以被多次遍歷绩鸣。通過定義startIndex和endIndex屬性怀大，表示集合起始和結(jié)束位置。

• 我們看一下colletcion定義

public protocol Collection: Sequence {
  // FIXME: ideally this would be in MigrationSupport.swift, but it needs
  // to be on the protocol instead of as an extension
  @available(*, deprecated/*, obsoleted: 5.0*/, message: "all index distances are now of type Int")
  typealias IndexDistance = Int  

  // FIXME: Associated type inference requires this.
  override associatedtype Element

  associatedtype Index: Comparable

  var startIndex: Index { get } 

  var endIndex: Index { get }

  // sequence協(xié)議的實(shí)現(xiàn)
  associatedtype Iterator = IndexingIterator<Self>

  override __consuming func makeIterator() -> Iterator

  associatedtype SubSequence: Collection = Slice<Self>
  where SubSequence.Index == Index,
        Element == SubSequence.Element,
        SubSequence.SubSequence == SubSequence

  func index(after i: Index) -> Index
   
  // 省略部分方法
}

• 遵循Collection協(xié)議呀闻，此時(shí)我們就需要實(shí)現(xiàn) startIndex化借、endIndex 和 index(after:) 方法，index(after:) 是為了便于移動(dòng)當(dāng)前索引的位置捡多。

mutableCollection

• mutableCollection定義

public protocol MutableCollection: Collection
where SubSequence: MutableCollection
{
  // FIXME: Associated type inference requires these.
  override associatedtype Element
  override associatedtype Index
  override associatedtype SubSequence

  @_borrowed
  override subscript(position: Index) -> Element { get set }

  override subscript(bounds: Range<Index>) -> SubSequence { get set }

  mutating func partition(
    by belongsInSecondPartition: (Element) throws -> Bool
  ) rethrows -> Index

  mutating func swapAt(_ i: Index, _ j: Index)
  
  mutating func _withUnsafeMutableBufferPointerIfSupported<R>(
    _ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R
  ) rethrows -> R?

  mutating func withContiguousMutableStorageIfAvailable<R>(
    _ body: (inout UnsafeMutableBufferPointer<Element>) throws -> R
  ) rethrows -> R?
}

• 遵循該協(xié)議蓖康，實(shí)現(xiàn)了下標(biāo)的setter方法，便于在語法上直接通過下標(biāo)來訪問并修改這個(gè)元素的值垒手。

RangeReplaceableCollection

• RangeReplaceableCollection允許集合修改任意區(qū)間的元素

public protocol RangeReplaceableCollection: Collection
  where SubSequence: RangeReplaceableCollection {
  // FIXME: Associated type inference requires this.
  override associatedtype SubSequence

  /// Creates a new, empty collection.
  init()

  mutating func replaceSubrange<C>(
    _ subrange: Range<Index>,
    with newElements: __owned C
  ) where C: Collection, C.Element == Element

  mutating func reserveCapacity(_ n: Int)

  init(repeating repeatedValue: Element, count: Int)

  init<S: Sequence>(_ elements: S)
    where S.Element == Element

  mutating func append(_ newElement: __owned Element)

  mutating func append<S: Sequence>(contentsOf newElements: __owned S)
    where S.Element == Element

  mutating func insert(_ newElement: __owned Element, at i: Index)
 
  @discardableResult
  mutating func remove(at i: Index) -> Element

  mutating func removeSubrange(_ bounds: Range<Index>)

  mutating func _customRemoveLast() -> Element?

  mutating func _customRemoveLast(_ n: Int) -> Bool

  @discardableResult
  mutating func removeFirst() -> Element

  mutating func removeFirst(_ k: Int)

  mutating func removeAll(keepingCapacity keepCapacity: Bool /*= false*/)

  // 省略部分方法
}

• 除此之外還有很多針對(duì)集合的協(xié)議蒜焊，比如說BidirectionalCollection可以向前或向后遍歷集合;RandomAccessCollection可以任意訪問集合元素等。
• 根據(jù)功能的不同劃分科贬，定義在不同的協(xié)議里面山涡，符合借口單一原則，通過協(xié)議的組合，可以達(dá)到不同復(fù)雜度的集合鸭丛。