深入Swift集合类型背后的协议，方法，扩展（一）

转自http://www.jianshu.com/p/b93c07fa8c3d

先说几个问题

• 数组类型(_ArrayType)、集合(Collection)、序列(Sequence)、生成器(Generator)、元素(Element)、下标(Index)，这些类型(协议)各自的作用。
  数组是如何利用上面这些类实现各种方法的。
• map、reduce、filter等方法的作用是什么，他们是怎么实现的。
• 只有数组有上面这些方法么，如果不是，什么样的类型才有这些方法。
• 如果实现一个自定义的集合类型，应该怎么做。

相关类型简介

元素(Element)

对于任何一种集合来说，它本质上是一种数据结构，也就是用来存放数据的。我们在各种代码中见到的Element表示的就是最底层数据的类型别名。因为对于集合这种范型类型来说，它不关心具体存放的数据的类型，所以就用通用的Element来代替，比如我们写这样的代码:

let array: Array<Int> = [1,2,3]

这就相当于告诉数组，Element现在具体变为Int类型了。

生成器(Generator)

对于集合来说，它往往还需要提供遍历的功能。那怎么把它设计为可遍历的呢？不要指望for循环，要知道目前我们什么都没有，没有数组的概念，更没有下标的概念。有一句名言说：“任何编程问题都可以通过增加一个中间层来解决”。于是，我们抽象出一个Generator(生成器)的概念。我们把它声明成一个协议，任何实现这个协议的类都要提供一个next方法，返回集合中的下一个元素：

protocol GeneratorType {
      typealias Element
      mutating func next() -> Element?
}

可以想象的是这样一来，实现了GeneratorType协议的类，就可以隐藏具体元素的信息，通过不断调用next方法就可以获得所有元素了。比如你可以用一个生成器，不断生成斐波那契数列的下一个数字。

总的来说，生成器(Generator)允许我们遍历所有的元素。

序列(Sequence)

生成器不断生成下一个元素，但是已经生成过的元素就无法再获取到了。比如在斐波那契数列中通过3和5得到了8，那么这个生成器永远也不会再生成元素3了，下一个生成的元素是13。也就是说对于生成器来说，已经访问过的元素就无法再次获取到。
然而对于集合来说，它所包含的元素总是客观存在的。为了能够多次遍历集合，我们抽象出了序列(Sequence)的概念。Sequence封装了Generator对象的创建过程：

protocol SequenceType { 
     typealias Generator: GeneratorType 
     func generate() -> Generator
}

序列(Sequence)相比于单纯的Generator，使反复遍历集合中的元素成为可能。这时候，我们已经可以通过for循环而不是Generator来遍历所有元素。