Using Collections Effectively

Swift 提供了Array, Set, Dictionary 三种基本的集合类型用来存储数据。Array是有序数据的集合，Set是无序无重复数据的集合，Dictionary是无序的键值对的集合。

集合非常普遍并且共享非常多的常见特性和算法，因为在Swift中它们都遵守一个通用协议Collection。在Swift中，集合就是序列，其中的元素可以以非破坏性的方式多次遍历，并且其元素可以通过下标访问。

这可能是一个在连续内存中定义的数组，哈希表，红黑树，链表或者你可以想象的任何其他东西。作为集合它们都支持起始索引（startIndex）和结束索引（endIndex），可以用来访问集合的初始元素和用来标识集合的结束。集合支持从其startIndex到endIndex直接遍历元素，同时也支持使用下标（subscript[index]）来获取集合中的元素。

Collection 集合

集合的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

protocol Collection : Sequence { 

    // 集合中元素的类型
    associatedtype Element 

    // 索引类型, 需要遵守Comparable协议
    associatedtype Index : Comparable 

    // 遍历时所用到的方法了, 即通过索引查询到对应的元素
    subscript(position: Index) -> Element { get } 

    // 开始索引
    var startIndex: Index { get } 

    // 结束索引
    var endIndex: Index { get } 

    // 通过一个索引, 获取它后面的索引
    func index(after i: Index) -> Index 
}

这里用到了associatedtype关键字, 在Swift协议定义的时候, 会看到使用这个关键字, 你可以认为这是一个占位符, 具体的类型直到被用到的时候才会确定. 但是有时候我们需要规定这个占位符要有一些能力, 比如这里的Index, 他就需要遵守Comparable协议.

集合协议的扩展

通过遵守Collection协议，你可以访问集合中各种丰富的功能, 有一些我们常用的first, last，isEmpty,count等属性，以及dropFirst，dropLast,reversed，split等函数以及一些map，filter之类的高阶函数。

我们也可以通过自定义一些协议扩展来实现更加强大的功能。

如隔元素遍历的功能：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

extension Collection { // 扩展集合协议  
    func everyOther(_ body: (Element) -> Void) { 
        // 获取首元素索引
        let start = self.startIndex 
        // 获取末尾元素索引
        let end = self.endIndex 
        var iter = start 
        // 未走到末尾
        while iter != end {
            // 执行外部的闭包 
            body(self[iter])
            // 获取当前元素的下一个索引
            let next = index(after: iter) 
            // 检查索引是否走到末尾
            if next == end { break } 
            // 将当前索引指向next的下一个
            iter = index(after: next) 
        } 
    } 
} 

(1...10).everyOther { print($0) }

集合的继承结构

除了强大的Collection本身，Swift中还有其他很多继承自Collection的协议。

• BidirectionalCollection 双向集合，可以向前访问元素
• RandomAccessCollection 随机访问集合，提供了复杂度O(1)的访问方法，因为继承自BidirectionalCollection,也可以向前向后访问元素
• MutableCollection 可变集合，提供了修改集合元素的能力
• RangeReplaceableCollection 范围替换集合，可以通过指定范围替换元素

Indces 索引

集合可以通过索引的方式来访问其中的元素，其中

• 每个集合都有自己的索引
• 索引必须满足Comparable
• 将索引作为不透明的类型(索引可能是正数，也可能是其他类型)

如何访问第一个元素

通过下标进行直接访问

使用array[0]访问第一个元素, 当然没有问题, 可是如果我们扩展开来, 如果给的集合不是数组, 而是一个set, 那么, 这样的方式就行不通了.

通过索引进行访问

使用set[set.startIndex]进行访问, 这样就可以了。 这个方法普遍适用于其他集合类型，如array[array.startIndex]

但是, 你同样需要注意一些潜在的问题, 如需要判空, 需要判断越界, 诸如此类

first

我们可以使用set.first进行获取. 而且不用担心那些潜在的问题

如何访问集合的第二个元素

我们可以通过向集合来添加一个新属性来实现

显然我们不能通过这两种方式来进行获取，因为我们之前说过，Collection的索引类型并不一定是Int，而是一个遵守Comparable协议的类型。

Slice 切片

切片是仅描述集合一部分元素的类型，每个切片都有自己的起始和结束索引，并且切片与其原始集合分开存在。切片不占用额外的存储空间，只是引用原始集合，因此非常高效。当使用切片下标时，它将读出原始缓冲区中的数据，切片能这么做的原因是因为它与其原始集合共享同样的索引。

通过切片，我们可以更优雅的实现访问第二个元素的功能。 我们去掉首元素，然后再获取新得到的集合的第一个元素就可以实现了。

切片与源集合共享索引

每个类型都可以自由定义自己的切片类型

内存问题

值得注意的是, 持有切片, 将使得即便将原来的集合置空, 内存也不会释放。切片是一个 原有集合 + 映射关系 的产物. 所以, 除非将切片也置空, 否则, 原有集合并不会被释放.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

extension Array {
    var firstHalf: ArraySlice<Element> {
        return self.dropLast(self.count / 2)
    }
}

var array = [1, 2, 3, 4, 5, 6, 7, 8]
var firstHalf = array.firstHalf // [1, 2, 3, 4]
// 将数组设置为空
array = []

print(firstHalf.first!) // 1

let copy = Array(firstHalf) // [1, 2, 3, 4]
// 将切片置为空
firstHalf = []
print(copy.first!) // 1

在这里，只有将源数组array设置为空且将切片firstHalf也设置为空之后，底层的存储才会真正消失。

过程如下

切片的工作方式有点像延迟拷贝，可以选择何时自己创建元素的副本，事实证明这种”懒”行为和延迟做某事的概念，在其他情况下也非常有用。

一种情况是函数调用。

Lazy Function

默认情况下，Swift中的函数是”Eager(急切)”的，也就是说它们接收了输入并按照要求返回输出。

经过这样的一套操作, 我们计算了4004个元素, 如果我们后面还有一些其他的操作, 更糟糕的是, 如果我们最终只是取取first, 这样, 前面生成的那些元素, 都成为了浪费.

我们可以通过lazy关键字来规避这样的浪费。可以看到, 使用lazy后, 刚才的遍历过程, 变成了组织一个新集合的过程,

只有在first进行计算的时候，才进行计算。

使用lazy时如何避免重复计算的过程

lazy的目的是只根据需要进行计算，但它避免的另一件事是创建中间存储。

何时使用 Lazy

• 链式计算
• 只需要结果中的一部分
• 没有其他副作用 No side effects
• 避免跨越API边界时

MutableCollection

当尝试修改集合时，使用了失效的索引：

如何避免

• 在持有索引和切片时, 处理要谨慎
• 集合发生改变时, 要更新索引后再使用
• 在需要索引和切片的情况下才对其进行计算

多线程访问

如何避免

• 隔离数据使其只能被单个线程访问
• 实现适当形式的互斥，如串行调度队列或锁
• 使用Thread Sanitizer来检查

建议

首选不可变集合来避免之前提到的问题

• 如果可以避免，就不要使用可变集合
• 可以使用切片和lazy操作符来模拟想要执行的改变
• 当尝试修改不可变集合石，编译器会提示你

如果可以, 尽量使用带capacity的初始化函数去初始化你的集合, 因为这样节省一些不必要的内存开销, 虽然这并不能节省多少, 但是想象你的项目中有成千上万个集合对象, 他们可以省出一个相当可观的内存数量.

Foundation Collection

引用类型的集合：

值类型和引用类型

对于值类型来说, 这样有什么好处呢? 因为在现代CPU在设计的时候, 采用了缓存机制, 可以快速的访问连续区域的地址. 而值类型的这种操作, 各个元素之间的内存是相连的, 而引用类型的则不是.

在Swift中使用Foundation集合时，通过桥接的方式将Objective-C中的API以Swift原生的值类型。桥接使我们可以在两种不同的运行时表示之间进行转换。尽管已经对Swift和Objective-C之间的桥接进行了优化，但是两种语言之间桥接时总会产生一些开销。

当在语言之间桥接时，必须先建立新的对等的存储空间，然后需要逐个元素的在它们之间进行转换。当桥接发生在两种语言的边界时，称之为”Eager”桥接，当集合中元素也需要桥接时，集合本身将总是进行”Eager”桥接，这种情况最常出现在以字符串作为键的字典中。当集合桥接并不急切时，我们称之为’lazy’桥接。当集合元素的类型并不需要桥接时，就会发生这种情况，比如NSView，在这种情况下，桥接将会被推迟到首次使用该集合时。

发生桥接的地方和所需开销：

这里的桥接发生在

• NSMutableAttributedString取string上, return bridge.
• 需要传入一个NSString, 参数类型桥接 param bridge

其中 “Brown” 这里也会有一个小的桥接，这里的”Brown”是一个Swift值类型的字符串，每当我们调用NSString的range(of:)时，实际上会把这个字符串桥接回NSString。

建议

什么时候应该使用Foundation Collection？

现在我们对Swift中强大的集合世界的探索已经接近尾声，希望你能够使用这种新视角来检视你现在使用集合的方式，寻找可以通过更有效地使用索引和切片来改进代码的地方，寻找可以通过惰性或者调整桥接方式而受益的地方，用ThreadSanitizer辅助审查可变状态。并通过应用今天讨论的所有概念在自己的App或者Playground中进一步锻炼你对集合的掌握.