在前一章中,我们看到了 Array,Dictionary 和 Set,它们并非空中楼阁,而是建立在一系列由 Swift 标准库提供的用来处理元素序列的抽象之上的。这一章我们将讨论 Sequence 和 Collection 协议,它们构成了这套集合类型模型的基石。我们会研究这些协议是如何工作的,它们为什么要以这样的方式工作,以及你如何写出自己的序列和集合类型等话题。
序列
Sequence 协议是集合类型结构中的基础。一个序列 (sequence) 代表的是一系列具有相同类型的值,你可以对这些值进行迭代。遍历一个序列最简单的方式是使用 for 循环:
for element in someSequence {
doSomething(with: element)
}
Sequence 协议提供了许多强大的功能,满足该协议的类型都可以直接使用这些功能。上面这样步进式的迭代元素的能力看起来十分简单,但它却是 Sequence 可以提供这些强大功能的基础。我们已经在上一章提到过不少这类功能了,每当你遇到一个能够针对元素序列进行的通用的操作,你都应该考虑将它实现在 Sequence 层的可能性。在本章和书中接下来的部分,我们将会看到许多这方面的例子。
满足 Sequence 协议的要求十分简单,你需要做的所有事情就是提供一个返回迭代器 (iterator) 的 makeIterator() 方法:
protocol Sequence {
associatedtype Iterator: IteratorProtocol
func makeIterator() -> Iterator
// ...
}
对于迭代器,我们现在只能从 Sequence 的 (这个简化后的) 定义中知道它是一个可以创建迭代器 (Iterator) 协议的类型。所以我们首先来仔细看看迭代器是什么。
迭代器
序列通过创建一个迭代器来提供对元素的访问。迭代器每次产生一个序列的值,并且当遍历序列时对遍历状态进行管理。在 IteratorProtocol 协议中唯一的一个方法是 next(),这个方法需要在每次被调用时返回序列中的下一个值。当序列被耗尽时,next() 应该返回 nil:
protocol IteratorProtocol {
associatedtype Element
mutating func next() -> Element?
}
关联类型 Element 指定了迭代器产生的值的类型。比如 String 的迭代器的元素类型是 Character。通过扩展,迭代器同时也定义了它对应的序列的元素类型 (我们会在本章以及接下来的协议中看到很多关于带有关联类型的协议的内容):
public 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)
}
迭代器是单向结构,它只能按照增加的方向前进,而不能倒退或者重置。虽然大部分的迭代器的 next() 都只产生有限数量的元素,并最终会返回 nil,但是你也完全可以创建一个无限的,永不枯竭的序列。实际上,除了那种一上来就返回 nil 的迭代器,最简单的情况应该是一个不断返回同样值的迭代器了:
struct ConstantIterator: IteratorProtocol {
typealias Element = Int
mutating func next() -> Int? {
return 1
}
}
显示地使用 typealias 指定 Element 的类型其实并不是必须的 (不过通常可以用为文档的目的帮助理解代码,特别是在更大的协议中这点尤为明显)。如果我们去掉它,编译器也将会从 next() 的返回值类型中推断出 Element 的类型:
struct ConstantIterator: IteratorProtocol {
mutating func next() -> Int? {
return 1
}
}
注意这里 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
}
}
遵守序列协议
我们也可以创造有限序列的迭代器,比如下面这个 PrefixGenerator 就是一个例子。它将顺次生成字符串的所有前缀 (也包含字符串本身)。它从字符串的开头开始,每次调用 next 时,会返回一个追加之后一个字符的字符串切片,直到达到整个字符串尾部为止:
struct PrefixIterator: IteratorProtocol {
let string: String
var offset: String.Index
init(string: String) {
self.string = string
offset = string.startIndex
}
mutating func next() -> Substring? {
guard offset < string.endIndex else { return nil }
offset = string.index(after: offset)
return string[..<offset]
}
}
(string[..<offset] 是一个对字符串的切片操作,它将返回从字符串开始到偏移量为止的子字符串。我们在前一章已经看到过部分范围的语法了,稍后我们会再对切片进行一些讨论。)
有了 PrefixIterator,定义一个 PrefixSequence 类型就很容易了。和之前一样,我们不需要指明关联类型 Iterator 或 Element 的具体类型,因为编译器可以从 makeIterator 方法的返回类型中自己推断出来:
struct PrefixSequence: Sequence {
let string: String
func makeIterator() -> PrefixIterator {
return PrefixIterator(string: string)
}
}
现在,我们可以使用 for 循环来进行迭代,并打印出所有的前缀了:
for prefix in PrefixSequence(string: "Hello") {
print(prefix)
}
/*
H
He
Hel
Hell
Hello
*/
我们还可以对它执行 Sequence 提供的所有操作:
PrefixSequence(string: "Hello").map { $0.uppercased() }
// ["H", "HE", "HEL", "HELL", "HELLO"]
通过同样的方式,我们可以为 ConstantIterator 和 FibsIterator 创建对应的序列。我们在这里就不进行展示了,你可以自己尝试一下。不同之处在于这些迭代器会创建出无穷序列,你可以使用像是 for i in fibsSequence.prefix(10) 的方式来截取其中有限的一段进行测试。
迭代器和值语义
我们至今为止所看到的迭代器都具有值语义。如果你复制一份,迭代器的所有状态也都会被复制,这两个迭代器将分别在自己的范围内工作,这是我们所期待的。标准库中的大部分迭代器也都具有值语义,不过也有例外存在。
为了说明值语义和引用语义的不同,我们首先来看看 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)”
var i4 = i3
在这种情况下,原来的迭代器和复制后的迭代器并不是独立的,因为实际的迭代器不再是一个结构体,AnyIterator 并不具有值语义。AnyIterator 中用来存储原来迭代器的盒子对象是一个类实例,当我们将 i3 赋值给 i4 的时候,只有对这个盒子的引用被复制了。盒子里存储的对象将被两个迭代器所共享。所以,任何对 i3 或者 i4 进行的调用,都会增加底层那个相同的迭代器的取值:
i3.next() // Optional(4)
i4.next() // Optional(5)
i3.next() // Optional(6)
i3.next() // Optional(7)
显然,这可能会造成一些 bug,不过在实践中你可能很少会遇到这种问题。这是因为平时你一般不会在你的代码里把迭代器这样来回传递.
基于函数的迭代器和序列
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 fibsSequence2 = sequence(state: (0, 1[…])) {
// 在这里编译器需要一些类型推断的协助
(state: inout (Int, Int)) -> Int? in
let upcomingNumber = state.0
state = (state.1, state.0 + state.1)
return upcomingNumber
}
Array(fibsSequence2.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 则将一个单一的值展开形成一个序列。
这两个 sequence 方法非常有用,它们经常用来代替传统的 C 风格的循环,特别是当下标的步长不遵守线性关系的时候。在结构体和类一章中,我们会看到更多关于 inout 参数的内容。
无限序列
就像我们至今为止看到的迭代器一样,sequence 对于 next 闭包的使用是被延迟的。也就是说,序列的下一个值不会被预先计算,它只在调用者需要的时候生成。这使得我们可以使用类似 fibsSequence2.prefix(10) 这样的语句,因为 prefix(10) 只会向序列请求它的前十个元素,然后停止。如果序列是主动计算它的所有值的话,因为序列是无限的,程序将会在有机会执行下一步之前就因为整数溢出的问题而发生崩溃。
对于序列和集合来说,它们之间的一个重要区别就是序列可以是无限的,而集合则不行。
不稳定序列
序列并不只限于像是数组或者列表这样的传统集合数据类型。像是网络流,磁盘上的文件,UI 事件的流,以及其他很多类型的数据都可以使用序列来进行建模。但是这些都和数组不太一样,对于数组,你可以多次遍历其中的元素,而上面这些例子中你并非对所有的序列都能这么做。
斐波纳契序列确实不会因为遍历其中的元素而发生改变,你可以从 0 开始再次进行遍历,但是像是网络包的流这样的序列将会随着遍历被消耗。你就算再次对其进行迭代,它也不会再次产生同样的值。两者都是有效的序列,Sequence 的文档非常明确地指出了序列并不保证可以被多次遍历:
Sequence 协议并不关心遵守该协议的类型是否会在迭代后将序列的元素销毁。也就是说,请不要假设对一个序列进行多次的 for-in 循环将继续之前的循环迭代或者是从头再次开始,一个非集合的序列可能会在第二次 for-in 循环时产生随机的序列元素。
for element in sequence {
if ... some condition { break }
}
for element in sequence {
// 未定义行为
}
这也解释了为什么我们只有在集合类型上能见到 first 这个看起来很简单的属性,而在序列中该属性却不存在。调用一个属性的 getter 方法应该是非破坏的,但只有 Collection 协议能保证多次进行迭代是安全的,Sequence 中对此并没有进行保证。
举一个破坏性的可消耗序列的例子:我们有一个对 readLine 函数的封装,它会从标准输入中读取一行:
let standardIn = AnySequence {
return AnyIterator {
readLine()
}
}
现在,你可以使用 Sequence 的各种扩展来进行操作了,比如你可以这样来写一个带有行号的类型 Unix 中 cat 命令的函数:
let numberedStdIn = standardIn.enumerated()
for (i, line) in numberedStdIn {
print("\(i+1): \(line)")
}
enumerate 将一个序列转化为另一个带有递增数字的新序列。和 readLine 进行的封装一样,这里的元素也是延迟生成的。对于原序列的消耗只在你通过迭代器移动到被迭代的序列的下一个值时发生,而不是在序列被创建时发生的。因此,你在命令行中运行上面的代码的话,会看到程序在 for 循环中进行等待。当你输入一行内容并按下回车的时候,程序会打印出相应的内容。当按下 control-D 结束输入的时候,程序才会停止等待。不过无论如何,每次 enumerate 从 standardIn 中获取一行时,它都会消耗掉标准输入中的一行。你没有办法将这个序列迭代两次并获得相同的结果。
如果你在写一个 Sequence 的扩展的话,你并不需要考虑这个序列在迭代时是不是会被破坏。但是如果你是一个序列类型上的方法的调用者,你应该时刻提醒自己注意访问的破坏性。
如果一个序列遵守 Collection 协议的话,那就可以肯定这个序列是稳定的了,因为 Collection 在这方面进行了保证。但是反过来却不一定,稳定的序列并不一定需要是满足 Collection。在标准库中,就有一些非集合的序列是可以被多次遍历的。这样的例子包括 stride(from:to:by:) 返回的 StrideTo 类型,以及 stride(from:through:by:) 所返回的 StrideThrough 类型。因为你可以很取巧地使用浮点数步长来获取值,这使得它们无法被描述为一个集合,所以它们只能作为序列存在。
序列和迭代器之间的关系
序列和迭代器非常相似,你可能会问,为什么它们会被分为不同的类型?我们为什么不能直接把 IteratorProtocol 的功能包含到 Sequence 中去呢?对于像是前面标准输入例子那种破坏性消耗的序列来说,这么做确实没有问题。这类序列自己持有迭代状态,并且会随着遍历而发生改变。
然而,对于像斐波纳契序列这样的稳定序列来说,它的内部状态是不能随着 for 循环而改变的,它们需要独立的遍历状态,这就是迭代器所提供的 (当然还需要遍历的逻辑,不过这部分是序列的内容)。makeIterator 方法的目的就是创建这样一个遍历状态。
其实对于所有的迭代器来说,都可以将它们看作是即将返回的元素所组成的不稳定序列。事实上,你可以单纯地将迭代器声明为满足 Sequence 来将它转换为一个序列,因为 Sequence 提供了一个默认的 makeIterator 实现,对于那些满足协议的迭代器类型,这个方法将返回 self 本身。Swift 团队也在 swift-evolution 的邮件列表里声明过,要不是由于语言限制的原因,IteratorProtocol 应该继承自 Sequence (具体来说,这个原因是编译器缺乏对于递归的关联类型约束的支持)。
虽然现在不可能添加这样的强制关系,不过标准库中的大部分迭代器还是满足了 Sequence 协议的。
子序列
Sequence 还有另外一个关联类型,叫做 SubSequence:
protocol Sequence {
associatedtype Element
associatedtype Iterator: IteratorProtocol where Iterator.Element == Element
associatedtype SubSequence
// ...
}
在返回原序列的切片的操作中,SubSequence 被用作返回值的子类型,这类操作包括:
prefix 和 suffix — 获取开头或结尾 n 个元素
prefix(while:) - 从开头开始当满足条件时,
dropFirst 和 dropLast — 返回移除掉前 n 个或后 n 个元素的子序列
drop(while:) - 移除元素,直到条件不再为真,然后返回剩余元素
split — 将一个序列在指定的分隔元素时截断,返回子序列的的数组
如果你没有明确指定 SubSequence 的类型,那么编译器会将它推断为 AnySequence<Iterator.Element>,这是因为 Sequence 以这个类型作为返回值,为上述方法提供了默认的实现。如果你想要使用你自己的子序列类型,你必须为这些方法提供自定义实现。
在有些时候,子序列和原来序列的类型一致,也就是 SubSequence == Self 时,会非常方便,因为这让你可以将切片传递回那些参数是原始集合类型的函数中。在标准库中的集合类型拥有不一样的切片类型,不过,这么做的主要考量还是防止不经意的内存“泄漏”,一个非常小的切片将会持有它原来的集合类型 (有可能非常大),在切片的生命周期比预期要长得多的时候,这可能造成一些问题。使用它们自己的类型来表示切片,可以比较容易将它们的生命周期绑定到局部作用域中。
在理想世界里,SubSequence 关联类型的声明应该要包括 (a) 其本身也是序列,(b) 子序列的元素类型和其子序列类型,要和原序列中的对应类型一致这两个约束。如果我们加上这些约束,声明看起来会是这样的:
associatedtype SubSequence: Sequence where Element == SubSequence.Element, SubSequence.SubSequence == SubSequence
在 Swift 4.0 中,由于编译器现在没有循环协议约束 (Sequence 会对自身进行引用),这是无法做到的。我们希望最后这个特性能在未来的 Swift 版本中引入。在那之前,你需要自己发现这些约束条件,并将它们添加到你自己的 Sequence 扩展方法中,否则编译器将无法理解相关类型。标准库从一开始就考虑了递归约束;一旦递归约束的特性被实现,许多 Sequence 和 Collection 的 API 将变得更加易于理解,因为它们会将现在还依然需要的显式的约束舍弃掉。
下面这个例子检查了一个序列的开头和结尾是否以同样的 n 个元素开始。它通过比较序列的 prefix 的 n 个元素以及 suffix 的 n 个元素的逆序序列来实现。
extension Sequence where Element: Equatable, SubSequence: Sequence,SubSequence.Element == Element
{
func headMirrorsTail(_ n: Int) -> Bool {
let head = prefix(n)
let tail = suffix(n).reversed()
return head.elementsEqual(tail)
}
}
[1,2,3,4,2,1].headMirrorsTail(2) // true
用来比较的 elementsEqual 方法只能在我们告诉编译器子序列也是一个序列,并且它的元素类型和原序列的元素类像相同的情况下才能工作 (序列中的类型已经遵守了 Equatable):
在泛型中我们还会有一个关于序列扩展方面的例子。
链表
作为自定义序列的例子,让我们来用间接枚举实现一个最基础的数据类型:单向链表。一个链表的节点有两种可能:要么它是一个节点,其中包含了值及对下一个节点的引用,要么它代表链表的结束。我们可以这样来定义它:
/// 一个简单的链表枚举
enum List<Element> {
case end
indirect case node(Element, next: List<Element>)
}
在这里使用 indirect 关键字可以告诉编译器这个枚举值 node 应该被看做引用。Swift 的枚举是值类型,这意味着一个枚举将直接在变量中持有它的值,而不是持有一个指向值位置的引用。这样做有很多好处,我们会在结构体和类一章中介绍它们。但是值类型不能循环引用自身,否则编译器就无法计算它的尺寸了。indirect 关键字允许一个枚举成员能够被当作引用,这样一来,它就能够持有自己了。
我们通过创建一个新的节点,并将 next 值设为当前节点的方式来在链表头部添加一个节点:
let emptyList = List<Int>.end
let oneElementList = List.node(1, next: emptyList)
// node(1, next: List<Swift.Int>.end)
为了使用起来简单一些,我们为它创建了一个方法。我们将这个添加方法命名为 cons,这是因为在 LISP 中这个操作就是叫这个名字 (它是“构造” (construct) 这个词的缩写,在列表前方追加元素的操作有时候也被叫做“consing”):
extension List {
/// 在链表前方添加一个值为 `x` 的节点,并返回这个链表
func cons(_ x: Element) -> List {
return .node(x, next: self)
}
}
// 一个拥有 3 个元素的链表 (3 2 1)
“let list = List<Int>.end.cons(1).cons(2).cons(3)
/*
node(3, next: List<Swift.Int>.node(2, next: List<Swift.Int>.node(1,
next: List<Swift.Int>.end)))
*/
链式的语法调用使链表的构建过程十分清晰,但是它看起来却十分丑陋。我们可以为它添加 ExpressibleByArrayLiteral 支持,这样我们就能用数组字面量的方式来初始化一个链表了。我们首先对输入数组进行逆序操作 (因为链表是从末位开始构建的),然后使用 reduce 函数,并以 .end 为初始值,来将元素一个一个地添加到链表中:
extension List: ExpressibleByArrayLiteral {
init(arrayLiteral elements: Element...) {
self = elements.reversed().reduce(.end) { partialList, element in
partialList.cons(element)
}
}
}
let list2: List = [3,2,1]
/*
node(3, next: List<Swift.Int>.node(2, next: List<Swift.Int>.node(1,
next: List<Swift.Int>.end)))
*/
这个列表类型有一个很有趣的特性,它是“持久”的。节点都是不可变的,一旦它们被创建,你就无法再进行更改了。将另一个元素添加到链表中并不会复制这个链表,它仅仅只是给你一个链接在既存的链表的前端的节点。
也就是说,两个链表可以共享链表尾:
链表共享
链表的不可变性的关键就在这里。假使你可以改变链表 (比如移除最后的条目,或者对某个节点的元素进行升级等),那么这种共享就将出现问题 — x 将会改变链表,而改变将会影响到 y。
我们还可以在 List 上定义一些可变方法,来让我们能够将元素推入和推出 (因为链表其实也是一个栈,构造相当于 push,获取 next 元素相当于 pop):
extension List {
mutating func push(_ x: Element) {
self = self.cons(x)
}
mutating func pop() -> Element? {
switch self {
case .end: return nil
case let .node(x, next: tail):
self = tail
return x
}
}
}
但是我们刚刚不是才说过链表具有持久性和不可变的特性吗?为什么它可以有一个可变方法?
这些可变方法其实并没有改变链表本身,它们改变的只是变量所持有的列表的节点到底是哪一个:
var stack: List<Int> = [3,2,1]
var a = stack
var b = stack
a.pop() // Optional(3)
a.pop() // Optional(2)
a.pop() // Optional(1)
stack.pop() // Optional(3)
stack.push(4)
b.pop() // Optional(3)
b.pop() // Optional(2)
b.pop() // Optional(1)
stack.pop() // Optional(4)
stack.pop() // Optional(2)
stack.pop() // Optional(1)
这足以说明值和变量之间的不同。列表的节点是值,它们不会发生改变。一个存储了 3 并且指向确定的下一个节点的节点永远不会变成其他的值,就像数字 3 不会发生改变一样,这个节点也不会发生改变。虽然这些节点值可以通过引用的方式互相关联,但是这并不改变它们是结构体的事实,它们所表现出的也完全就是值类型的特性。
另一方面,变量 a 所持有的值是可以改变的,它能够持有任意一个我们可以访问到节点值,也可以持有 end 节点。不过改变 a 并不会改变那些节点,它只是改变 a 到底持有的是哪个节点。
这正是结构体上的可变方法所做的事情,它们其实接受一个隐式的 inout 的 self 作为参数,这样它们就能够改变 self 所持有的值了。这并不改变列表,而是改变这个变量现在所呈现的是列表的哪个部分。这样一来,通过 indirect,变量就变成链表的迭代器了:
链表迭代器
当然,你可以使用 let 而不是 var 来声明这些变量。这样一来,这些变量将变为常量 (也就是说,当它们所持有的值一旦被设定以后,也不能再被更改了)。不过 let 是和变量相关的概念,它和值没什么关系。值天生就是不能变更的,这是定义使然。
现在,一切就顺理成章了。在实际中,这些互相引用的节点会被放在内存中。它们会占用一些内存空间,如果我们不再需要它们,那么这些空间应该被释放。Swift 使用自动引用计数 (ARC) 来管理节点的内存,并在不再需要的时候释放它们:
“链表的内存管理
我们会在函数中对 inout 进行更详细的介绍,对于可变方法和 ARC 的有关内容,我们也将在结构体和类再深入探讨。
让 List 遵守 Sequence
因为列表的变量可以进行列举,所以你能够使用它们来让 List 遵守 Sequence 协议。事实上,和我们在序列和迭代器的关系中看到过的一样,List 是一个拥有自己的迭代状态的不稳定序列。我们只需要提供一个 next() 方法,就能一次性地使它遵守 IteratorProtocol 和 Sequence 协议。实现的方式就是使用 pop:
extension List: IteratorProtocol, Sequence {
mutating func next() -> Element? {
return pop()
}
}
现在,你能够在列表上使用 for...in 了:
let list: List = ["1", "2", "3"]
for x in list {
print("\(x) ", terminator: "")
} // 1 2 3
同时,得益于协议扩展的强大特性,我们可以在 List 上使用很多标准库中的函数:
list.joined(separator: ",") // 1,2,3
list.contains("2") // true
list.flatMap { Int($0) } // [1, 2, 3]
list.elementsEqual(["1", "2", "3"]) // true
在计算机科学的理论中,链表对一些常用操作会比数组高效得多。但是实际上,在当代的计算机架构上,CPU 缓存速度非常之快,相对来说主内存的速度要慢一些,这让链表的性能很难与数组相媲美。因为数组中的元素使用的是连续的内存,处理器能够以更高效的方式对它们进行访问。想要进一步了解 Swift 中的集合类型的性能,推荐看看 Károly Lőrentey 关于集合类型优化的相关书籍。
网友评论