Swift Sequence（一）

Sequence 协议是集合类型的基础，可以通过实现 Sequence 协议来实现一个自定义的序列类型。满足 Sequence 协议的要求十分简单，只需要提供一个返回迭代器(Iterator)的 makeIterator() 方法：

protocol Sequence {
	associatetype Iterator: IteratorProtocol
	func makeIterator() -> Iterator
	// ...
}

IteratorProtocol

序列通过创建一个迭代器来访问元素，迭代器每次产生一个序列的值，并且当遍历序列时对遍历状态进行管理。在 IteratorProtocol 协议中唯一的一个方法是 next(), 每次调用返回序列的下一个值，当到达序列末尾时返回 nil:

protocol IteratorProtocol {
	associatetype Element
	mutating func next() -> Element?
}

遍历序列最常用、最简单的方式就是 for 循环，从本质上来说，for 循环是下面这种形式的简写:

var iterator = someSequence.makeIterator()
	while let element = iteraotr.next() {
	// do something...
}

自定义一个裴波那契序列：

struct FibsIterator: IteratorProtocol {
    var state = (0, 1)
    
    mutating func next() -> Int? {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        return upcomingNumber
    }
}

struct FibsSequence: Sequence {
    func makeIterator() -> FibsIterator {
        return FibsIterator()
    }
}

let fibs = FibsSequence()
for num in fibs.prefix(10) {
    print(num)
}
/*
 0
 1
 1
 2
 3
 5
 8
 13
 21
 34
*/

迭代器的值语义

FibsIterator 迭代器具有值语义，即如果复制一份迭代器，迭代器的所有状态也会被复制，标准库中的大部分迭代器都具有值语义。

var i1 = FibsIterator(upRangeBound: 20)
i1.next() // 0
i1.next() // 1
var i2 = iterator
i1.next() // 1
i2.next() // 2
i2.next() // 1
i2.next() // 2

要创建一个不具有值语义的迭代器，可用 AntIterator 对迭代器进行封装。AnyIterator 进行封装的做法是将迭代器包装到一个内部的对象中，而这个对象是引用类型。

var i3 = AnyIterator(i1)
var i4 = i3
i3.next() // 3
i4.next() // 5
i3.next() // 8
i4.next() // 13

i3 和 i4 并不是相互独立的，i3 不再是一个结构体，将 i3 复值给 i4 时只是复值了引用，两个迭代器共享一份状态。

无限序列

序列和集合一个最重要的区别是序列可以是无限的，而集合不行。

FibsSequence 就是一个无限序列，从上方的例子可以看出序列对 next 闭包的调用时延迟执行的，即序列的下一个值不会预先被计算，只在调用者需要的时候生成，否则定义完 FibsSequence 后程序会因为整数溢出而崩溃。

不稳定序列

序列和集合另一个重要的区别是序列并不保证可以被多次遍历，也就是说 Sequence 协议并不保证在迭代后元素是否销毁。

for element in sequence {
	// do something
}
for element in sequence {
	// 未定义行为
}

一个非集合的序列可能会在第二次 for-in 循环时产生随机的序列元素

栗子

用枚举实现一个单向链表

一个链表的节点只有两种可能，要么它是一个节点，要么代表链表的结尾，So 可以这样来定义链表：

enum List<Element> {
    case end
    indirect case node(Element, next: List<Element>)
}

由于枚举是值类型，不能循环引用自身，故用 indirect 关键字来定义枚举成员告诉编译器将 node 当做引用，这样就可以循环引用自己了。尽管 node 会被当做引用，但这并不会改变枚举成员值类型的本质。

为链表创建一个添加方法：

extension List {
    func cons(_ x: Element) -> List {
        return .node(x, next: self)
    }
}
// 一个拥有三个元素的链表
let list = List.end.cons(1).cons(2).cons(3)

实现 ExpressibleByArrayLiteral 以便用数组字面量来初始化链表

extension List: ExpressibleByArrayLiteral {
    init(arrayLiteral elements: Element...) {
        self = elements.reversed().reduce(.end){result, element in
            result.cons(element)
        }
    }
}

var list2: List = [1, 2, 3]

链表其实也是一个栈，为链表实现 push 和 pop 方法：

extension List {
    func push(_ x: Element) {
        self.cons(x)
    }
    mutating func pop() -> Element? {
        switch self {
        case .end:
            return nil
        case let .node(x, next: trail):
            self = trail
            return x
        }
    }
}

var list3: List = [1, 2, 3]

list3.pop() // 1
list3.pop() // 2
list3.pop() // 3
list3.pop() // nil

现在让 List 遵守 Sequence 协议就很简单了，我们只需要实现一个 next 方法即可同时遵守 IteratorProtocol 和 Sequence 协议

extension List: IteratorProtocol, Sequence {
    mutating func next() -> Element? {
        return pop()
    }
}

现在就可以在 List 上使用 for-in 了

var list: List = [1, 2, 3, 4]
for element in list {
    print(element)
}
// 1
// 2
// 3
// 4

Collection

Collection 协议建立在 Sequence 的基础上。与序列不同 Collection 协议保证了集合类型的稳定性。遵守 Collection 协议的集合类型即指那些稳定的有限的序列，可以被多次遍历并保持一致。

自定义集合类型

下面以实现一个 FIFO 的队列为例，展示如何自定义集合类型。FIFO 队列我们可以用 Array 的 push 和 remove(at: 0) 来实现，但是因为数组中的元素是存储在一段连续的内存中，所以移除非尾部元素的时候其他元素都要移动去填补空白，这个操作的复杂度是 O(n)。So，下面我们实现一个更合理的队列类型。

第一步，定义一个协议来描述队列到底是什么

protocol Queue {
    // 队列中元素类型
    associatedtype Element
    // 入队一个元素
    mutating func enqueue(_ newElement: Element)
    // 出队一个元素
    mutating func dequeue()
}

如上，Queue 协议只是定义了一个队列的基本属性，并没有定义这是一个先进先出队列，还是一个后进先出队列。

第二步，实现队列

struct FIFOQueue<Element>: Queue {
    private var left: [Element] = []
    private var right: [Element] = []
    /// 将元素添加到队列末尾
    /// - 复杂度： O(1)
    mutating func enqueue(_ newElement: Element) {
        right.append(newElement)
    }
    /// 从队列前端移除一个元素
    /// - 复杂度：平摊O(1)
    mutating func dequeue() ->Element? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

dequeue 方法中包含一个复杂度为 O(n) 的 reversed 操作，对于单个元素的操作来说可能耗时会长一些，但是对于非常多的 push 和 pop 操作来说，取出一个数的平摊耗时是一个常数。

第三步，遵守 Collection 协议

目前 Swift 4.2 版本中 Collection 协议有7个属性，5个关联类型，11个实例方法，和两个下标方法。所幸其中大部分属性、方法都有默认的实现，要满足 Collection 协议，最少的情况下你只需满足以下条件：

startIndex 和 endIndex 属性
能够读取类型中元素的下标方法
集合索引之间步进的 index(after:) 方法

最后我们需要实现的方法和属性有：

protocol Collection: Sequence {
    /// 一个表示集合中位置的类型 
    /// 不需要显示的申明，Swift 可以从属性和方法的定义中推断出来
    associatedtype Index: Comparable
    /// 一个非空集合中首个元素的位置
    var startIndex: Index { get }
    /// 集合中超过末位的位置---也就是比最后一个有效下标值大 1 的位置
    var endIndex: Index { get }
    /// 返回在给定索引之后的那个索引值
    func index(after i: Index) -> Index
    /// 访问特定位置的元素
    subscript(position: Index) -> Element { get }
}

让 FIFOQueue 遵守 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) -> Element {
        precondition((0..<endIndex).contains(position), "下标越界")
        if position < left.endIndex {
            return left[left.count - position - 1]
        } else {
            return right[position - left.count]
        }
    }
}

最后，遵守 ExpressibleByArrayLiteral 协议

自定义集合类型时，最好都实现一下 ExpressibleByArrayLiteral 协议，方便用数组字面量来创建类型。

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

简单的应用：

var q: FIFOQueue = [1, 3, 5, 4, 6]
q.dequeue() // 1
q.enqueue(2) // left: [6, 4, 5, 3] right: [2]
q.dequeue() // 3
q.enqueue(9) // left: [6, 4, 5] right: [2, 9]
let sortedQ = q.sorted() // [2, 4, 5, 6, 9]

索引

集合类型的 index 不一定都是整数类型，实现了 Comparable 协议的类型都可以作为集合类型 index。

当集合发生改变时，索引可能会失效。有以下两种情况：

索引本身仍是有效的，但是指向的是另外的元素。
索引本身已失效，使用它访问集合会造成崩溃。

var arr = [1, 2, 3, 4, 5]
let secondIndex = arr.index(after: arr.startIndex)

var val = arr[secondIndex] // 2
var lastVal = arr[lastIndex] // 5

arr.insert(9, at: 1)
val = arr[secondIndex] // 9

let lastIndex = arr.index(before: arr.endIndex)
arr.removeLast()
lastVal = arr[lastIndex] // 数组越界

切片

所有集合类型都有切片操作的默认实现，且有一个接受 Range<index> 作为参数的下标方法。

1
2
3

var arr = [1, 2, 3, 4, 5]
// slice 的类型不是 Array<Int> 而是 ArraySlice<Int>
var slice = arr[1..<4] // [2, 3, 4]

标准库中实现了一些常用的快速获取切片的方法，如：dropFirst()、dropLast()、suffix()、prefix()等。

var arr = [1, 2, 3, 4, 5]
let dropFirst = arr.dropFirst() // [2, 3, 4, 5]
let dropLast = arr.dropLast() // [1, 2, 3, 4]
let subffix2 = arr.suffix(2) // [4, 5]
let subffixFrom = arr.suffix(from: 1) // [2, 3, 4, 5]
let prefix = arr.prefix(3) // [1, 2, 3]
let prefixUpTo = arr.prefix(upTo: 3) // [1, 2, 3]

切片与原集合共享索引

集合类型和它的切片拥有相同的索引。只要集合和它的切片在创建后没有改变，切片中某个索引位置上的元素，应当也存在于原集合中同样的索引位置上。这就引出一个问题，一个集合的索引不需要从0开始。

1
2
3

var arr = [1, 2, 3, 4, 5]
var slice = arr.dropFirst()
slice.startIndex // 1

这种情况下，访问 slice[0] 会崩溃，slice 的开始索引不再是0而是1。所以，不要假设集合类型的开始索引总是0，始终使用 startIndex 和 endIndex 访问集合的开始、结束索引。

不要长期存储切片实例

切片会持有原集合整个存储的引用，而不仅仅是切片需要展示的内容，即使在原集合的生命周期结束后切片仍会持有原集合整个存储的引用。长期存储切片实例，切片的生命周期比原集合久，当原集合生命周期结束后会造成内存泄漏。

特定的集合类型

Collection 协议没有提供向后移动索引的方法，也没有提供像是插入、移除或者替换集合元素这样的方法。标准库中，有四个专门的集合类型协议来对 Collection 进行扩展。

BidirectionalCollection 一个即支持前向又支持后向遍历的集合
RandomAccessCollection 一个支持高效随机存取索引遍历的集合
MutableCollection 一个支持下标赋值的集合
RangeReplaceableCollection 一个支持将任意子范围的元素用别的集合中的元素记性替换的集合