隆重推出 Swift Collections

Karoy Lorentey Karoy Lorentey

我很高兴地宣布 Swift Collections，这是一个新的开源包，专注于扩展可用的 Swift 数据结构集。与之前的 Swift Algorithms 和 Swift Numerics 包一样，我们发布 Swift Collections 是为了帮助孵化 Swift 标准库的新功能。

Swift 标准库目前实现了三个最基本且通用的数据结构：Array、Set 和 Dictionary。这些是各种用例的正确工具，并且特别适合用作常用类型。但有时，为了高效地解决问题或维护不变性，Swift 程序员将受益于更大的数据结构库。

我们期望 Collections 包能够让您以更少的精力编写更快、更可靠的程序。

简要导览

Collections 包的初始版本包含三个最常被请求的数据结构的实现：双端队列（简称 “deque”）、有序集合和有序字典。

Deque

Deque（发音为 “deck”）的工作方式与 Array 非常相似：它是一个有序的、随机访问的、可变的、可范围替换的集合，具有整数索引。

与 Array 相比，Deque 的主要优势在于它支持在两端进行高效的插入和删除操作。

这使得双端队列成为我们需要先进先出队列时的绝佳选择。为了强调这一点，Deque 提供了方便的操作来在两端插入和弹出元素

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"]


Deque Prepend Benchmark

对于 Deque 而言，前置添加元素是常数时间操作，但对于 Array 而言，则是线性时间操作。

注意：所有图表均在 对数-对数 刻度上绘制每个元素的平均处理时间。越低越好。基准测试是在我的 2017 iMac Pro 上运行的。

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

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"]


Deque Lookup Benchmark

与 Array 类似，对于 Deque 而言，以任意偏移量访问元素是常数时间操作。

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

OrderedSet

OrderedSet 是 Array 和 Set 的强大混合体。

我们可以使用任何符合 Hashable 协议的元素类型来创建有序集合

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


OrderedSet Append Benchmark

追加元素（包括确保其唯一性）对于 OrderedSet 而言是常数时间操作。

注意：所有基准测试都配置了 std::unordered_set 和 std::unordered_map 以使用与 Swift 相同的哈希函数，以便进行同类比较。

与 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 Lookup Benchmark

对于 OrderedSet 而言，成员资格测试是常数时间操作，但对于 Array 而言，则是线性时间操作。

OrderedSet 使用标准数组值进行元素存储，可以使用最小的开销提取该值。如果我们想将有序集合的内容传递给仅接受 Array 的函数（或泛型于 RangeReplaceableCollection 或 MutableCollection），这是一个很好的选择

func buildHouses(_ houses: Array<String>)

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

对于需要 SetAlgebra 一致性的情况，OrderedSet 还提供了符合 SetAlgebra 的元素的有效无序视图

func blowHousesDown<S: SetAlgebra>(_ houses: S) { ... }

blowHousesDown(buildingMaterials) // error: `OrderedSet<String>` does not conform to `SetAlgebra`
blowHousesDown(buildingMaterials.unordered) // OK

OrderedSet 还实现了一些 RangeReplaceableCollection 和 MutableCollection 的功能，以及大部分 SetAlgebra 的功能。（成员唯一性和区分顺序的相等性阻止了完全一致性。）

这是通过维护成员数组（用于高效的随机访问遍历）和索引到该数组的哈希表（用于高效的成员资格测试）来实现的。由于存储在哈希表中的索引通常可以编码为比标准 Int 更少的位，因此 OrderedSet 通常会比普通的旧 Set 使用更少的内存！

OrderedDictionary

OrderedDictionary 是 Dictionary 的有用替代品，当元素的顺序很重要，或者我们需要能够高效地访问集合中各个位置的元素时。

我们可以使用任何符合 Hashable 协议的键类型来创建有序字典

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


OrderedDictionary Append Benchmark

将新的键值对插入 OrderedDictionary 会以常数时间将其追加到末尾。

OrderedDictionary 提供了许多与 Dictionary 相同的操作。例如，我们可以使用熟悉的基于键的下标高效地查找和添加值

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


OrderedDictionary Lookup Benchmark

对于 OrderedDictionary 而言，查找键的值是常数时间操作。

如果使用下标 setter 添加新条目，则会将其追加到字典的末尾。因此，默认情况下，字典会按照元素最初插入的顺序包含元素

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

OrderedDictionary 使用整数索引，第一个元素始终从 0 开始。为了避免基于键和基于索引的下标之间的歧义，OrderedDictionary 不直接符合 Collection。相反，它提供了对其键值对的随机访问视图

responses[0] // nil (key-based subscript)
responses.elements[0] // (200, "OK") (index-based subscript)

与标准 Dictionary 类似，OrderedDictionary 也提供了轻量级的 keys 和 values 视图。相同的索引在字典提供的所有内容视图中都是可移植的

if let i = responses.index(forKey: 404) {
  responses.keys[i] // 404
  responses.values[i] // "Not Found"
  responses.remove(at: i + 1) // (500, "Internal Server Error")
}
// `responses` is now [200: "OK", 403: "Forbidden", 404: "Not Found"]

OrderedDictionary 实现了一些 MutableCollection 和 RangeReplaceableCollection 的功能，尽管它对成员唯一性的要求使其无法实现这两个协议的完全一致性。

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

与 Swift 标准库的关系

我们的目标是让标准库包含一组丰富且实用的通用数据结构。

与 Swift Numerics 和 Swift Algorithms 等软件包类似，Collections 包的一个重要目标是充当新数据结构实现的（相对）低摩擦的试验场，然后再通过常规 Swift 演进过程准备好作为官方库添加项提出。

我们使用软件包形式的这些构造所获得的经验将为最终的审查讨论提供信息。它还将为我们提供机会在设计问题被铭刻在石头上之前纠正它们。

Collections 包在某种程度上是对向 Swift 贡献新数据结构所涉及的挑战的认可。由于标准库是 ABI 稳定的，因此必须花费大量时间来思考数据结构的哪些部分将是 @frozen，哪些不是，以及哪些方法应该是 @inlinable 并接触那些冻结的内部结构。

因此，Collections 包不仅仅是一组数据结构。它也是一个供想要更多了解 ABI 设计的黑暗艺术的贡献者聚集的地方，以及一个复杂的工具包，可帮助满足数据结构所需的正确性和效率的高标准。

但是，仅仅因为一个添加项可能是包含在 Collections 包中的良好候选者，它也不需要在那里开始其生命周期。这并不是对 Swift 演进过程 的更改。尽管新数据结构的门槛很高，但始终如一地考虑充分支持的提案。

贡献标准

该软件包的当前重点是孵化一组实用的、生产级的数据结构 —— 类似于您在 C++ 容器 库或 Java 集合 框架中可能找到的那些。

要成为包含在 Collections 包中的良好候选者，数据结构应显着提高实际 Swift 代码的性能或正确性，并且其实施策略应考虑到现代计算机体系结构和 Swift 的性能特征。

Collections 包并非旨在成为数据结构的综合分类。许多经典数据结构不值得包含，因为与标准库中的现有类型相比，它们提供的价值不足，或者存在具有更优实施策略的替代方案。（例如，我们不太可能想要实现链表或红黑树 —— 相同的利基市场可能可以通过高扇出搜索树（例如内存 B 树）更好地填补。）

由于该软件包的重点是提供生产级数据结构实现，因此包含的门槛很高。评估贡献的一些基线标准

开始研究新数据结构的最好方法是在 论坛上 讨论它。这样，我们可以确定数据结构是否适合该软件包，讨论实施策略，并计划分配容量以提供帮助。

参与进来！

非常欢迎您的经验、反馈和贡献！

有问题吗？

请随时在 Swift 论坛上的相关主题中提出关于这篇文章的问题。