《Advanced Swift》笔记3:如何自己实现一个Swift数组

本文中,我们将会探索Swift原生Array数组的实现方式,并且自定义实现一个数组类型,能够字面量来创建数组,通过下标来获取元素。

通过查看文档我们发现,Swift的数组是一个结构体类型,它遵守了CollectionTypeMutableCollectionType_DstructorSafeContainer协议,其中最重要的就是CollectionType协议,数组的一些主要功能都是通过这个协议实现的。
CollectionType协议又遵守IndexableSequenceType这两个协议。而在这两个协议中,SequenceType协议是数组、字典等集合类型最重要的协议,在文档中解释了SequenceType是一个可以通过forin循环迭代的类型,实现了这个协议,就可以forin循环了。

A type that can be iterated with a forin loop.

SequenceType是建立在GeneratorType基础上的,sequence需要GeneratorType来告诉它如何生成元素。

GeneratorType

GeneratorType协议有两部分组成:

  1. 它需要有一个Element关联类型,这也是它产生的值的类型。
  2. 它需要有一个next方法。这个方法返回Element的可选对象。通过这个方法就可以一直获取下一个元素,直到返回nil,就意味着已经获取到了所有元素。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/// Encapsulates iteration state and interface for iteration over a
/// sequence.
///
/// - Note: While it is safe to copy a generator, advancing one
/// copy may invalidate the others.
///
/// Any code that uses multiple generators (or `for`...`in` loops)
/// over a single sequence should have static knowledge that the
/// specific sequence is multi-pass, either because its concrete
/// type is known or because it is constrained to `CollectionType`.
/// Also, the generators must be obtained by distinct calls to the
/// sequence's `generate()` method, rather than by copying.
public protocol GeneratorType {
/// The type of element generated by `self`.
associatedtype Element
/// Advance to the next element and return it, or `nil` if no next
/// element exists.
///
/// - Requires: `next()` has not been applied to a copy of `self`
/// since the copy was made, and no preceding call to `self.next()`
/// has returned `nil`. Specific implementations of this protocol
/// are encouraged to respond to violations of this requirement by
/// calling `preconditionFailure("...")`.
@warn_unused_result
public mutating func next() -> Self.Element?
}

我把自己实现的数组命名为MYArray,generator为MYArrayGenerator,为了简单,这里通过字典来存储数据,并约定字典的key为从0开始的连续数字。就可以这样来实现GeneratorType:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/// 需保准dic的key是从0开始的连续数字
struct MYArrayGenerator<T>: GeneratorType {
private let dic: [Int: T]
private var index = 0

init(dic: [Int: T]) {
self.dic = dic
}

mutating func next() -> T? {
let element = dic[index]
index += 1
return element
}
}

这里通过next方法的返回值,隐式地为Element赋值。显式地赋值可以这样写typealias Element = T。要使用这个生成器就非常简单了:

1
2
3
4
5
6
7
8
9
10
let dic = [0: "XiaoHong", 1: "XiaoMing"]

var generator = MYArrayGenerator(dic: dic)

while let elment = generator.next() {
print(elment)
}
// 打印的结果:
// XiaoHong
// XiaoMing

SequenceType

有了generator,接下来就可以实现SequenceType协议了。SequenceType协议也是主要有两部分:

  1. 需要有一个Generator关联类型,它要遵守GeneratorType
  2. 要实现一个generate方法,返回一个Generator。
    同样的,我们可以通过制定generate方法的方法类型来隐式地设置Generator:
1
2
3
4
5
6
7
struct MYArray<T>: SequenceType {
private let dic: [Int: T]

func generate() -> MYArrayGenerator<T> {
return MYArrayGenerator(dic: dic)
}
}

这样我们就可以创建一个MYArray实例,并通过for循环来迭代:

1
2
3
4
5
6
7
8
let dic = [0: "XiaoHong", 1: "XiaoMing", 2: "XiaoWang", 3: "XiaoHuang", 4: "XiaoLi"]
let array = MYArray(dic: dic)

for value in array {
print(value)
}

let names = array.map { $0 }

当然,目前这个实现还存在很大的隐患,因为传入的字典的key是不可知的,虽然我们限定了必须是Int类型,但无法保证它一定是从0开始,并且是连续,因此我们可以通过修改初始化方法来改进:

1
2
3
4
init(elements: T...) {
dic = [Int: T]()
elements.forEach { dic[dic.count] = $0 }
}

然后我们就可以通过传入多参数来创建实例了:

1
let array = MYArray(elements: "XiaoHong", "XiaoMing", "XiaoWang", "XiaoHuang", "XiaoLi")

再进一步,通过实现ArrayLiteralConvertible协议,我们可以像系统的Array数组一样,通过字面量来创建实例:

1
2
3
4
5
6
7
8
extension MYArray: ArrayLiteralConvertible {
init(arrayLiteral elements: T...) {
dic = [Int: T]()
elements.forEach { dic[dic.count] = $0 }
}
}

let array = ["XiaoHong", "XiaoMing", "XiaoWang", "XiaoHuang", "XiaoLi"]

最后还有一个数组的重要特性,就是通过下标来取值,这个特性我们可以通过实现subscript方法来实现:

1
2
3
4
5
6
7
8
extension MYArray {
subscript(idx: Int) -> Element {
precondition(idx < dic.count, "Index out of bounds")
return dic[idx]!
}
}

print(array[3]) // XiaoHuang

至此,一个自定义的数组就基本实现了,我们可以通过字面量来创建一个数组,可以通过下标来取值,可以通过for循环来遍历数组,可以使用map、forEach等高阶函数。

小结

要实现一个数组的功能,主要是通过实现SequenceType协议。SequenceType协议有一个Generator实现GeneratorType协议,并通过Generator的next方法来取值,这样就可以通过连续取值,来实现for循环遍历了。同时通过实现ArrayLiteralConvertible协议和subscript,就可以通过字面量来创建数组,并通过下标来取值。

CollectionType

上面我们为了弄清楚SequenceType的实现原理,通过实现SequenceTypeGeneratorType来实现数组,但实际上Swift系统的Array类型是通过实现CollectionType来获得这些特性的,而CollectionType协议又遵守IndexableSequenceType这两个协议。并扩展了两个关联类型GeneratorSubSequence,以及9个方法,但这两个关联类型都是默认值,而且9个方法也都在协议扩展中有默认实现。
因此,我们只需要为Indexable协议中要求的 startIndexendIndex 提供实现,并且实现一个通过下标索引来获取对应索引的元素的方法。只要我们实现了这三个需求,我们就能让一个类型遵守 CollectionType 了。因此这个自定义的数组可以这样实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct MYArray<Element>: CollectionType {

private var dic: [Int: Element]

init(elements: Element...) {
dic = [Int: Element]()
elements.forEach { dic[dic.count] = $0 }
}

var startIndex: Int { return 0 }
var endIndex: Int { return dic.count }
subscript(idx: Int) -> Element {
precondition(idx < endIndex, "Index out of bounds")
return dic[idx]!
}
}

extension MYArray: ArrayLiteralConvertible {
init(arrayLiteral elements: Element...) {
dic = [Int: Element]()
elements.forEach { dic[dic.count] = $0 }
}
}

注意:在Swift 3 中,SequenceTypeGeneratorTypeArrayLiteralConvertible都已改名。

坚持原创技术分享,您的支持将鼓励我继续创作!