序言

发现了一个美好的地方:swift-algorithm-club,有一群猿媛基于Swift的基本数据结构Array、Dictionary、Set等扩展出了程序世界其他数据结构,另外用Swift讨论实现了些常用算法。

看了几篇说明文档及源码,或翔实或简洁,深受启发。打算记录下来,意译文档,或抒发个人感悟,另将没有适配到Swift3.0的代码做好适配。这一系列是数据结构,之后可就算法再来一系列。

数据结构:Array2D

数据结构:Array2D - 敏捷大拇指 - 数据结构:Array2D





Array2D 二维数组

在C或Objective-C里,我们可以这样:

[C] 纯文本查看 复制代码
int cookies[9][7];


定义一个 9x7 cookies 格子。这将创建一个包含63个int的二维数组. 要取出第3行第6列的元素,这样就行:

[C] 纯文本查看 复制代码
myCookie = cookies[3][6];


不爽的是,在Swift里不能那样写。在Swift的世界创建一个多维数组要类似这样做:

[Swift] 纯文本查看 复制代码
var cookies = [[Int]]()
for _ in 1...9 {
    var row = [Int]()
    for _ in 1...7 {
        row.append(0)
    }
    cookies.append(row)
}


取元素倒也简单:

[Swift] 纯文本查看 复制代码
let myCookie = cookies[3][6]


上面的创建代码也可以缩为一行:

[Swift] 纯文本查看 复制代码
var cookies = [[Int]](repeating: [Int](repeating: 0, count: 7), count: 9)


老实说,太丑了。可以来个工具函数美化美化:

[Swift] 纯文本查看 复制代码
func dim<T>(_ count: Int, _ value: T) -> [T] {
    return [T](repeating: value, count: count)
}


现在可以这样创建我们的二维数组了:

[Swift] 纯文本查看 复制代码
var cookies = dim(9, dim(7, 0))


Swift 能推断出数组的元素是 Int 类型,因为我们是以0这个数字初始化数组的。如果元素是String呢:

[Swift] 纯文本查看 复制代码
var cookies = dim(9, dim(7, "yum"))


再用 dim() 定义多维数组试试:

[Swift] 纯文本查看 复制代码
var threeDimensions = dim(2, dim(3, dim(4, 0)))


这种形式的多维数组(即嵌套的一维数组),缺陷是什么? 就是看起来不明朗,定位元素费事。

所以,我们还是来定义自己的二维数组。看看,简洁又性感:

[Swift] 纯文本查看 复制代码
public struct Array2D<T> {
    public let columns: Int
    public let rows: Int
    private var array: [T]
    public init(columns: Int, rows: Int, initialValue: T) {
        self.columns = columns
        self.rows = rows
        array = Array(repeating: initialValue, count: rows*columns)
    }
    public subscript(column: Int, row: Int) -> T {
        get {
            return array[row*columns + column]
        }
        set {
            array[row*columns + column] = newValue
        }
    }
}


Array2D 支持泛型,可以放任意类型的元素,不只是数字。

现在创建我们的cookies数组:

[Swift] 纯文本查看 复制代码
var cookies = Array2D(columns: 9, rows: 7, initialValue: 0)


因为写了 subscript 函数,取元素也方便:

[Swift] 纯文本查看 复制代码
let myCookie = cookies[column, row]


改变某个元素:

[Swift] 纯文本查看 复制代码
cookies[column, row] = newCookie


Array2D 内部用了一个一维的数组来存储数据,实际元素的索引是 row x columns + column。 但作为 Array2D 的使用者,不用担心这些,你只需要以为确实是个rows x columns的二维数组, 放心用就好。 这就是对原始类型包装的好处。




原作者: Matthijs Hollemans