集合類型模塊分四篇筆記來學習：
- 第一篇：
- 數(shù)組和可變性
- 數(shù)組的變形
- 第二篇：
- 字典和集合
- 集合協(xié)議
- 第三篇：
- 集合
- 第四篇：
- 索引
本篇開始學習第三篇，Go科吭！
集合
集合協(xié)議 CollectionType 是在序列上構(gòu)建的笋轨，它為序列添加了可重復進行迭代(由于序列是值類型代咸，所以不能單獨進行迭代)氧猬，以及通過索引訪問元素的能力。
為了展示 Swift 的集合類型是如何工作的脆烟，我們將實現(xiàn)一個我們自己的集合類型。隊列 (queue) 是在 Swift 標準庫中不存在房待，但卻又最常用到的容器類型了邢羔。Swift 的數(shù)組可以很容易地被用來實現(xiàn)棧 (stack) 結(jié)構(gòu)，只需要使用 append 入棧和 popLast 出棧就可以了桑孩。但是將數(shù)組作為隊列來使用的話就不那么理想拜鹤。
為隊列設(shè)計協(xié)議
在實際實現(xiàn)隊列之前，我們應(yīng)該先定義它到底是什么流椒。我們可以通過下面定義的協(xié)議來描述隊列的特性：
/// 一個能夠?qū)⒃厝腙牶统鲫牭念愋?protocol QueueType {
/// 在 `self` 中所持有的元素的類型
associatedtype Element
/// 將 `newElement` 入隊到 `self`
mutating func enqueue(newElement: Element)
/// 從 `self` 出隊一個元素
mutating func dequeue() -> Element?”
}
隊列的實現(xiàn)
下面是一個很簡單的隊列署惯，它的 enqueue 和 dequeue 方法是基于一系列數(shù)組來構(gòu)建的。
/// 一個高效的 FIFO 隊列镣隶，其中元素類型為 `Element`
struct Queue<Element>: QueueType {
private var left: [Element]
private var right: [Element]
init() {
left = []
right = []
}
/// 將元素添加到隊列最后极谊，復雜度 O(1)
mutating func enqueue(element: Element) {
right.append(element)
}
/// 從隊列前端移除一個元素，復雜度 O(1).
/// 當隊列為空時安岂，返回 nil
mutating func dequeue() -> Element? {
guard !(left.isEmpty && right.isEmpty) else { return nil }
if left.isEmpty {
left = right.reverse()
right.removeAll(keepCapacity: true)
}
return left.removeLast()
}
至此我們實現(xiàn)了一個最簡單的隊列轻猖，接下來通過分別實現(xiàn)CollectionType、ArrayLiteralConvertible域那、RangeReplaceableCollectionType來擴展Queue咙边。
遵守 CollectionType
CollectionType 是對 Indexable 和 SequenceType 的擴展猜煮。該協(xié)議有兩個關(guān)聯(lián)類型和九個方法。不過败许，這兩個關(guān)聯(lián)類型都有默認值王带，而不少方法也有它們的默認實現(xiàn)。
我們要做的是為 Indexable 協(xié)議中要求的 startIndex 和 endIndex 提供實現(xiàn)市殷，并且實現(xiàn)一個通過下標索引來獲取對應(yīng)索引的元素的方法愕撰。只要我們實現(xiàn)了這三個需求，我們就能讓一個類型遵守 CollectionType 了醋寝。
我們現(xiàn)在已經(jīng)有一個能夠出隊和入隊的容器了搞挣，要將它轉(zhuǎn)變?yōu)橐粋€集合，Queue 需要遵守 CollectionType：
extension Queue: CollectionType {
var startIndex: Int { return 0 }
var endIndex: Int { return left.count + right.count }
subscript(idx: Int) -> Element {
precondition((0..<endIndex).contains(idx), "Index out of bounds")
if idx < left.endIndex {
return left[left.count - idx.successor()]
} else {
return right[idx - left.count]
}
}
}
有了這幾行代碼音羞，Queue 現(xiàn)在已經(jīng)遵守 CollectionType 了囱桨。因為 CollectionType 是基于 SequenceType 的，所以 Queue 也遵守 SequenceType⌒岽拢現(xiàn)在我們的隊列已經(jīng)擁有超過 40 個方法和屬性供我們使用了：
var q = Queue<String>()
for x in ["1", "2", "foo", "3"] {
q.enqueue(x)
}
// 你可以用 for...in 循環(huán)訪問隊列
for s in q { print(s) } // 打印 1 2 foo 3
// 將其傳遞給接受序列的方法
q.joinWithSeparator(",") // "1,2,foo,3"
let a = Array(q) // a = ["1", "2", "foo", "3]
// 調(diào)用 SequenceType 的擴展方法
q.map { $0.uppercaseString } // ["1", "2", "FOO", "3"]
q.flatMap { Int($0) } // [1,2,3]
q.filter { // ["foo"]
$0.characters.count > 1
}
// 調(diào)用 CollectionType 的擴展方法
q.isEmpty // false
q.count // 4
q.first // "1"
q.last // "3”
遵守 ArrayLiteralConvertible
實現(xiàn)ArrayLiteralConvertible 可以直接已字面量的方式賦值舍肠，實現(xiàn)這個協(xié)議非常容易：
extension Queue: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
self.left = elements.reverse()
self.right = []
}
}
現(xiàn)在我們就可以用數(shù)組字面量來創(chuàng)建一個隊列了：
let q: Queue = [1,2,3]
遵守 RangeReplaceableCollectionType
隊列下一個要支持的是 RangeReplaceableCollectionType。這個協(xié)議要求我們做三件事情：
- reserveCapacity 方法：我們在實現(xiàn) map 的時候已經(jīng)使用過這個方法了窘面。因為最后元素的個數(shù)事前就已經(jīng)知道了貌夕，因此它能夠在數(shù)組申請內(nèi)存時避免不必要的元素復制。一個集合其實在收到 reserveCapacity 調(diào)用時可以什么都不做民镜，忽略掉它并不會造成很大影響啡专。
- 一個空的初始化方法：在泛型函數(shù)中這會很有用，它可以允許我們創(chuàng)建相同類型的空的集合制圈。
- replaceRange 函數(shù)：它接受一個范圍和一個集合们童，并將原來集合中這個范圍內(nèi)的內(nèi)容用新的集合替換。
RangeReplaceableCollectionType 是展現(xiàn)協(xié)議擴展的絕佳的例子鲸鹦。你通過實現(xiàn)一個超級靈活的 replaceRange 函數(shù)慧库，就能直接由其得到一組引申出的有用的方法：
- append 和 appendContentsOf：將 endIndex..<endIndex 范圍 (也就是集合末尾的空范圍) 用新的元素進行替換。
- removeAtIndex 和 removeRange：將 i...i 或者 subRange 的內(nèi)容用空集合進行替換
- splice 和 insertAtIndex：將 atIndex..<atIndex (也就是在這個位置的空范圍) 用新的值進行替換
- removeAll：將 startIndex..<endIndex 用一個空集合進行替換
以下是具體的實現(xiàn)：
extension Queue: RangeReplaceableCollectionType {
mutating func reserveCapacity(n: Int) {
return
}
mutating func replaceRange<C: CollectionType where C.Generator.Element == Element>(subRange: Range<Int>, with newElements: C){
right = left.reverse() + right
left.removeAll(keepCapacity: true)
right.replaceRange(subRange, with: newElements)
}
}
至此一個自定義的Queue集合就實現(xiàn)并且豐滿完畢了馋嗜。
