Swift 中的两种数据结构: Array和Dictionary
Array
数组是用于存储元素集合的通用容器,通常用于各种Swift程序。您可以使用数组文字创建数组,数组文字是用方括号括起来的逗号分隔值列表。例如:这是一种泛型类型,因为它可以跨任何元素类型进行抽象。元素类型没有正式要求;它可以是任何东西。在下面的示例中,编译器类型将元素推断为String类型。
// An array of `String` elements
let people = ["Brian", "Stanley", "Ringo"]
Swift使用协议定义数组。这些协议中的每一个都在阵列上提供更多功能。例如,Array是一个Sequence,这意味着您可以至少迭代一次。它也是一个集合,这意味着它可以非破坏性地遍历多次,并且可以使用下标运算符进行访问。 Array也是一个RandomAccessCollection,可以保证效率。
例如,count属性保证是写成O(1)的“廉价”恒定时间操作。这意味着无论您的数组有多大,计算计数总是花费相同的时间。
数组对于元素的排序也很有用。
数组中的元素是显式排序的。以上面的人数组为例,“Brian”出现在“Stanley”之前。
数组中的所有元素都具有相应的从零开始的整数索引。例如,上例中的people数组有三个索引,一个对应于每个元素。
您可以通过编写以下代码来检索数组中元素的值:
people[0] // "Brian"
people[1] // "Stanley"
people[2] // "Ringo"
顺序由数组数据结构定义,不应视为理所当然。一些数据结构,例如Dictionary,具有较弱的顺序概念。
随机访问
随机访问是数据结构可以声明的特性,如果它们可以在恒定的O(1)时间内处理元素检索。 例如,从people数组中获取“Ringo”需要恒定的时间。 同样,这种表现不应该被视为理所当然。 其他数据结构(如链接列表和树)没有恒定的时间访问权限。
阵列性能
18除了作为一个随机访问集合之外,还有其他一些性能领域作为开发人员感兴趣,特别是当数据结构包含的数据需要增长时,数据结构的好坏程度如何? 对于阵列,这取决于两个因素。
插入位置
第一个因素是您选择在数组中插入新元素的位置。 向元素添加元素的最有效方案是将其附加到数组的末尾:
people.append("Charles") print(people)
// prints ["Brian", "Stanley", "Ringo", "Charles"]
使用append方法插入“Charles”会将字符串放在数组的末尾。 这是一个恒定时间操作,是将元素添加到数组中的最有效方法。 但是,您可能需要在特定位置插入元素,例如在数组的中间位置。 在这种情况下,这是O(n)操作。
为了帮助说明原因,请考虑以下类比。 你站在剧院排队。 有人加入阵容。 添加人员到阵容的最简单的地方是什么? 当然结束了!
如果新手试图将自己插入中间位置,他们将不得不说服半个阵容重新腾出空间来。
如果他们非常粗鲁,他们会尝试将自己插入前头。 这是最糟糕的情况,因为阵容中的每个人都需要重新排列为前面的这个新人腾出空间!
这正是数组的工作原理。从数组末尾的任何位置插入新元素将强制元素向后移动以为新元素腾出空间:
people.insert("Andy", at: 0) // ["Andy", "Brian", "Stanley", "Ringo", "Charles"]
确切地说,每个元素必须向后移动一个索引,这需要n步。 因此,它被认为是线性时间或O(n)操作。 如果数组中的元素数量加倍,则此插入操作所需的时间也将增加一倍。
如果在集合前插入元素是程序的常用操作,则可能需要考虑使用不同的数据结构来保存数据。
决定插入速度的第二个因素是阵列的容量。 如果超出了阵列预分配的空间(容量),则必须重新分配存储并复制当前元素。 这意味着任何给定的插入,即使在最后,如果制作副本,也可以完成n步。 但是,标准库采用了一种微妙的技巧来防止追加O(n)时间。 每次存储耗尽并需要复制时,它的容量就会翻倍。 这样做允许数组具有摊销成本,它仍然是恒定时间O(1)。
Dictionary
字典是另一个保存键值对的通用集合。例如,这是一个包含用户姓名及其分数的字典:
var scores:[String:Int] = [“Eric”:9,“Mark”:12,“Wayne”:
字典没有任何订单保证,也不能在20字面插入字典没有任何订单保证,也不能插入特定索引。他们还对Key类型提出了Hashable的要求。幸运的是,几乎所有的标准类型都已经Hashable,在最新版本的Swift中,采用Hashable协议现在已经很简单了。
您可以使用以下语法向字典添加新条目:
scores["Andrew"] = 0
这会在字典中创建一个新的键值对:
[“Eric”:9,“Mark”:12,“Andrew”:0,“Wayne”:1]
“Andrew”键被插入到字典中。字典是无序的,因此您无法保证新条目的放置位置。当Collection协议提供时,可以多次遍历字典的键值。这个顺序虽然未定义,但每次遍历时都会相同,直到集合发生变化(变异)。
缺乏明确的排序劣势伴随着一些赎回特征。与数组不同,字典不需要担心元素的转移。插入字典总是O(1)。查找操作也在O(1)时间内完成,这明显快于数组中特定元素的O(n)查找时间。
总结
Swift中最常见的两种数据结构,并简要介绍了两者之间的一些权衡。 其余部分将介绍具有独特性能特征的其他数据结构,这些特性使其具有一定的优势
21个场景。 令人惊讶的是,使用这两个简单的标准库原语可以有效地构建许多其他数据结构。