集合类型模块分四篇笔记来学习：
- 第一篇：
- 数组和可变性
- 数组的变形
- 第二篇：
- 字典和集合
- 集合协议
- 第三篇：
- 集合
- 第四篇：
- 索引
本篇开始学习第三篇，Go！
集合
集合协议 CollectionType 是在序列上构建的，它为序列添加了可重复进行迭代(由于序列是值类型，所以不能单独进行迭代)，以及通过索引访问元素的能力。
为了展示 Swift 的集合类型是如何工作的，我们将实现一个我们自己的集合类型。队列 (queue) 是在 Swift 标准库中不存在，但却又最常用到的容器类型了。Swift 的数组可以很容易地被用来实现栈 (stack) 结构，只需要使用 append 入栈和 popLast 出栈就可以了。但是将数组作为队列来使用的话就不那么理想。
为队列设计协议
在实际实现队列之前，我们应该先定义它到底是什么。我们可以通过下面定义的协议来描述队列的特性：
/// 一个能够将元素入队和出队的类型
protocol QueueType {
/// 在 `self` 中所持有的元素的类型
associatedtype Element
/// 将 `newElement` 入队到 `self`
mutating func enqueue(newElement: Element)
/// 从 `self` 出队一个元素
mutating func dequeue() -> Element?”
}
队列的实现
下面是一个很简单的队列，它的 enqueue 和 dequeue 方法是基于一系列数组来构建的。
/// 一个高效的 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()
}
至此我们实现了一个最简单的队列，接下来通过分别实现CollectionType、ArrayLiteralConvertible、RangeReplaceableCollectionType来扩展Queue。
遵守 CollectionType
CollectionType 是对 Indexable 和 SequenceType 的扩展。该协议有两个关联类型和九个方法。不过，这两个关联类型都有默认值，而不少方法也有它们的默认实现。
我们要做的是为 Indexable 协议中要求的 startIndex 和 endIndex 提供实现，并且实现一个通过下标索引来获取对应索引的元素的方法。只要我们实现了这三个需求，我们就能让一个类型遵守 CollectionType 了。
我们现在已经有一个能够出队和入队的容器了，要将它转变为一个集合，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 现在已经遵守 CollectionType 了。因为 CollectionType 是基于 SequenceType 的，所以 Queue 也遵守 SequenceType。现在我们的队列已经拥有超过 40 个方法和属性供我们使用了：
var q = Queue<String>()
for x in ["1", "2", "foo", "3"] {
q.enqueue(x)
}
// 你可以用 for...in 循环访问队列
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]
// 调用 SequenceType 的扩展方法
q.map { $0.uppercaseString } // ["1", "2", "FOO", "3"]
q.flatMap { Int($0) } // [1,2,3]
q.filter { // ["foo"]
$0.characters.count > 1
}
// 调用 CollectionType 的扩展方法
q.isEmpty // false
q.count // 4
q.first // "1"
q.last // "3”
遵守 ArrayLiteralConvertible
实现ArrayLiteralConvertible 可以直接已字面量的方式赋值，实现这个协议非常容易：
extension Queue: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
self.left = elements.reverse()
self.right = []
}
}
现在我们就可以用数组字面量来创建一个队列了：
let q: Queue = [1,2,3]
遵守 RangeReplaceableCollectionType
队列下一个要支持的是 RangeReplaceableCollectionType。这个协议要求我们做三件事情：
- reserveCapacity 方法：我们在实现 map 的时候已经使用过这个方法了。因为最后元素的个数事前就已经知道了，因此它能够在数组申请内存时避免不必要的元素复制。一个集合其实在收到 reserveCapacity 调用时可以什么都不做，忽略掉它并不会造成很大影响。
- 一个空的初始化方法：在泛型函数中这会很有用，它可以允许我们创建相同类型的空的集合。
- replaceRange 函数：它接受一个范围和一个集合，并将原来集合中这个范围内的内容用新的集合替换。
RangeReplaceableCollectionType 是展现协议扩展的绝佳的例子。你通过实现一个超级灵活的 replaceRange 函数，就能直接由其得到一组引申出的有用的方法：
- append 和 appendContentsOf：将 endIndex..<endIndex 范围 (也就是集合末尾的空范围) 用新的元素进行替换。
- removeAtIndex 和 removeRange：将 i...i 或者 subRange 的内容用空集合进行替换
- splice 和 insertAtIndex：将 atIndex..<atIndex (也就是在这个位置的空范围) 用新的值进行替换
- removeAll：将 startIndex..<endIndex 用一个空集合进行替换
以下是具体的实现：
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集合就实现并且丰满完毕了。
网友评论