到目前为止，我们在数组和自己实现的队列中，一直用整数作为集合的下标.
但不是所有的下标都可以随机访问，可以随机访问的下标也不都是整数。在Swift中，一个类型想要作为集合的下标，至少需要实现ForwardIndexType协议。这个协议很简单，只有两部分构成：一个successor()方法以及实现Equatable协议，也就是说这个类型需要一个==运算符。
为了解释的更加清楚，我们来实现一个最基本的，只能前向访问的集合：单链表。在此之前，我们先展示一种通过间接枚举来实现数据结构的方法。
链表的节点有两部分内容：一个是数据，另一个是下一个节点的引用(如果是链表的尾部，就没有引用了)。我们可以这样定义：
enum List<Element> {
//链表结尾
case End
indirect case Node(Element, next: List<Element>)
}
indirect关键字表示编译器要把这个值当做一个引用。Swift的枚举是值类型，这意味着枚举直接直接持有枚举值，而不是持有枚举值的引用。这种做法有很多优点，我们在后面的章节中会详细讨论。但这同时也表示枚举无法持有对自己的引用。indirect允许某个枚举值作为一个引用被持有，因此也就可以持有指向自己的引用了。
要想向列表的表头添加一个节点，你可以创建一个新节点，并把这个节点的next指向当前节点。为了简化这个过程，我们可以创建一个函数：
extension List {
//返回一个以x开头的链表
func cons(x: Element) -> List {
return .Node(x, next:self)
}
}
//创建一个有三个元素的链表，(3,2,1)
let l = List<Int>.End.cons(1).cons(2).cons(3)
我们把这个向链表头部添加元素的方法叫做cons是因为在LISP语言中它就是这么叫的。
这种链表具有一个有趣的特性：它是永久的。节点一旦创建就不能改变了，把另一个新元素添加到现有链表的头部不会复制链表，只会给你一个新的节点，这个节点的next指向原来链表的头部。
这意味着两个链表变量可以共享同一段尾部。
这是，链表的不可变性就很关键了。如果链表可以被修改(比如移除最后一个节点或修改某一个节点中存的值)，那多个变量之间的共享就会出问题。对其中一个的修改会影响到另一个。
这个链表也可以理解成一个栈。cons方法类似于push，获取下一个节点相当于pop。我们之前还提到过数组也是栈，所以我们来定义一个通用的栈协议：
protocol StackType {
/// 栈中存放的数据的类型别名
typealias Element
/// 把'x'压入栈顶
/// 平均时间复杂度O(1)
mutating func push(x: Element)
/// 将栈顶元素弹栈
/// 如果栈为空返回nil
/// 平均时间复杂度O(1)
mutating func pop() -> Element?
}
这一次的注释要详细一些，包括了函数调用性能的保证。
可以让数组遵守StackType协议：
extension Array: StackType {
mutating func push(x: Element) {
self.append(x)
}
mutating func pop() -> Element? {
guard !self.isEmpty else { return nil }
return self.removeLast()
}
}
也可以让链表实现StackType协议：
extension List: StackType {
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: xs):
self = xs
return x
}
}
}
但我们之前不是说了链表是不可变的么，为什么它还会有被标记为mutating的方法呢？
因为这些变异方法并不是改变链表，而是改变变量所指向的链表中的部分[1]：
var stack = List<Int>.End.cons(1).cons(2).cons(3)
var a = stack
var b = stack
a.pop() // 3
a.pop() // 2
a.pop() // 1
stack.pop() // 3
stack.push(4)
b.pop() // 3
b.pop() // 2
b.pop() // 1
stack.pop() // 4
stack.pop() // 2
stack.pop() // 1
这段代码展示了变量和值的区别。链表的节点是值，它们是不能改变的。一个存储了数据3，同时还有一个next引用的节点，不可能变成其他的值。它永远都是当前这个状态，它所包含的数据也不能变。
但是对于变量a来说，它可以改变它所持有的值。它可以持有任何一个节点的间接引用，或者直接只有末端节点。但是对a的改变不会影响到节点本身，只会改变a到底引用的是哪一个节点。
这就是编结构体的变异方法的定义：他们有一个隐式的inout参数self，所以可以改变self持有的值。链表本身不能被改变，但可以改变变量当前所指向数组的哪一部分。在函数章节我们会讨论更多关于inout关键字的细节。
从这个意义上讲，通过indirect关键字，变量变成了链表的迭代器。
你当然可以把变量声明成let，这样变量就变成了常量(也就是说变量的值一旦确定，就不能再修改了)。但let修饰的是变量而非值，虽然值也是固定不可修改的，但这是由队列定义决定的。
以上是整个链表的模型，实际上节点被放在内存中，它们占据一定空间，彼此指向其他节点。当它们不再需要时，Swift用自动引用计数(ARC)来管理，释放不再使用的节点占用的内存。在后面的章节中我们还会详细讨论ARC
###链表实现SequenceType协议
刚刚我们提到链表变量其实是一种迭代器，所以它可以实现SequenceType协议：
extension List: SequenceType {
func generate() -> AnyGenerator<Element> {
// 用一个变量截获self的状态，通过这个变量迭代
var current = self
return anyGenerator {
//调用next方法时会调用到pop，如果链表为空返回nil
current.pop()
}
}
}
为了让链表使用更简单，你可以让它也实现ArrayLiteralConvertible协议：
extension List: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
self = elements.reverse().reduce(.End, combine: { $0.cons($1) })
}
}
现在就可以使用for .... in语法了：
let l: List = ["1", "2", "3"]
for x in l {
print("\(x) ",terminator: "")
}
同时，由于实现了ArrayLiteralConvertible协议，我们还可以用很多标准库中定义的库函数：
l.joinWithSeparator(",") // "1,2,3,"
l.contains("2") // true
l.flatMap { Int($0) } // [1,2,3]
l.elementsEqual(["1", "2", "3"]) // true
实现CollectionType
接下来让链表类实现CollectionType协议。这样我们可以访问链表变量的.first属性，并在不用pop的情况下获取第一个元素(相当于peek方法)
更重要的是，实现CollectionType协议可以保证将序列多次传递是安全的。官方文档里的描述是：
实现
SequenceType协议的类不关心是否可以反复迭代，如果要保证它在迭代后不会被破坏性[2]”消耗“，就让它实现CollectionType协议。
这解释了为什么只有集合才有first属性——提供计算属性的集合，应该是非破坏性迭代的。至于破坏性迭代的序列，可以参考readLine()函数。对于这样的序列，读取到后面就不能回头，自然也就无法提供first属性了。
let standardIn = AnySequence {
return anyGenerator {
readLine()
}
}
现在你可以用这个序列和SequenceType的协议拓展来写一个行数计算版本的Unix cat了：
let numberedStdIn = standardIn.enumerate()
for (i, line) in numberedStdIn {
print("\(i+1): \(line)")
}
enumerate把一个序列包装在新的序列中，并提供一个递增的下标。和这里对readLine()函数的包装类似，enumerate得到的序列中的元素也是懒创建的。只有在你通过生成器，在新序列里遍历时，才会读取原序列中的元素。所以如果你运行上面这段代码，你输入的内容在你按回车时被打印出来，而不是等到按下'control+D'结束输入。
enumerate方法的实现可能如下：
extension SequenceType {
func enumrate() -> AnySequence<(Int, Generator.Element)> {
return AnySequence { _ -> AnyGenerator<(Int, Generator.Element)> in
//创建一个新的计数器和生成器开始枚举
var i = 0
var g = self.generate()
//在闭包中截取这些变量并在一个新的生成器中返回他们
return anyGenerator{
// 当原序列读到末尾时返回nil
guard let next = g.next() else { return nil }
return (i++, next)
}
}
}
}
但尽管如此，每一次enumrate从numberedStdIn序列中读取一行输入，这一行就无法再次被获取了，也就是说你无法遍历原序列两次并获得相同的值。
有些序列我们可以多次遍历，其中一些序列不必是集合。比如stride方法返回的StrideTo和StrideThrough类型就不是集合。虽然在遍历浮点数时，它们有时候看上去像是集合，不过它们确实只是序列。但他们毫无疑问是可重用的。如果你想要自己拓展SequenceType协议，你不必考虑序列的遍历是否是破坏性的。但如果你要调用SequenceType的方法，那就要搞清楚这个问题了。
我们的链表可以反复遍历，所以如果能实现CollectionType协议是再好不过了。但在此之前，先把节点从链表和下标类型中分离开来。
一种很自然的想法是直接让枚举实现CollectionType和ForwardIndexType协议，不过这样会可能会导致一些问题。比如这两个协议对==运算符的要求完全不同[3]：
ForwardIndexType协议需要知道同一个链表的两个下标是否指的是同一位置。它不要求元素本身实现Equatable协议CollectionType协议则需要比较两个不同的链表，看它们是否包含相同的元素，这就需要元素实现Equatable协议
我们可以把集合和下标用不同的类型表示，这样就可以分别为他们实现==运算符了。同时，因为这两者都不是节点的枚举，我们可以让节点的实现细节变成私有的，对集合的使用者隐藏。
我们还需要做一些调整才能实现下标的==运算符。正如我们之前讨论过的，节点是值类型，因此它没有自己的标识，所以如何区分两个变量是否指向同一个节点呢？为了解决这个问题，我们需要改变一下cons方法使它能用一个递增的数标记每个节点。这样一来，同一个链表中的两个tag相同的节点一定是相同的了：
private enum ListNode<Element> {
//链表结尾
case End
indirect case Node(Element, tag: Int, next: ListNode<Element>)
//用于获取tag的计算属性，.End的tag默认为0
var tag: Int {
switch self {
case .End: return 0
case let .Node(_, tag: n, next: _): return n
}
}
func cons(x: Element) -> ListNode<Element> {
return .Node(x, tag: tag+1, next: self)
}
}
接下来是我们在链表中要用到的下标：
public struct ListIndex<Element> {
private let node: ListNode<Element>
}
ListIndex要做的就是把ListNode封装起来，它没有多余的信息，所以ListNode和ListIndex占用内存的大小是一样的：
assert(sizeof(ListNode<Int>) == sizeof(ListIndex<Int>))
但ListIndex隐藏了ListNode的具体实现。它自己也可以实现ForwardIndex协议，这是任何一个想要可索引的类型都必须遵守的协议。
这个无成本的抽象允许我们构建一些有用的类型而不必考虑影响性能。它可以帮助我们更好的向编译器解释我们的真正目的。
还需要注意一点，ListIndex是一个拥有私有属性(node)的公有(public)结构体。这意味着它的初始化不是公有的，因为它的“默认”构造器无法直接被用户使用。所以你可以从链表中获得ListIndex，却不能自己创建一个。
ForwardIndexType协议只有两个要求。首先，实现它的类型必须有一个successor()方法返回下一个下标：
extension ListIndex: ForwardIndexType {
public func successor() -> ListIndex<Element> {
switch node {
case .End: fatalError("cannot increment endIndex")
case let .Node(_, _, next: next): return ListIndex(node: next)
}
}
}
以及第二点：实现Equatable协议，这样才能判断两个下标是不是相等的。对于链表节点，我们只要判断它们的tag是否相同：
public func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
return lhs.node.tag == rhs.node.tag
}
现在ListIndex结构体就成功实现ForwardIndexType协议了，他现在可以被实现了CollectionType的链表使用了：
public struct List<Element>: CollectionType {
//下标类型可以被自动推导，不过显示地标出有助于理解代码
public typealias Index = ListIndex<Element>
public var startIndex: Index
public var endIndex: Index
public subscript(idx: Index) -> Element {
switch idx.node {
case .End: fatalError("Sbuscript out of range")
case let .Node(x, tag: _, next: _): return x
}
}
}
为了让链表更容易创建，我们实现一下ArrayLiteralConvertible协议：
extension List: ArrayLiteralConvertible {
public init(arrayLiteral elements: Element...) {
startIndex = ListIndex(node: elements.reverse().reduce(.End, combine: { $0.cons($1) }))
endIndex = ListIndex(node: .End)
}
}
现在可以用字面量创建链表了：
let l: List = ["one", "two", "three"]
l.first
l.indexOf("two")
还有一个福利：因为tag其实就是.end节点前所有节点的数量，所以链表有了一个可以在常量级时间访问的属性count，这样就不需要用O(n)的时间通过下标遍历链表了。
extension List {
public var count: Int {
return startIndex.node.tag - endIndex.node.tag
}
}
这里做一个减法(虽然endIndex的tag目前来看一定是0)是为了在使用链表切片时也能正确计算长度。
最后，由于链表和下标现在是不同的类型，所以就可以单独实现链表的==运算符了：
public func == <T: Equatable>(lhs: List<T>, rhs: List<T>) -> Bool {
return lhs.elementsEqual(rhs)
}
实现自定义切片
和默认的下标生成器类似，集合还提供了切片的默认实现，语法是[Range<Index>]，这就是dropFirst方法的实现原理：
let firstDropped = l[l.stratIndex.successor()..<l.endIndex]
在默认情况下，firstDropped的类型不是链表而是链表切片Slice<List<String>>。切片是基于集合的轻量级包装，它的实现大约是这样：
struct Slice<Base: CollectionType>: CollectionType {
let collection: Base
let bounds: Range<Base.Index>
var startIndex: Base.Index { return bounds.startIndex }
var endIndex: Base.Index { return bounds.endIndex }
subscript(idx: Base.Index) -> Base.Generator.Element {
return collection[idx]
}
typealias SubSequence = Slice<Base>
subscript(bounds: Range<Base.Index>) -> SubSequence {
return Slice(collection: collection, bounds: bounds)
}
}
默认的Slice封装了原来的集合，还提供了一个下标子区域。所以这样的切片的大小是同样的数组的两倍[4]：
///链表的大小是两个节点的大小(开始节点和结束节点)
sizeofValue(l) // 结果为16
///链表切片的大小由切片内的链表大小，和子范围的大小组成。
///子范围指的是两个下标之间的范围，在链表看来，这是一些节点
sizeofValue(l.dropFirst()) // 结果为32
这是因为通过持有不同的开始和结束下标(startIndex和endIndex)，链表可以把自己当作子序列返回。我们可以让链表实现自定义的操作：
extension List {
private init(subRange: Range<Index>) {
startIndex = subRange.startIndex
endIndex = subRange.endIndex
}
public subscript(subRange: Range<Index>) -> List<Element> {
return List(subRange: subRange)
}
}
这样，链表切片它们自己也是链表类型的了：
sizeofValue(l.dropFirst()) // 结果为32
这会给链表的实现带来另一个好处。我们知道Swift中有很多切片，比如数组切片、字符串切片等。而切片和原集合共享同一块存储空间，这回导致一个很讨厌的副作用：即使原来的集合已经超出其作用域 ，切片会一直持有这块存储空间。假设你的某个数组占用1G内存，然后产生了一个很小的切片，在这个切片被销毁之前这1G的内存空间都不会被释放。
对于链表来说，这还不算最坏的。我们之前已经看到，节点通过ARC管理：当只有切片还引用这一块内存时，dropFirst部分因为没有被引用，就会立刻被释放。但尾部的节点不会释放，因为切片的最后一个下标还指向在链表中的后面一个节点。
切片的默认实现需要我们注意另一件事：即使是使用整数作为下标，也不要假设集合的下标从0开始。
比如的队列用的是默认的切片实现，所以如果你创建一个队列然后切割它，就会得到一个Slice<Queue<Element>>类型的切片:
let q: Queue = ["a", "b", "c", "d", "e"]
let s = q[2..<5]
现在这个切片的开始下标是子范围的开始下标，切片的结束下标是子范围的结束下标：
q.startIndex // 0
q.endIndex // 5
s.startIndex // 2
s.endIndex // 4
这就是为什么我们倾向于使用for x in collection或for index in collection.indices而不是用C语言风格的代码。当你遍历一个集合时，总是记得把代码写成var i = collection.startIndex而不是var i = 0
前向下标
我们选择实现一个简单的链表是因为读者很熟悉它只能前向遍历的特点。你不能直接跳到链表的中间，也不能从链表的尾部向前遍历。你只能老老实实的一个一个向后遍历。
出于这个原因，我们的链表集合，有一个first属性，却没有last属性。如果你确实想要读取最后一个节点，你需要一路遍历下去直到最后一个节点。由于这是一个O(n)复杂度的算法，所以提供last属性可能误导别人用它，但实际上这样的性能非常低。
提供一个快捷访问的属性需要保证这个属性可以在大约常量级时间中被获取，除非这样的操作显然不可能用常量级时间完成。
这是一个有点含糊的定义，“必须在常量级时间中完成”这个定义会更好，因为可以排除类似于"hello".uppercaseString这样明显不是常量级时间但也是合理的计算属性。
函数需要另外考虑。我们的链表类型没有reverse操作：
let reversed = l.reverse()
上面代码中被调用的reverse是标准库对SequenceType类型的拓展。任何SequenceType类型都可以用这个函数：
extension SequenceType {
// 返回一个把自己含有元素逆序排列的序列
func reverse() -> [Self.Generator.Element]
}
这个函数返回的是一个数组，但我们希望它能返回一个链表。所以我们可以拓展一下链表的reverse()函数：
extension List {
public func reverse() -> List<Element> {
let reversedList: ListNode<Element> = self.reduce(.End, combine: { $0.cons($1) })
return List(startIndex: ListIndex(node: reversedList), endIndex: ListIndex(node: .End))
}
}
现在，当你调用一个链表的reverse方法时，得到的是另一个链表。这是因为Swift的函数重载机制，它会选择执行最具体的那个函数实现(区别于范型函数)。因此当我们调用链表的reverse方法时，调用的是我们自己的方法实现而不是SequenceType协议提供的默认实现。
有时候我们需要的确实就是数组，这种情况下用SequenceType协议提供的默认实现会更方便，因为用我们自己的实现需要把链表再转成数组，这样就多了一步。这时候，我们可以指定返回值的类型，就可以强制Swift执行其默认的reverse方法了：
let reversedArray: [String] = l.reverse()
如果这个结果要放到函数中做参数使用，我们可以使用as关键字。比如下面这行代码表示检查我们自定义的reverse方法是否和默认的reverse方法结果一致：
l.reverse().elementsEqual(l.reverse as [String])
提示: 做这样的测试需要确保函数重载确实发生了，否则你其实调用了两个一样的方法，测试当然会通过
你可以用is关键字来检查返回结果是否是List类型，但是编译器会告诉你这样做是没有意义的(因为事实上重载是发生了的，所以判断结果总是为true)。为了避免这个警告，你可以这么写：
l.reverse() as Any is List<Int>
双向下标
BidirectionalIndexType协议为下标添加了一个非常关键的方法：predecessor()。这使得我们的链表可以有一个和first属性对应的last属性：
extension CollectionType where Index: BidirectionalIndexType {
var last: Generator.Element? {
guard !isEmpty else { return nil }
return self[endIndex.predecessor()]
}
}
Swift标准库中，String.CharacterView就有双向下标，我们在字符串章节会对和Unicode相关的知识做进一步介绍。字符串集合不能被随机访问，但可以从最后一个字符向前，一个一个地遍历。
String.CharacterView还有一个非常高效的reverse操作，它不会立刻反转集合，而是返回一个懒视图：
extension CollectionType where Index: BidirectionalIndexType {
// 返回一个懒加载的CollectionType，包含了反向排列的self元素
func reverse() -> ReverseCollection<Self>
}
实际上并没有reverse操作发生。ReverseCollection只是持有了原来的结合并且反悔了一个successor和predecessor都相反的下标。我们只要对原来的集合做很少的封装，改变遍历方法就可以做到这一点：
struct ReverseIndex<Base: BidirectionalIndexType>: BidirectionalIndexType {
let idx: Base
func successor() -> ReverseIndex<Base> {
return ReverseIndex(idx: idx.predecessor())
}
func predecessor() -> ReverseIndex<Base> {
return ReverseIndex(idx: idx.successor())
}
}
func ==<T>(lhs: ReverseIndex<T>, rhs: ReverseIndex<T>) -> Bool {
return lhs.idx == rhs.idx
}
struct ReverseCollection<Base: CollectionType where Base.Index: BidirectionalIndexType> :CollectionType {
let base: Base
var startIndex: ReverseIndex<Base.Index> { return ReverseIndex(idx: base.endIndex) }
var endIndex: ReverseIndex<Base.Index> { return ReverseIndex(idx: base.startIndex) }
subscript(idx: ReverseIndex<Base.Index>) -> Base.Generator.Element {
return base[idx.idx.predecessor()]
}
}
在这段代码中，变量值的复制非常重要。在创建ReverseCollection时，我们把原集合“复制”到base变量中。这其实是写实复制，但对于数组(或者其他不可变的持久化数据结构如链表，队列等)来说非常高效。即使原集合的元素被改变，也不会影响到base中拷贝的元素。这意味着ReverseCollection和其他用reverse方法返回的数组一样，具有可观察的行为。
随机下标[5]
#译者注
[1]：书上的解释，还是不太清楚，其实用文字解释有点困难。比如说链表本身是[4,3,2,1]，一个变量刚开始指向的节点是4，这时候它其实包括了[4,3,2,1]这部分。后来执行pop操作之后，变量指向了节点3，这时候它包括了[3,2,1]部分。也就是变量自身改变了，但链表本身没有改变。
[2]：所谓的非破坏性，是指能够多次遍历。之前我们见过某些数据结构，从头到尾遍历一次就不能再遍历了，比如一个普通的生成器。
[3]：对swift不熟的童鞋需要注意，这里强调==运算符是因为swift中对运算符重载的要求比较严。它不能定义在某个类的内部，而是写成全局函数，通过参数类型来确定到底重载哪个类型的的运算符。所以如果把下标和链表都放在枚举中，就只能重载枚举类型的==运算符了。也就是说CollectionType和ForwardIndexType协议所需要的==必然有一个不能满足。
[4]：切片定义中的两个变量是计算属性，不占用空间，因为他们不存储实际的东西。collection变量就是集合，bounds属性是一个子范围，观察一下定义发现它也是一个集合。所以最终切片的大小是原来链表的两倍。
[5]：这一节目前只有代码没有解释，等正式版出来之后再翻译吧
