一：Sequence

對于 Sequence 協(xié)議來說赖瞒，表達(dá)的是既可以是一個(gè)有限的集合擒抛，也可以是一個(gè)無限的集合坯苹，而它只需要提供集合中的元素，和如何訪問這些元素的接口即可幻碱。

Sequence和Collection的關(guān)系.png

1.1 迭代器 Iterator

Sequence 是通過迭代器 Iterator 來訪問元素的阐肤，那么什么是迭代器劫笙？直接來看 for..in 函數(shù)

let numbers = [1, 2, 3, 4]

for num in numbers {
    print(num)
}

for..in 函數(shù)其實(shí)是一種語法糖晾浴，他的本質(zhì)是怎么去調(diào)用的呢？編譯成 SIL 并定位到 main 函數(shù)中 for..in 的調(diào)用不重要的代碼我就直接省略了

// main
sil @main : $@convention(c) (Int32, UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>) -> Int32 {
bb0(%0 : $Int32, %1 : $UnsafeMutablePointer<Optional<UnsafeMutablePointer<Int8>>>):
  ...
  // function_ref Collection<>.makeIterator()
  %36 = function_ref @$sSlss16IndexingIteratorVyxG0B0RtzrlE04makeB0ACyF : $@convention(method) <τ_0_0 where τ_0_0 : Collection, τ_0_0.Iterator == IndexingIterator<τ_0_0>> (@in τ_0_0) -> @out IndexingIterator<τ_0_0> // user: %37
  %37 = apply %36<Array<Int>>(%31, %34) : $@convention(method) <τ_0_0 where τ_0_0 : Collection, τ_0_0.Iterator == IndexingIterator<τ_0_0>> (@in τ_0_0) -> @out IndexingIterator<τ_0_0>
  %38 = tuple ()
  dealloc_stack %34 : $*Array<Int>                // id: %39
  br bb1                                          // id: %40

bb1:                                              // Preds: bb3 bb0
  %41 = alloc_stack $Optional<Int>                // users: %47, %44, %48
  %42 = begin_access [modify] [static] %31 : $*IndexingIterator<Array<Int>> // users: %44, %46
  // function_ref IndexingIterator.next()
  %43 = function_ref @$ss16IndexingIteratorV4next7ElementQzSgyF : $@convention(method) <τ_0_0 where τ_0_0 : Collection> (@inout IndexingIterator<τ_0_0>) -> @out Optional<τ_0_0.Element> // user: %44
  %44 = apply %43<Array<Int>>(%41, %42) : $@convention(method) <τ_0_0 where τ_0_0 : Collection> (@inout IndexingIterator<τ_0_0>) -> @out Optional<τ_0_0.Element>
  %45 = tuple ()
  end_access %42 : $*IndexingIterator<Array<Int>> // id: %46
  ...
} // end sil function 'main'

• // function_ref Collection<>.makeIterator()
%36 = function_ref @$sSlss16IndexingIteratorVyxG0B0RtzrlE04makeB0ACyF : $@convention(method) <τ_0_0 where τ_0_0 : Collection, τ_0_0.Iterator == IndexingIterator<τ_0_0>> (@in τ_0_0) -> @out IndexingIterator<τ_0_0> // user: %37
  這里我們可以看到調(diào)用了一個(gè) makeIterator() 的方法榜田，這個(gè)方法需要兩個(gè)參數(shù)一個(gè)是在上文中創(chuàng)建 的 IndexingIterator , 一個(gè)是 Array 的引用益兄。
• // function_ref IndexingIterator.next()
%43 = function_ref @$ss16IndexingIteratorV4next7ElementQzSgyF : $@convention(method) <τ_0_0 where τ_0_0 : Collection> (@inout IndexingIterator<τ_0_0>) -> @out Optional<τ_0_0.Element> // user: %44
  這里調(diào)用 IndexingIterator 的 next() 方法來遍歷數(shù)組中一個(gè)又一個(gè)的元素。
  因此可以發(fā)現(xiàn)執(zhí)行 for..in 的時(shí)候箭券，本質(zhì)上會(huì)通過 Collection 創(chuàng)建一個(gè)迭代器 Iterator净捅，然后把當(dāng)前的數(shù)組傳給迭代器 Iterator，最后調(diào)用迭代器 Iterator 的 next 方法將數(shù)組的元素遍歷出來邦鲫。

接著我們打開 Swift源碼 定位到 collection.swift 中的 IndexingIterator

@frozen
public struct IndexingIterator<Elements: Collection> {
  @usableFromInline
  internal let _elements: Elements
  @usableFromInline
  internal var _position: Elements.Index

  /// Creates an iterator over the given collection.
  @inlinable
  @inline(__always)
  public /// @testable
  init(_elements: Elements) {
    self._elements = _elements
    self._position = _elements.startIndex
  }

  /// Creates an iterator over the given collection.
  @inlinable
  @inline(__always)
  public /// @testable
  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>

  @inlinable
  @inline(__always)
  public mutating func next() -> Elements.Element? {
    if _position == _elements.endIndex { return nil }
    let element = _elements[_position]
    _elements.formIndex(after: &_position)
    return element
  }
}

可以看見 IndexingIterator 是一個(gè)接收泛型參數(shù) Collection 的結(jié)構(gòu)體灸叼，并且這個(gè)結(jié)構(gòu)體遵循了兩個(gè)協(xié)議，分別是 IteratorProtocol 和 Sequence 庆捺。 IteratorProtocol 是一個(gè)一次提供一個(gè)序列值的類型古今， 它和 Sequence 協(xié)議是息息相關(guān)的， 每次通過創(chuàng)建迭代器來訪問序列中的元素滔以。
所以我們每次在使用 for..in 的時(shí)候捉腥，其實(shí)都是使用這個(gè)集合的迭代器來遍歷當(dāng)前集合或者序列當(dāng)中的元素。

1.2 IteratorProtocol協(xié)議

在 sequence.swift 文件中定位到 IteratorProtocol

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

  mutating func next() -> Element?
}

可以看到有一個(gè)關(guān)聯(lián)類型你画，實(shí)現(xiàn)該協(xié)議時(shí)需要執(zhí)行 Element 的類型抵碟，還有一個(gè) next() 函數(shù)返回的是這個(gè)關(guān)聯(lián)類型桃漾。

1.3 Sequence協(xié)議

接著在 sequence.swift 文件中 定位到 Sequence

public protocol Sequence {
  /// A type representing the sequence's elements.
  associatedtype Element

  /// A type that provides the sequence's iteration interface and
  /// encapsulates its iteration state.
  associatedtype Iterator: IteratorProtocol where Iterator.Element == Element

  /// A type that represents a subsequence of some of the sequence's elements.
  // associatedtype SubSequence: Sequence = AnySequence<Element>
  //   where Element == SubSequence.Element,
  //         SubSequence.SubSequence == SubSequence
  // typealias SubSequence = AnySequence<Element>

  /// Returns an iterator over the elements of this sequence.
  __consuming func makeIterator() -> Iterator

  ...
}

• 可以看到這里也是有一個(gè)關(guān)聯(lián)類型 Element
• 還有一個(gè)關(guān)聯(lián)類型 Iterator 并且 Iterator 要遵循 IteratorProtocol 協(xié)議并且 Iterator 對于協(xié)議 IteratorProtocol 的關(guān)聯(lián)類型要與 Sequence 的關(guān)聯(lián)類型相等
• 有一個(gè)創(chuàng)建迭代器的方法 makeIterator() 返回當(dāng)前關(guān)聯(lián)類型 Iterator (這個(gè)就類似與車間一樣，Iterator 就是一條流水線)
  因此對于 Sequence 協(xié)議來說拟逮，表達(dá)的是既可以是一個(gè)有限的集合撬统，也可以是一個(gè)無限的集合，而它只需要提供集合中的元素敦迄，和如何訪問這些元素的接口即可恋追。

1.4 通過Sequence協(xié)議自定義有限的集合

直接上代碼

struct MyIterator: IteratorProtocol {
    typealias Element = Int
    
    let seq: MySequence
    
    init(_ seq: MySequence) {
        self.seq = seq
    }
    
    var count = 0
    
    // 對于迭代器來說要遍歷當(dāng)前 `sequence` 中的元素
    mutating func next() -> Int? {
        guard count < self.seq.arrayCount else {
            return nil
        }
        count += 1
        return count
    }
}

struct MySequence: Sequence {
    typealias Element = Int
    
    var arrayCount: Int
    
    // 對于 sequence 來說需要一個(gè)迭代器
    func makeIterator() -> MyIterator {
        return MyIterator.init(self)
    }
}


var seq = MySequence(arrayCount: 10)

for element in seq {
    print(element)
}

打印結(jié)果：
1
2
3
4
5
6
7
8
9
10

對于 sequence 來說需要一個(gè)迭代器，而對于對于迭代器來說要遍歷當(dāng)前 sequence 中的元素罚屋，所以需要 MyIterator 提供一個(gè)遍歷的構(gòu)造函數(shù) init(_ seq: MySequence)
同樣的我們也可以創(chuàng)建一個(gè)無限的序列苦囱，但是在實(shí)際開發(fā)當(dāng)中一般不會(huì)出現(xiàn)這種場景，所以這里就不繼續(xù)了脾猛。

二：Collection

2.1 環(huán)形數(shù)組

環(huán)形數(shù)組是一種用于表示一個(gè)頭尾相連的緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)撕彤。跟環(huán)形隊(duì)列差不多。接下來通過 Collection 來表達(dá)一個(gè)環(huán)形數(shù)組猛拴。

// 參照源碼
extension FixedWidthInteger {
    /// Returns the next power of two.
    @inlinable
    func nextPowerOf2() -> Self {
        guard self != 0 else {
            return 1
        }

        return 1 << (Self.bitWidth - (self - 1).leadingZeroBitCount)
    }
}


struct RingBuffer <Element>{
    
    //ContiguousArray 可以理解為存粹的 Swift 的數(shù)組羹铅。和 OC 沒有任何關(guān)系的數(shù)組，它的效率比 Array 更快漆弄。
    internal var _buffer: ContiguousArray<Element?>
    internal var headIndex: Int = 0
    internal var tailIndex: Int = 0

    internal var mask: Int{
        return self._buffer.count - 1
    }

    // 初始化方法
    init(initalCapacity: Int) {
        let capcatiy = initalCapacity.nextPowerOf2()

        self._buffer = ContiguousArray<Element?>.init(repeating: nil, count:capcatiy)
    }

    // 移動(dòng)環(huán)形數(shù)組的尾
    mutating func advancedTailIndex(by: Int){
        self.tailIndex = self.indexAdvanced(index: self.tailIndex, by: by)
    }

    // 移動(dòng)環(huán)形數(shù)組的頭
    mutating func advancedHeadIndex(by: Int){
        self.headIndex = self.indexAdvanced(index: self.headIndex, by: by)
    }

    // 獲取元素下標(biāo)
    func indexAdvanced(index: Int, by: Int) -> Int{
        return (index + by) & self.mask
    }

    // 添加新元素
    mutating func append(_ value: Element){
        _buffer[self.tailIndex] = value
        self.advancedTailIndex(by: 1)

        if self.tailIndex == self.headIndex {
            fatalError("out of bounds")
        }
    }

    // 讀取元素
    mutating func read() -> Element?{
        let element = _buffer[self.headIndex]
        self.advancedHeadIndex(by: 1)
        return element
    }
}

這個(gè)結(jié)構(gòu)體通過一個(gè) ContiguousArray 類型的 _buffer 來記錄環(huán)形數(shù)組的元素睦裳，ContiguousArray 可以理解為存粹的 Swift 的數(shù)組造锅。和 OC 沒有任何關(guān)系的數(shù)組撼唾，它的效率比 Array 更快。

并且通過 headIndex 和 tailIndex 來表示環(huán)形數(shù)組的起始和結(jié)束的位置哥蔚。以及一些方法倒谷。

在初始化方法中 nextPowerOf2 這個(gè)方法表示 2^n，這個(gè)表示使 capacity 始終為 2^n糙箍。

2.2 MutableCollection

MutableCollection 允許集合通過下標(biāo)修改自身元素渤愁。對于 MutableCollection 需要

• 定義 startIndex 和 endIndex 屬性，表示集合起始和結(jié)束位置
• 定義一個(gè)只讀的下標(biāo)操作符
• 實(shí)現(xiàn)一個(gè) index(after:) 方法用于在集合中移動(dòng)索引位置

extension RingBuffer: Collection, MutableCollection {
    var startIndex: Int{
        return self.headIndex
    }

    var endIndex: Int{
        return self.tailIndex
    }

    subscript(position: Int) -> Element? {
        get{
            return self._buffer[position]
        }
        set{
            self._buffer[position] = newValue
        }
    }

    // 移動(dòng)當(dāng)前索引的位置
    func index(after i: Int) -> Int {
        return (i + 1) & self.mask
    }
}

這里實(shí)現(xiàn)了 subscript 的 get 和 set 深夯，對于 Collection 來說可以不提供 set ,這個(gè)時(shí)候我們就沒有辦法通過下標(biāo)的方式改變自身元素了抖格，所以對 MutableColletion 來說下標(biāo)語法提供一個(gè) setter 就行。就好比

var array = [1, 2, 3, 4]
array[1] = 5

這里直接通過下標(biāo)修改元素

2.3 RangeReplaceableCollection

RangeReplaceableCollection 允許集合修改任意區(qū)間的元素咕晋。對于 RangeReplaceableCollection 我們需要提供一個(gè)默認(rèn)的 init 方法雹拄。其他的如果不需要 RangeReplaceableCollection 都有默認(rèn)的實(shí)現(xiàn)。

extension RingBuffer: RangeReplaceableCollection {
    
    init() {
        self.init(initalCapacity: 10)
    }

    mutating func remove(at i: Int) -> Element? {
        var currentIndex = i
        let element = _buffer[i]
        self._buffer[currentIndex] = nil
        
        switch i {
        case self.headIndex:
            self.advancedHeadIndex(by: 1)
        default:
            var nextIndex = self.indexAdvanced(index: i, by: 1)
            while nextIndex != self.tailIndex {
                self._buffer.swapAt(currentIndex, nextIndex)
                currentIndex = nextIndex
                nextIndex = self.indexAdvanced(index: currentIndex, by: 1)
            }
        }
        return element
    }
}

對于環(huán)形數(shù)組來說這里的 remove 方法：首先都是把當(dāng)前位置的元素刪除掌呜，然后根據(jù)刪除的位置來進(jìn)行判斷

• 當(dāng)刪除的位置剛好是 headIndex 的位置滓玖，那么就將 headIndex 往后移動(dòng)一個(gè)位置。
• 不是 headIndex 的位置质蕉，就需要將后面的元素往前移一個(gè)位置势篡，然后再把尾節(jié)點(diǎn)指向當(dāng)前空閑節(jié)點(diǎn)的位置翩肌。

2.4 BidirectionalCollection

BidirectionalCollection 可以向前或向后遍歷集合。 比如可以獲取最后一個(gè)元素禁悠、反轉(zhuǎn)序列念祭、快速的獲取倒序等等。既然正序是通過 subscript 和 index(after:) 來實(shí)現(xiàn)的碍侦，那么倒序添加一個(gè) index(before:) 就可以往前遞歸了棒卷，這就好像雙向鏈表 Remove 一樣，只不過雙向鏈表獲取的是值祝钢，而這里的集合獲取的都是索引比规。

extension RingBuffer: BidirectionalCollection{
    func index(before i: Int) -> Int {
        return (i - 1) & self.mask
    }
}

2.5 RandomAccessCollection

RandomAccessCollection 任意訪問集合元素。對于 RandomAccessCollection 需要實(shí)現(xiàn) index(_:offsetBy:) 和 distance(from:to:)

extension RingBuffer: RandomAccessCollection{
    func index(_ i: Int, offsetBy distance: Int) -> Int {
        return (i + distance) & self.mask
    }

    func distance(from start: Int, to end: Int) -> Int {
        return end - start
    }
}

當(dāng)然拦英，對于這個(gè)集合 (RingBuffer) 我們不去實(shí)現(xiàn)也是可以的蜒什。因?yàn)槲覀儼?index(after:) 和 index(before:) 已經(jīng)實(shí)現(xiàn)了，對于系統(tǒng)來說疤估，它是可以通過這兩個(gè)方法來推斷當(dāng)前要移動(dòng)的距離灾常。但是考慮到效率的問題，在這里直接實(shí)現(xiàn)會(huì)比系統(tǒng)去推斷要好得多铃拇，因?yàn)橹苯邮∪チ讼到y(tǒng)推斷的時(shí)間钞瀑。

使用示例代碼

var buffer: RingBuffer = RingBuffer<Int>.init(initalCapacity: 10)
for i in 0..<10 {
    buffer.append(i)
}

print(buffer.index(0, offsetBy: 5))

打印結(jié)果:
5