Swift标准库是包含Swift语言的核心组件的框架。在里面，你会发现各种工具和类型，以帮助建立你的Swift应用程序。在你开始构建自己的自定义数据结构之前，了解Swift标准库已经提供的主要数据结构很重要。
在本章中，你将专注于标准库开箱即提供的三种主要数据结构。数组、字典和集合。
数组是一个通用的通用容器，用于存储有序的元素集合，它在各种 Swift 程序中都很常用。你可以通过使用一个数组字面来创建一个数组，一个用方括号包围的逗号分隔的数值列表。比如说
let people = ["Brian", "Stanley", "Ringo"] 。
Swift使用协议来定义数组。这些协议中的每一个都在数组上叠加了更多的功能。例如，数组是一个序列，这意味着你可以至少在它身上迭代一次。它也是一个集合，这意味着它可以被多次遍历，非破坏性地访问，并使用下标操作符。数组也是一个RandomAccessCollection，它对效率做出了保证。
Swift数组被称为通用集合，因为它可以与任何类型的集合一起工作。事实上，大部分的Swift标准库都是用通用代码构建的。
与任何数据结构一样，有一些值得注意的特征，你应该注意。其中第一个是顺序的概念。
数组中的元素是明确排序的。以上面的人物数组为例，"Brian "排在 "Stanley "之前。
一个数组中的所有元素都有一个相应的基于零的整数索引。例如，上面例子中的people数组有三个索引，每个元素对应一个索引。你可以通过编写以下内容来检索数组中某个元素的值。
people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"
顺序是由数组数据结构定义的，不应该想当然。有些数据结构，如Dictionary，有一个较弱的顺序概念。
随机访问是数据结构的一个特征，如果它们能在恒定的时间内处理元素的检索，就可以声称是随机访问。例如，从人物数组中获取 "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 scores: [String: Int] = ["Eric": 9, "Mark": 12, "Wayne": 1]
字典没有任何顺序的保证，也不能在一个特定的索引处插入。他们还对Key类型提出了一个要求，即它是可散列的。幸运的是，几乎所有的标准类型都已经是Hashable了，而且在最近的Swift版本中，采用Hashable协议已经是小事一桩了。你可以用下面的语法向字典添加一个新条目。
scores["Andrew"] = 0
这在字典中创建了一个新的键值对。
["Eric": 9, "Mark": 12, "Andrew": 0, "Wayne": 1]
"Andrew "这个键被插入到字典的某个地方。字典是无序的，所以你不能保证新条目会被放在哪里。
正如 Collection 协议所规定的那样，有可能多次遍历一个字典的键值。这个顺序虽然没有被定义，但每次被遍历的时候都是一样的，直到集合被改变（突变）。
缺乏显式排序的缺点也有一些值得称道的特点。
与数组不同，dictionary 不需要担心元素的移动。向字典中插入总是需要一个恒定的时间。
查找操作也需要一个恒定的时间，这比在数组中寻找一个特定的元素要快得多，后者需要从数组的开头走到插入点。
集合是一个容纳唯一值的容器。想象一下，它是一个袋子，允许你向其中插入项目，但拒绝已经被插入的项目。
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集合包。这个包允许新的集合类型在成为官方标准库的一部分之前由社区开发和测试。
在下一节，你将深入了解这个包中的一个数据结构。
早些时候，你了解到在数组的前面插入元素会导致所有元素的洗牌。
乍一看，Deque（读作 "甲板"）数据结构似乎与数组的目的相同。你可以把它作为一个通用的容器，按顺序保存数值。就像数组一样，你可以调用append来向Deque添加元素，或者调用remote(at:)来删除某个索引上的特定元素。
事实上，接口几乎是相同的，因为Array和Deque都实现了相同的集合协议。那么，为什么使用Deque而不是数组呢？在你考虑到时间复杂性之前，很难看到其中的权衡。
Deque是一个双端队列。因此，Deque对来自集合前部和后部的修改进行了优化。与Array不同，从Deque的前面插入或删除一个元素是一个便宜的O(1)操作。
很好，那么缺点是什么呢？在编程中，所有的东西都是关于权衡的。对于Deque来说，它是以改善前面的修改为代价，在其他方面的性能略有下降。作为一个程序员，你的工作是权衡各种选择，为工作挑选最好的工具。如果你的应用程序需要经常修改一个集合的前部，Deque的性能会比Array好得多。这可能会转化为更好的用户体验--这可能会使一个敏捷和迟缓的应用程序之间产生差异。
Swift集合包包含了额外的数据结构，如OrderedDictionary和OrderedSet。正如其前缀所示，这些是Dictionary和Set的变体，保留了元素的顺序。和Deque一样，这些数据结构有一些性能上的折衷。你可以在 https://swift.org/blog/swift-collections/ 上了解更多关于它们的信息。
每种数据结构都有其优点和缺点。了解它们是编写高性能软件的关键。
诸如Array的insert(at:)等函数具有性能特点，如果胡乱使用，会使性能下降。如果你发现自己需要频繁地使用insert(at:)，而且索引在数组的开头附近，你可能要考虑一个不同的数据结构，如链接列表。
Dictionary为了快速插入和搜索，放弃了保持其元素顺序的能力。
Set保证了值的集合的唯一性。Set针对速度进行了优化，放弃了保留元素顺序的能力。
Swift集合包包含专门的数据结构，在某些情况下表现更好。
| 上一章 | 目录 | 下一章 |
|---|