Swift 中的集合类型包括:Array，Dictionary 和 Set 等。它们是建立在一系列由 Swift 标准库提供的用来处理元素序列的抽象之上的。将讨论 Sequence 和 Collection 协议，它们构成了这套集合类型模型的基石。研究这些协议是如何工作的，它们为什么要这样工作，以及如何自定义序列和集合类型等话题。

Sequence 提供了迭代的能力。它允许创建一个迭代器，但对于序列是否只能单次遍历 (例如读取标准输入的内容) 或者支持多次遍历 (例如遍历一个数组)，则不提供任何保障。
Collection 扩展了 Sequence。它不仅是一个可以多次遍历的序列，还允许你通过索引访问其中的元素。并且，Collection 还通过 SubSequence 提供了集合切片的能力，而这个切片自身也是一个集合。
MutableCollection 提供了可以在常数时间内，通过下标修改集合元素的能力。但它不允许向集合中添加删除元素。
RangeReplaceableCollection 提供了替换集合中一个连续区间的元素的能力。通过扩展，这个能力还衍生出了诸如 append 和 remove 等方法。很多可变集合类型 (mutable collections) 都可以进行区间内容替换，但其中也有例外。例如，最常用的 Set 和 Dictionary 就不支持这个操作，而 Array 和 String 则没问题。
BidirectionalCollection 添加了从集合尾部向集合头部遍历的能力。显然，无法遍历一个 Dictionary，但 “逆着” 遍历一个字符串则完全没问题。对于某些算法来说，逆向遍历是一个至关重要的操作。
RandomAccessCollection 扩展了 BidirectionalCollection，添加了更有效率的索引计算能力:它要求计算索引之间的距离或移动索引位置都是常数时间的操作。例如:Array 就是一个随机访问集合，但字符串就不是，因为计算两个字符之间距离是一个线性时间的操作。
LazySequenceProtocol 定义了一个只有在开始遍历时才计算其中元素的序列。在函数式风格编写的算法里，它很常用:可以接受一个无穷序列，从中筛选元素，然后读取结果中的前几个记录。这个过程并不会因为需要计算结果集之外的无穷多个元素而耗尽资源。
LazyCollectionProtocol 和 LazySequenceProtocol 是类似的，只是它用于定义有相同行为特性的集合类型。

序列

Sequence 协议是集合类型结构中的基础。一个序列 (sequence) 代表的是一系列类型相同的值，可以对这些值进行迭代。遍历一个序列最简单的方式是使用 for 循环:

for element in someSequence { 
    doSomething(with: element)
}
复制代码

实际上，Sequence 依赖于上面这种步进式迭代元素的能力，为实现它的类型提供了大量有用的方法。

protocol Sequence {
    associatedtype Element associatedtype Iterator: IteratorProtocol
    func makeIterator() -> Iterator
    // ...
}
复制代码

从这个 (简化后的) Sequence 定义中，能发现两件事情:一个是 Sequence 有一个关联类型 Element，另一个是它有一个创建迭代器的方法。

迭代器

序列通过创建一个迭代器来提供对元素的访问。迭代器每次产生序列中的一个值，并对遍历状态进行管理。在 IteratorProtocol 协议中，唯一的一个方法是 next()，这个方法需要在每次被调用时返回序列中的下一个值。当序列被耗尽时，next() 应该返回 nil:

protocol IteratorProtocol { 
    associatedtype Element 
    mutating func next() -> Element?
}
复制代码

关联类型 Element 指定了迭代器产生的值的类型。比如 String 的迭代器的元素类型是 Character。通过扩展，迭代器同时也定义了它对应的序列的元素类型。这是通过给 Sequence 的关联类型 Iterator 定义了一个类型约束实现的:Iterator.Element == Element，它确保了序列和迭代器中的元素类型是一致的:

protocol Sequence {
    associatedtype Element 
    associatedtype Iterator: IteratorProtocol
        where Iterator.Element == Element // ...
}
复制代码

一般来说，只有在实现一个自定义序列类型的时候，才需要关心迭代器。除此之外，几乎不会直接去使用它，因为 for 循环才是我们遍历序列常用的方式。实际上，for 正是通过迭代器实现的:编译器会为序列创建一个新的迭代器，并且不断调用迭代器的 next 方法，直到它返回 nil 为止。从本质上说， for 循环，其实是下面这段代码的一种简写形式:

var iterator = someSequence.makeIterator() 
while let element = iterator.next() {
    doSomething(with: element) 
}
复制代码

迭代器是单向结构，它只能按照增加的方向前进，而不能倒退或者重置。为了重新迭代，只能新建一个迭代器 (实际上，这也正是 Sequence 允许通过 makeIterator() 完成的操作)。虽然大部分的迭代器的 next() 都只产生有限数量的元素，并最终会返回 nil，但是也完全可以创建一个无限的序列。实际上，除了那种一上来就返回 nil 的迭代器，最简单的情况应该是一个不断返回同样值的迭代器了:

struct ConstantIterator: IteratorProtocol { 
    typealias Element = Int
    mutating func next() -> Int? {
    return 1 
    }
}
复制代码

在上面的代码里，并不用显式使用 typealias 指定 Element 的类型 (不过通常可以把这种做法看作文档，它有助于理解代码，特别是大型协议中这点尤为明显)。即便去掉它，编译器也可以从 next() 的返回值中推断出 Element 的类型。

注意这里 next() 被标记为了 mutating。对于这个简单的例子来说，我们的迭代器不包含任何可变状态，所以它并不是必须的。不过在实践中，迭代器的本质是存在状态的。几乎所有有意义的迭代器都会要求可变状态，这样它们才能够管理在序列中的当前位置。

现在，我们可以创建一个 ConstantIterator 的实例，并使用 while 循环来对它产生的序列进行迭代，这将会打印无穷的数字 1:

var iterator = ConstantIterator() 
while let x = iterator.next() {
    print(x) 
}
复制代码

FibsIterator 可以产生一个斐波那契序列。它记录接下来的两个数字，并作为状态存储。而 next 方法则返回第一个数，并在接下来的调用中更新存储的状态。和之前的例子一样，这个迭代器也将产生一个 “无限” 序列，它将持续累加数字，直到程序因为所得到的数字发生类型溢出而崩溃:

struct FibsIterator: IteratorProtocol {
    var state = (0, 1)
    mutating func next() -> Int? {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        return upcomingNumber
    }
}
var a = FibsIterator.init()
while let b = a.next() {
    print(b)
}
/*
0  1  1  2  3  5  8...
*/
复制代码

遵守序列协议

我们也可以创造有限序列的迭代器，例如下面这个 PrefixGenerator，它将顺次生成字符串的所有非空前缀 (也包含字符串本身)。对于字符串 “abc” 来说，它会生成 “a”，”ab” 和 “abc”。它从字符串的起始位置开始，每次调用 next，就在上一次返回的字符串切片后面追加当前位置的下一个字符，直到遍历完整个字符串为止:

struct PrefixIterator: IteratorProtocol {
    
    typealias Element = Substring
    var string: String
    var offset: String.Index
    
    init(string: String) {
        self.string = string
        offset = string.startIndex
    }
    
    mutating func next() -> Element? {
        guard offset < string.endIndex else {
            return nil
        }
        offset = string.index(after: offset)
        return string[..<offset]
    }
}

var test = "abcdefg"
var iterator = PrefixIterator.init(string: test)
while let temp = iterator.next() {
    print(String(temp))
}
//a
//ab
//abc
//abcd
//abcde
//abcdef
//abcdefg
复制代码

有了 PrefixIterator，定义一个 PrefixSequence 类型就很容易了。和之前一样，不需要指明关联类型 Iterator 或 Element 的具体类型，因为编译器可以从 makeIterator 方法的返回类型中自己推断出来:

struct PrefixSequence: Sequence {
    let string: String
    func makeIterator() -> some IteratorProtocol {
        return PrefixIterator.init(string: string)
    }
}

var sequence = PrefixSequence(string: test)
for it in PrefixSequence.init(string: "abcdefg") {
    print(it)
}
//a
//ab
//abc
//abcd
//abcde
//abcdef
//abcdefg
复制代码

迭代器和值语义

至今为止，迭代器都具有值语义.如果复制一份，迭代器的所有状态也都会被复制，这两个迭代器将分别在自己的范围内工作。标准库中的大部分迭代器也都具有值语义，不过也有例外存在。

为了说明值语义和引用语义的不同，先看 StrideToIterator 的例子。它是 stride(from:to:by:) 方法返回的序列所使用的迭代器。可以创建一个 StrideToIterator 并试着调用几次 next 方法:

// 一个从0到9的序列
let seq = stride(from: 0, to: 10, by: 1)
var i1 = seq.makeIterator() i1.next() // Optional(0) 
i1.next() // Optional(1)

// 现在，i1 已经准备好返回 2 了。接下来，对它进行复制: 
var i2 = i1

// 这样，原有的迭代器和新复制的迭代器就是分开且独立的了。
// 在下两次 next 时，它们都会分别 返回 2 和 3:
i1.next() // Optional(2) 
i1.next() // Optional(3) 
i2.next() // Optional(2) 
i2.next() // Optional(3)
复制代码

这是因为 StrideToIterator 是一个很简单的结构体，它的实现和上面的斐波纳契迭代器没有太大不同，也具有值语义。

接下来，再来看一个不具有值语义的迭代器的例子。AnyIterator 是一个对别的迭代器进行封装的迭代器，它可以将原始迭代器的具体类型 “抹消” 掉。

比如你在创建公有 API 时想要将一个很复杂的迭代器的具体类型隐藏起来，而不暴露它的具体实现的时候，就可以使用这种迭代器。AnyIterator 进行封装的做法是将另外的迭代器包装到一个内部的盒子对象中，而这个对象是引用类型 (可以看看协议一章中关于类型消除器部分的内容)。

创建一个包装了 i1 的 AnyIterator，然后进行复制:

var i3 = AnyIterator(i1) 
vari4=i3
复制代码

在这种情况下，原来的迭代器和它的副本就不再是彼此独立的了，因为它们不再是一个结构体， AnyIterator 并不具有值语义。AnyIterator 中用来存储原始迭代器的盒子对象是一个类实例，当我们将 i3 赋值给 i4 的时候，只有对这个盒子的引用被复制了。盒子里存储的对象将被两个迭代器所共享。所以，任何对 i3 或者 i4 进行的 next 调用，实际上都作用于底层那个相同的原始迭代器:

i3.next() // Optional(4) 
i4.next() // Optional(5) 
i3.next() // Optional(6) 
i3.next() // Optional(7)
复制代码

显然，这可能会造成一些 bug，不过在实践中可能很少会遇到这种问题，因为迭代器通常不会在代码里被传来传去。基本上你只是会在本地创建迭代器，用它来循环元素，然后就将其抛。这种行为有时是显式进行的，但更多的时候是通过使用 for 循环隐式完成的。如果发现要与其他对象共享迭代器，可以考虑将它封装到序列中，而不是直接传递它。

基于函数的迭代器和序列

AnyIterator 还有另外一个接受 next 函数作为参数的初始化方法。把它和对应的 AnySequence 类型结合起来使用，就可以让我们在不定义任何新类型的情况下，创建迭代器和序列。举个例子，可以通过一个返回 AnyIterator 的函数来定义斐波纳契迭代器:

func fibsIterator() -> AnyIterator<Int> {
    var state = (0, 1)
    return AnyIterator {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        return upcomingNumber
    }
}
复制代码

通过将 state 放到迭代器的 next 函数外面，并在闭包中将其进行捕获，闭包就可以在每次被调用时对其进行更新。这里的定义和上面使用自定义类型的斐波纳契迭代器只有一个功能上的不同，那就是自定义的结构体具有值语义，而使用 AnyIterator 定义的没有。

通过这种方式创建序列甚至更简单，因为 AnySequence 提供了一个接受返回迭代器的函数作为参数的初始化方法:

let fibsSequence = AnySequence(fibsIterator) 
Array(fibsSequence.prefix(10)) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
复制代码

另一种方法是使用 sequence 函数，这个函数有两个版本。第一个版本，sequence(first:next:) 它使用第一个参数的值作为序列的首个元素，并使用 next 参数传入的闭包生成序列的后续元素，最后返回生成的序列。另一个版本是 sequence(state:next:)，因为可以在两次 next 闭包被调用之间保存任意的可变状态，所以它更强大一些。通过它，我们可以只进行一次方法调用就构建出斐波纳契序列:

let fibsSequence = sequence(state: (0, 1), next: {
    state -> Int? in
    let num = state.0
    state = (state.1, state.0 + state.1)
    return num
})

print(Array(fibsSequence.prefix(10))) // [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
复制代码

sequence(first:next:) 和 sequence(state:next:) 的返回值类型是 UnfoldSequence。这个类型的名称来自函数式编程，在函数式编程中，这种操作被称为展开 (unfold)。sequence 是和 reduce 对应的，在函数式编程中 reduce 又常被叫做折叠 (fold)。 reduce 将一个序列缩减 (或者说折叠) 为一个单一的返回值，而 sequence 则将一个单一的值展开形成一个序列。

尽管 AnyIterator 要比那些有一长串复杂名称的迭代器看上去有好一些，标准库还是由于性能方面的原因更倾向于使用专门定制的迭代器类型。使用 AnyIterator 会导致编译器难以对这部分代码进行优化，有时，这会带来上百倍的性能损失。 forums.swift.org/t/rationali…

就像迭代器一样，sequence 对于 next 闭包的使用是被延迟的。也就是说，序列的下一个值不会被预先计算，它只在调用者需要的时候生成。这使得我们可以使用类似 fibsSequence.prefix(10) 这样的语句，因为 prefix(10) 只会向序列请求它的前十个元素，然后停止。如果序列是主动计算它的所有值的话，因为序列是无限的，程序将会在有机会执行下一步之前就因为整数溢出的问题而发生崩溃。

对于序列和集合来说，它们之间的一个重要区别就是序列可以是无限的，而集合则不行。

单次遍历序列

序列并不只限于像是数组或者列表这样的传统集合数据类型。像是网络流，磁盘上的文件，UI 事件的流，以及其他很多类型的数据都可以使用序列进行建模。但它们之中，并不是所有类型的序列都和数组一样，可以反复遍历其中的元素。

斐波纳契序列确实不会因为遍历其中的元素而发生改变，你可以从 0 开始再次进行遍历，但是像是网络包流这样的序列则只能遍历一次。就算再次对其进行迭代，它也不会产生同样的值。但斐波纳契序列和网络包流都是有效的序列，因此，Sequence 的文档非常明确地指出了序列并不保证可以被多次遍历:developer.apple.com/documentati…

Sequence 协议并不关心遵守该协议的类型是否会在迭代后将序列的元素销毁。也就是说，请不要假设对一个序列进行多次的 for-in 循环将继续之前的迭代或是从头开始。一个非集合的序列可能会在第二次 for-in 循环时产生随机的序列元素。

这也解释了为什么只有在集合类型上能见到 first 这个看起来很简单的属性，而序列中却没有。调用一个属性的 getter 方法应该是没有任何副作用的，但只有 Collection 协议能保证多次进行迭代是安全的。

举一个只能单次遍历序列的例子:有一个对 readLine 函数的封装，它会从标准输入中读取一行:

let standardIn = AnySequence { 
    return AnyIterator {
        readLine() 
    }
}
复制代码

现在，可以使用 Sequence 的各种扩展来进行操作了，比如可以这样来写一个带有行号的类似 Unix 中 cat 命令的函数:

let numberedStdIn = standardIn.enumerated() 
for (i, line) in numberedStdIn {
    print("\(i+1): \(line)") 
}
复制代码

enumerated 将一个序列转化为另一个带有 (从0开始) 递增数字的新序列。和 readLine 进行的封装一样，这里的元素也是延迟生成的。对原序列的消耗只在你通过迭代器读取序列下一个元素的时候发生，而不是在序列被创建时发生的。因此，如果在命令行中运行上面的代码，会看到程序在 for 循环中进行等待。当输入一行内容并按下回车的时候，程序才会打印出相应的内容。当按下 control-D 结束输入的时候，程序会停止等待。不过无论如何，每次 enumerated 从 standardIn 中获取一行时，它都会消耗掉标准输入中的一行，没有办法将这个序列迭代两次并获得相同的结果。

如果只是写一个 Sequence 扩展，你并不需要考虑这个序列是否只能单次遍历，但也应该尽可能基于单次遍历的序列实现你的算法。如果是一个序列方法的调用者，则应该时刻提醒注意正在使用的序列是否只能单次遍历。

如果一个序列遵守 Collection 协议的话，那它肯定可以被反复遍历，因为 Collection 在这方面进行了保证。但反过来却不一定，标准库中就有些序列可以安全地多次遍历，但它们并不是集合类型。例如:stride(from:to:by:) 返回的 StrideTo，以及 stride(from:through:by:) 返回的 StrideThrough。

序列和迭代器之间的关系

序列和迭代器非常相似，你可能会问，为什么它们会被分为不同的类型?为什么不能直接把 IteratorProtocol 的功能包含到 Sequence 中呢?对于单次遍历的序列 (例如之前标准输入的例子)，这么做确实没有问题。这类序列自己持有迭代状态，并且会随着遍历而发生改变。

然而，对于像斐波纳契序列这样的可多次遍历序列来说，它的值不能随着 for 循环而改变，它们需要独立的遍历状态，这就是迭代器所存在的意义 (当然还需要遍历的逻辑，不过这部分是序列的内容)。makeIterator 方法的目的就是创建这样一个遍历状态。

其实，可以把每一个迭代器都看作是由它们返回的元素所组成的单次遍历序列。实际上，只要声明迭代器实现了 Sequence 协议，它就可以名正言顺地成为一个序列类型。因为 Sequence 为迭代器类型提供了一个默认的 makeIterator 实现，这个方法就是返回 self 本身。
标准库中的大部分迭代器都实现了 Sequence 协议。

让 List 遵守 Sequence

在枚举这一章中，通过给间接枚举 (indirect enum) 实现 push 和 pop 方法，展示了一个链表的例子。这一节，我们让 List 实现 Sequence 协议。以下是一个更紧凑的 List 定义:

enum List<Element> {
    case end
    indirect case node(Element, next: List<Element>)
}

extension List {
    mutating func push(_ x: Element) {
        self = .node(x, next: self)
    }
    mutating func pop() -> Element? {
        switch self {
        case .end: return nil
        case let .node(x, next: tail):
            self = tail
            return x
        }
    }
}

// 另外， List 实现了 ExpressibleByArrayLiteral:
extension List: ExpressibleByArrayLiteral {
    public init(arrayLiteral elements: Element...) {
        self = elements.reversed().reduce(into: .end) {partialList, element in
            partialList.push(element)
        }
    }
}

let list: List = [3,2,1]
/*
node(3, 
next: List<Swift.Int>.node(2, 
next: List<Swift.Int>.node(1,
next: List<Swift.Int>.end))) 
*/
复制代码

List 是一个持久化数据结构:尽管一个 List 变量可以修改它指向的节点的值，但已经形成的列表结构，是不可修改的。出于这个特性，可以用 List 变量自身作为链表的迭代器。为了让 List 实现 Sequence 协议，我们只需要提供一个 next 实现，让它返回当前节点的值并移动到下一个节点就好了。而这，其实就是 pop 方法的工作:

extension List: IteratorProtocol, Sequence { 
    public mutating func next() -> Element? {
        return pop() 
    }
}
复制代码

这里，无需实现 makeIterator 方法。对于那些迭代器类型就是它自己的序列，Swift 会提供一份默认的实现。这样，就可以通过 for … in 遍历 List 对象了:

let list2: List = ["1", "2", "3"]
for x in list2 {
    print("\(x)", terminator: " ")
} // 1 2 3
复制代码

同时，得益于协议扩展的强大特性，实现了 Sequence 还意味着，我们可以在 List 上使用很多标准库中的函数:

list2.joined(separator: ",") // 1,2,3 
list2.contains("2") // true 
list2.compactMap { Int($0) } // [1, 2, 3] 
list2.elementsEqual(["1", "2", "3"]) // true
复制代码

要注意的是，尽管 List 扮演了自身迭代器的角色，并且迭代器是以单次遍历的形式定义的，但 List 仍就是一个可以多次遍历的序列。这是因为 for 循环和其它 Sequence 方法会在内部调用 makeIterator 得到一份 self 的拷贝，虽然迭代本身会消耗掉这份拷贝，但是原始的链表对象不会发生任何变化，它的 self 指向的始终都是表头。

在计算机科学的理论中，链表对一些常用操作会比数组高效得多。但是实际上，在当代的计算机架构上，CPU 缓存速度非常之快，相对来说主内存的速度要慢一些，这让链表的性能很难与数组相媲美。因为数组中的元素使用的是连续的内存，处理器能够以更高效的方式对它们进行访问。

集合类型

集合类型 (Collection) 指的是那些可以被多次遍历且保持一致的序列。除了线性遍历以外，集合中的元素也可以通过下标索引的方式访问。下标索引通常是整数，至少在数组中是这样。不过索引也可以是一些不透明值 (比如在字典或者字符串中)，它们用起来有时就不如整数那样直观。集合的索引值可以构成一个有限的范围，包含了定义好的开始和结束位置。也就是说，和序列不同，集合类型不能是无限的。每一个集合类型还有一个关联类型 SubSequence，它表示集合中一段连续内容的切片。

Collection 协议是建立在 Sequence 协议上的。除了从 Sequence 继承了全部方法以外，得益于可以获取指定位置的元素以及稳定迭代的保证，集合还获取了一些新的能力。比如 count 属性 (如果对只能单次遍历的序列进行计数，将会消耗序列中的元素)。

即使用不到集合类型提供的这些特性，依旧可以让自定义序列满足 Collection 协议，这将告诉序列类型的使用者该序列是有限的，而且可以进行多次迭代。不过如果你只是想说明序列可以被多次迭代，但却必须选择一个合适的索引类型，确实会显得比较奇怪。在实现 Collection 协议时，最难的部分就是选取一个合适的索引类型来表达集合类型中的位置。这样设计的一个目的是，Swift 团队希望避免引入一个专门的可多次遍历序列的协议，因为它和 Sequence 拥有同样的要求，但是语义却不一致，这容易让用户感到迷惑。lists.swift.org/pipermail/s…

集合类型在标准库中运用广泛。除了 Array，Dictionary 和 Set 之外，String 和它的各种视图， [Closed]Range 以及 UnsafeBufferPointer 都是集合类型。标准库以外的一些类型也实现了 Collection 协议。其中的两个例子，就是 Foundation 框架中的 Data 和 IndexSet，它们通过 Collection 获得了很多新的能力。

自定义的集合类型

为了展示 Swift 中集合类型的工作方式，将实现一个自己的集合类型。“队列” 可能是在 Swift 标准库中没有被实现，但是却最有用的容器类型了。Swift 数组可以很容易地被当作栈来使用，我们可以用 append 来入栈，用 popLast 出栈。但是对于队列来说，就不那么理想。你可以结合使用 push 和 remove(at: 0) 来实现，但是因为数组是在连续的内存中持有元素的，所以移除非尾部的数组元素时，其他每个元素都需要移动去填补空白，这个操作的复杂度会是 O(n) (而出栈最后一个元素只需要常数时间就能完成)。
下面是一个很简单的先进先出队列，我们基于两个数组实现了它的 enqueue 和 dequeue 方法:

/// 一个高效的 FIFO 队列，其中元素类型为 `Element` 
struct FIFOQueue<Element> {
    private var left: [Element] = [] 
    private 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() 
    }
}
复制代码

这个实现使用两个栈 (两个常规的数组) 来模拟队列的行为。当元素入队时，它们被添加到 “右” 栈中。当元素出队时，它们从 “右” 栈的反序数组，也就是 “左” 栈中被弹出。当左栈变为空时，再将右栈反序后设置为左栈。

dequeue 操作被声明为 O(1) 感到有点奇怪。它包含了一个复杂度为 O(n) 的 reverse 操作。对于单个的操作来说可能耗时会长一些，不过对于非常多的 push 和 pop 操作来说，取出一个元素的平摊耗时是一个常数。

理解这个复杂度的关键在于理解反向操作发生的频率以及发生在多少个元素上。

现在拥有一个可以出队和入队元素的容器了。下一步是为 FIFOQueue 添加 Collection 协议的支持。不幸的是，在 Swift 中，想要找出要实现某个协议所需要提供的最少实现有时候并不容易。

Collection 协议有五个关联类型，五个属性，六个实例方法，以及两个下标操作符:

protocol Collection: Sequence {
    associatedtype Element // 从 Sequence 继承而来 
    associatedtype Index: Comparable // 省去了 where ... 语句 
    var startIndex: Index { get }
    var endIndex: Index { get }
    
    associatedtype Iterator = IndexingIterator<Self> 
    associatedtype SubSequence: Collection = Slice<Self>
        where Element == SubSequence.Element, 
              SubSequence == SubSequence.SubSequence
              
    subscript(position: Index) -> Element { get } 
    subscript(bounds: Range<Index>) -> SubSequence { get }
    
    associatedtype Indices: Collection =
        DefaultIndices<Self> where Indices == Indices.SubSequence
        
    var indices: Indices { get } 
    var isEmpty: Bool { get } 
    var count: Int { get }
    
func makeIterator() -> Iterator // 从 Sequence 继承而来
func index(_ i: Index, offsetBy distance: Int) -> Index
func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? 
func distance(from start: Index, to end: Index) -> Int
func index(after i: Index) -> Index
func formIndex(after i: inout Index)
}
复制代码

关联类型 SubSequence 使用了递归约束表明 SubSequence 自身也是一个集合类型。这个约束确保了 SubSequence 中元素的类型和原始集合中的元素类型是相同的，并且， SubSequence 中的 SubSequence 类型和它自身相同。例如:String 的 SubSequence 类型是 Substring，而 Substring 中的 SubSequence 类型仍旧是 Substring。

关联类型 Indices 也是一个集合类型。为了突出重点，省去了Collection中对 Index 类型的一长串约束。简单来说，就是 Collection 中的 Index 是这个 Indices 集合中的元素类型、索引 =类型以及 Indices.SubSequence 集合中的索引类型。

考虑到上面的要求如此繁杂，遵守 Collection 看起来让人望而却步。不过，实际上事情并没有那么糟糕。除了 Index 和 Element 以外，其他的关联类型都有默认值，除非自定义类型有特殊要求，否则你都不必去关心它们。对于大部分方法、属性和下标，情况同样如此:Collection 的协议扩展也为我们提供了默认实现。不过，这些扩展中，有些包含对关联类型的约束，它们要求关联类型是协议中的默认类型;比如，Collection 只为 Iterator 为 IndexingIterator<Self> 的类型提供了 makeIterator 方法的默认实现:

extension Collection where Iterator == IndexingIterator<Self> { 
    func makeIterator() -> IndexingIterator<Self>
}
复制代码

如果类型需要一个不同的迭代器类型，就需要自己实现这个方法。

为了实现一个协议，找出哪些方法必须实现，哪些存在默认实现，这件事情本身并不十分困难，不过它需要花时间亲自去找，而且一旦不小心，就会进入到根据编译器的结果进行猜猜猜的游戏里。其中最恼人的部分在于，其实编译器本来知道实现一个协议必备的所有条件，但它提供给我们的信息却不是十分有用。

结果就是，现如今，你最应该给予希望的是在文档中去寻找满足一个协议的需要实现的最小要求。好在，这方面 Collection 不会让你失望:

要让一个类型实现 Collection，你必须声明以下内容:

startIndex 和 endIndex 属性。
至少能以只读方式访问集合元素的下标操作符。
用来在集合索引之间进行步进的 index(after:) 方法。

于是最后，需要实现的有:

protocol Collection: Sequence { 
    /// 一个表示序列中元素的类型
    associatedtype Element
    /// 一个表示集合中位置的类型
    associatedtype Index: Comparable
    /// 一个非空集合中首个元素的位置
    var startIndex: Index { get }
    /// 集合中超过末位的位置---也就是比最后一个有效下标值大 1 的位置
    var endIndex: Index { get }
    /// 返回在给定索引之后的位置
    func index(after i: Index) -> Index
    /// 访问特定位置的元素
    subscript(position: Index) -> Element { get }
}
复制代码

让 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 >= startIndex && i < endIndex, "Index out of bounds")
        returni + 1
    }
    public subscript(position: Int) -> Element {
        precondition((startIndex..<endIndex).contains(position), "Index out of bounds")
        if position < left.endIndex {
            return left[left.count - position - 1]
        } else {
            return right[position - left.count]
        }
    }
}
复制代码

这里，使用了 Int 作为 FIFOQueue 的 Index 类型。但并没有显式地提供这个关联类型，和 Element 一样，Swift 可以帮我们从方法和属性的定义中将它推断出来。注意索引是从集合开头开始返回元素的，所以 FIFOQueue.first 将会返回下一个即将被出队的元素 (可以将它当做 peek 来使用)。

var queue = FIFOQueue<String>() 
for x in ["1", "2", "foo", "3"] {
    queue.enqueue(x) 
}
for s in queue{
    print(s, terminator: " ")
} // 1 2 foo 3 

// 我们可以将队列传递给接受序列的方法:
var a = Array(queue) // ["1", "2", "foo", "3"] 
a.append(contentsOf: queue[2...3])
a // ["1", "2", "foo", "3", "foo", "3"]

// 我们可以调用那些 Sequence 的扩展方法和属性:
queue.map { $0.uppercased() } // ["1", "2", "FOO", "3"] 
queue.compactMap { Int($0) } // [1, 2, 3]
queue.filter { $0.count > 1 } // ["foo"]
queue.sorted() // ["1", "2", "3", "foo"] 
queue.joined(separator: " ") // 1 2 foo 3

// 我们也可以调用 Collection 的扩展方法和属性:
queue.isEmpty // false 
queue.count // 4
queue.first // Optional("1")
复制代码

数组字面量

当实现一个类似 FIFOQueue 这样的集合类型时，最好也去实现一下ExpressibleByArrayLiteral。这可以让用户能够以他们所熟知的 [value1, value2, etc] 语法创建一个队列。而这个协议只要求我们实现一个下面这样的初始化方法就好了:

extension FIFOQueue: ExpressibleByArrayLiteral { 
    public init(arrayLiteral elements: Element...) { 
        self.init(left: elements.reversed(), right: [])
    } 
}

// 现在我们就可以用数组字面量来创建一个队列了:
let queue2: 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<Float>，而不是 Array<Int>。

关联类型

Iterator – 这是从 Sequence 继承来的关联类型。已经在关于序列的篇幅中详细看过迭代器的相关内容了。集合类型中的默认迭代器类型是 IndexingIterator<Self>，这是个很简单的结构体，它对集合进行了封装，并用集合本身的索引来迭代每个元素。

标准库中大多数集合类型都使用 IndexingIterator 作为它们的迭代器。几乎没有理由需要为一个自定义的集合类型单独定义迭代器。

SubSequence – 是表示集合中一段连续内容切片的类型。SubSequence 自身也是集合类型。它的默认值是 Slice<Self>，这是对原始集合的封装，并存储了切片相对于原始集合的起始和终止索引。

为一个集合类型自定义它的 SubSequence 是很常见的情况，特别是当 SubSequence 就是 Self 时 (也就是说，一个集合的切片拥有和集合本身相同的类型)。Foundation 框架中的 Data 就是一个这种集合的例子。

Indices – 集合的 indices 属性的类型。它是集合中所有有效索引按升序排列组成的集合。注意 endIndex 并不包含在其中，因为 endIndex 代表的是最后一个有效索引之后的那个索引，它不是有效的下标参数。

Indices 的默认类型是 DefaultIndices<Self>。和 Slice 一样，它是对于原来的集合类型的简单封装，并包含起始和结束索引。它需要保持对原集合的引用，这样才能够对索引进行步进。当用户在迭代索引的同时改变集合的内容的时候，可能会造成意想不到的性能问题:如果集合是以写时复制 (就像标准库中的所有集合类型所做的一样) 来实现的话，这个对于集合的额外引用将触发不必要的复制。因此，如果你可以为自定义集合类型提供一个不需要引用原始序列的 Indices 类型，这绝对是一个值得尝试的优化。实际上，只要索引位置的计算不依赖于集合自身，例如数组或之前实现的 FIFOQueue，就都应该如此。如果索引是整数类型，可以直接使用 Range<Index>:

extension FIFOQueue: Collection { // ...
    typealias Indices = Range<Int> 
    var indices: Range<Int> {
        return startIndex..<endIndex
    }
}
复制代码

索引

索引表示了集合中的位置。每个集合都有两个特殊的索引值:startIndex 和 endIndex。startIndex 指定集合中第一个元素，endIndex 是集合中最后一个元素的下一个位置。所以 endIndex 并不是一个有效的下标索引，可以用它创建索引的范围 (someIndex..<endIndex)，或者将它与别的索引进行比较，例如:控制循环的退出条件 (while someIndex < endIndex)。

到现在为止，我们都使用整数作为集合的索引。Array 如此，FIFOQueue 类型在经过一些操作之后亦是如此。整数索引十分直观，但它并不是唯一选项。集合类型的 Index 的唯一要求是，它必须实现 Comparable，换句话说，索引必须要有确定的顺序。

用 Dictionary 作为例子，因为我们使用字典的键来定位字典中的值，所以可能使用键来作为字典的索引看上去会是很自然的选择。但这是行不通的，因为你无法 (像计算整数索引位置一样)移动一个键，不能给出某个键之后的索引值应该是什么。另外，使用索引进行下标访问应该立即返回获取的元素，而不是再去搜索或者计算哈希值。

所以，字典的索引是 DictionaryIndex 类型，它是一个指向字典内部存储缓冲区的不透明值。事实上这个类型只是一个 Int 偏移值的封装，不过它包含了字典类型使用者所不需要关心的实现细节 (其实事情要比这里描述的复杂得多。一方面，字典的索引还包含了一个计数器，字典通过这个计数器检测不可用索引的访问;另一方面，字典还可能被传递到 Objective-C 的 API，或者是由 Objective-C 的 API 获取到的，为了效率，它们会使用 NSDictionary 作为背后的存储，这样的字典的索引类型又有所不同。不过意思是一样的)。

这也说明了为什么通过索引下标访问 Dictionary 时返回的值，不像用字典键下标访问时那样是一个可选值。我们平时用键访问的 subscript(_ key: Key) 方法是直接定义在 Dictionary 上的下标方法的一个重载，它返回可选的 Value:

struct Dictionary { ...
    subscript(key: Key) -> Value? 
}
复制代码

而通过索引访问的方法是 Collection 协议所定义的，它总是返回非可选值。因为使用 (像是数组里的越界索引这样的) 无效的下标被认为是程序员犯的错误，即便程序 “崩了” 也是理所因当的事情:

protocol Collection {
    subscript(position: Index) -> Element { get }
}
复制代码

注意，subscript 的返回类型是 Element。Element 类型是一个多元组:
(key: Key, value: Value)，因此对 Dictionary，下标访问返回的是一个键值对，而非单个的 Value。这也是通过 for 循环遍历字典会得到键值对的原因。

索引失效

当集合发生改变时，索引可能会失效。失效有两层含义，它可能意味着虽然索引本身仍是有效的，但是它现在指向了一个另外的元素;或者有可能索引本身就已经无效了，通过它对集合访问将造成崩溃。在你用数组进行思考时，这个问题会比较直观。当你添加一个元素后，所有已有的索引依然有效。但是当你移除第一个元素后，指向最后一个元素的索引就无效了。同时，那些较小的索引依然有效，但是它们所指向的元素都发生了改变。

典的索引不会随着新键值对的加入而失效，直到字典的尺寸增大到触发重新的内存分配。这是因为一般情况下字典存储的缓冲区内的元素位置是不会改变的，而在元素超过缓冲区尺寸时，缓冲区会被重新分配，其中的所有元素的哈希值也会被重新计算。从字典中移除元素总是会使索引失效。

索引应该是一个只存储包含描述元素位置所需最小信息的简单值。在尽可能的情况下，索引不应该持有对它们集合的引用。类似地，一个集合通常也无法区分它 “自己的” 索引和一个来自同样类型集合的索引。用数组来举例子就再清楚不过了。显然，你可以用从一个数组中获取到的整数索引值来访问另一个数组的内容:


let numbers = [1,2,3,4]
let squares = numbers.map { $0 * $0 }
let numbersIndex = numbers.firstIndex(of: 4)! // 3 
squares[numbersIndex] // 16
复制代码

这对那些不透明的索引类型，例如:String.Index，也是适用的。在这个例子中，使用一个字符串的 startIndex 来访问另一个字符串的首字符:

let hello = "Hello"
let world = "World"
let helloIdx = hello.startIndex world[helloIdx] // W
复制代码

不过，能这么做并不意味着这么做是个好主意。如果我们用这个索引作为下标访问一个空字符串的话，程序将因为索引越界而发生崩溃。另外，由于字符长度是可变的，指向一个字符串中第 n 个字符的索引在另一个字符串中不一定指向的是一个正确的字符边界。

另外，在集合之间共享索引也是有其合理用法的，在切片上我们会大量使用这种方式。Collection 协议要求原集合的索引必须在切片上也命中同样的元素，这样一来，在切片之间共享索引就总是一个安全的操作。

索引步进

Swift 3 在集合处理索引遍历的方面引入了一个大的变化。现在，向前或者向后移动索引 (或者说，从一个给定索引计算出新的索引) 的任务是由集合来负责的了，而在 Swift 3 之前，索引是可以自行移动的。之前可能会用 someIndex.successor() 来获取下一个索引，现在你需要写 collection.index(after: someIndex)。

为什么做这样的变化?为了性能。通常，从一个索引获取到另一个索引会涉及到集合内部的信息。数组中的索引没有这个顾虑，因为在数组里索引的步进就是简单的加法运算。但是对于字符串索引，因为字符在 Swift 中是尺寸可变的，所以计算索引时就需要考虑字符的实际数据到底是什么。

在之前可以自行移动的索引模型中，索引必须保存一个对集合存储的引用。这个额外的引用会在集合被迭代修改时造成不必要的复制，它带来的开销足以抵消标准库中集合的写时复制特性带来的性能改善。

新的模型通过将索引保持为简单值，就可以解决这个问题。它的概念更容易理解，也可以更简单地实现自定义的索引类型。当你实现你自己的索引类型时，请记住尽可能地避免持有集合类型的引用。在大多数情况下，索引可以由一个或者两个高效地对集合底层存储元素位置进行编码的整数值所表示。

自定义集合索引

作为非整数索引集合的例子，我们将会构建一种在字符串中迭代单词的方式。当要将一个字符串分割成一个个的单词，最简单的方法就是使用 split(separator:maxSplits:omittingEmptySubsequences:)，这个方法将使用提供的分割元素进行分割，把一个集合转变为其 SubSequence 的数组:

var str = "Still I see monsters"
str.split(separator: " ") // ["Still", "I", "see", "monsters"]
复制代码

上面的代码返回一组单词。每个单词的类型都是 SubString，这正是 String 所关联的 SubSequence 类型。当想要分割一个集合类型时，split 方法往往是最适合的工具。不过，它有一个缺点:这个方法将计算出整个数组。如果字符串非常大，而且只需要前几个词的话，这么做是相当低效的。为了提高性能，构建一个 Words 集合，它能够让我们不一次性地计算出所有单词，而是可以用延迟加载的方式进行迭代。

我们从在 SubString 中寻找第一个单词的范围开始。这里，我们直接使用空格作为单词的边界，当然，作为练习也可以将它写为可配置的值。一个子字符串可能由若干个空格作为开始，我们将它们跳过。start 是所有前置空格都被移除了的子字符串。接下来，我们寻找下一个空格; 如果找到空格，就以它作为单词的结束边界。如果无法找到另一个空格，则使用 endIndex:

extension Substring {
    var nextWordRange: Range<Index> {
        let start = drop(while: { $0 == " "})
        let end = start.firstIndex(where: { $0 == " "}) ?? endIndex return 
        start.startIndex..<end
    } 
}
复制代码

逻辑上来说，Words 集合类型的索引类型的第一选择应该是 Int:某个整数索引 i 代表的是集合类型中的第 i 个单词。不过，通过索引下标访问某个元素应该是一个 O(1) 操作，而为了找到第 i 个单词，我们需要对整个字符串进行处理 (这会是一个 O(n) 的操作)。

对于索引类型，另一个选择是使用 String.Index。string.startIndex 将成为集合类型的 startIndex，之后的索引则成为下一个单词的开始索引，以此类推。不过不幸的是，这种下标实现也存在一样的问题:寻找最后的单词依然是 O(n) 复杂度。

采取的办法是将 Range<Substring.Index> 进行包装，然后用它来作为索引类型。集合类型的索引需要满足 Comparable (因为 Comparable 继承自 Equatable，所以还需要实现 ==)。在比较两个索引时，只比较范围的下边界。虽然在一般的情况下，这并不能完成对于 Range 类型的比较，但是在这个例子中，比较范围下界就足够了。通过将 range 属性以及使用它的初始化方法标记为 fileprivate，可以把 WordsIndex 当作一个不透明类型来使用;集合类型的使用者不知道它的内部结构，想要创建一个索引，唯一的方式是通过集合的接口:

struct WordsIndex: Comparable {
    fileprivate let range: Range<Substring.Index> 
    fileprivate init(_ value: Range<Substring.Index>) {
        self.range = value 
    }
    static func <(lhs: Words.Index, rhs: Words.Index) -> Bool { 
        return lhs.range.lowerBound < rhs.range.lowerBound
    }
    static func ==(lhs: Words.Index, rhs: Words.Index) -> Bool { 
        return lhs.range == rhs.range
    } 
}
复制代码

现在，就可以来构建 Words 集合类型了。它在底层将 String 作为 SubString 存储,并提供了一个起始索引和一个结束索引。Collection 协议要求 startIndex 的复杂度为 O(1)。不过，现在计算它的开销是 O(n)，n 是字符串开头的空格的数量。因此，我们将会在初始化方法中对它进行计算和存储，而不是将其定义为一个计算属性。对于结束索引，使用在底层字符串边界以外的一个空范围来表示:

struct Words {
    let string: Substring
    let startIndex: WordsIndex
    init(_ s: String) { self.init(s[...]) }
    private init(_ s: Substring) {
        self.string = s
        self.startIndex = WordsIndex(string.nextWordRange)
    }
    public var endIndex: WordsIndex {
        let e = string.endIndex
        return WordsIndex(e..<e)
    }
}
复制代码

集合类型需要我们提供 subscript 下标方法来获取元素。这里我们直接使用索引中的范围值。使用单词的范围作为索引，可以使下标的实现满足 O(1) 复杂度:

extension Words {
    subscript(index: WordsIndex) -> Substring {
    return string[index.range] 
    }
}
复制代码

Collection 的最后一个要求是给定某个索引时，能够计算出下一个索引。由于索引中范围上界表示的是当前单词的结束的下一个位置。所以，只要上界的值不是字符串的 endIndex (这表示已经遍历到了字符串末尾)，就可以从这个上界开始，继续在剩余的子字符串中寻找下一个单词的范围:

extension Words: Collection {
    public func index(after i: WordsIndex) -> WordsIndex {
        guard i.range.upperBound < string.endIndex else { return endIndex } 
        let remainder = string[i.range.upperBound...]
        return WordsIndex(remainder.nextWordRange)
    } 
}
Array(Words(" hello world test ").prefix(2)) // ["hello", "world"]
复制代码

再经过一些完善的话，Words 集合类型将能够可以处理一些更为普遍的问题。首先，可以对单词的边界进行设置:相对于现在直接使用空格，我们可以传入一个 isWordBoundary: (Character) -> Bool 的函数来确定单词边界。其次，这些代码并不是只针对字符串的:完全可以将 String 替换成任意集合类型。比如，可以用同样的算法来将 Data 延迟分割为可处理的小数据块。

子序列

Collection 协议还有一个关联类型，叫做 SubSequence。它表示集合中一个连续的子区间:

extension Collection {
associatedtype SubSequence: Collection = Slice<Self>
    where Element == SubSequence.Element, 
    SubSequence == SubSequence.SubSequence
}
复制代码

SubSequence用于那些返回原始集合类型切片的操作:

prefix 和 suffix — 获取开头或结尾的 n 个元素。
prefix(while:) – 从集合开始，获取满足 while 指定条件的操作。
dropFirst 和 dropLast — 返回移除掉前 n 个或后 n 个元素的子序列。
drop(while:) – 移除元素，直到条件不再为真，然后返回剩余元素。
split — 将一个序列通过指定的分隔元素截断，返回子序列的数组。

另外，基于范围的下标操作符也会以切片的形式返回这个范围内的索引在原始集合中标记的区间。这样做，相比于直接返回一个包含所有子序列元素的新集合 (例如数组) 的好处就是不会招致额外的内存分配，因为子序列和它们原始的集合类型是共享内部存储的。

默认情况下，Collection 会把 Slice<Self> 作为自己的 SubSequence 类型。但很多具体类型都有它们自己定制的实现:例如，String 的 SubSequence 类型是 Substring，Array 的 SubSequence 类型是 ArraySlice。

在有些时候，让子序列和原始集合的类型一致，也就是 SubSequence == Self，会非常方便。因为这样，只要能传递原始集合类型的地方，都能够使用切片类型。Foundation 中的 Data 就是这么做的，所以当你见到一个 Data 实例的时候，无法分辨这究竟是一块儿完整的数据 (startIndex == 0 并且 endIndex == count)，还是一大块数据的切片 (拥有不是基于0开始的索引)。但标准库中的集合却拥有不一样的切片类型，这么做的主要考量是为了防止不经意的内存 “泄漏”，一个非常小的切片将会持有它原来的集合类型 (有可能非常大)。在切片的生命周期比预期要长得多的时候，这可能造成一些问题。使用它们自己的类型来表示切片，可以比较容易将它们的生命周期绑定到局部作用域中。

下面这个例子，就以每 n 个元素切割集合。在它的实现里，只要迭代集合索引，每步进 n，就创建一个切片，并把结果保存一个子序列数组里。如果集合中元素个数不是 n 的倍数，最后一个切片就会小一些:

extension Collection {
    public func split(batchSize: Int) -> [SubSequence] {
        var result: [SubSequence] = [] 
        var batchStart = startIndex while batchStart < endIndex {
            let batchEnd = index(batchStart, offsetBy: batchSize, limitedBy: endIndex) ?? endIndex
            let batch = self[batchStart ..< batchEnd] 
            result.append(batch)
            batchStart = batchEnd
        }
    return result 
    }
}
let letters = "abcdefg"
let batches = letters.split(batchSize: 3) // ["abc", "def", "g"]
复制代码

由于子序列也是一个同样以 Element 作为元素类型的集合，我们完全可以用处理集合的方法处理与之对应的切片类型。例如，我们来验证下，刚才实现的 split 返回的所有切片中元素的个数和原始集合中元素的个数是相同的:

let batchesCount = batches.map { $0.count }.reduce(0, +) // 7 
batchesCount == letters.count // true
复制代码

鉴于它们的内存开销很低，子序列非常适合表达中间结果。但是，为了避免小块切片意外地把整个原始序列保持在内存里，通常不建议长时间保存子序列 (例如:定义一个子序列属性)，或者把它传递给有可能造成这种结果的方法。为了切断子序列和原始集合类型之间的关系，可以用子序列创建一个新集合，例如:String(substring) 或 Array(arraySlice)。

切片

所有的集合类型都有切片操作的默认实现，并有一个接受Range<Index>作为参数的 subscript 方法。下面的操作等价于 list.dropFirst():

let words: Words = Words("one two three")
let onePastStart = words.index(after: words.startIndex) 
let firstDropped = words[onePastStart..<words.endIndex] 
Array(firstDropped) // ["two", "three"]
复制代码

因为像是 words[somewhere..<words.endIndex] (从某个位置到结尾的切片) 和 words[words.startIndex..<somewhere] (从开头到某个位置的切片) 是非常常见的操作，所以在标准库中有一些更容易理解的变体来进行这些操作:

let firstDropped2 = words.suffix(from: onePastStart)
//或者
let firstDropped3 = words[onePastStart...]
复制代码

默认情况下，firstDropped 的类型不是 Words，而是 Slice<Words>。Slice 是基于任意集合类型的一个轻量级封装、它的实现看上去会是这样的:

struct Slice<Base: Collection>: Collection {
    typealias Index = Base.Index
    let collection: Base
    var startIndex: Index var endIndex: Index
    init(base: Base, bounds: Range<Index>) {
        collection = base
        startIndex = bounds.lowerBound endIndex = bounds.upperBound
    }
    func index(after i: Index) -> Index {
        return collection.index(after: i)
    }
    subscript(position: Index) -> Base.Element {
        return collection[position]
    }
subscript(bounds: Range<Index>) -> Slice<Base> {
        return Slice(base: collection, bounds: bounds)
    }
}
复制代码

Slice 非常适合作为默认的子序列类型，不过当创建一个自定义集合类型时，最好还是考虑下是否能将集合类型本身当作它的 SubSequence 使用。对于 Words 来说，这非常容易:

extension Words {
    subscript(range: Range<WordsIndex>) -> Words {
        let start = range.lowerBound.range.lowerBound 
        let end = range.upperBound.range.upperBound 
        return Words(string[start..<end])
    } 
}
复制代码

编译器会通过基于范围的下标操作符返回的类型，来推断出 SubSequence 的类型。

将集合类型的 SubSequence 定义为和集合类型相同的类型，可以减轻集合类型使用者的负担，因为他们只需要理解单个类型就可以了，而不需要学习两个类型。不过另一面，让原始集合和它的切片使用不同的类型，有助于避免意外的内存 “泄漏”，这也是标准库中使用 ArraySlice 和 Substring 来作为 Array 和 String 的子序列的原因。

切片与原集合共享索引

Collection 协议还有另一个正式的要求，那就是切片的索引可以和原集合的索引互换使用。

Swift 文档是这样陈述这个要求的:集合类型和它的切片拥有相同的索引。只要集合和它的切片在切片被创建后没有改变，切片中某个索引位置上的元素，应当也存在于原集合中同样的索引位置上。
developer.apple.com/documentati…

这种模型带来了一个很重要的暗示，那就是即使在使用整数索引时，一个集合的索引也并不需要从 0 开始。这里是一个数组切片的开始索引和结束索引的例子:

let cities = ["New York", "Rio", "London", "Berlin", "Rome", "Beijing", "Tokyo", "Sydney"]
let slice = cities[2...4]
cities.startIndex // 0 
cities.endIndex // 8 
slice.startIndex // 2 
slice.endIndex // 5
复制代码

这种情况下，如果不小心访问了 slice[0]，程序将会崩溃。这也是我们应当尽可能始终选择 for x in collection 的形式，而不去手动计算索引的一个原因。

而我们之前提到过的 Data 在集合的这个特性下，用起来就比较危险了。Data 用整数作为索引，所以很自然的就会想到用数字 0 表示 Data 的起始位置。然而事实并非总是如此，因为 Data 的 SubSequence 类型也是它自己。

如果你确实需要访问索引，使用 for index in collection.indices 在绝大多数时候都比手工计算更可靠。但这也有一个例外，如果你通过索引进行迭代的同时修改了集合，indices 持有的原始集合的强引用会破坏写时复制的优化机制，并引发本不需要的额外拷贝。取决于集合自身的大小，这个拷贝可能会带来非常严重的性能影响 (并不是所有集合使用的 Indices 类型都会持有原始集合的强引用，但由于标准库中默认的 DefaultIndices 就是这样做的，所以绝大多数集合类型都有这样的性质)。

要避免这件事情发生，可以将 for 循环替换为 while 循环，然后手动在每次迭代的时候增加索引值，这样你就不会用到 indices 属性。当这么做的时候，一定要从 collection.startIndex 开始进行循环，而不要把 0 作为开始。

专门的集合类型

和所有精心设计的协议一样，Collection 努力将它的需求控制在最小。为了使更多的类型能满足 Collection，对于实现它的类型来说，应该只需要提供完成 Collection 核心功能所必备的方法就好了。

对于 Collection 来说，有两个特别有意思的限制:一个是它无法往回移动索引，另一个是，它也没有提供像是插入，移除或者替换元素这样改变集合内容的功能。当然，这并不是说满足 Collection 的类型不能拥有这些能力，只是 Collection 协议自身没有把它们当作必须要实现的功能。

有些算法会对集合支持的操作有额外的要求，这使得只有部分集合可以和它们搭配在一起工作。如果可以把这些额外的要求抽象出来形成一些通用的集合变体，用起来就会更加方便。为此，标准库提供了四个专门的集合类型，每一个都用特定的方式给 Collection 追加了新的功能 (以下这些内容引用自标准库文档):

BidirectionalCollection — “一个既支持前向又支持后向遍历的集合。”
RandomAccessCollection — “一个支持高效随机访问索引进行遍历的集合。”
MutableCollection — “一个支持下标赋值的集合。”
RangeReplaceableCollection — “一个支持将任意子范围的元素用别的集合中的元素进行替换的集合。”

BidirectionalCollection

BidirectionalCollection 给集合添加了一个关键的能力，就是通过 index(before:) 方法把索引往回移动一个位置。有了这个方法，就可以对应 first，给出默认的 last 属性的实现了:

extension BidirectionalCollection { /// 集合中的最后一个元素。
    public var last: Element? {
        return isEmpty ? nil : self[index(before: endIndex)]
    } 
}
复制代码

当然了，Collection 本身也能提供 last 属性，但是这么做不太好。在一个只能前向进行索引的集合类型中，想要获取最后一个元素，你就得一路从头迭代到尾，而这是一个 O(n) 操作。通过一个看起来人畜无害的简单的 last 属性来获取最后一个元素，可能会带来问题。比如一个含有数百万条数据的单链表中，为了获取最后一个元素，你会花费很长时间。

标准库中的 String 就是双向索引集合的一个例子。由于 Unicode 相关的原因，一个字符集合不能含有随机存取的索引，只能从后往前一个一个对字符进行遍历。

受益于这种可以向前遍历集合的能力，BidirectionalCollection 还实现了一些可以高效执行的方法，比如 suffix，removeLast 和 reversed。其中，reversed 不会直接将集合反转，而是返回一个延时加载的视图:

extension BidirectionalCollection {
/// 返回一个表达集合中元素逆序排列的视图
/// - 复杂度: O(1)
    public func reversed() -> ReversedCollection<Self> {
        return ReversedCollection(_base: self) 
    }
}
复制代码

和上面 Sequence 的 enumerated 封装类似，ReverseCollection 并不会真的把元素逆序排列，而是会持有原来的集合，并使用一个定制的索引类型实现逆序遍历。另外，ReverseCollection 还逆向了所有索引遍历方法，这样一来，向前移动它的索引就相当于在原始序列中向后移动索引，反之一样。

这种做法之所以可行，很大部分是依赖了值语义的特性。在构建时，这个封装将原集合 “复制” 到它自己的存储中，这样对原序列的子序列进行改变，也不会改变 ReversedCollection 中持有的复制。也就是说，ReverseCollection 可观测到的行为和通过 reversed 返回的数组的行为是一致的。

标准库中的大部分类型都在实现 Collection 的同时，实现了 BidirectionalCollection。然而，像是 Dictionary 和 Set 这样的类型，它们本身就是无序的集合类型，所以对于它们来说，讨论前向迭代还是后向迭代，几乎都是没有意义的。

RandomAccessCollection

RandomAccessCollection 提供了最高效的元素存取方式，它能够在常数时间内跳转到任意索引。要做到这一点，满足该协议的类型必须能够 (a) 以任意距离移动一个索引，以及 (b) 测量任意两个索引之间的距离，两者都需要是 O(1) 时间的常数操作。RandomAccessCollection 以更严格的约束重新声明了关联的 Indices 和 SubSequence 类型，这两个类型自身也必须是可以进行随机存取的。除此之外，相比于 BidirectionalCollection，RandomAccessCollection 并没有更多的要求。不过，满足协议的类型必须确保满足文档所要求的 O(1) 复杂度。可以通过提供 index(_:offsetBy:) 和 distance(from:to:) 方法，或者是使用一个满足 Strideable 的 Index 类型 (像是 Int)，就可以做到这一点。

像我们的 Words 这样的简单前向遍历的集合的索引也能够以任意距离进行前进。但这其中有很大区别，对于 Collection 和 BidirectionalCollection，index(_:offsetBy:) 操作通过渐进的方式访问下一个索引，直到到达目标索引为止。这显然是一个线性复杂度的操作，随着距离的增加，完成操作需要消耗的时间也线性增长。而随机存取索引则完全不同，它可以直接在两个索引间进行移动。

随机存取的集合类型可以在常数时间内计算 startIndex 和 endIndex 之间的距离，这意味着该集合同样能在常数时间内计算出 count。

MutableCollection

可变集合支持原地的元素更改。相比于 Collection，MutableCollection 只增加了一个要求，那就是单个元素的下标访问方法 subscript 现在必须提供一个 setter:

extension FIFOQueue: MutableCollection {
    public var startIndex: Int { return 0 }
    public var endIndex: Int { return left.count + right.count }
    public func index(after i: Int) -> Int { returni+1 }
    public subscript(position: Int) -> Element { 
        get {
            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]
            } 
        }
        set {
            precondition((0..<endIndex).contains(position), "Index out of bounds") 
            if position < left.endIndex {
                left[left.count - position - 1] = newValue 
            } else {
                return right[position - left.count] = newValue 
            }
        } 
    }
}
复制代码

注意编译器不让我们向一个已经存在的 Collection 中通过扩展添加下标 setter 方法。一方面，编译器不允许只提供 setter 而不提供 getter，另一方面，我们也无法重新定义已经存在的 getter 方法。所以我们只能替换掉已经存在的满足 Collection 的扩展，并提供一个新的扩展方法来满足 MutableCollection。现在这个队列可以通过下标进行更改了:

var playlist: FIFOQueue = ["Shake It Off", "Blank Space", "Style"] playlist.first // Optional("Shake It Off")
playlist[0] = "You Belong With Me"
playlist.first // Optional("You Belong With Me")
复制代码

很多对集合进行原地修改的算法都要求对应的集合类型满足 MutableCollection 协议。例如标准库中的原地排序、逆序以及 swapAt 方法。

相对来说，标准库中满足 MutableCollection 的类型并不多。在三个主要的集合类型中，只有 Array 满足这个协议。MutableCollection 允许改变集合中的元素值，但是它不允许改变集合的长度或者元素的顺序。正是这个不可改变元素顺序的要求，解释了为什么 Dictionary 和 Set 虽然是可变的数据结构，却不满足 MutableCollection 的原因。

字典和集合都是无序的集合类型，两者中元素的顺序对于使用这两个集合类型的代码来说是没有定义的。不过，即使是这些集合类型，在内部实现上说，它的元素顺序也是唯一确定的。当要通过下标赋值的 MutableCollection 来改变一个元素时，被改变的元素的索引必须保持不变，也就是说，这个索引在 indices 中的位置必须不能改变。Dictionary 和 Set 无法保证这一点，因为它们的索引表示的是元素在内部存储中的位置，而一旦元素发生变化，这个位置也会发生改变。

字符串也不是一个 MutableCollection 类型，因为字符在字符串缓冲区中的大小是不固定的。结果就是，替换字符串中的一个字符需要线性时间完成，缓冲区的尾部也可能需要根据替换的字符适当延长或缩短几个字节。另外，修改了一个字符之后，新字符还可能和相邻的字符形成新的字位族，进而改变字符串的 count 属性。

RangeReplaceableCollection

对于需要添加或者移除元素的操作，可以使用 RangeReplaceableCollection 协议。这个协议有两个要求:

一个空的初始化方法 — 在泛型函数中这很有用，因为它允许一个函数创建相同类型的空集合。
一个replaceSubrange(_:with:) 方法 — 它接受一个要替换的范围以及一个用来进行替换的集合。

RangeReplaceableCollection 是展示协议扩展强大能力的绝佳例子。只需要实现一个灵活的 replaceSubrange 方法，协议扩展就可以为你引申出一系列有用的方法:

append(_:) 和 append(contentsOf:) — 将 endIndex..<endIndex (也就是说末尾的空范围) 替换为单个或多个新的元素。
remove(at:) 和 removeSubrange(_:) — 将 i…i 或者 subrange 替换为空集合。
insert(at:) 和 insert(contentsOf:at:) — 将 i..<i (或者说在数组中某个位置的空范围) 替换为单个或多个新的元素。
removeAll — 将 startIndex..<endIndex 替换为空集合。

这些方法，也是协议要求的一部分。也就是说，特定的集合类型可以根据自己的情况为这些方法提供更高效的实现。这些实现在使用时将比协议扩展中的默认实现具有更高的优先级。

和RandomAccessCollection 扩展了 BidirectionalCollection 不同， RangeReplaceableCollection 并不是对 MutableCollection 的扩展，它们拥有各自独立的继承关系。在标准库中，String 就是一个实现了 RangeReplaceableCollection 但是却没有实现 MutableCollection 的例子。究其原因，是因为我们刚才说过的索引必须在任何一个元素改变时保持稳定，而 String 不能保证这一点。

组合能力

这些专门的集合协议还可以被很好地组合起来，作为一组约束，来匹配每个特定算法的要求。举例来说，标准库中有个 sort 方法，可以原地对一个集合进行排序 (而不像它的不可变版本 sorted 那样，返回一个排序后的数组)。原地排序需要集合是可变的，如果你想要排序保持迅速，你还需要随机存取。最后，当然你还需要能够比较集合中元素的大小。

extension MutableCollection
where Self: RandomAccessCollection, Element: Comparable { 
/// 原地对集合进行排序
    public mutating func sort() { ... }
}
复制代码

延迟序列

标准库为支持延迟编程 (lazy programming) 提供了两个协议:LazySequenceProtocol 和 LazyCollectionProtocol。延迟编程意味着结果只有在真正需要的时候才会计算出来，这是相较于立即编程 (eager programming) 而提出的概念，而后者也是 Swift 默认的编程方式。一个延迟序列 (lazy sequence) 可以在序列的生成和使用之间创建一个隔离:你不必预先创建出整个序列。相反，只有当使用者真正需要序列的下一个元素时，延迟序列才产生这个元素。这种方式不仅仅是一种编程风格，还可以带来性能上的收益。

展示了三种不同的构建斐波那契数列的方法:使用定制的迭代器，使用 AnySequence，以及使用 sequence(first:next:) 方法。这些方法都会产生一个包含无穷多个元素的数值流，只是这个流中的元素都是延迟生成出来的，下一个值只有在使用者通过 next 方法获取的时候，才会计算出来。这就让使用者可以决定究竟要在序列中生成多少个元素。例如，我们可以只获取这个序列的第一个元素，或者某个元素的前缀。

延迟计算序列的一个问题就是有些变换操作需要对整个序列进行计算。例如，对于之前定义的 standardIn，它从标准输入逐行读取输入的字符串，这是一个只能单次遍历的序列。可能希望只打印某些符合特定条件的行。通过函数式风格表达的话，想到用 filter 来实现。但 Sequence 中 filter 的返回值是个数组(这也就意味着它不再具有延迟计算的特性了)，因此这个实现只有在处理完所有从标准输入读取的内容之后，才会返回结果。换句话说，这个结果已经不是延迟计算出来的了。下面的代码会打印输入中所有多于三个字符的行，但结果只有在标准输入收到了 EOF 信号之后才会显示出来:

let filtered = standardIn.filter { 
    $0.split(separator: " ").count > 3
}
for line in filtered { print(line) }
复制代码

e
希望每读到一行符合条件的结果，就打印一个消息。一个可行的解决方案就是采用下面命令式编程的风格:

for line in standardIn {
    guard line.split(separator: " ").count > 3 else { continue } 
    print(line)
}
复制代码

如果我们希望使用函数式的风格，用方法的串联替代掉 for 循环，我们必须在获取到值的时候就生成筛选后的结果，而不是等读取了所有的输入之后再处理。换句话说，我们需要一个延迟序列。标准库为 Sequence 提供了一个 .lazy 属性帮助我们实现这样的行为。因此之前的例子可以改成这样:

let filtered = standardIn.lazy.filter { 
    $0.split(separator: " ").count > 3
}
for line in filtered { print(line) }
复制代码

.lazy 的返回值类型是 LazySequence<Self>。这也就意味着 standardIn.lazy 的类型是 LazySequence<AnySequence<String>>。LazySequence 会在内部存储原始的序列，但它不会对其进行额外的处理。然后，LazySequence 的 filter 方法会返回一个 LazyFilterSequence<AnySequence<String>>。它会在内部存储原始的序列以及 filter 的谓词函数。

这也就意味着，在上面的例子中，随着遍历 filtered，从标准输入中读到的每一行都会立即处理，可以在控制台立即看到符合条件的输入，而不是等到 EOF 信号之后统一处理。这样一来，也就不会创建保存所有输入结果的临时数组了。

另外，当需求发生变化时，观察这种编程方式下代码的变化也很有意思。例如，让我们只打印第一个输入大于三个字符的行。使用 lazy，我们完全不需要修改 filtered 的定义，只要访问它的 first 属性就好了:


let filtered = standardIn.lazy.filter { 
    $0.split(separator: " ").count > 3
}
print(filtered.first ?? "<none>")
复制代码

如果没有 lazy，上面的代码就会从标准输入读入所有的行，直到它收到 EOF 信号。然后再从中找到第一个符合条件的元素。使用 lazy，它就只会读到第一个满足条件的输入，之后的标准输入就不再处理了。如果要读取前两个符合条件的输入，我们可以把 first 改成 prefix(2)。相比于修改命令式编程的代码，修改这些函数式风格的代码通常都要更简单和清晰。例如，下面就是同一个功能两种实现方式的比较，一个是 lazy 的版本，另一个则是命令式编程的版本:

//函数式
let result = Array(standardIn.lazy.filter {
    $0.split(separator: " ").count > 3 
}.prefix(2))
//命令式
var result: [String] = [] for line in standardIn {
    guard line.split(separator: " ").count > 3 else { continue } 
    result.append(line)
    if result.count == 2 { break }
}
复制代码

集合的延迟处理

当在一个常规集合类型 (例如:Array) 上串联多个操作的时候，可以延迟处理的序列会更有效率。如果更倾向于函数式编程，可能会写出下面这样的代码:

(1..<100).map { $0 * $0 }.filter { $0 > 10 }.map { "\($0)"}
复制代码

习惯函数式编程之后，上面的代码就会显得很清晰并易于理解。但是，它却存在着效率不佳的问题:每一次调用 map 和 filter 都会新建一个包含中间结果的数组，并且，这个数组在函数返回的时候就被销毁了。通过在这个调用链的开始插入 .lazy，就不会产生任何保存中间结果的数组，代码的执行就会更有效率:

(1..<100).lazy.map { $0 * $0 }.filter { $0 > 10 }.map { "\($0)"}
复制代码

在 Swift 5.0 中，不启用编译器优化的条件下，使用了 .lazy 的代码可以比之前的版本快三倍，
而使用 -O 开启优化之后，性能可以提升八倍。

LazyCollectionProtocol 扩展了 LazySequence，它要求实现它的类型也是一个实现了 Collection 的类型。在一个延迟加载的序列里，我们只能 “按需” 逐个生成序列中的每个元素。但在一个集合里，我们可以直接 “按需” 生成指定的某个元素。例如，当你对一个延迟加载的集合应用 map 方法之后，通过下标访问其中的某个元素，map 就只会对你访问的那个结果执行变换 (在这里例子中，就是第 51 个元素):

let allNumbers = 1..<1_000_000
let allSquares = allNumbers.lazy.map { $0 * $0 } 
print(allSquares[50]) // 2500
复制代码

但是，延迟加载的集合也不总是能在性能方面胜出，有些情况你就需要特别注意。当使用下标访问元素的时候，每一次结果都是计算出来的。根据集合在获取结果是进行的计算，下标操作符可能就不是一个 O(1) 操作了。例如，考虑下面这个例子:

let largeSquares = allNumbers.lazy.filter { $0 > 1000 }.map { $0 * $0 } 
print(largeSquares[50]) // 2500
复制代码

在打印语句执行前，filter 和 map 不会进行任何实质性的工作。由于对 allNumbers 进行了过滤，因此，largeSquares 中的第 51 个元素和 allNumbers 中是不一样的。为了找到正确的元素，每次像这样 [50] 访问的时候，filter 都必须计算出原始序列中的前 51 个元素，显然，这并不是一个常量时间的操作。

文章版权归作者所有，未经允许请勿转载。

THE END

IOS