Swift 进阶【二】集合类型协议

发表于 分类于 Disqus：

序列（Sequence）

Sequence定义：

1
2
3
4
protocol Sequence {
    associatedtype Iterator: IteratorProtocol
    func makeIterator() -> Iterator
}

要实现一个Sequence，首先需要提供一个返回迭代器（iterator）的makeIterator() 方法。
对于迭代器，它是一个满足 IteratorProtocol 协议的类型。

IteratorProtocol协议的定义：

1
2
3
4
protocol IteratorProtocol {
    associatedtype Element
    mutating func next() -> Element?
}

IteratorProtocol 协议中唯一的一个方法是 next()，这个方法需要在每次被调用时返回序列中的下一个值。当序列被耗尽时，next() 应该返回 nil

关联类型 Element 指定了迭代器产生的值的类型。

举几个例子进行体会：

1、斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// 菲波那切数列
struct FibsIterator: IteratorProtocol {
    var state = (0, 1)
    mutating func next() -> Int? {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        if upcomingNumber > 1000 {
            return nil
        }
        return upcomingNumber
    }
}

var iterator = FibsIterator()
while let number = iterator.next() {
    print(number)
}
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987

2、返回字符串切片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/// 依次返回字符串的切片
struct PrefixIterator: IteratorProtocol {
    var string: String
    var offset: String.Index
    
    init(str: String) {
        self.string = str
        self.offset = str.startIndex
    }
    
    mutating func next() -> String? {
        guard offset < string.endIndex else { return nil }
        offset = string.index(after: offset)
        return String(string[string.startIndex..<offset])
    }
}

var strIterator = PrefixIterator(str: "ABCDEFG")
while let str = strIterator.next() {
    print(str)
}

// A
// AB
// ABC
// ABCD
// ABCDE
// ABCDEF
// ABCDEFG

再定义一个PrefixSequence类型：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/// 实现PrefixIterator的sequence协议，之后可以用for来进行循环
struct PrefixSequence: Sequence {
    let str: String
    
    func makeIterator() -> PrefixIterator {
        return PrefixIterator(str: str)
    }
}

for str in PrefixSequence(str: "ABCDEFGHIJKLMN") {
    print(str)
}

// 实现了sequence协议，就可以使用sequence协议中提供的所有方法
let lower = PrefixSequence(str: "ABCDEFGHIJKLMN").map { return $0.lowercased() }
print(lower.prefix(10))

集合类型

集合类型 (Collection) 指的是那些稳定的序列，它们能够被多次遍历且保持一致。和序列不同，集合类型不能是无限的。

Collection 协议是建立在 Sequence 协议上的。除了从 Sequence 继承了全部方法以外，得益于可以获取指定位置的元素以及稳定迭代的保证，集合还获取了一些新的能力。比如 count 属性，如果序列是不稳定的，那么对序列计数将会消耗序列中的元素，这显然不是我们的目的。但是对于稳定的集合类型，我们就可以对其进行计数。

集合类型在标准库中运用广泛。除了 Array，Dictionary 和 Set 以外，String 的四种表示方式都是集合类型。另外还有 CountableRange 和 UnsafeBufferPointer 也是如此。更进一步，我们可以看到标准库外的一些类型也遵守了 Collection 协议。有两个我们熟知的类型通过这种方法获得了很多新的能力，它们是 Data 和 IndexSet，它们都来自 Foundation 框架。

自定义一个队列的集合类型：

1、为队列设计协议：

1
2
3
4
5
6
7
8
9
/// 一个能够将元素入队和出队的类型
protocol Queue {
    /// 在 `self` 中所持有的元素的类型
    associatedtype Element
    /// 将 `newElement` 入队到 `self`
    mutating func enqueue(_ newElement: Element)
    /// 从 `self` 出队一个元素
    mutating func dequeue() -> Element?
}

2、队列的实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/// 一个高效的 FIFO 队列，其中元素类型为 `Element`
struct FIFOQueue<Element>: Queue {
    fileprivate var left: [Element] = []
    fileprivate var right: [Element] = []
    /// 将元素添加到队列最后
    /// - 复杂度: O(1)
    mutating func enqueue(_ newElement: Element) {
        right.append(newElement)
    }
    /// 从队列前端移除一个元素
    /// 当队列为空时，返回 nil
    /// - 复杂度: 平摊 O(1)
    mutating func dequeue() -> Element? {
        if left.isEmpty {
            left = right.reversed()
            right.removeAll()
        }
        return left.popLast()
    }
}

你可能会对 dequeue 操作被声明为 O(1) 感到有一点奇怪。确实，它包含了一个复杂度为 O(n) 的 reverse 操作。对于单个的操作来说可能耗时会长一些，不过对于非常多的 push 和 pop 操作来说，取出一个元素的平摊耗时是一个常数。

理解这个复杂度的关键在于理解反向操作发生的频率以及发生在多少个元素上。我们可以使用“银行家理论”来分析平摊复杂度。想象一下，你每次将一个元素放入队列，就相当于你在银行存了一块钱。接下来，你把右侧的栈的内容转移到左侧去，因为对应每个已经入队的元素，你在银行里都相当于有一块钱。你可以用这些钱来支付反转。你的账户永远不会负债，你也从来不会花费比你付出的更多的东西。

这个理论可以用来解释一个操作的消耗在时间上进行平摊的情况，即便其中的某次调用可能不是常数，但平摊下来以后这个耗时依然是常数。Swift 中向数组后面添加一个元素的操作是常数时间复杂度，这也可以用同样的理论进行解释。当数组存储空间耗尽时，它需要申请更大的空间，并且把所有已经存在于数组中的元素复制过去。但是因为每次申请空间都会使存储空间翻倍，“添加元素，支付一块钱，数组尺寸翻倍，最多耗费所有钱来进行复制”这个理论已然是有效的。

遵守 ExpressibleByArrayLiteral 协议

遵守 ExpressibleByArrayLiteral 协议的好处是，可以像用字面量去创建一个Array的方式去创建队列（[value1, value2, etc]）。

1
2
3
4
5
6
7
extension FIFOQueue: ExpressibleByArrayLiteral {
    typealias ArrayLiteralElement = Element
    init(arrayLiteral elements: Element...) {
        self.init(left: elements.reversed(), right: [])
    }
}
let queue: FIFOQueue<Int> = [1, 4, 5, 6, 2, 6, 1]

字面量和类型的区别

在这里需要特别注意 Swift 中字面量和类型的区别。这里的 [1, 2, 3] 并不是一个数组，它只是一个“数组字面量”，是一种写法，我们可以用它来创建任意的遵守 ExpressibleByArrayLiteral 的类型。在这个字面量里面还包括了其他的字面量类型，比如能够创建任意遵守 ExpressibleByIntegerLiteral 的整数型字面量。
这些字面量有“默认”的类型，如果你不指明类型，那些 Swift 将假设你想要的就是默认的类型。正如你所料，数组字面量的默认类型是 Array，整数字面量的默认类型是 Int，浮点数字面量默认为 Double，而字符串字面量则对应 String。但是这只发生在你没有指定类型的情况下。

关联类型

building…