Swift 团队开源 Collections，提供更多高效数据结构

发表于 3年以前 | 总阅读数：338 次

Swift 团队于上周开源新软件包 Swift Collections，以扩展 Swift 的数据结构集合。这个新的开源软件包与 Swift Algorithms 和 Swift Numerics 一样，目的在于扩展 Swift 标准库的新功能。Swift 标准库目前实现了三个最基本的通用数据结构：Array、Set 和 Dictionary，这几个数据结构可以满足基本的需求，但有时候为了更有效地解决问题或保持不变性，开发人员可能需要更多的数据结构。而 Swift Collections 软件包就提供了不少新的数据结构，以让开发人员可以以更少的精力编写更快、更可靠的程序。

我们这里简要介绍一下 Swift Collections 里新的数据结构。

Collections 包的初始版本包含三个最常用的数据结构的实现：双端队列，有序集合和有序字典。

Deque

Deque 的工作方式与 Array 十分相似：它是一个有序、可随机访问、可变、范围可替换且具有整数索引的集合。Deque 优于 Array 的主要好处是它支持两端的有效插入和删除。如果需要 FIFO 队列时，双端队列都是一个不错的选择。

var colors: Deque = ["red", "yellow", "blue"]

colors.prepend("green")
colors.append("orange")
// `colors` is now ["green", "red", "yellow", "blue", "orange"]

colors.popFirst() // "green"
colors.popLast() // "orange"
// `colors` is back to ["red", "yellow", "blue"]

也可以使用任何熟悉的 MutableCollection 和 RangeReplaceableCollection 方法来访问和修改集合的元素。索引的工作方式与数组中完全相同 – 第一个元素始终位于索引零处：

colors[1] // "yellow"
colors[1] = "peach"
colors.insert(contentsOf: ["violet", "pink"], at: 1)
// `colors` is now ["red", "violet", "pink", "peach", "blue"]
colors.remove(at: 2) // "pink"
// `colors` is now ["red", "violet", "peach", "blue"]
colors.sort()
// `colors` is now ["blue", "peach", "red", "violet"]

为了支持在前面的有效插入，双端队列需要放弃将其元素保持在连续的缓冲区中。对于不需要在前端插入/删除元素的情况，这往往会使它们的工作速度比数组慢一些，因此用双端队列盲目替换所有数组可能不是一个好主意。

OrderedSet

OrderedSet 是数组和集合的强大混合体。我们可以使用任何符合 Hashable 协议的元素类型创建有序集合：

let buildingMaterials: OrderedSet = ["straw", "sticks", "bricks"]

像 Array 一样，有序集合按用户指定的顺序维护其元素，并支持对其成员的有效随机访问遍历：

for i in 0 ..< buildingMaterials.count {
  print("Little piggie #\(i) built a house of \(buildingMaterials[i])")
}
// Little piggie #0 built a house of straw
// Little piggie #1 built a house of sticks
// Little piggie #2 built a house of bricks

像 Set 一样，有序集合可确保每个元素仅出现一次并提供有效的成员测试：

buildingMaterials.append("straw") // (inserted: false, index: 0)
buildingMaterials.contains("glass") // false
buildingMaterials.append("glass") // (inserted: true, index: 3)
// `buildingMaterials` is now ["straw", "sticks", "bricks", "glass"]

OrderedSet 用标准数组来存储元素，可以以最小的开销提取元素。如果我们要将有序集合的内容传递给仅接受数组的函数（或在 RangeReplaceableCollection 或 MutableCollection 上通用）的函数，则可以用以下方式：

func buildHouses(_ houses: Array<String>)

buildHouses(buildingMaterials) // error
buildHouses(buildingMaterials.elements) // OK

OrderedDictionary

当元素的顺序很重要或我们需要能够有效访问集合中各个位置的元素时， OrderedDictionary 是 Dictionary 的有用替代方法。我们可以使用符合 Hashable 协议的任何键类型创建有序字典：

let responses: OrderedDictionary = [
  200: "OK",
  403: "Forbidden",
  404: "Not Found",
]

OrderedDictionary 提供了许多与 Dictionary 相同的操作。例如，我们可以使用下标有效地查找并添加值：

responses[200] // "OK"
responses[500] = "Internal Server Error"

如果使用下标设置器添加了新条目，则它将添加到字典的末尾。因此，默认情况下，字典按其最初插入的顺序包含其元素：

for (code, phrase) in responses {
  print("\(code) (\(phrase))")
}
// 200 (OK)
// 403 (Forbidden)
// 404 (Not Found)
// 500 (Internal Server Error)

有序字典由包含键的 OrderedSet 以及包含其关联值的常规 Array 组成。可以以最小的开销提取其中的每一个元素，这是与期望某种类型的函数进行互操作的有效选择。

Swift Collections 与标准库的关系

与 Swift Numerics 和 Swift Algorithms 一样，Collections 初期目标是提供这些新数据结构的一个试验场，最终目标则是要将这些数据结构合并到标准库中。

由于目前标准库是 ABI 稳定的，因此需要花大量时间考量新的数据结构哪些归类到 @frozen 而哪些不是，哪些方法应该是 @inlinable 并可触及内部结构。另外 Collections 不仅仅是一组数据结构，如果开发人员希望进一步了解 ABI 设计的黑科技及完善的工具包，这也是个不错的学习资源。

同时，Swift 团队也鼓励开发人员积极参与到其中。由于这个软件包的重点是提供生产级数据结构的实现，因此标准也会很高，主要是关注可靠性、运行时性能和内存开销。