5.集合类

创建数组

字面量创建

• 可以使用数组字面量来初始化一个数组，它是一种以数组集合来写一个或者多个值的简 写方式。数组字面量写做一系列的值，用逗号分隔，用方括号括起来

  
  01

字面量创建空数组

• 创建空数组的时候必须携带类型信息

• 如果内容已经提供了类型信息，比如说作为函数的实际参数或者已经分类了的变量或常 量，你可以通过空数组字面量来创建一个空数组

  
  02

初始化器

• 使用初始化器有两种方式
  类型
  Array<类型>()

03

初始化器参数

• init(repeating repeatedValue: Element, count: Int)

• init(arrayLiteral elements: Element...)

  
  04

• init<S>(_ elements: S) where S : Sequence, Self.Element == S.Element - init(from decoder: Decoder) throws

  
  05

数组遍历和索引

数组遍历

• For-In
• forEach方法

无法使用 break 或 continue 跳出或者跳过循环
使用 return 只能退出当前一次循环的执行体

06

• 同时得到索引和值 enumerated()

  
  07

• 使用 Iterator 遍历数组

  
  08

索引

• startIndex 返回第一个元素的位置，对于数组来说，永远都是 0。
• endIndex 返回最后一个元素索引 +1 的位置，对于数组来说，等同于count 。
• 如果数组为空，startIndex 等于 endIndex 。

• indices 获取数组的索引区间

  
  09

数组的查找操作

判断是否包含指定元素

• contains(_:) 判断数组是否包含给定元素
• contains(where:) 判断数组是否包含符合给定条件的元素

判断所有元素符合某个条件

• allSatisfy(_:) 判断数组的每一个元素都符合给定的条件

  
  10

查找元素

• first 返回数组第一个元素(optional)，如果数组为空，返回 nil 。
• last 返回数组最后一个元素(optional)，如果数组为空，返回 nil 。
• first(where:) 返回数组第一个符合给定条件的元素(optional)。
• last(where:) 返回数组最后一个符合给定条件的元素(optional)。

11

查找索引

• firstIndex(of:) 返回给定的元素在数组中出现的第一个位置(optional)

• lastIndex(of:) 返回给定的元素在数组中出现的最后一个位置(optional)

  
  12

• firstIndex(where:) 返回符合条件的第一个元素的位置(optional)

• lastIndex(where:) 返回符合条件的最后一个元素的位置(optional)

  
  13

查找最大最小元素

• min() 返回数组中最小的元素

• max() 返回数组中最大的元素

  
  14

• min(by:) 利用给定的方式比较元素并返回数组中的最小元素

• max(by:) 利用给定的方式比较元素并返回数组中的最大元素

  
  15

数组添加和删除

在末尾添加

• append(_:) 在末尾添加一个元素

• append(contentsOf: ) 在末尾添加多个元素

  
  16

在任意位置插入

• insert(_:at:) 在指定的位置插入一个元素
• insert(contentsOf: at:) 在指定位置插入多个元素

17

字符串也是 Collection

• 字符串也是 Collection ，Element 是 Character 类型。

  
  18

移除单个元素

• remove(at:) 移除并返回指定位置的一个元素

• removeFirst() 移除并返回数组的第一个元素

  
  19

• removeLast() 移除并返回数组的最后一个元素

• popLast() 移除并返回数组的最后一个元素(optional)，如果数组为空返回nil 。

  
  20

移除多个元素

• removeFirst(:) 移除数组前面多个元素

• removeLast(:) 移除数组后面多个元素

  
  21

• removeSubrange(_:) 移除数组中给定范围的元素

• removeAll() 移除数组所有元素

• removeAll(keepingCapacity:) 移除数组所有元素，保留数组容量

  
  22

ArraySlice

移除多个元素

• ArraySlice 是数组或者其他 ArraySlice 的一段连续切片，和原数组共享内存。

• 当要改变 ArraySlice 的时候，ArraySlice 会 copy 出来，形成单独内存。 - ArraySlice 拥有和 Array 基本完全类似的方法

  
  23

通过 Drop 得到 ArraySlice

• dropFirst(:) “移除”原数组前面指定个数的元素得到一个 ArraySlice
• dropLast(:) “移除”原数组后面指定个数的元素得到一个 ArraySlice

• drop(:) “移除”原数组符合指定条件的元素得到一个 ArraySlice

  
  24

通过 prefix 得到 ArraySlice

• prefix() 获取数组前面指定个数的元素组成的 ArraySlice
• prefix(upTo: ) 获取数组到指定位置(不包含指定位置)前面的元素组成的 ArraySlice
• prefix(through: ) 获取数组到指定位置(包含指定位置)前面的元素组成的 ArraySlice

• prefix(while: ) 获取数组前面符合条件的元素(到第一个不符合条件的元素截止)组成的 ArraySlice

  
  25

通过 suffix 得到 ArraySlice

• suffix() 获取数组后面指定个数的元素组成的 ArraySlice

• suffix(from: ) 获取数组从指定位置到结尾(包含指定位置)的元素组成的 ArraySlice

  
  26

通过 Range 得到 ArraySlice

• 可以通过对数组下标指定 Range 获取 ArraySlice，可以使用闭区间、半开半闭区间、单侧区 间、甚至可以只使用 ... 来获取整个数组组成的 ArraySlice 。

  
  27

ArraySlice 转为 Array

• ArraySlice 无法直接赋值给一个 Array 的常量或变量，需要使用 Array(slice) 。

  
  28

ArraySlice 和原 Array 相互独立

• ArraySlice 和原 Array 是相互独立的，它们添加删除元素不会影响对方

  
  29

重排操作

数组元素的随机化

• shuffle() 在原数组上将数组元素打乱，只能作用在数组变量上。
• shuffled() 返回原数组的随机化数组，可以作用在数组变量和常量上。

30

数组的逆序

• reverse() 在原数组上将数组逆序，只能作用在数组变量上。

• reversed() 返回原数组的逆序“集合表示”，可以作用在数组变量和常量上，该方法不 会分配新内存空间。

  
  31

数组的分组

• partition(by belongsInSecondPartition: (Element) throws -> Bool) 将数组以某个 条件分组，数组前半部分都是不符合条件的元素，数组后半部分都是符合条件的元素。

  
  32

数组的排序

• sort() 在原数组上将元素排序，只能作用于数组变量。
• sorted() 返回原数组的排序结果数组，可以作用在数组变量和常量上。

33

交换数组两个元素

• swapAt(::) 交换指定位置的两个元素
  34

拼接操作

字符串数组拼接

• joined() 拼接字符串数组里的所有元素为一个字符串

• joined(separator:) 以给定的分隔符拼接字符串数组里的所有元素为一个字符串

  
  35

元素为 Sequence 数组的拼接

• joined() 拼接数组里的所有元素为一个更大的 Sequence
• joined(separator:) 以给定的分隔符拼接数组里的所有元素为一个更大的 Sequence

36

数组探秘

数组的协议结构

37

Sequence

• 一个序列 (sequence) 代表的是一系列具有相同类型的值，你可以对这些值进行迭代。

  
  38

IteratorProtocol

• Sequence 通过创建一个迭代器来提供对元素的访问。迭代器每次产生一个序列的值， 并且当遍历序列时对遍历状态进行管理。

• 当序列被耗尽时，next() 应该返回 nil 。

  
  39

定义自己的 Sequence

40

Collection

• 一个 Collection 是满足下面条件的 Sequence
  稳定的 Sequence，能够被多次遍历且保持一致
  除了线性遍历以外，集合中的元素也可以通过下标索引的方式被获取到
  和 Sequence 不同，Collection 类型不能是无限的

  
  41

Array 的迭代器

42

Array 的下标访问

43

Array 的 buffer

44

_ContiguousArrayBuffer

45

_ContiguousArrayBuffer 的 getElement

46

UnsafeMutablePointer 的下标操作

47

问题:endIndex vs count

48

索引

49 50

实现栈和队列

Stack

• 栈( Stack )是一种后入先出( Last in First Out )的数据结构，仅限定在栈顶进行插 入或者删除操作。栈结构的实际应用主要有数制转换、括号匹配、表达式求值等等。

  
  51

Queue

• 队列在生活中非常常见。排队等位吃饭、在火车站买票、通过高速路口等，这些生活中 的现象很好的描述了队列的特点:先进先出 ( FIFO, first in first out )，排在最前面的 先出来，后面来的只能排在最后面。

52

Set

• Set 是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。其中，构成 Set 的 这些对象则称为该 Set 的元素。

集合的三个特性

• 确定性 :给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一。
• 互斥性 : 一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。
• 无序性 : 一个集合中，每个元素的地位都是相同的，元素之间是无序的。

Swift 里面的集合

• Swift 的集合类型写做 Set<Element>，这里的 Element 是 Set 要储存的类型。不同与数 组，集合没有等价的简写。

创建 Set

• 使用初始化器语法来创建一个确定类型的空 Set

• 使用数组字面量创建 Set

  
  53

Set 类型的哈希值

• 为了能让类型储存在 Set 当中，它必须是可哈希的——就是说类型必须提供计算它自身哈希值的方法。
• 所有 Swift 的基础类型(比如 String, Int, Double, 和 Bool)默认都是可哈希的，并且可以用于 Set 或者 Dictionary 的键。

54

• 自定义类型需要实现 Hashable 协议

  
  55

访问和修改 Set

遍历 Set

• 可以用for-in遍历set

• 因为 Set 是无序的，如果要顺序遍历 Set，使用 sorted()方法。

  
  56

访问 Set

• 使用 count 获取 Set 里元素个数

• 使用 isEmpty 判断 Set 是否为空

  
  57

添加元素

• insert(_:) 添加一个元素到 Set

• update(with:) 如果已经有相等的元素，替换为新元素。如果 Set 中没有，则插入。

  
  58

移除元素

• filter(_:) 返回一个新的 Set，新 Set 的元素是原始 Set 符合条件的元素。

  
  59

• remove(_:) 从 Set 当中移除一个元素，如果元素是 Set 的成员就移除它，并且返回移除的 值，如果合集没有这个成员就返回 nil 。

• removeAll() 移除所有元素

  
  60

• removeFirst() 移除 Set 的第一个元素，因为 Set 是无序的，所以第一个元素并不是放入的 第一个元素。

  
  61

执行 Set 操作

基本 Set 操作的定义

62

• intersection(_:) 交集，由属于A且属于B的相同元素组成的集合，记作A∩B(或B∩A)。
• union(_:) 并集，由所有属于集合A或属于集合B的元素所组成的集合，记作A∪B(或B∪A)。
• symmetricDifference(_:) 对称差集，集合A与集合B的对称差集定义为集合A与集合B中所有不属 于A∩B的元素的集合。

• subtracting(_:) 相对补集，由属于A而不属于B的元素组成的集合，称为B关于A的相对补集，记 作A-B或A\B。

  
  63

Set 判断方法

• isSubset(of:) 判断是否是另一个 Set 或者 Sequence 的子集 - isSuperset(of:) 判断是否是另一个 Set 或者 Sequence 的超集
• isStrictSubset(of:) 和 isStrictSuperset(of:) 判断是否是另一个 Set 的子集或者超集，但是 又不等于另一个 Set 。

• isDisjoint(with:) 判断两个 Set 是否有公共元素，如果没有返回 true，如果有返回 false

  
  64

Set 算法

• 给定一个集合，返回这个集合所有的子集

思路1 - 位

• 思路:解这道题的思想本质上就是元素选与不选的问题，于是我们就可以想到用二进制来代 表选与不选的情况。“1”代表这个元素已经选择，而“0”代表这个元素没有选择。假如三 个元素 A B C ，那么 101 就代表 B 没有选择，所以 101 代表的子集为 AC 。

  
  65

思路2 - 递归

• 思路:如果只有一个元素，那么它的子集有两个，分别是本身和空集，然后在已经有一个元素的 子集的基础上，第二个元素有两种选法，那就是加入到前面的子集里面或者不加入到前面的子集 里面，也就是选与不选的问题。而前面的子集一共有两个，对每一个子集都有来自于下一个元素 的加入和不加入两种选法。那么就可以得出两个元素的子集一共有四个。依次类推，就可以得出 n 的元素所有子集(这里 n 个元素的子集一共有 2n 个，非空子集一共有 2n-1 个)。

  
  66

Set 实现探秘

从 Set 的 insert 说起

67

_NativeSet 的 find 方法

68

HashTable

69 70

线性探测的开放寻址法

71

_NativeSet 的 insertNew

72

HashTable 的 insertNew

73

_NativeSet 的 uncheckedInitialize

74

字典

Dictionary

• 字典储存无序的互相关联的同一类型的键和同一类型的值的集合
• 字典类型的全写方式 Dictionary<Key, Value>，简写方式 [Key: Value]，建议使用简写方式
• 字典的 key 必须是可哈希的

创建空字典

• 初始器方式
• 简写方式

• 字面量方式

  
  75

字面量创建字典

• [key 1: value 1, key 2: value 2, key 3: value 3]

  
  76

count 和 isEmpty

• 可以使用 count 只读属性来找出 Dictionary 拥有多少元素
• 使用布尔量 isEmpty 属性检查字典是否为空

遍历字典

• For-In 循环
• 可以通过访问字典的 keys 和 values 属性来取回可遍历的字典的键或值的集合
• Swift 的 Dictionary 类型是无序的。要以特定的顺序遍历字典的键或值，使用键或值的 sorted() 方法

77

字典常用操作

添加或更新元素

• 使用下标添加或更新元素
• 使用 updateValue(_:forKey:) 方法添加或更新元素，返回一个字典值类型的可选项值

移除元素

• 使用下标脚本语法给一个键赋值 nil 来从字典当中移除一个键值对
• 使用 removeValue(forKey:)来从字典里移除键值对。这个方法移除键值对如果他们存在的 话，并且返回移除的值，如果值不存在则返回 nil 。

合并两个字典

• merge(_:uniquingKeysWith:)

78

firstIndex

• 虽然字典是无序的，但是每个kv对在扩容之前的位置是稳定的。如果你需要保持顺序的kv对 可以使用 KeyValuePairs

  
  79

字典实现探秘

从下标操作谈起

80

Dictionary._Variant 的 setValue

81

_NativeDictionary 的 setValue

82

_NativeDictionary 的 _insert

83

_NativeDictionary 的 uncheckedInitialize

84

_NativeDictionary 的 findKey

85