实现Swift的Array

发表于 更新于 分类于

当我们从Obj-C转到Swift时，会发现Swift提供的数据结构大量使用值语义，如Array、Dictionary等，今天，我们将实现Array的基本功能，来理解值语义以及写时复制。

值和引用语义

在实现之前，我们来简单讨论一下值语义和引用语义的区别。当我们使用Obj-C及大多数其他面向对象语言开发时，经常会使用对象指针或引用，而这就是常说的引用语义，我们可以赋值一个对象实例的引用给一个变量：

MyClass *a = ...;

接着，可以将该变量赋值给另一个变量：

MyClass *b = a;

此时，a和b将指向同一个对象，如果指向的对象是可变的，当我们修改对象的内容时，两者对其都可见。

值语义相对比较简单，我们使用的如int、struct等都是值语义，声明为值语义的变量，其直接指向真正的值，而不是值的指针。所以当我们进行赋值时，将得到值的拷贝，如：

1
2
3
int a = 42;
int b = a;
b++;

此时，b的值为43，而a依然为42。

在Swift中，class类型仍然是引用语义，struct则为值语义，所以，如果对class类型进行赋值时，将得到一个指向同一个实例的引用，对实例对象内容的修改将对所有的引用可见；使用struct时，则不会，每个变量之间都是独立的。

对于使用过Obj-C开发过的人来说，转到Swift使用其提供的数组和字典时，可能会不习惯，因为Swift中两者已经变成了值语义，如：

1
2
3
var a = [1, 2, 3]
var b = a
b.append(4)

对于大多数语言，如上代码的结果一般都是a和b都指向同一个数组[1, 2, 3, 4]。而在Swift中，a指向[1, 2, 3]，b则指向[1, 2, 3, 4]。

实现值语义

如果对象包含固定数量的数据，那么实现就比较简单：我们直接将数据放到struct中即可。比如想要一个2D Point类型且满足值语义，可以创建一个struct包含x``y的值：

1
2
3
4
struct Point {
    var x: Int
    var y: Int
}

固定数量实现起来比较简单，但是我们使用的Array，它的个数不定，我们不可能直接把所有数组元素放到struct中，所以，我们需要创建一个指针，用来指向数组元素的内存：

1
2
3
struct Array<T> {
    var ptr: UnsafeMutablePointer<T>
}

不过，有这还不够，我们还需要针对struct的赋值和销毁做一些操作；当struct被赋值时，需要对新的struct的ptr元素赋值，这时候需要将原struct的ptr指向的所有元素拷贝到一组新的内存块中，并将新的struct的ptr指向新的第一个元素的地址。当struct销毁时，其指针指向的元素占用的内存同样需要被释放。而这两个需求，Swift的struct并没有提供自定义方法可以实现。

由于class有deinit方法，所以析构功能可以通过class来实现，指针指向的内容可以在deinit中进行处理，但是class又不是值语义的，不过我们依然可以解决，既外封装struct，使用struct作为外部接口进行数组的使用，如下：

1
2
3
4
5
6
7
8
9
10
11
12
class ArrayImpl<T> {
    var ptr: UnsafeMutablePointer<T>

    deinit {
        ptr.destroy(...)
        ptr.dealloc(...)
    }
}

struct Array<T> {
    var impl: ArrayImpl<T>
}

接下来，在Array<T>中添加一个接口，其内部则调用ArrayImpl的实现。

如上，尽管使用了struct，但是我们还并没有实现值语义，如果拷贝一个struct，新的struct依然指向相同的ArrayImpl，而我们又没法自定义struct的赋值操作，所以也没法拷贝。不过，我们可以从另一个角度去解决这个问题，我们可以思考一下，真正需要在什么时候进行拷贝的操作呢，答案就是做修改操作时，俗称的COW，既只有当进行修改操作时，才进行真正的拷贝。

比如，实现append方法来对ArrayImpl的拷贝添加一个元素（假设ArrayImpl已经实现了copy方法）：

1
2
3
4
mutating func append(value: T) {
    impl = impl.copy()
    impl.append(value)
}

这样，就实现了Array的值语义，尽管a``b赋值后依然指向相同的数据，但是只要修改其中的一个，就会进行拷贝操作，以保持数据的独立性。

如上的append方法，虽然实现了功能，但是效率太差，如：

1
2
3
4
var a: [Int] = []
for i in 0..<1000 {
    a.append(i)
}

在每一次进行迭代时，指向的数据都会进行拷贝的操作，然后立即销毁之前的存储内存，那么我们如何处理这种情况呢？

isKnownUniquelyReferenced

该API返回一个布尔值，表明某个对象是否只有一个单独的强引用指向它。

有了这个API，我们就可以修改一下append方法，只在必要的时候进行拷贝：

1
2
3
4
5
6
7
mutating func append(_ value: T) {
    // isKnownUniquelyReferenced并不是线程安全的哦
    if !isKnownUniquelyReferenced(&impl) {
        impl = impl.copy()
    }
    impl.append(obj: value)
}

ArrayImpl

接下来，我们将开始实现ArrayImpl。数组包含3个属性：数据指针、数组中元素的个数，以及当前分配的内存可存放的总个数。数据指针和数组元素个数这两个值是必须的，不过我们应当预先分配一定量的空闲内存区域，以避免过多的reallocation操作。

1
2
3
4
class ArrayImpl<T> {
    var space: Int
    var count: Int
    var ptr: UnsafeMutablePointer<T>！

接下来，实现init方法，init方法获取两个参数，count、ptr，拷贝指针的内容到新的对象。

1
2
3
4
5
6
7
8
9
10
11
12
init(count: Int = 0, ptr: UnsafeMutablePointer<T>? = nil) {
    self.count = count
    self.space = count
    
    self.ptr = UnsafeMutablePointer<T>.allocate(capacity: count)
    
    guard let ptr = ptr else {
        return
    }
    
    self.ptr.initialize(from: ptr, count: count)
}

接下来，实现append方法，首先检查是否需要重新分配内存，如果没有多余的空间，则需要一块新的内存：

1
2
func append(obj: T) {
    if space == count {

首次分配内存时，分配容量初始为space的2倍，且最小容量设置为16.

1
2
let newSpace = max(space * 2, 16)
let newPtr = UnsafeMutablePointer<T>.allocate(capacity: newSpace)

接着将数据从原位置拷贝到新的指针所在的内存。

1
newPtr.moveInitialize(from: ptr, count: count)

拷贝完成之后，就可以释放原来的内存了：

1
2
3
ptr.deallocate(capacity: count)
ptr = newPtr
space = newSpace

现在，已经有足够的空间来存放新的元素，我们将其拷贝到当前所有元素中最后一个元素后面内存区域并将count自增1：

1
2
(ptr + count).initialize(to: obj)
count += 1

remove操作也很简单，因为不需要重新分配内存。首先，清理待移除元素所在的内存：

1
2
func remove(at index: Int) {
    (ptr + index).deinitialize()

moveInitialize方法可以使所有剩余的元素移动到指定的内存区域：

1
(ptr + index).moveInitialize(from: ptr + index + 1, count: count - index - 1)

然后将count减一来表明已经移除一个元素:

1
count -= 1

当然，我们也需要实现copy方法，以实现必要的拷贝操作（真正执行拷贝操作是在init方法中）：

1
2
3
func copy() -> ArrayImpl<T> {
    return ArrayImpl<T>(count: count, ptr: ptr)
}

最后，别忘了释放内存，我们可以在deinit中进行内存的释放操作：

1
2
3
4
deinit {
    ptr.deinitialize(count: count)
    ptr.deallocate(capacity: space)
}

这样，ArrayImpl基本方法已经完成，接下来就是实现Array的struct的接口方法，其主要是调用ArrayImpl的实现。

Array

接下来，实现Array的一些接口方法，由于比较简单，直接上代码，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
private mutating func ensureUnique() {
    if !isKnownUniquelyReferenced(&impl) {
        impl = impl.copy()
    }
}
    
mutating func append(_ value: T) {
    ensureUnique()
    impl.append(obj: value)
}
    
mutating func remove(at index: Int) {
    ensureUnique()
    impl.remove(at: index)
}

最后，我们还要加上两个功能，下标访问以及for...in迭代，下标可以通过实现subscript(index: Int)方法，for...in迭代可以通过实现Collection协议的方法，具体如下：

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
27
28
29
30
31
32
33
34
35
36
37
38
    var count: Int {
    return impl.count
}
    
subscript(index: Int) -> T {
    get {
        return impl.ptr[index]
    }
    mutating set {
        ensureUnique()
        impl.ptr[index] = newValue
    }
}
    
var description: String {
    var str = ""
    for value in self {
        if !str.isEmpty {
            str += ", "
        }
        str += String(describing: value)
    }
    return "(\(impl.ptr): " + str + ")"
}
    
typealias Index = Int
    
var startIndex: Index {
    return 0
}
    
var endIndex: Index {
    return count
}
    
func index(after i: Int) -> Int {
    return i + 1
}

源代码及测试代码

所有实现已上传Github：https://gist.github.com/zhongwuzw/2b194c9fb2e4aaaca04cedb79bf207f1

参考

https://www.mikeash.com/pyblog/friday-qa-2015-04-17-lets-build-swiftarray.html