3.Swift标准库¶

Swift standard library是包含Swift语言的核心组件的框架。在里面，你会发现各种工具和类型，以帮助建立你的Swift应用程序。在你开始构建自己的自定义数据结构之前，了解Swift标准库已经提供的主要数据结构很重要。

在本章中，你将专注于标准库开箱即提供的三种主要数据结构：Array、Dictionary和Set。

`Array`¶

数组是一个通用的通用容器，用于存储有序的元素集合，它常用于各种Swift程序中。你可以通过使用array literal来创建一个数组，一个用方括号包围的逗号分隔的数值列表。比如说：

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

Swift使用协议来定义数组。这些协议中的每一个都为数组添加了更多的功能。例如，Array是一个Sequence，这意味着你可以至少遍历它一次。它也是一个Collection，这意味着它可以被多次遍历，非破坏性地访问，并使用下标操作符。数组也是一个RandomAccessCollection，它对效率做出了保证。

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

与任何数据结构一样，有一些值得注意的特征，你应该注意到。其中第一个是order的概念。

`Order`¶

数组中的元素是明确ordered。以上面的people数组为例，"Brian"排在"Stanley"之前。

一个数组中的所有元素都有一个相应的基于零的整数索引. 例如，上面例子中的people数组有三个索引，每个元素对应一个索引。你可以通过写以下内容来检索数组中某个元素的值:

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

顺序是由数组数据结构定义的，不应该想当然。一些数据结构，如Dictionary，有一个较弱的顺序概念。

随机访问¶

随机访问是数据结构可以宣称的特性，如果它们可以在恒定的时间内处理元素的检索。例如，从people数组中获取"Ringo"需要持续的时间。同样，这种性能不应该被认为是理所当然的。其他数据结构，如链接列表和树，并没有恒定的时间访问。

`Array`性能¶

除了是一个随机访问的集合之外，其他的性能领域也是你作为一个开发者所关心的，特别是，当数据结构所包含的数据量需要增长时，它的表现是好是坏？对于数组来说，这取决于两个因素。

插入位置¶

第一个因素是你选择在数组内插入新的元素。向数组添加元素的最有效方案是将其追加到数组的末端：

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

使用append方法插入"Charles"将把字符串放在数组的最后。这是一个恒定时间的操作，意味着无论数组变得多大，执行这个操作的时间都是一样的。然而，有时你可能需要在一个特定的位置插入一个元素，例如在数组的最中间。

为了帮助说明为什么会这样，请考虑下面这个比喻。你在排队看戏。有人来加入这个队伍。什么地方最容易把人加入队伍？当然是在最后面!

如果新来的人试图把自己插到队伍的中间，他将不得不说服一半的队伍向后移动以腾出空间。

如果他非常无礼，他就会试图把自己插到队伍的前面去。这是最糟糕的情况，因为队列中的每个人都需要向后洗牌，以便为前面的这个新人腾出空间！这正是阵列的工作原理。

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

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

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

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

决定插入速度的第二个因素是数组的capacity。在引擎盖下面，Swift数组为其元素分配了一个预定的空间量。如果你试图向一个已经达到最大容量的数组添加新的元素，数组必须重组自己，为更多的元素腾出更多的空间。这是通过将数组的所有当前元素复制到内存中一个新的更大的容器中来实现的。然而，这样做是有代价的；数组的每个元素都必须被访问和复制。

这意味着任何插入，即使是在最后，如果进行复制，可能需要n步来完成。然而，标准库采用了一种策略，最大限度地减少这种复制需要发生的次数。每次当它的存储空间用完并需要复制时，它就会将容量增加一倍。

`Dictionary`¶

字典是另一个通用的集合，用来保存key-value对。例如，这里有一个包含用户姓名和分数的字典：

var scores: [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协议所规定的那样，可以多次遍历一个字典的键值。这个顺序虽然没有被定义，但每次被遍历的时候都是一样的，直到集合被改变（突变）。

缺乏显式排序的缺点也有一些值得称道的地方。

与数组不同，dictionary不需要担心元素的移动。插入一个字典总是需要一个恒定的时间。

查找操作也需要一个恒定的时间，这比在数组中寻找一个特定的元素要快得多，后者需要从数组的开头走到插入点。

`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)
}

你不会像数组和字典那样经常使用集合，但它仍然很常见，足以成为你的工具箱中的一个重要数据结构。不过，有一点需要注意。与字典类似，集合中的值没有顺序的概念。当你使用一个集合来聚合数据时，请记住这一点。

`Swift`集合包¶

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

在下一节，你将深入了解这个包中的一个数据结构。

`Deque`¶

早些时候，你了解到在Array的前面插入元素会导致所有元素的洗牌。

乍一看，Deque（读作 "甲板"）数据结构似乎与Array的作用相同。你可以把它作为一个通用的容器，按顺序保存数值。就像Array一样，你可以调用append来向Deque添加元素，或者调用remove(at:)来删除某个索引上的特定元素。

事实上，接口几乎是相同的，因为Array和Deque都实现了相同的集合协议。那么，为什么使用Deque而不是Array？在你考虑到时间复杂性之前，很难看到权衡。

Deque是一个双端队列。因此，Deque优化了从集合的前部和后部进行的修改。与Array不同，从Deque的前面插入或移除一个元素是一个便宜的O(1)操作。

很好，那么缺点是什么呢？在编程中，所有的东西都是关于权衡的。对于Deque来说，它是为了改善前面的修改，而代价是其他方面的性能略有下降。作为一个程序员，你的工作是权衡各种选择，为工作挑选最好的工具。如果你的应用程序需要经常修改一个集合的前部，Deque将比Array的性能好得多。这可能会转化为更好的用户体验--这可能是一个快速和迟缓的应用程序之间的区别。

Swift集合包包含了额外的数据结构，如OrderedDictionary和OrderedSet。正如前缀所示，这些是Dictionary和Set的变体，保留了元素的顺序。像Deque一样，这些数据结构有一些性能上的权衡。你可以在https://swift.org/blog/swift-collections/了解更多关于它们的信息。

关键点¶

每种数据结构都有其优点和缺点。了解它们是编写高性能软件的关键。
诸如insert(at:)这样的函数对于Array来说具有性能上的特点，如果胡乱使用的话，会削弱性能。如果你发现自己需要经常使用insert(at:)，而且索引在数组的开头附近，你可能要考虑使用不同的数据结构，如链接列表。
Dictionary为了快速插入和搜索而放弃了保持其元素顺序的能力。
Set保证了值的集合的唯一性。Set为速度而优化，放弃了保留元素顺序的能力。
Swift集合包包含专门的数据结构，在某些情况下表现更好。

3.Swift标准库¶

Array¶

Order¶

随机访问¶

Array性能¶

插入位置¶

Dictionary¶

Set¶

Swift集合包¶

Deque¶