前言

有需要的同学可以订阅专栏：Swift数据结构和算法专题
代码地址：Swift数据结构和算法代码

正文

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

数组

数组是一种通用的通用容器，用于存储有序的元素集合，它在各种 Swift 程序中普遍使用。我们可以使用数组字面量创建数组，数组字面量是由方括号括起来的以逗号分隔的值列表。例如：

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

Swift 使用协议定义数组。这些协议中的每一个都在阵列上分层了更多功能。例如，一个数组是一个序列，这意味着我们可以至少迭代一次。它也是一个集合，这意味着它可以被多次非破坏性地遍历，并且可以使用下标运算符进行访问。数组也是一个RandomAccessCollection，它保证了效率。

Swift Array 被称为泛型集合，因为它可以处理任何类型。事实上，大部分 Swift 标准库都是用通用代码构建的。与任何数据结构一样，我们应该注意某些值得注意的特征。首先 其中包括秩序的概念。数组中的元素是明确排序的。以上述人员数组为例，“Brian”排在“Stanley”之前。数组中的所有元素都有一个对应的从零开始的整数索引。例如，上面示例中的 people 数组具有三个索引，一个对应于每个元素。我们可以通过编写以下代码来检索数组中元素的值：

people[0] // "Brian" 
people[1] // "Stanley" 
people[2] // "Ringo" 
复制代码

顺序由数组数据定义结构，不应被视为理所当然。某些数据结构，例如 Dictionary，具有较弱的顺序概念。

随机访问

如果数据结构可以在恒定时间内处理元素检索，则随机访问是一种特征。例如，从 people 数组中获取“Ringo”需要恒定的时间。同样，这种表现不应被视为理所当然。其他数据结构，如链表和树，没有固定时间访问。

数组性能

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

插入位置

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

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

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

为了帮助说明为什么会出现这种情况，请考虑以下类比。你正在排队等剧院。新来的人加入了阵容。将人员添加到阵容中最容易的地方是什么？最后，当然！

如果新人试图将自己插入队伍的中间，他将不得不说服一半的阵容重新洗牌以腾出空间。

如果他非常粗鲁，他会试图把自己插在队伍的最前面。这是最坏的情况，因为阵容中的每个人都需要重新洗牌，为前面的新人腾出空间！

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

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

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

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

决定插入速度的第二个因素是阵列的容量。在底层，Swift 数组为其元素分配了预定数量的空间。如果我们尝试将新元素添加到已达到最大容量的数组中，则该数组必须自行重组，以便为更多元素腾出更多空间。这是通过复制所有当前元素来完成的 在内存中一个新的更大的容器中的数组。然而，这是有代价的；必须访问和复制数组的每个元素。这意味着如果进行了复制，任何插入，即使是在最后，也可能需要 n 步才能完成。但是，标准库采用了一种策略，可以最大限度地减少这种复制需要发生的时间。每次它用完存储空间并需要复制时，它的容量就会增加一倍。

字典

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

var score: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]
复制代码

字典没有任何顺序保证，也不能在特定索引处插入。他们还对 Key 类型提出了要求，即它是 Hashable。幸运的是，几乎所有的标准类型都已经是 Hashable 并且在 Swift 的最新版本中，采用 Hashable 协议现在是微不足道的。我们可以使用以下语法向字典中添加新条目：

scores["Andrew"] = 0
复制代码

这将在字典中创建一个新的键值对：

["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1] 
复制代码

"Andrew" 键被插入到字典的某个位置。字典是无序的，所以你不能保证新条目会放在哪里。

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

缺乏明确的排序劣势带来了一些可取之处。

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

集合

集合是一个包含唯一值的容器。想象它是一个包 允许我们将项目插入其中，但拒绝已插入的项目：

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 已经有了它，因此它是重复的 
  } 
  bag.insert(value) 
} 
复制代码

使用集合的次数几乎不会与与数组和字典一样多，但它仍然很常见，可以作为重要的数据结构保存在我们的工具带中。不过，有一个警告。与字典类似，集合中的值没有顺序的概念。当我们使用集合来聚合数据时，请记住这一点。

Swift Collections 包

Swift 标准库只实现了三个最重要的数据结构：Array、Set 和 Dictionary。对于其他数据结构，我们可以查看 Swift Collections 包。这个包允许社区在它们成为官方标准库的一部分之前开发和测试新的集合类型。

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

Deque

之前，我们了解到在 Array 的前面插入元素会导致所有元素的混洗。乍一看，Deque（读作“deck”）数据结构似乎与 Array 具有相同的用途。我们可以将其用作按顺序保存值的通用容器。就像数组一样，我们可以调用 append 将元素添加到 Deque，或调用 remote(at:) 以删除某个索引处的特定元素。事实上，接口几乎是相同的，因为 Array 和 Deque 都实现了相同的收集协议。 那么为什么要在数组上使用双端队列呢？除非我们考虑时间复杂度，否则很难看到权衡取舍。 Deque 是一个双端队列。因此，Deque 针对集合前后的修改进行了优化。与 Array 不同，从 Deque 的前面插入或删除元素是一种快速的 O(1) 操作。太好了 - 那么有什么缺点呢？在编程中，一切都是关于权衡的。对于 Deque，它是关于改进前端的修改，以牺牲其他所有方面的性能略有下降。作为程序员，我们的工作是权衡选项并选择最适合工作的工具。如果我们的应用程序需要频繁修改集合的前面，则 Deque 的性能将比 Array 好得多。这可以转化为更好的用户体验——一种可以在快速和缓慢的应用程序之间产生差异的体验。 Swift Collections 包包含额外的数据结构，例如 OrderedDictionary 和 OrderedSet。正如前缀所暗示的， 这些是 Dictionary和 Set 的变体，它们保留了元素的顺序。与 Deque 一样，这些数据结构也有一些性能折衷。我们可以在 swift.org/blog/swift-… 了解更多关于它们的信息。

关键点

• 每个数据结构都有优点和缺点。了解它们是编写高性能软件的关键。

• 用于Array 的insert(at:) 等函数具有性能特征，在随意使用时会削弱性能。如果我们发现自己需要经常在数组开头附近使用带有索引的 insert(at:)，我们可能需要考虑使用不同的数据结构，例如链表。

• 字典放弃了保持其元素顺序的能力，以实现快速插入和搜索。

• Set 保证值集合的唯一性。Set针对速度进行了优化，放弃了保留元素顺序的能力。

• Swift Collections 包包含在某些场景中表现更好的专用数据结构。