Swift进阶五——集合类之Set&Dictionary
Set的定义和创建
Set是指具有某种特定性质的具体的或者抽象的对象汇总而成的集体。其中，构成Set的这些对象则称为该Set的元素。
Set的三个特性：
1，确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一。
2，互斥性：一个集合中，任意两个元素都是不相同的，即每个元素只能出现一次
3，无序性：一个集合中，元素之间是无序的。
在Swift中，集合类型写作Set<Element>，这里的Element是Set要存储的类型，也就是说，Set是支持泛型的。
创建Set有两种方式：
1，使用初始化器语法来创建一个确定类型的空Set
var aaa = Set<Int>()2，使用数组字面量语法来创建Set
var bbb: Set<Int> = [1,2,3]Set类型的哈希值
为了能够让类型存储在Set当中，该类型必须是可哈希的——也就是说，类型必须提供计算其哈希值的方法。
所有Swift的基础类型（比如String、Int、Bool等），默认都是可哈希的，因此他们都可以用于Set，或者用于Dictionary的键。
struct Student {
var name: String
var score: Double
}
var studentSet: Set<Student> = [] // 这里会报错：Type 'Student' does not conform to protocol 'Hashable'现在我们自定义一个Student结构体，然后声明一个Set<Student>类型的变量，此时编译器会报错，报错信息如下：
这是因为自定义的Student结构体没有实现Hashable协议，所以不可以作为Set的元素类型。
为了使Student结构体可以存储在Set中，我们就需要给Student结构体遵循Hashable协议并实现对应的协议方法：
struct Student {
var name: String
var score: Double
}
extension Student: Hashable {
func hash(into hasher: inout Hasher) {
hasher.combine(name)
hasher.combine(score)
}
}
var studentSet: Set<Student> = []
studentSet.insert(Student(name: "Lavie", score: 100))
print(studentSet) // [LavieSwift.Student(name: "Lavie", score: 100.0)]Set的访问和修改
由于Set也是一个Sequence，因此我们可以通过for-in来遍历Set；但是Set是无序的，如果我们想要顺序遍历Set，那么就要使用sorted()方法。
let courses: Set = ["Math", "Chinese", "English"]
for course in courses {
print(course)
}
print("------")
for course in courses.sorted() {
print(course)
}
//打印如下：
English
Chinese
Math
------
Chinese
English
Math可以使用count来获取Set里面元素的个数，使用isEmpty来判断Set是否为空。
let courses: Set = ["Math", "Chinese", "English"]
print(courses.count)
print(courses.isEmpty)
//打印如下：
3
false添加元素
可以通过insert添加一个元素到Set
struct Student {
var name: String
var score: Double
}
extension Student: Hashable {
func hash(into hasher: inout Hasher) {
hasher.combine(name)
hasher.combine(score)
}
}
var studentSet: Set<Student> = []
studentSet.insert(Student(name: "Lavie", score: 100))
print(studentSet) // [LavieSwift.Student(name: "Lavie", score: 100.0)]通过update方法，如果已经有相等的元素，则替换成新的元素；如果没有，则插入。
var studentSet: Set<Student> = []
studentSet.insert(Student(name: "Lavie", score: 100))
studentSet.update(with: Student(name: "Lavie", score: 99))
print(studentSet)那么如何来判断Set中的两个元素相等呢？那就要通过Hashable协议中的hash方法来制定这个标准：
extension Student: Hashable {
func hash(into hasher: inout Hasher) {
hasher.combine(name)
hasher.combine(score)
}
}比如上面hash这个协议方法里定义的判断相等的标准是：
只有当Student类型的变量的name属性和score属性都相等的时候，才会认定这两个Student类型的变量相等。
筛选
filter会返回一个新的Set，新Set中的元素是原始Set中符合筛选条件的元素。
var studentSet: Set<Student> = []
studentSet.insert(Student(name: "Lavie", score: 100))
studentSet.update(with: Student(name: "Norman", score: 99))
print(studentSet)
print(studentSet.filter({$0.score == 100}))
打印如下：
[LavieSwift.Student(name: "Lavie", score: 100.0), LavieSwift.Student(name: "Norman", score: 99.0)]
[LavieSwift.Student(name: "Lavie", score: 100.0)]移除元素
remove会从Set中移除一个元素。如果元素是Set的成员，就移除它并返回移除的成员值；如果元素不是Set的成员，就返回nil。
removeAll()会移除所有元素。
var studentSet: Set<Student> = []
studentSet.insert(Student(name: "Lavie", score: 100))
studentSet.update(with: Student(name: "Norman", score: 99))
print(studentSet) // [LavieSwift.Student(name: "Lavie", score: 100.0), LavieSwift.Student(name: "Norman", score: 99.0)]
studentSet.remove(Student(name: "Lavie", score: 100))
print(studentSet) // [LavieSwift.Student(name: "Norman", score: 99.0)]
studentSet.removeAll()
print(studentSet) // []需要注意的是，Set也有一个removeFirst函数，用于移除当前Set中的第一个元素。但是由于Set是无序的，它在每一次哈希之后，其元素的排列顺序是不一定的，因此removeFirst函数移除的并不是第一个放入set的元素，而是当前哈希之后排在第一个位置的元素。
Set的计算和判断
基本的Set操作
- 交集：intersection，由属于集合A且属于集合B的相同元素组成的集合，记做A∩B或者B∩A，支持交换律
- 并集：union，由所有属于集合A或者属于集合B的元素所组成的集合，记做A∪B或者B∪A，支持交换律
- 对称差集：symmetricDifference，集合A与集合B中左右不属于A∩B的元素所组成的集合，支持交换律
- 相对补集：subtracting，由属于A但是不属于B的元素组成的集合。
let set1: Set = [1, 2, 3]
let set2: Set = [3, 4, 5, 6]
print(set1.intersection(set2)) // [3]
print(set1.union(set2)) // [5, 1, 2, 3, 4, 6]
print(set1.symmetricDifference(set2)) // [5, 6, 2, 4, 1]
print(set1.subtracting(set2)) // [1, 2]判断方法
- isSubset：判断是否是另一个Set或者Sequence的子集。
- isSuperset：判断是否是另一个Set或者Sequence的超集。
- isStrictSubset和isStrictSuperset：判断是否是另一个Set或者Sequence的子集或者超级，同时又不等于另一个Set或者Sequence。
- isDisjoint：判断两个Set是否有公共元素，如果没有则返回true，如果有则返回false
let set1: Set = [1, 2, 3]
let set2: Set = [1, 2, 3, 4, 5, 6]
print(set1.isSubset(of: set2)) // true
print(set2.isSuperset(of: set1)) // true
print(set1.isStrictSubset(of: set2)) // true
print(set2.isStrictSuperset(of: set1)) // true
print(set1.isDisjoint(with: set2)) // false实现自己的集合算法
题目如下：
给定一个集合，返回该集合的所有子集。
首先来明确一下自己的概念：如果一个集合A中的所有元素都属于集合B，那么集合A就是集合B的子集。
解法1：位运算
func getSubsets< T>(_ set: Set<T>) -> Array<Set<T>> {
let count = 1 << set.count // 一个集合的子集合的个数是2的n次方（n是集合中元素的个数）
let setElements = Array(set) // 由于Set中元素的排列是无序的，因此为了能够得到指定元素，需要将Set转化为Array
var subSets = [Set<T>]() // 用于记录子集合
//一共有count个子集合，原集合中的每个元素，在子集合中要么有要么没有。
//0..<count区间中的每一个数的二进制表示中，共有count个二进制位，每一个二进制位要么是0要么是1。
//因此，可以获取到0..<count区间的每一个数，然后遍历该数的每一个二进制位，最后根据是0还是1来决定是否将该坐标下的元素插入到当前的子集合中。
for i in 0..<count {
var subset = Set<T>()
for j in 0..<setElements.count {
if ((i >> j) & 1) == 1 {
subset.insert(setElements[j])
}
}
subSets.append(subset)
}
return subSets
}核心思路：
原集合中的每一个元素，在子集合中要么存在要么不存在，因此，一共有2^n个子集合。
遍历0..<2^n区间内的每一个值，该值一共有n个二进制表示位，每一个二进制表示位要么是0要么是1。这样就与子集合要么存在要么不存在对应起来了。
这种方法有一个弊端：
Int是有位数限制的，如果在某个平台上Int最多只有64位，那么当原集合中的元素个数超过64的时候，该方法就不适用了。
解法2：递归
func getSubsets<T>(_ set: Set<T>) -> Array<Set<T>> {
let setElements = Array(set)
return getSubsets1(elements: setElements, index: setElements.count - 1, count: setElements.count)
}
//传入index是为了处理是否要将第index个元素加入到子集合中；
//传入count是为了处理原集合中没有元素的情形。
private func getSubsets1<T>(elements: Array<T>, index: Int, count: Int) -> Array<Set<T>> {
var subSets = Array<Set<T>>()
if count <= 0 {
return subSets
}
if index == 0 { // 处理第一个元素
subSets.append(Set<T>())
var subSet = Set<T>()
subSet.insert(elements[0])
subSets.append(subSet)
return subSets
}
subSets = getSubsets1(elements: elements, index: index - 1, count: count)
for subSet in subSets {
var subsetWithCurret = subSet
subsetWithCurret.insert(elements[index])
subSets.append(subsetWithCurret)
}
return subSets
}
核心思路：
如果只有一个元素，那么它的子集有两个，分别是自身和空集。
如果有多个元素，那么在前面第一个元素的两个子集（空集和第一个元素自身）的基础上，第二个元素有两种选法，要么加入前面的子集里面，要么不加入前面的子集里面。
而前面的子集一共有两个，对每一个子集，都有来自于下一个元素的加入与不加入两种选法，也就是说，此时的前面的这两个子集，都是下一个元素没有加入的情形，当把下一个元素加入之后，那么就可以得到两个元素的子集一共有4个。
以此类推，就可以得出n个元素的所有子集。
Dictionary
字典的初级语法：Swift基础语法（一）
字典是存储无序的互相关联的同一类型的Key和同一类型的值的集合。
字典的Key必须是可哈希的
struct Person: Hashable {
var name: String
var age: Int
func hash(into hasher: inout Hasher) {
hasher.combine(name)
}
}
var dic1 = [Person(name: "norman", age: 29) : 100]
dic1.updateValue(99, forKey: Person(name: "norman", age: 30))
print(dic1) // [LavieSwift.Person(name: "norman", age: 29): 100, LavieSwift.Person(name: "norman", age: 30): 99]这段代码中，我使用了Person对象作为的字典的key，正常情况下，自定义的类型是不可以作为字典的Key的，但是我给Person结构体遵循了Hashable协议，因此Person对象就可以作为字典的key了。
通过最后的打印结果可以看出来，dic的Value值更新了，但是dic的key（即Person对象）的age并没有改变，这是因为我在Person的hash方法中只绑定了name属性，因此，只要name相同，就会认定这两个Person对象相同。
Swift中的字典类型是无序的，如果要想以特定的顺序遍历字典的键或者值，需要使用Sorted方法：
let dic = ["lily":33, "norman":77, "lavie":55, "moon":22, "marks":73]
for key in dic.keys.sorted() {
print(key)
}
for value in dic.values.sorted() {
print(value)
}
打印如下：
lavie
lily
marks
moon
norman
22
33
55
73
77KeyValuePairs
字典是无序的，如果想要字典的结构，又需要有序，那么可以使用KeyValuePairs：
let kvs: KeyValuePairs = ["a":1, "b":2, "c":3, "d":4, "e":5]
print(kvs) // ["a": 1, "b": 2, "c": 3, "d": 4, "e": 5]合并两个字典
使用merge来合并两个字典。
当Key重合的时候，采用当前字典的value值：
var dic1 = ["lily":33, "norman":77, "lavie":55, "moon":22, "marks":73]
let dic2 = ["moon":122, "marks":173, "lily":118]
dic1.merge(dic2) { (current, _) -> Int in current } // 当Key重合的时候，采用当前字典的value值
print(dic1) // ["marks": 73, "norman": 77, "lavie": 55, "moon": 22, "lily": 33]当Key重合的时候，采用新字典中的value值：
var dic1 = ["lily":33, "norman":77, "lavie":55, "moon":22, "marks":73]
let dic2 = ["moon":122, "marks":173, "lily":118]
dic1.merge(dic2) { (_, new) -> Int in new } // 当Key重合的时候，采用新字典中的value值
print(dic1) // ["marks": 173, "norman": 77, "lavie": 55, "lily": 118, "moon": 122]以上。