购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.3 Set

标准库中第三种主要的集合类型是集合Set(虽然听起来有些别扭)。集合是一组无序的元素,每个元素只会出现一次。你可以将集合想象为一个只存储了键而没有存储值的字典。和Dictionary一样,Set也是通过哈希表实现的,并拥有类似的性能特性和要求。测试集合中

是否包含某个元素是一个常数时间的操作,和字典中的键一样,集合中的元素也必须满足Hashable。

如果你需要高效地测试某个元素是否存在于序列中并且元素的顺序不重要时,使用集合是更好的选择(同样的操作在数组中的复杂度是 O ( n ))。另外,当你需要保证序列中不出现重复元素时,也可以使用集合。

Set遵守ExpressibleByArrayLiteral协议,也就是说,我们可以用数组字面量的方式初始化一个集合:

let naturals:Set=[1,2,3,2]

naturals//[2,3,1]

naturals.contains(3)//true

naturals.contains(0)//false

注意数字2在集合中只出现了一次,重复的数字并没有被插入到集合中。

和其他集合类型一样,集合也支持我们已经见过的那些基本操作:你可以用for循环进行迭代,对它进行map或filter操作,或者做其他各种事情。

集合代数

正如其名,集合Set和数学概念上的集合有着紧密关系;Set也支持你在高中数学中学到的那些基本集合操作。比如,我们可以在一个集合中求另一个集合的 补集

let iPods:Set=["iPod touch","iPod nano","iPod mini",

"iPod shuffle","iPod Classic"]

let discontinuedIPods:Set=["iPod mini","iPod Classic"]

let currentIPods=iPods.subtracting(discontinuedIPods)

//["iPod shuffle","iPod nano","iPod touch"]

我们也可以求两个集合的 交集 ,找出两个集合中都含有的元素:

let touchscreen:Set=["iPhone","iPad","iPod touch","iPod nano"]

let iPodsWithTouch=iPods.intersection(touchscreen)

//["iPod touch","iPod nano"]

或者,我们能求两个集合的 并集 ,将两个集合合并为一个(当然,移除那些重复多余的元素):

var discontinued:Set=["iBook","Powerbook","Power Mac"]

discontinued.formUnion(discontinuedIPods)

//["iBook","iPod mini","Powerbook","Power Mac","iPod Classic"]这里我们使用了可变版本的formUnion来改变原来的集合(正因如此,我们需要将原来的集合用var声明)。几乎所有的集合操作都有不可变版本以及可变版本的形式,后一种都以form...开头。想要了解更多的集合操作,可以看看SetAlgebra协议。

索引集合和字符集合

Set是标准库中唯一实现了SetAlgebra的类型,但是这个协议在Foundation中还被另外两个很有意思的类型实现了:那就是IndexSet和CharacterSet。两者都是在Swift诞生之前很久就已经存在的了。包括这两个类在内的其他一些Objective-C类现在被完全以值类型的方式导入Swift中,在此过程中,它们还遵守了一些常见的标准库协议。这对Swift开发者来说非常友好,这些类型立刻就变得熟悉了。

IndexSet表示了一个由正整数组成的集合。当然,你可以用Set<Int>来做这件事情,但是IndexSet更加高效,因为它内部使用了一组范围列表进行实现。打个比方,现在有一个含有1000个用户的table view,你想要用一个集合来管理已经被选中的用户的索引。使用Set<Int>的话,根据选中的个数不同,则最多可能会存储1000个元素。而IndexSet不太一样,它会存储连续的范围,也就是说,在选取前500行的情况下,IndexSet里其实只存储了选择的首位和末位两个整数值。

不过,作为IndexSet的用户,你不需要关心这个数据结构的内部实现,所有这一切都隐藏在我们所熟知的SetAlgebra和Collection接口之下。(除非你确实需要直接操作内部的范围,对于这种需求,IndexSet暴露了它的rangeView属性,代表了集合内部的范围)。举例来说,你可以向一个索引集合中添加一些范围,然后对这些索引map操作,就像它们是独立的元素一样:

var indices=IndexSet()

indices.insert(integersIn:1..<5)

indices.insert(integersIn:11..<15)

let evenIndices=indices.filter{$0%2==0}//[2,4,12,14]

同样地,CharacterSet是一个高效的存储Unicode字符的集合。它经常被用来检查一个特定的字符串是否只包含某个字符子集(比如字母数字alphanumerics或者数字decimalDigits)中的字符。不过和IndexSet有所不同,CharacterSet并不是一个集合类型。本书会在字符串一章中对CharacterSet进行更多讨论。

在闭包中使用集合

就算不暴露给函数的调用者,字典和集合在函数中也会是非常好用的数据结构。如果想要为Sequence写一个扩展,来获取序列中所有的唯一元素,那么只需要将这些元素放到一个Set里,然后返回这个集合的内容就行了。不过,因为Set并没有定义顺序,所以这么做是 不稳定 的,输入的元素的顺序在结果中可能会不一致。为了解决这个问题,我们可以创建一个扩展来解决这个问题,在扩展方法内部我们还是使用Set来验证唯一性:

extension Sequence where Iterator.Element:Hashable{

func unique()->[Iterator.Element]{

var seen:Set<Iterator.Element>=[]

return filter{

if seen.contains($0){

return false

}else{

seen.insert($0)

return true

}

}

}

}

[1,2,3,12,1,3,4,5,6,4,6].unique()//[1,2,3,12,4,5,6]

上面这个方法让我们可以找到序列中的所有不重复的元素,并且维持它们原来的顺序。在传递给filter的闭包中,使用了一个外部的seen变量,我们可以在闭包里访问和修改它的值。本书会在函数一章中详细讨论它背后的技术。 ZwiEb5y6BGtDNbfi0AhcrlzcIGEFgcaSfxkfrpy+0+/3xpImZevWCw93L/osNkaw

点击中间区域
呼出菜单
上一章
目录
下一章
×