下载掌阅APP，畅读海量书库
立即打开
索引表示了集合中的位置。每个集合都有两个特殊的索引值：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}
}
返回的类型是Element。对字典来说，Element类型是一个多元组：(key:Key,value:Value)，因此对于Dictionary，下标访问返回的是一个键值对，而非单个的Value。
在第2章的数组索引部分，我们讨论过为什么像Swift这样一门“安全”的语言不把所有可能失败的操作用可选值或者错误包装起来。“如果所有API都可能失败，那你就没法写代码了 [6] 。我们需要有一个基本盘的东西可以依赖，并且信任这些操作的正确性”，否则我们的代码将会深陷安全检查的囹圄。
当集合发生改变时，索引可能会失效。失效有两层含义，它可能意味着虽然索引本身仍是有效的，但是它现在指向了一个另外的元素；或者有可能索引本身就已经无效了，通过它对集合访问将造成程序崩溃。在你用数组进行思考时，这个问题会比较直观。当你添加一个元素后，所有已有的索引依然有效。但是当你移除第一个元素后，指向最后一个元素的索引就无效了。同时，那些较小的索引依然有效，但是它们所指向的元素都发生了改变。字典的索引不会随着新的键值对的加入而失效， 直到 字典的尺寸增大到触发重新的内存分配。这是因为一般情况下字典存储的缓冲区内的元素位置是不会改变的，而在元素超过缓冲区尺寸时，缓冲区会被重新分配，其中的所有元素的哈希值也会被重新计算。从字典中移除元素总是会使索引失效 [7] 。
索引应该是一个只存储包含描述元素位置所需最小信息的简单值。在尽可能的情况下，索引不应该持有对它们集合的引用。类似地，一个集合通常不能够区分它“自己的”索引和一个来自同样类型集合的索引之间的区别。用数组来举例子就再清楚不过了。显然，我们可以用从一个数组中获取到的整数索引值来访问另一个数组的内容：
let numbers=[1,2,3,4]
let squares=numbers.map{$0*$0}
let numbersIndex=numbers.index(of:4)!//3
squares[numbersIndex]//16
这对那些像String.Index的不透明的索引类型也是适用的。在这个例子中，我们使用一个字符串的startIndex来访问另一个字符串的首字符：
let hello="Hello"
let world="World"
let helloIdx=hello.startIndex
world[helloIdx]//W
不过，能这么做并不意味着这么做会是一个好方法。如果用这个索引来通过下标访问一个空字符串，那么程序将因为索引越界而发生崩溃。
在集合之间共享索引是有其合理用法的，在切片上我们会大量使用这种方式。子序列通常会与它们的原序列共享底层的存储，所以原序列的索引在切片中也会定位到同样的元素。
Swift3在集合处理索引遍历方面引入了一个大的变化 [8] 。现在，向前或者向后移动索引（或者说，从一个给定索引计算出新的索引）的任务是由集合来负责的了，而在Swift2中，索引是可以自己进行步进移动的。之前我们可能会用someIndex.successor()来获取下一个索引，现在我们需要写collection.index(after:someIndex)。
为什么Swift团队要做这样的变化？简单地说，为了性能。通常，从一个索引获取到另一个索引会涉及集合内部的信息。数组中的索引没有这个顾虑，因为在数组里索引的步进都是一些简单的加法运算。但是例如对于一个字符串索引，因为字符在Swift中尺寸是可变的，所以计算索引时需要考虑实际字符的数据到底是什么。
在原来的自己管理的索引模型中，索引必须保存一个对集合存储的引用。这个额外的引用会在集合被迭代修改时造成不必要的复制，它带来的开销足以抵消标准库中集合的写时复制特性带来的性能改善。
新的模型通过将索引保持为简单值，就可以解决这个问题。它的概念更容易理解，也让我们可以更简单地实现自定义的索引类型。当我们实现自己的索引类型时，要尽可能地避免持有集合类型的引用。在大多数情况下，索引可以由一个或者两个高效地对集合底层存储元素位置进行编码的整数值所表示。
新的索引模型的缺点是，有时候它的语法会显得有一些啰唆。
作为非整数索引的例子，让我们来实现最基础的集合类型：单向链表。在此之前，先来看看实现数据结构的另一种方法：使用间接枚举（indirect enum）。
一个链表的节点有两种可能：要么它有值，并且指向对下一个节点的引用，要么它代表链表的结束。我们可以这样来定义它：
///一个简单的链表枚举
enum List<Element>{
case end
indirect case node(Element,next:List<Element>)
}
在这里使用indirect关键字可以告诉编译器这个枚举值应该被看作引用。Swift的枚举是值类型，这意味着一个枚举将直接在变量中持有它的值，而不是持有一个指向值位置的引用。这样做有很多好处，我们会在第5章中介绍它们。但是这同时也意味着它们不能包含一个对自己的引用。indirect关键字允许一个枚举成员能够持有引用，这样一来，它就能够持有自己。
我们通过创建一个新的节点，并将next值设为当前节点的方式来在链表头部添加一个节点。为了使用起来简单一些，我们为它创建了一个方法。我们将这个添加方法命名为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,List<Swift.Int>.node(2,List<Swift.Int>.node(1,List<Swift.Int>.end)))
链式的语法调用使链表的构建过程十分清晰，但是它看起来却十分丑陋。和队列类型一样，可以为它添加ExpressibleByArrayLiteral，这样就能用数组字面量的方式来初始化一个链表了。首先对输入数组进行逆序操作（因为链表是从末位开始构建的），然后使用reduce以及.end为初始值来将元素一个个地添加到链表中（见图3.1）：
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,List<Swift.Int>.node(2,List<Swift.Int>.node(1,List<Swift.Int>.end)))
图3.1 List Sharing
这个列表类型有一个很有趣的特性——它是“持久 [9] ”的。节点都是不可变的，一旦它们被创建，我们就无法再进行更改了。将另一个元素添加到链表中并不会复制这个链表，它仅仅只是给你一个链接在既存的链表的前端的节点。
也就是说，两个链表可以共享链表尾：
链表的不可变性的关键就在这里。假使你可以改变链表（比如移除最后的条目，或者对某个节点的元素进行升级等），那么这种共享就会出现问题——x将会改变链表，而改变将会影响到y。
栈
链表其实是一个栈，构建链表相当于进栈，获取下一个值相当于出栈。前面提到过，数组也可以看作栈。现在让我们像对待队列那样，来定义一个通用的栈的协议：
///一个进栈和出栈都是常数时间操作的后进先出(LIFO)栈
protocol Stack{
///栈中存储的元素的类型
associatedtype Element
///将x入栈到self作为栈顶元素
///-复杂度：O(1).
mutating func push(_x:Element)
///从self移除栈顶元素，并返回它
///如果self是空，返回nil
///-复杂度：O(1)
mutating func pop()->Element?
}
我们这次在Stack的协议定义的文档注释中做了详细一些的约定，包括给出了性能上的保证。
Array可以遵守Stack：
extension Array:Stack{
mutating func push(_x:Element){append(x)}
mutating func pop()->Element?{return popLast()}
}
List也行：
extension List:Stack{
mutating func push(_x:Element){
self=self.cons(x)
}
mutating func pop()->Element?{
switch self{
case.end:return nil
case let.node(x,next:xs):
self=xs
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，变量就变成链表的迭代器了（见图3.2）。当然，你可以使用let而不是var来声明这些变量。这样一来，这些变量将变为常量，当它们所持有的值一旦被设定以后，也不能再被更改了。不过let是和变量相关的概念，它和值没什么关系。值天生就是不能变更的，这是定义使然。
现在，一切就顺理成章了。在实际中，这些互相引用的节点会被放在内存中。它们会占用一些内存空间，如果我们不再需要它们，那么这些空间应该被释放。Swift使用自动引用计数（ARC）来管理节点的内存，并在不再需要的时候释放它们（见图3.3）。
图3.2链表迭代器
图3.3 链表的内存管理
我们会在第6章中详细介绍input，对于可变方法和ARC的有关内容，会在第5章再深入探讨。
让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
让List遵守Collection
接下来，我们要让List实现Collection。要做到这一点，需要确定List的索引类型。前面说过，对集合来说，最好的索引类型是关于集合存储的一个简单的整数偏移值，但是在这里并不适用，因为链表并不是连续的存储结构。想要通过基于整数的索引（比如从链表开头节点到某个特定节点所需要步数）来获取元素，每次都只能对链表从startIndex开始进行遍历，这会使得下标索引变成一个 O ( n )操作。然而，Collection的文档 [10] 指出，下标访问应该是 O (1)的，“因为很多集合操作都依赖于 O (1)的下标操作，否则它们也将无法达到保证的性能。”
如此一来，我们的索引必须要直接引用链表的节点。这不会造成性能问题，因为List是不可变的，它没有使用任何的写时复制优化。因为我们已经将List直接作为迭代器来使用了，采用同样的方式，将枚举本身作为索引来使用也是一件很诱惑人的事情。不过这可能会导致问题，比如索引和集合需要的==实现并不相同：
·索引需要知道从相同列表中取出的两个索引是否在相同的位置。它不需要列表中的元素满足Equatable。
·而对集合来说，它应该可以比较两个不同的列表，检查它们是否含有相同的元素。这需要列表元素满足Equatable。
通过创建不同的类型来分别代表索引和集合，可以为它们实现两个不同的==运算符。另外，由于索引不是节点枚举，可以将节点的实现标记为私有，从而将这个细节隐藏起来。新的ListNode类型看起来和我们一开始的List非常相似：
///List集合类型的私有实现细节
fileprivate enum ListNode<Element>{
case end
indirect case node(Element,next:ListNode<Element>)
func cons(_x:Element)->ListNode<Element>{
return.node(x,next:self)
}
}
索引类型封装了ListNode。某个类型必须满足Comparable，才能成为集合类型的索引。而Comparable有两个要求：它需要实现一个小于运算符（<）和一个从Equatable继承的等于运算符（==）。一旦有了这两个运算符实现，则另外的像>、<=和>=就都可以使用默认的实现。要实现==和<，还需要一些额外的信息。前面提到过，节点是值，值是不具有同一性的。那么怎么说明两个变量是指向同一个节点的呢？为了解决这个问题，我们使用一个递增的数字来作为每个索引的标记值（tag）（.end节点的标记值为0）。我们之后会看到，在索引中存储这些标记可以让操作变得非常高效。列表的工作原理决定了如果相同列表中的两个索引拥有同样的标记值，那么它们就是同一个索引：
public struct ListIndex<Element>:CustomStringConvertible{
fileprivate let node:ListNode<Element>
fileprivate let tag:Int
public var description:String{
return"ListIndex(\(tag))"
}
}
另一个值得注意的地方是，虽然ListIndex是被标记为公开的结构体，但是它有两个私有属性（node和tag）。这意味着该结构体不能被从外部构建，因为它的“默认”构造函数ListIndex(node:tag:)对外部用户来说是不可见的。可以从一个List中拿到ListIndex，但是不能自己创建一个ListIndex。这是非常有用的技术，它可以帮助你隐藏实现细节，并提供安全性。
我们还需要实现Equatable。前面已经讨论过，通过检查tag标记值就可以判定它们是否相等了：
extension ListIndex:Comparable{
public static func==<T>(lhs:ListIndex<T>,rhs:ListIndex<T>)->Bool{
return lhs.tag==rhs.tag
}
public static func<<T>(lhs:ListIndex<T>,rhs:ListIndex<T>)->Bool{
//startIndex的tag值最大,endIndex最小
return lhs.tag>rhs.tag
}
}
现在我们有合适的索引类型了，下一步是创建满足Collection协议的List结构体：
public struct List<Element>:Collection{
//Index的类型可以被推断出来，不过写出来可以让代码更清晰一些
public typealias Index=ListIndex<Element>
public let startIndex:Index
public let endIndex:Index
public subscript(position:Index)->Element{
switch position.node{
case.end:fatalError("Subscript out of range")
case let.node(x,_):return x
}
}
public func index(after idx:Index)->Index{
switch idx.node{
case.end:fatalError("Subscript out of range")
case let.node(_,next):return Index(node:next,tag:idx.tag-1)
}
}
}
注意，List除了startIndex和endIndex并不需要存储其他东西。因为索引封装了列表节点，而节点又相互联系，所以可以通过startIndex来访问到整个列表。endIndex对于所有的实例（至少在我们之后谈及切片前）来说，都是相同的ListIndex(node:.end,tag:0)。
为了让创建列表变得简单一些，我们还实现了ExpressibleByArrayLiteral：
extension List:ExpressibleByArrayLiteral{
public init(arrayLiteral elements:Element...){
startIndex=ListIndex(node:elements.reversed().reduce(.end){
partialList,element in
partialList.cons(element)
},tag:elements.count)
endIndex=ListIndex(node:.end,tag:0)
}
}
从Sequence继承得到的能力可以让我们很容易地写出一个简单的description实现，从而能更好地进行调试输出。将列表元素进行map操作，将它们转为字符串的表示形式，然后再拼接成一个单独的字符串：
extension List:CustomStringConvertible{
public var description:String{
let elements=self.map{String(describing:$0)}
.joined(separator:",")
return"List:(\(elements))"
}
}
现在，我们的列表可以使用Collection的扩展了：
let list:List=["one","two","three"]//List:(one,two,three)
list.first//Optional("one")
list.index(of:"two")//Optional(ListIndex(2))
除此之外，因为tag计算了添加到.end之前的节点的数量，所以List可以拥有一个常数时间的复杂度count属性。而一般的链表的count是 O ( n )复杂度的：
extension List{
public var count:Int{
return startIndex.tag-endIndex.tag
}
}
list.count//3
被减去的列表末尾的tag值，到现在为止都一定会是0。在这里将它写为更一般的endIndex，是因为我们还想要支持马上就要提到的切片操作。最后，因为List和ListIndex是两个不同类型，可以为List实现一个不同的==运算符，用来比较集合中的元素：
public func==<T:Equatable>(lhs:List<T>,rhs:List<T>)->Bool{
return lhs.elementsEqual(rhs)
}
在一个完美的类型系统中，我们不仅会去重载==，还应该在将List本身声明为Equatable的同时，将它的Element类型也约束为Equatable，就像这样：
extension List:Equatable where Element:Equatable{}
//错误:含有约束的List类型不能拥有继承语句关系
如果能做到这样，我们就将可以比较一系列的列表，或者将List用在其他任何需要Equatable的地方。不过现在这门语言还不支持这样的约束方式。不过， 按条件遵守的协议 是一个被高度期望的特性，很可能在Swift4中可以看到它的出现。