集合類型協(xié)議

3.2集合類型:Collection

這一節(jié)只要目的是通過自定義一個FIFO(First Input First Output)的集合去了解一些細節(jié)。

穩(wěn)定的序列(可多次遍歷且保持一致)，可通過下標獲取其中的元素。

知識點1：Collection建立在Sequence協(xié)議之上

知識點2：String，Data，IndexSet也準守了Collection協(xié)議。

知識點3：swift數(shù)組可以當做棧 用append入棧，popLast出棧

注：數(shù)組是在連續(xù)的內(nèi)存中持有元素，移除非末尾元素時，后面的元素都會移動填補空白，復雜度為O(n)。 做類似操作的時候可以從性能方面去考慮一下。

隊列可以結(jié)合使用 push和remove(at:0)

為隊列設計協(xié)議：Iterator

/// 自己寫一個最簡單的將元素入隊和出隊的類型
protocol Queue{
    ///self中所持有的元素類型
    associatedtype Element
    ///把newElement 加入隊列
    mutating func enqueue(_ newElement: Element)
    ///從self出隊一個元素
    /// 返回值是可選值? 隊列為空時這樣的做法是安全的
    mutating func dequeue() -> Element?
}

這就表述了隊列的定義。

隊列的實現(xiàn)

下面我們將準守上面的Queue協(xié)議，寫一個FIFO( First Input First Output)隊列

///FIFO( First Input First Output)
struct FIFOQueue:Queue {
    
    fileprivate var left: [Int] = []
    fileprivate var right: [Int] = []
    
    ///把元素添加到隊尾
    /// 復雜度O(1)
    mutating func enqueue(_ newElement: Int) {
        right.append(newElement)
    }
    
    
    /// 從隊列首部移除一個元素
    /// 隊列為nil時候返回空
    /// - 復雜度： 平攤 O(1)
    mutating func dequeue() -> Int? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

入隊添加到"右",
出隊從"右"的反序"左"中被彈出。 "左"為空時再將"右"反序設置為左(好繞，不太理解的同學可以自己看著代碼把流程走走就很快能理解啦~)

準守Collection協(xié)議

前面我們已經(jīng)有一個FIFO隊列了，下面可以為它添加Collection協(xié)議啦~ 在swift2.0的時候Collection協(xié)議有
4個關聯(lián)類型
4個屬性
7個實例方法
2個下標方法

在swift4.2中有略微改進。。具體可參照Collection 蘋果官方文檔

是不是有點慌。一開始看到的時候我也慌??，其實捏 所有的關聯(lián)類型都有默認值 除非你有特殊需求，一般不用關心的。

下面我們就開始讓我們的FIFO去遵守Collection吧~

extension FIFOQueue:Collection {

    public var startIndex: Int { return 0 }
    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) -> Int {
        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]
        }
    }
}

下面就可以愉快地使用我們創(chuàng)建的FIFOQueue啦~

遵守 ExpressibleByArrayLiteral協(xié)議

ExpressibleByArrayLiteral的主要作用是可以讓對象支持字面量初始化
第一次看這個名詞我也一臉懵。
其實就是讓你的集合可以用[value1, value2, etc]的方式去創(chuàng)建。

extension FIFOQueue:ExpressibleByArrayLiteral{
    ///ExpressibleByArrayLiteral 的init方法去實現(xiàn)一下就ok~ 
    init(arrayLiteral elements: Int...) {
        self.init(left: elements.reversed(), right: [])
    }
}

關聯(lián)類型

Iterator 是從Sequence 繼承的關聯(lián)類型。Iterator 是對集合的封裝，用集合本身的索引去迭代每一個元素。 這里講的比較簡單，可百度，待補充。 (TO BE ENHANCEMENT)

文章源文件地址