下载掌阅APP，畅读海量书库
立即打开
集合类型（Collection）指的是那些稳定的序列，它们能够被多次遍历且保持一致。除线性遍历外，集合中的元素也可以通过下标索引的方式被获取到。下标索引通常是整数，至少在数组中是这样的。不过下面会看到，索引也可以是一些不透明值（比如在字典或者字符串中），这有时候让使用起来不那么直观。集合的索引值可以构成一个有限的范围，它具有定义好了的开始索引和终止索引。也就是说，和序列不同，集合类型不能是无限的。
Collection协议是建立在Sequence协议上的。除从Sequence继承了全部方法外，得益于可以获取指定位置的元素以及稳定迭代的保证，集合还获取了一些新的能力。比如count属性，如果序列是不稳定的，那么对序列计数将会消耗序列中的元素，这显然不是我们的目的。但是对于稳定的集合类型，我们就可以对其进行计数。
即使用不到集合类型提供的这些特性，我们依旧可以让自己的序列满足Collection协议，这将告诉我们的序列类型的使用者该序列是有限的，而且可以进行多次迭代。不过如果我们只是想说明序列可以被多次迭代，但却必须去选一个合适的索引类型，那么确实会显得比较奇怪。在实现Collection协议时，最难的部分在于选取一个合适的索引类型来表达集合类型中的位置。这样设计的一个目的是，Swift团队希望避免引入一个专门的可多次迭代序列的协议 [3] ，因为它和Sequence拥有同样的要求，但是语义却不一致，这样容易让用户感到迷惑。
集合类型在标准库中运用广泛。除Array、Dictionary和Set外，String的四种表示方式都是集合类型。另外还有CountableRange和UnsafeBufferPointer也是如此。更进一步，我们可以看到标准库外的一些类型也遵守了Collection协议。有两个我们熟知的类型通过这种方法获得了很多新的能力，它们是Data和IndexSet，它们都来自Foundation框架。
为了展示Swift中集合类型的工作方式，我们将实现一个自己的集合类型。可能在Swift的标准库中没有被实现，但是最有用的容器类型就是队列了。Swift数组可以很容易地被当作栈来使用，我们可以用append来入栈，用popLast来出栈。但是对队列来说，就不那么理想。可以结合使用push和remove(at:0)来实现，但是因为数组是在连续的内存中持有元素的，所以在移除非数组尾部元素时，其他每个元素都需要移动去填补空白，这个操作的复杂度会是 O ( n )（而出栈最后一个元素只需要常数的时间就能完成）。
在实际实现队列之前，我们应该先定义它到底是什么。定义一个协议来描述队列到底是什么，是一个好方法。先来看看下面的定义：
///一个能够将元素入队和出队的类型
protocol Queue{
///在self中所持有的元素的类型
associatedtype Element
///将newElement入队到self
mutating func enqueue(_newElement:Element)
///从self出队一个元素
mutating func dequeue()->Element?
}
就这么简单，它表述了我们通常所说的队列的定义：这个协议是通用的，通过设定关联类型Element，它能够包含任意的类型。协议中没有任何关于Element的限制，它只需要是某个特定的类型就可以了。
需要特别指出的是，在上面协议中，方法前的注释非常重要，它和实际的方法名及类型名一样，也是协议的一部分，这些注释用来保证协议应有的行为。在这里，我们并没有给出超过我们现在所做的范围的承诺：没有保证enqueue或者dequeue的复杂度。我们其实可以写一些要求，比如这两个操作的复杂度应该是常数时间（ O (1)）。这将会给协议的使用者一个大概的概念，满足这个协议的 所有 类型都应该非常快。但是实际上这取决于最终实现所采用的数据结构，比如对一个优先队列来说，入队操作的复杂度就可能是 O (log n )，而非 O (1)。我们也没有提供一个peek操作来在不出队的前提下检视队列的内容。也就是说，我们的队列定义里就不包含这样的特性，只能进行出队，而不能peek。另外，它没有指定这两个操作是否是线程安全的，也没有说明这个队列是不是一个Collection（虽然稍后将它作为集合类型进行了实现）。
我们也没有说过这是一个先进先出（FIFO）队列，它甚至可以是一个后进先出（LIFO）队列，这样我们就可以用Array来实现它了，只需要用append来实现enqueue，然后用结合使用isEmpty和popLast来实现dequeue就行了。
话说回来，在这里协议 确实 还是指定了一些规则的：和Array的popLast类似（但是和它的removeLast不同），dequeue返回的是可选值。如果队列为空，那么它将返回nil，否则它将移除需要出队的元素并返回它。我们没有提供一个Array.removeLast那样的当数组为空时就让程序崩溃的类似的方法。
通过将dequeue设置为可选值，可以将这个操作缩短到一行中，同时这种做法是安全的，不会出现错误：
while let x=q.dequeue(){
//处理队列元素
}
缺点是就算已经知道队列 不可能 为空时，也还是需要进行解包。最好通过权衡你的使用方式来决定选择合适的数据类型。（不过，如果自定义类型满足Collection协议，就可以免费得到popFirst和removeFirst这两个版本的方法了，它们都已经被Collection实现了。）
现在我们定义了队列，让我们开始实现它吧。下面是一个很简单的先进先出队列，它的enqueue和dequeue方法是基于一系列数组来构建的。
因为我们把队列的泛型占位符命名为与协议中所要求的关联值一样的Element，所以就不需要再次对它进行定义了。这个占位类型并不是一定需要叫作Element，我们只是随意选择的。我们也可以把它叫作Foo，不过这样的话，我们就还需要定义typealias Element=Foo，或者让Swift通过enqueue和dequeue的实现所返回的类型来进行隐式的类型推断：
///一个高效的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()
}
}
这个实现使用两个栈（两个常规的Swift数组）来模拟队列的行为。当元素入队时，它们被添加到“右”栈中。当元素出队时，它们从“右”栈的反序数组的“左”栈中被弹出。当左栈变为空时，再将右栈反序后设置为左栈。
你可能会对dequeue操作被声明为 O (1)感到有一点奇怪。确实，它包含了一个复杂度为 O ( n )的reverse操作。对于单个的操作来说可能耗时会长一些，不过对于非常多的push和pop操作来说，取出一个元素的平摊耗时 [4] 是一个常数。
理解这个复杂度的关键在于理解反向操作发生的频率以及发生在多少个元素上。我们可以使用“银行家理论”来分析平摊复杂度。想象一下，你每次将一个元素放入队列，就相当于你在银行存了一元钱。接下来，你把右侧的栈的内容转移到左侧，因为对应每个已经入队的元素，你在银行里都相当于有一元钱。你可以用这些钱来支付反转。你的账户永远不会负债，你也从来不会花费比你付出的更多的钱。
这个理论可以用来解释一个操作的消耗在时间上进行 平摊 的情况，即便其中的某次调用可能不是常数，但平摊下来以后这个耗时依然是常数。在Swift中向数组后面添加一个元素的操作是常数时间复杂度，这也可以用同样的理论进行解释。当数组存储空间耗尽时，它需要申请更大的空间，并且把所有已经存在于数组中的元素复制过去。但是因为每次申请空间都会使存储空间翻倍，“添加元素，支付一元钱，数组尺寸翻倍，最多耗费所有钱来进行复制”这个理论已然是有效的。
现在我们拥有一个可以出队和入队元素的容器了。下一步是为FIFOQueue添加Collection协议的支持。不幸的是，在Swift中，想要找出要遵守某个协议所需要提供的最少实现有时候并不容易。
在本章写作的时候，Collection协议有四个关联类型、四个属性、七个实例方法，以及两个下标方法：
protocol Collection:Indexable,Sequence{
associatedtype Iterator:IteratorProtocol=IndexingIterator<Self>
associatedtype SubSequence:IndexableBase,Sequence=Slice<Self>
associatedtype IndexDistance:SignedInteger=Int
associatedtype Indices:IndexableBase,Sequence=DefaultIndices<Self>
var first:Iterator.Element?{get}
var indices:Indices{get}
var isEmpty:Bool{get}
var count:IndexDistance{get}
func makeIterator()->Iterator
func prefix(through position:Index)->SubSequence
func prefix(upTo end:Index)->SubSequence
func suffix(from start:Index)->SubSequence
func distance(from start:Index,to end:Index)->IndexDistance
func index(_i:Index,offsetBy n:IndexDistance)->Index
func index(_i:Index,offsetBy n:IndexDistance,limitedBy limit:Index)->Index?
subscript(position:Index)->Iterator.Element{get}
subscript(bounds:Range<Index>)->SubSequence{get}
}
而且它还继承了Sequence和Indexable，所以想要实现我们的类型，则还需要将那些协议的需求也添加到to-do列表中。想想就让人绝望吧？
好吧，其实实际上事情没那么糟。可以看到，所有的关联类型都有默认值，所以除非你的类型有特殊的要求，否则你不必去关心它。对于大部分方法、属性和下标，这一点也同样适用：Collection的协议扩展为我们提供了默认的实现。这些扩展有一些包含关联类型的约束，它们要求协议中的关联类型需要是默认类型；比如，Collection只为那些其中Iterator 为IndexingIterator<Self>的类型提供makeIterator方法的默认实现：
extension Collection where Iterator==IndexingIterator<Self>{
///返回一个基于集合元素的迭代器
func makeIterator()->IndexingIterator<Self>
}
如果你的类型需要一个不同的迭代器类型，那么你就需要自己实现这个方法。
寻找哪些是必需的，哪些已经默认提供了，这件事本身并不十分困难，不过它需要很多手动工作，而且一旦你不小心，就可能会陷入和编译器进行猜测的境地，这十分烦人。其中最恼人的部分在于，编译器会将所有的信息提供给你，这些信息其实并没有给我们足够的帮助。结果，其实你最应该给予希望的是满足一个协议的最小需求已经被写在文档里了，Collection就是这么做的。
遵守Collection协议
……要使你的类型满足Collection，你可以声明startIndex和endIndex属性，并提供一个下标方法，使其至少能够读取你的类型的元素。最后，你还需要提供index(after:)方法来在你的集合索引之间进行步进。
于是最后，我们需要实现的有：
protocol Collection:Indexable,Sequence{
///一个表示集合中位置的类型
associatedtype Index:Comparable
///一个非空集合中首个元素的位置
var startIndex:Index{get}
///集合中超过末位的位置，也就是比最后一个有效下标值大1的位置
var endIndex:Index{get}
///返回在给定索引之后的那个索引值
func index(after i:Index)->Index
///访问特定位置的元素
subscript(position:Index)->Element{get}
}
相比最初Collection协议的要求，只有下标被保留了。其他的要求是通过IndexableBase以及Indexable的路径继承下来的。IndexableBase和Indexable这两个协议可以被看作只存在于Swift3中的实现细节，这是由于Swift3中缺少对循环协议约束的支持所导致的。我们希望它们能够在Swift4里被移除，并折叠进Collection中。我们应该不会需要直接用到这些协议。
我们能够让FIFOQueue满足Collection了：
extension FIFOQueue:Collection{
public var startIndex:Int{return 0}
public var endIndex:Int{return left.count+right.count}
public func index(after i:Int)->Int{
precondition(i<endIndex)
return i+1
}
public subscript(position:Int)->Element{
precondition((0..<endIndex).contains(position),"Index out of bounds")
if position<left.endIndex{
return left[left.count-position-1]
}else{
return right[position-left.count]
}
}
}
上面使用Int来作为Index类型。这里没有显式地提供这个关联类型，和Element一样，Swift可以帮我们从方法和属性的定义中将它推断出来。注意索引集合是从开头开始返回元素的，所以Queue.first将会返回下一个即将被出队的元素（你可以将它当作peek来使用）。
有了这几行代码，队列已经拥有超过40个方法和属性供我们使用了。我们可以迭代队列：
var q=FIFOQueue<String>()
for x in["1","2","foo","3"]{
q.enqueue(x)
}
for s in q{
print(s,terminator:"")
}//1 2 foo 3
可以将队列传递给接受序列的方法：
var a=Array(q)//["1","2","foo","3"]
a.append(contentsOf:q[2...3])//()
可以调用那些Sequence的扩展方法和属性：
q.map{$0.uppercased()}//["1","2","FOO","3"]
q.flatMap{Int($0)}//[1,2,3]
q.filter{$0.characters.count>1}//["foo"]
q.sorted()//["1","2","3","foo"]
q.joined(separator:"")//1 2 foo 3
也可以调用Collection的扩展方法和属性：
q.isEmpty//false
q.count//4
q.first//Optional("1")
当实现一个类似队列这样的集合类型时，最好也去实现一下ExpressibleByArrayLiteral。这可以让用户以他们所熟知的[value1,value2,etc]语法创建一个队列。要做到这个非常简单：
extension FIFOQueue:ExpressibleByArrayLiteral{
public init(arrayLiteral elements:Element...){
self.init(left:elements.reversed(),right:[])
}
}
对我们的队列逻辑来说，我们希望元素已经在左侧的缓冲区准备好。当然，我们也可以将这些元素直接放在右侧数组里，但是因为在出队时我们迟早要将它们复制到左侧，所以直接先逆序将它们复制过去会更高效一些。
现在我们就可以用数组字面量来创建一个队列了：
let queue:FIFOQueue=[1,2,3]
//FIFOQueue<Int>(left:[3,2,1],right:[])
在这里需要特别注意Swift中字面量和类型的区别。这里的[1,2,3]并不是一个数组，它只是一个“数组字面量”，是一种写法，我们可以用它来创建任意的遵守ExpressibleByArrayLiteral的类型。在这个字面量里面还包括了其他的字面量类型，比如能够创建任意遵守ExpressibleByIntegerLiteral的整数型字面量。
这些字面量有“默认”的类型，如果我们不指明类型，那么那些Swift将假设我们想要的就是默认的类型。正如我们所料，数组字面量的默认类型是Array，整数字面量的默认类型是Int，浮点数字面量默认为Double，而字符串字面量则对应String。但是这只发生在我们没有指定类型的情况下，举个例子，上面声明了一个类型为Int的队列类型，但是如果指定了其他整数类型，那么也可以声明一个其他类型的队列：
let byteQueue:FIFOQueue<UInt8>=[1,2,3]
//FIFOQueue<UInt8>(left:[3,2,1],right:[])
通常来说，字面量的类型可以从上下文中推断出来。举个例子，下面这个函数可以接受一个从字面量创建的参数，而调用时所传递的字面量的类型，可以根据函数参数的类型被推断出来：
func takesSetOfFloats(floats:Set<Float>){
//...
}
takesSetOfFloats(floats:[1,2,3])
//这个字面量被推断为Set，而不是Array
在前面你已经看到Collection为除Index外的关联类型提供了默认值。虽然你 不需要 关心其他的关联类型，不过如果能简单看看它们到底是什么，则会对你理解它们做的事情有所帮助。
Iterator。这是从Sequence所继承的关联类型。我们已经在关于序列的篇幅中详细看过迭代器的相关内容了。集合类型中的默认迭代器类型是IndexingIterator<Self>，这个类型是一个很简单的结构体，它是对集合的封装，并用集合本身的索引来迭代每个元素。它的实现 [5] 非常直接：
struct IndexingIterator<Elements:IndexableBase>:IteratorProtocol,Sequence{
private let_elements:Elements
private var_position:Elements.Index
init(_elements:Elements){
self._elements=_elements
self._position=_elements.startIndex
}
mutating func next()->Elements._Element?{
guard_position<_elements.endIndex else{
return nil
}
let element=_elements[_position]
_elements.formIndex(after:&_position)
return element
}
}
（<Elements:IndexableBase>这个泛型约束其实应该是<Elements:Collection>，不过编译器还不允许循环关联类型约束。）
标准库中大多数集合类型都使用IndexingIterator作为它们的迭代器。我们几乎没有理由需要为一个自定义的集合类型写一个自己的迭代器类型。
SubSequence。也是从Sequence继承的，不过Collection用更严格的约束重新定义了这个类型。一个集合类型的SubSequence本身也应该是一个Collection（我们这里使用了“应该”而不是“必须”这个词，是因为现在在类型系统中无法表达出这个约束）。它的默认值是Slice<Self>，它是对原来的集合的封装，并存储了切片相对于原来集合的起始和终止索引。集合类型可以对它的SubSequence的类型进行自定义，这种情况并不少见，特别是当SubSequence就是Self时（也就是说，一个集合的切片拥有和集合本身相同的类型）。我们会在本章后面的切片部分再回到这个话题。
IndexDistance。一个有符号整数类型，代表了两个索引之间的步数。应该没有理由去改变它的默认值Int。
Indices。集合的indices属性的返回值类型。它代表对于集合的所有有效下标的索引所组成的集合，并以升序进行排列。注意endIndex并不包含在其中，因为endIndex代表的是最后一个有效索引之后的那个索引，它不是有效的下标参数。
在Swift2中，indices属性返回的是Range<Index>，我们可以用它来迭代集合类型中的所有有效索引。在Swift3里，因为索引自己不再能够进行步进，而是由集合来决定索引的迭代，所以Range<Index>不再能够进行迭代了。Indices类型也取代了Range<Index>以使对索引的迭代能够保持工作。
Indices的默认类型是DefaultIndices<Self>。和Slice一样，它是对于原来的集合类型的简单封装，并包含起始和终止索引。它需要保持对原集合的引用，这样才能够对索引进行步进。当用户在迭代索引的同时改变集合的内容时，可能会造成意想不到的性能问题：如果集合是以写时复制（就像标准库中的所有集合类型所做的一样）来实现，那么这个对于集合的额外引用将触发不必要的复制。在结构体和类中会涉及写时复制的内容，现在，你只需要知道如果在为自定义集合提供另外的Indices类型作为替换，那么你不需要让它保持对原集合的引用，这样做可以带来性能上的提升。这对于那些计算索引时不依赖于集合本身的集合类型都是有效的，比如数组或者我们的队列就是这样的例子。如果索引是整数类型，那么可以直接使用CountableRange<Index>：
extension FIFOQueue:Collection{
...
typealias Indices=CountableRange<Int>
var indices:CountableRange<Int>{
return startIndex..<endIndex
}
}