数据结构与算法三：Swift Standard Library

Swift 标准库（Swift Standard Library）

Swift 标准库是包含 Swift 语言核心组件的框架。在标准库里，我们可以使用各种各样的工具和类型来构建我们的 Swift 应用程序。在开始构建自定义数据结构之前，了解 Swift 标准库已经提供的主要数据结构非常必要。

在本章中，我们将关注标准库开箱即用的三个主要数据结构：数组、字典和集合。

Array

数组是一种通用的容器，用于存储有序的元素集合。我们可以使用数组字面量（array literal）创建数组，数组字面量是由方括号括起来的以逗号分隔的值列表。 例如：

let people = ["Brian", "Stanley", "Ringo"]

Swift 使用协议定义数组。一个数组是一个序列，我们可以至少迭代一次；同时，它也是一个集合，可以被多次非破坏性地遍历，并且可以使用下标运算符（subscript operator）进行访问；此外，数组也是一个 RandomAccessCollection，它保证了效率。

Swift Array 被称为泛型集合，因为它可以处理任何类型。事实上，大部分 Swift 标准库都是用通用代码构建的。

与任何数据结构一样，我们应该注意某些值得注意的特征，其中第一个是顺序（Order）的概念。

Order

数组中的元素是明确排序的。以上述人员数组为例，"Brian"排在"Stanley"之前。

数组中的所有元素都有一个对应的从零开始的整数索引。例如，上面示例中的 people 数组具有三个索引，我们可以通过编写以下内容来检索数组中元素的值：

people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"

Order 由数组数据结构定义，不是所有数据结构都有，某些数据结构，例如 Dictionary，具有较弱的顺序概念。

随机访问（Random-access）

如果数据结构可以在恒定时间内处理元素检索，则随机访问是一种不错的策略。例如，从 people 数组中获取"Ringo"需要恒定的时间。只是不是所有的数据结构都是这样的，其他数据结构，如链表和树，就没有固定时间访问。

数组表现（Array performance）

除了作为随机访问集合之外，作为开发人员，我们还应对其它性能领域感兴趣，特别是当数据结构包含的数据量大量增长时，它的表现如何？ 对于数组，这取决于两个因素。

插入位置（Insertion location）

第一个因素是选择在数组哪里插入新元素。将元素添加到数组的最有效方案是将其附加到数组的末尾：

people.append("Charles")
print(people) // prints ["Brian", "Stanley", "Ringo", "Charles"]

使用 append 方法插入"Charles"，会将字符串放在数组的末尾。这个操作时间是恒定的，这意味着无论数组有多大，执行此操作所需的时间都保持不变。但是，有时可能需要在特定位置插入元素，例如在数组的最中间。

这有点像，你正在排队购物，新来的人加入了队伍，他主动排到队伍的最后是最容易的。如果新来的人要插入队伍的中间，他将不得不说服队伍后面一半的人都后退以腾出空间。

如果他非常粗鲁，试图把自己插在队伍的最前面，这是最坏的情况，因为队伍中的每个人都需要重新移动位置。

这正是数组的工作原理。从数组末尾以外的任何地方插入新元素将强制元素向后洗牌，为新元素腾出空间：

people.insert("Andy", at: 0)
// ["Andy", "Brian", "Stanley", "Ringo", "Charles"]

准确地说，每个元素都必须向后移动一个索引，这需要 n 步。如果数组中的元素数量加倍，则此插入操作所需的时间也将加倍。

如果在集合前面插入元素是程序的常见操作，我们可能需要考虑使用其它数据结构来保存数据。

决定插入速度的第二个因素是 array 的容量。在底层，Swift 数组为其元素分配了预定数量的空间。如果尝试将新元素添加到已达到最大容量的数组中，则该数组必须自行重组，以便为更多元素腾出更多空间。这是通过将数组的所有当前元素复制到内存中一个新的更大的容器中来完成的。然而，这个代价是很大的，因为必须访问和复制数组的每个元素。

这意味着如果进行了复制，任何插入，即使是插入在最后，也可能需要 n 步才能完成。

所幸，标准库采用了一种策略，可以最大限度地减少这种复制需要发生的时间。即每次它用完存储空间并需要复制时，它的容量就会增加一倍。

字典（Dictionary）

字典是另一个保存键值对的通用集合。例如，这是一个包含用户名和分数的字典：

var scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]

字典没有任何顺序保证，也不能在特定索引处插入，而且还对 Key 类型提出了要求，即它必须遵守 Hashable协议。幸运的是，几乎所有的标准类型都已经遵守 Hashable 了。

我们可以使用以下语法向字典中添加新条目：

scores["Andrew"] = 0

在 dictionary 创建键值对：

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1]

"Andrew"键被插入到字典的某处。字典是无序的，所以不能保证新插入的数据会存储在哪里。

正如 Collection 协议所提供的，可以多次遍历字典的键值。虽然没有定义顺序，但每次遍历时数据都是相同的，直到集合发生变化（突变）。

缺乏明确的排序的劣势也带来了一些好处。

与数组不同，字典不需要担心元素的移动。插入字典耗时总是恒定的时间。查找操作也是固定的时间，这比在数组中查找特定元素需要从数组的开头遍历到插入点要快得多。

集合（Set）

集合是保存唯一值的容器。想象它是一个袋子，允许我们将物品插入其中，但拒绝插入已经存在的物品：

var bag: Set<String> = ["Candy", "Juice", "Gummy"]
bag.insert("Candy")
print(bag) // prints ["Candy", "Juice", "Gummy"]

由于集合强制唯一性，它适用于各种有趣的应用程序，例如在值集合中查找重复元素：

let values: [String] = [...]
var bag: Set<String> = []
for value in values {
  if bag.contains(value) {
    // bag already has it, therefore it is a duplicate
  }
  bag.insert(value)
}

你不会像数组和字典那样频繁使用集合，但它仍然很常见，它可以作为一个重要的数据结构保存在我们的工具带（toolbelt）中。不过，需要注意的是，与字典类似，集合中的值没有顺序的概念。当我们使用集合来聚合数据时，请注意这一点。

Swift Collections 包（The Swift Collections package）

Swift 标准库只实现了三个最重要的数据结构：Array、Set 和 Dictionary。对于其它数据结构，我们可以查看 Swift Collections 包。

在下一节中，我们将更深入地了解此包中的一个数据结构。

Deque

之前，我们了解到在 Array 的前面插入元素会导致所有元素的随机改动。

乍一看，Deque 数据结构似乎与 Array 具有相同的用途。我们可以将其用作按顺序保存值的通用容器。像数组一样，可以调用 append 将元素添加到 Deque，或 remove(at:) 以删除某个索引处的特定元素。

事实上， Array 和 Deque 接口几乎是相同的，因为它们都实现了相同的 collection 协议。那么为什么要在数组上使用双端队列呢？

这是要考虑时间复杂度。

Deque 是一个双端队列。因此，Deque 针对集合前后的修改进行了优化。与 Array 不同，从 Deque 的前面插入或删除元素是一种廉价的 O(1) 操作。

那么有什么缺点呢？

在编程中，一切都是关于权衡的。

作为程序员，我们的工作是权衡选项并选择最适合工作的工具。如果我们的应用程序需要频繁修改集合的前面，则 Deque 的性能将比 Array 好得多。这可以转化为更好的用户体验。

Swift Collections 包包含额外的数据结构，例如 OrderedDictionary 和 OrderedSet。正如前缀所暗示的，这些是保留元素顺序的“字典”和“集合”的变体。像 Deque 一样，这些数据结构有一些性能折衷。我们可以在 https://swift.org/blog/swift-collections/ 了解有关它们的更多信息。

本章关键点（Key points）

• 每个数据结构都有优点和缺点。了解它们是编写高性能软件的关键。
• 用于 Array 的 insert(at:) 等函数具有性能特征，在随意使用时会削弱性能。如果我们发现自己需要经常在数组开头附近使用带有索引的 insert(at:)，则可能需要考虑使用不同的数据结构，例如链表。
• 字典放弃了保持其元素顺序以实现快速插入和搜索的能力。
• Set 保证值集合中的唯一性。Set 针对速度进行了优化，放弃了保留元素顺序的能力。
• Swift Collections 包包含专门的数据结构，在某些情况下表现更好。

译于：
2022.08.27 16:51
上海 二联家园