集合类型模块分四篇笔记来学习：
- 第一篇：
- 数组和可变性
- 数组的变形
- 第二篇：
- 字典和集合
- 集合协议
- 第三篇：
- 集合
- 第四篇：
- 索引
本篇开始学习最后一篇，Go！
索引
到现在为止，我们都使用整数作为我们集合的索引。Array 如此，我们的 Queue 类型亦是如此。但是并不是所有的索引都必须满足随机存取特性，也不是所有的随机存取索引都必须是整数。
在 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)
}
}
此时先创建一个基础的列表baselist
let baselist = List<Int>.End.cons(1).cons(2).cons(3)
然后创建两个以baselist为基础的列表
let listA = baselist.cons(4)
let listB = baselist.cons(5)
基于栈构建一个列表
可以把这样的链表看做一个栈，构建链表相当于进栈，获取下一个值相当于出栈。接下来构建一个通用的栈
/// 一个进栈和出栈都是常数时间操作的后进先出 (LIFO) 栈
protocol StackType {
/// 栈中存储的元素的类型
associatedtype Element
/// 将 `x` 入栈到 `self` 作为栈顶元素
///- 复杂度：O(1).
“mutating func push(x: Element)
/// 从 `self` 移除栈顶元素，并返回它
/// 如果 `self` 是空，返回 `nil`
///
/// - 复杂度：O(1)
mutating func pop() -> Element?
}
使List遵循StackType：
extension List: StackType {
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>.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
让 List 遵守 SequenceType
因为列表的变量可以进行列举，也就是说，你能够使用它们来让 List 遵守 SequenceType 协议：
extension List: SequenceType {
func generate() -> AnyGenerator<Element> {
// 声明一个变量来追踪列表当前的列举状态
var current = self
return AnyGenerator {
// next() 将会出栈元素，如果列表为空，则返回 `nil`
current.pop()
}
}
}
为了使用起来简单一些，我们也可以让它遵守 ArrayLiteralConvertible 协议：
extension List: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
self = elements.reverse().reduce(.End) { $0.cons($1) }
}
}
现在可以对List采用以下操作了：
let l: List = ["1", "2", "3"]
for x in l {
print("\(x) ", terminator: "")
}
l.joinWithSeparator(",") // "1,2,3"
l.contains("2") // true
l.flatMap { Int($0) } // [1, 2, 3]
l.elementsEqual(["1", "2", "3"]) // true”
让 List 遵守 CollectionType
接下来，我们要让 List 实现 CollectionType。这将可以把像是 first 这样的属性带给我们的数据结构，有了它，我们就能够查看列表的第一个元素，而不用将它出栈了。更重要的是，通过实现 CollectionType，我们可以保证多次遍历序列不会出现问题。
在我们实际实现它之前，先来做些准备工作，将节点从列表和索引类型中分离出来。
// List 集合类型的私有实现细节
private enum ListNode<Element> {
case End
indirect case Node(Element, next: ListNode<Element>)
func cons(x: Element) -> ListNode<Element> {
// 每次 cons 调用将把 tag 加一
return .Node(x, next: self)
}
}
索引类型封装了 ListNode。索引可以通过访问节点的 next 来创建一个新的索引，由此返回它的之后的一个索引值、但是这只满足
了 ForwardIndexType 的一般的要求。我们还需要知道一些额外信息来为索引实现 == 运算符。我们前面提到过，节点是值，值是不具有同一性的。那我们怎么说明两个变量是指向同一个节点的呢？为了解决这个问题，我们使用一个递增的数字来作为每个索引的标记值 (tag)。我们之后会看到，在索引中存储这些标记可以让操作变得非常高效。列表的工作原理决定了如果相同列表中的两个索引拥有同样的标记值，那么它们就是同一个索引。
public struct ListIndex<Element> {
private let node: ListNode<Element>
private let tag: Int
}
ForwardIndexType 要求类型有一个 successor 方法，它应该返回下一个索引：
extension ListIndex: ForwardIndexType {
public func successor() -> ListIndex<Element> {
switch node {
case let .Node(_, next: next):
return ListIndex(node: next, tag: tag.predecessor())
case .End:
fatalError("cannot increment endIndex")
}
}
}
ListIndex 也必须实现 Equatable，这样你才能判断两个索引是否相等。
public func == <T>(lhs: ListIndex<T>, rhs: ListIndex<T>) -> Bool {
return lhs.tag == rhs.tag
}
现在 ListIndex 遵守 ForwardIndexType 了，它能够被 List 用来实现 CollectionType:
public struct List<Element>: CollectionType {
// Index 的类型可以被推断出来，不过写出来可以让代码更清晰一些
public typealias Index = ListIndex<Element>
public var startIndex: Index
public var endIndex: Index
public subscript(idx: Index) -> Element {
switch idx.node {
case .End: fatalError("Subscript out of range")
case let .Node(x, _): return x
}
}
}