publicprotocolForwardIndexType:_Incrementable{
}
publicprotocol_Incrementable:Equatable{
publicfuncsuccessor()->Self
对于下标类型来说,它们必须实现successor()方法,同时也得是Equatable的,否则怎么知道某个位置上的元素已经被访问过了呢。
数组简介
有了以上基本知识做铺垫,接下来就可以研究一下Swift中数组是怎么实现的了。
我们可能早已体会到Swift数组的强大,它的下标脚本不仅可以读取元素,还可以直接修改元素。它可以通过字面量初始化,还可以调用appendContentsOf方法从别的数组中添加元素。甚至于我们可能都没有仔细考虑过为什么可以用for number in array这样的语法。
首先,我们需要明确一个概念:数组丰富强大的特性绝不是由Array这一个类型可以提供的。实际上,这主要是协议的功劳。用OC写iOS时,协议几乎就是代理的代名词(可能是我对OC不甚精通,目光短浅),但毋庸置疑的是在Swift中,协议的功能被空前的强化。数组通过实现协议、以及协议的嵌套、拓展功能,具有了很多特性。数组的背后交织着错综复杂的协议、方法和拓展。
下面是数组的定义:
publicstructArray:CollectionType,MutableCollectionType,_DestructorSafeContainer{
startIndex:Int{get}
endIndex:Int{get}
publicsubscript(index:Int)->Element
publicsubscript(subRange:Range)->ArraySlice}
数组是一个结构体,它实现了三个协议,有两个变量和两个下标脚本。除此以外,数组还有大量的拓展。
数组的大量功能在拓展中完成,由于拓展很多,我就不列出完整代码,只是做一个整理。数组一共拓展了四类协议:
ArrayLiteralConvertible: 这个协议是为了支持这样的语法的:let a: Array= [1,3]。实现协议很简单,只要提供一个自定义方法即可:
publicinit(arrayLiteralelements:Element...)
_Reflectable:这个协议用于处理反射相关的内容,这里不做详解
CustomStringConvertible和CustomDebugStringConvertible:这两个是方便我们调试的协议,与数组自身的功能无关。
_ArrayType:这是数组最关键的部分。在实现这个协议之前,数组还只是一个普通的集合类型,它仅仅是拥有下标,而且可以重复遍历所有元素而已。而通过实现_ArrayType协议,它可以在指定位置(下标)添加或移除一个或多个元素,它还有了自己的count属性。
这一点也许有些颠覆我们此前的认识。一个集合类型,是不能添加或删除元素的。数组通过实现了_ArrayType协议提供了这样的功能。但这也很容易理解,因为集合的本质还是在于元素的收集,而非考虑如何改变这些元素。
_ArrayType协议还给了我们一个非常重要的启示。比如说我想实现自己的数据结构——栈,那么就应该实现对应的_StackType协议。这种协议要充分考虑数据结构自身的特点,从而提供对应的方法。比如我们不可能向栈的某个特定位置添加若干个元素(只能向栈顶添加一个)。所以_StackType协议中不会定义append、appendContentsOf这样的方法,而是应该定义pop和push方法。
SequenceType
接下来的任务是搞清楚ColectionType的原理了。不过在此之前,我们先来看看SequenceType的一些细节,毕竟CollectionType协议是继承了SequenceType协议的。
在有了Generator之后,我们已经可以在while循环中用Generator的next方法遍历所有元素了。之前也说过,SequenceType使对元素的多次遍历成为可能。
注意,仅仅是成为可能而已。如果遍历的细节由Generator控制,那么多次遍历是没有问题的。在极个别情况下,但如果遍历的细节依赖于SequenceType自身的某个属性,而且这个属性会发生变化,那么就不能多次遍历所有元素了。
SequenceType协议的基本部分非常简单,只有一个generator()方法,封装了Generator的创建过程。
一旦有了遍历元素的概念,SequenceType立刻就有了非常多的拓展。这里简单列举几个比较关键的:
-
forEach:这个拓展使得我们可以用for循环遍历集合了:for item in sequence
-
dropFirst(n: Int)和dropLast(n: Int):这两个方法返回的是除了前(后)n个元素之外的Sequence。需要提一下的是,由于此时的SequenceType还没有下标的概念,这两个方法的实现是非常复杂的。
-
prefix(maxLength: Int)和suffix(maxLength: Int):和刚刚两个方法类似,这两个方法返回的是前(后)maxLength个元素,实现也不简单。
-
elementsEqual、contains、minElement、maxElement等,这些都是针对元素的判断和选择。
-
map、flatMap、filter、reduce这些方法是针对所有元素的变换。
SequenceType的拓展实在是太多了,但总结来看不外乎两点:
-
由于可以多次遍历元素了,我们可以对元素进行各种比较、处理、筛选等等操作。这些派生出来的方法和函数极大的强化了SequenceType的功能。
-
由于SequenceType自身的局限性,不能保证一定可以多次遍历所有元素,还没有下标和元素位置的概念,因此某些方法的实现还不够高效,
带着这样的遗憾,我们来看看最关键的CollectionType是如何实现的。
细谈CollectionType
之前我们说过CollectionType协议是在SequenceType的基础上实现了Indexable协议。由于协议的继承关系,任何实现了CollectionType协议的类,必须实现Indexable协议规定的两个参数:startIndex和endIndex,以及一个下标脚本:subscript (position: Self.Index) -> Self._Element { get }。即使这三个要求在CollectionType中没有直接标出来。
回顾一下数组定义的前三行,正是满足了这三个要求。再看CollectionType,它不仅重载了Indexable的一个下标脚本,还额外提供了一个下标脚本用来访问某一段元素,这个下标脚本返回的类型是切片(Slice)。这也正是数组定义的第四行,实现的内容。
细心的读者可能已经注意到,CollectionType还定义了很多属性和方法,比如:prefixUpTo、suffixFrom、isEmpty、first等等。但数组没有实现其中的任何一个。
事实上,这不仅不是数组设计的失败之处,而正是Swift协议的强大之处。Swift可以通过协议拓展,为计算属性和方法提供默认实现。因此,数组可以不用写任何代码就具备这些方法。更赞的是,任何实现了CollectionType协议的类型也因此具有了这些方法。
观察一下CollectionType的其它拓展,大部分都是重写了SequenceType中的实现。之前已经提到过SequenceType没有下标的概念,而类似于dropFirst这样的方法,利用下标的概念是非常容易实现的。
除了对一些已有方法的重写之外,CollectionType还新增了一些基于下标的方法。比如indexOf()等。
套用官方文档中对CollectionType的总结就是:
A multi-pass sequence with addressable positions
也就是说CollectionType是可以多次遍历,元素可定位的SequenceType
总结
Element、Generator、SequenceType、CollectionType、Array由下至上构造了数组背后的层次结构。他们的关系如下图所示:
Swift数组层次结构
如果我们希望定义一个自己的数据结构,比如链表。首先可以明确它要实现CollectionType协议。链表应该是和Array同层次的类型。然后我们需要定义一个_ListType的协议,这个协议对应数组的_ArrayList协议,根据数据结构自身的特性定义一些方法。
如果觉得CollectionType甚至是SequenceType不满足我们的需求,我们还可以自己实现对应的类型。难度不会很大,因为它们虽然负责,但大多数方法已有默认实现,我们只要重写一些关键的逻辑即可。
最后需要说明的是,Swift中对集合的实现实在是太复杂了,如果每个都详细分析,怕是可以写一本书。希望读完这篇文章后,读者可以举一反三,自行阅读源码解决相关问题。
(编辑:李大同)
【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!
|