集合

這里的集合指的是建立在Sequence協(xié)議上的Collection協(xié)議。
集合是穩(wěn)定的序列，可以重復遍歷而不會發(fā)生變化，除了遍歷還可以使用下標訪問，swift的下標不一定是整數(shù)，但一定是一個有限的范圍，因此集合不能是無限的，如此，集合也產(chǎn)生了長度的屬性count。

通過定義一個集合類型來理解Collection如何工作。
首先設計一個隊列協(xié)議：

protocol Queue{
    //聲明類型
    associatedtype Element
    //入隊
    mutating func enqueue(_ newElement:Element)
    //出隊
    mutating func dequeue() -> Element?
}

從這里能夠感受swift特性的冰山一角，這個協(xié)議就三行代碼，協(xié)議越簡單，工作范圍越大，使用越不受約束，效率可能就越低，因此如何使用非常關鍵，Xcode documentation里，swift協(xié)議的文檔有大量的注釋，其中還有很多demo，為的就是給出使用建議。
比如這個Squeue協(xié)議，我們可以建議入隊和出隊的復雜度需要是O(1),這就限制了可以使用這個協(xié)議的數(shù)據(jù)結(jié)構(gòu)。僅僅2個方法，能夠表達的功能太少，比如它沒有peek方法來獲取某個元素，只能按順序出隊，也沒有限制必須是Collection，甚至沒有限制它是FIFO先進先出還是LIFO后進先出等等。

接下來實現(xiàn)隊列

struct FIFOQueue<Element>:Queue{
    
    private var left:[Element] = []
    private var right:[Element] = []
 
    mutating func enqueue(_ newElement: Element) {
        right.append(newElement)
    }
    
    mutating func dequeue() -> Element? {
        if left.isEmpty{
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

這個實現(xiàn)使用兩個棧 (兩個常規(guī)的數(shù)組) 來模擬隊列的行為。當元素入隊時，它們被添加到 “右”
棧中。當元素出隊時，它們從 “右” 棧的反序數(shù)組的 “左” 棧中被彈出。當左棧變?yōu)榭諘r，再將右
棧反序后設置為左棧。

接下來實現(xiàn)Collection協(xié)議

protocol Collection: Sequence {
    associatedtype Element // inherited from Sequence
    associatedtype Index: Comparable
    associatedtype IndexDistance: SignedInteger = Int
    associatedtype Iterator: IteratorProtocol = IndexingIterator<Self>
where Iterator.Element == Element
    associatedtype SubSequence: Sequence /* ... */
    associatedtype Indices: Sequence = DefaultIndices<Self>
    /* ... */
    var frst: Element? { get }
    var indices: Indices { get }
    var isEmpty: Bool { get }
    var count: IndexDistance { get }
    func makeIterator() -> Iterator
    func prefx(through: Index) -> SubSequence
    func prefx(upTo: Index) -> SubSequence
    func suffx(from: Index) -> SubSequence
    func distance(from: Index, to: Index) -> IndexDistance
    func index(_: Index, offsetBy: IndexDistance) -> Index
    func index(_: Index, offsetBy: IndexDistance, limitedBy: Index) -> Index?
    subscript(position: Index) -> Element { get }
    subscript(bounds: Range<Index>) -> SubSequence { get }
}

Collection協(xié)議有這么多的內(nèi)容，不過很多都在extension中有默認實現(xiàn) ，最終只需要實現(xiàn)下面這些方法

extension FIFOQueue: Collection {
    /// ?個?空集合中?個元素的位置
    public var startIndex: Int { return 0 }
    /// 集合中超過末位的位置---也就是?最后?個有效下標值? 1 的位置
    public var endIndex: Int { return left.count + right.count }
    /// 返回在給定索引之后的那個索引值
    public func index(after i: Int) -> Int { precondition(i < endIndex)
        return i + 1
    }
    /// 訪問特定位置的元素
    public subscript(position: Int) -> Element {
        precondition((0..<endIndex).contains(position), "Index out of bounds")
        if position < left.endIndex {
            return left[left.count - position - 1]
        } else {
            return right[position - left.count]
        }
    }
}

重點在于下標方法 ，left和right兩個數(shù)組加起來保存這完整的隊列元素，需要根據(jù)不同的情況考慮從哪個數(shù)組取數(shù)據(jù)，現(xiàn)在來驗證一下

var q = FIFOQueue<String>()
        for x in ["a","b","c","d","e"]{
            q.enqueue(x)
        }
        q.forEach { s in
            print(s)
        }
        print("出隊 \(q.dequeue()!)")
        q.forEach { s in
            print(s)
        }
        print("入隊")
        q.enqueue("f")
        q.forEach { s in
            print(s)
        }
        print("出隊 \(q.dequeue()!)")
        q.forEach { s in
            print(s)
        }

輸出結(jié)果
a
b
c
d
e
出隊 a
b
c
d
e
入隊
b
c
d
e
f
出隊 b
c
d
e
f

實現(xiàn)ExpressibleByArrayLiteral的方法 直接字面量初始化

extension FIFOQueue : ExpressibleByArrayLiteral{
    typealias ArrayLiteralElement = Element
    public init(arrayLiteral elements: ArrayLiteralElement...) {
        left = elements.reversed()
        right = []
    }
}

var q:FIFOQueue = ["a","b","c","d","e"]

索引

索引表示集合中的位置，從上面可以看到，集合有兩個特殊索引，startIndex和endIndex，前者是第一個元素，后者是最后一個元素的下一個位置，也就是endIndex不是有效的下標。
索引一半都是整數(shù)，但這不是唯一的選擇，只要具有一定順序，遵循Comparable就可以。
字典也有索引，類型是DictionaryIndex，根據(jù)鍵訪問字典，得到一個value，而通過索引訪問字典，得到一個元組(key: Key, value: Value)
需要注意的是，Collection定義了索引訪問的方法 ，它返回一個非可選的值，哪怕可能會引起crash，因為錯誤的使用索引值，被認為是程序員的錯誤。通過key訪問字典獲取的是一個可選值，而通過DictionaryIndex獲得元組是非可選。
swift的安全檢查選擇了一個合適的范圍，如果所有的API都要考慮失敗，那就太折磨了

集合發(fā)生變化時，索引可能會失效，比如錯位，或者crash，但是字典不太一樣
字典的索引不會隨著新的鍵值對的加入而失效，直到字典的尺寸增大到觸發(fā)重新的內(nèi)存分配。
這是因為一般情況下字典存儲的緩沖區(qū)內(nèi)的元素位置是不會改變的，而在元素超過緩沖區(qū)尺寸
時，緩沖區(qū)會被重新分配，其中的所有元素的哈希值也會被重新計算。從字典中移除元素總是
會使索引失效。

關聯(lián)類型，SubSequence是繼承自Sequence，Collection對SubSequence添加了更詳細的擴展，一個集合類型的 SubSequence 本身也應該是一個 Collection,比如String的關聯(lián)類型SubString

自定義集合索引
作為非整數(shù)索引集合的例子，我們將會構(gòu)建一種在字符串中迭代單詞的方式。當你想要將一個
字符串分割成一個個的單詞，最簡單的方法就是使用
split(separator:maxSplits:omittingEmptySubsequences:) (當然，這是對英文而言)，這個方
法將使用提供的分割元素進行分割，把一個集合轉(zhuǎn)變?yōu)槠?SubSequence 的數(shù)組，它有一個缺點：這個方法將會熱心地為你計算出整個數(shù)組。如果你的字符串非常大，而且你只
需要前幾個詞的話，這么做是相當?shù)托У摹榱颂岣咝阅埽覀円獦?gòu)建一個 Words 集合，它能
夠讓我們不一次性地計算出所有單詞，而是可以用延遲加載的方式進行迭代。

實現(xiàn)方案
定義一個從文章中查找單詞的索引方法，首先把開頭的空格都去掉，然后尋找下一個空格作為結(jié)束，最后返回一個Range

extension Substring {
    var nextWordRange: Range<Index> {
        let start = drop(while: { $0 == " "})
        let end = start.firstIndex(where: { $0 == " "}) ?? endIndex
        return start.startIndex..<end
    }
}

struct WordsIndex: Comparable {
    fileprivate let range: Range<Substring.Index>
    fileprivate init(_ value: Range<Substring.Index>) {
        self.range = value
    }
    static func <(lhs: Words.Index, rhs: Words.Index) -> Bool {
        return lhs.range.lowerBound < rhs.range.lowerBound
    }
    static func ==(lhs: Words.Index, rhs: Words.Index) -> Bool {
        return lhs.range == rhs.range
    }
}

struct Words: Collection {
    let string: Substring
    let startIndex: WordsIndex
    init(_ s: String) {
        self.init(s[...])
    }
    private init(_ s: Substring) {
        self.string = s
        self.startIndex = WordsIndex(string.nextWordRange)
    }
    var endIndex: WordsIndex {
        let e = string.endIndex
        return WordsIndex(e..<e)
    }
    
    subscript(index: WordsIndex) -> Substring {
        return string[index.range]
    }
    
    func index(after i: WordsIndex) -> WordsIndex {
        guard i.range.upperBound < string.endIndex else { return endIndex }
        let remainder = string[i.range.upperBound...]
        return WordsIndex(remainder.nextWordRange)
    }
}

collection要求索引訪問元素應該是O(1)，如果使用整數(shù)的索引，在獲取第i個的時候，我們需要把整個字符串都處理好，然后取出第i個。
將 Range<Substring.Index> 進行包裝，然后用它來作為索引類型，另外由于Comparable基于Equatable，所以還需要實現(xiàn)==方法
現(xiàn)在使用單詞的range來作為索引訪問words集合，就是O(1)的復雜度，類似于String的索引。

切片

切片已經(jīng)在字符串操作中頻繁使用了，雖然語法有些啰嗦。
所有的集合類型都有切片操作的默認實現(xiàn)，并且有一個接受Range<Index> 作為參數(shù)的下標方法。

切片與原集合共享索引，這一點比較違反直覺，但是又覺著合理

let cities = ["New York", "Rio", "London", "Berlin", "Rome", "Beijing", "Tokyo", "Sydney"]
let slice = cities[2...4]
cities.startIndex // 0 
cities.endIndex // 8 
slice.startIndex // 2 
slice.endIndex // 5

如果訪問slice[0],就會crash，因為slice的startIndex是2，沒有0，因此swift不建議使用索引的值（for index in collection.indices）來作為訪問依據(jù)，應當盡可能始終選擇for x in collection 的形式。另外如果需要在迭代的時候修改集合的內(nèi)容，可以選擇使用while循環(huán)，然后手動在每次迭代的時候增加索引值，這樣你就不會用到 indices 屬性。當你這么做的時候，要記住一定要從collection.startIndex 開始進行循環(huán)，而不要把 0 作為開始。

專門的集合類型

1.雙向索引
BidirectionalCollection 在前向索引的基礎上只增加了一個方法，但是它非常關鍵，那就是獲取上一個索引值的 index(before:)，用它可以獲取last元素，

extension BidirectionalCollection { 
/// 集合中的最后?個元素。
 public var last: Element? { 
        return isEmpty ? nil : self[index(before: endIndex)] 
    }
 }

BidirectionalCollection 還添加了一些高效的實現(xiàn)，比如 suf?x，removeLast 和 reversed。這里的 reversed 方不會直接將集合反轉(zhuǎn)，而是返回一個延時加載的表示方式

extension BidirectionalCollection { 
    /// 返回集合中元素的逆序表示?式似乎數(shù)組 
    /// - 復雜度: O(1) 
    public func reversed() -> ReversedCollection<Self> {
         return ReversedCollection(_base: self)
     }
 }

和上面 Sequence 的 enumerated 封裝一樣，它不會真的去將元素做逆序操作。ReverseCollection 會持有原來的集合，并且使用逆向的索引。集合會將所有索引遍歷方法逆序，這樣一來就可以通過前向遍歷來在原來的集合中進行后向遍歷了，相反也一樣。

2.隨機存取的集合類型
RandomAccessCollection 提供了最高效的元素存取方式，它能夠在常數(shù)時間內(nèi)跳轉(zhuǎn)到任意索
引。要做到這一點，滿足該協(xié)議的類型必須能夠 (a) 以任意距離移動一個索引，以及 (b) 測量任
意兩個索引之間的距離，兩者都需要是 O(1) 時間常數(shù)的操作。

3.可變集合支持原地的元素更改
MutableCollection 增加了一個要求，單個元素的下標訪問方法 subscript 現(xiàn)在必須提供一個 setter。
標準庫中很少有滿足 MutableCollection 的類型。在三個主要的集合類型中，只有Array 滿足這個協(xié)議。MutableCollection 允許改變集合中的元素值，但是它不允許改變集合的?度或者元素的順序。后面一點解釋了為什么 Dictionary 和 Set 雖然本身當然是可變的數(shù)據(jù)結(jié)構(gòu)，卻不滿足 MutableCollection 的原因。

乍一看讀不懂，實際上就是list[0] = 1這種賦值方法。
給下標訪問添加setter和getter

public subscript(position: Int) -> Element {
  get { 
    precondition((0..<endIndex).contains(position), "Index out of bounds")
     if position < left.endIndex { 
        return left[left.count - position - 1]
     } else { 
        return right[position - left.count]
     } 
  } 
  set { 
    precondition((0..<endIndex).contains(position), "Index out of bounds")
     if position < left.endIndex {
            left[left.count - position - 1] = newValue 
      } else { 
          return right[position - left.count] = newValue 
        }
   }
}

4.添加或者移除元素
對于需要添加或者移除元素的操作，可以使用 RangeReplaceableCollection 協(xié)議。這個協(xié)議有兩個要求：
1.一個空的初始化方法 — 在泛型函數(shù)中這很有用，因為它允許一個函數(shù)創(chuàng)建相同類型的新的空集合。 2.replaceSubrange(_:with:) 方法 — 它接受一個要替換的范圍以及一個用來進行替換的
集合。

extension FIFOQueue: RangeReplaceableCollection { 
    mutating func replaceSubrange<C: Collection>(_ subrange: Range<Int>, with newElements: C) where     C.Element == Element {
     right = left.reversed() + right left.removeAll() right.replaceSubrange(subrange, with: newElements)
    }
 }

這個協(xié)議添加了這些方法
→ append(:) 和 append(contentsOf:) — 將 endIndex..<endIndex (也就是說末尾的空范圍) 替換為單個或多個新的元素。
→ remove(at:) 和 removeSubrange(:) — 將 i...i 或者 subrange 替換為空集合。
→ insert(at:) 和 insert(contentsOf:at:) — 將 i..<i (或者說在數(shù)組中某個位置的空范圍) 替換為單個或多個新的元素。
→ removeAll — 將 startIndex..<endIndex 替換為空集合

Sequence 和 Collection 協(xié)議構(gòu)成了 Swift 集合類型的基礎,從中理解了所謂面向協(xié)議的冰山一角，高層級的抽象會使模型變得復雜，很多東西不容易看明白，但是越看越覺著很????。