决定使用哪个数据结构来表示给定的值集合通常比看起来要复杂。 由于每种数据结构都是针对特定数量的用例进行优化的，因此为每组数据找到合适的匹配通常会对代码的效率产生很大的影响。
Swift标准库提供了三种主要的数据结构——数组、字典和集合——每一种都有不同的优化集和优缺点。 本周，让我们看看其中的一些特征，以及我们有时可能需要如何在标准库之外寻找适合我们需要的数据结构。
The linearity of arrays
Array是Swift中最常用的数据结构之一，这是有充分理由的。它保持其元素的序列，很容易以可预测的方式进行迭代，并且它可以存储任何类型的值——从结构到类实例，再到其他集合。
例如，这里我们使用一个数组来存储图形的集合，这些图形被放置在绘图应用程序的画布上。然后，当要求将我们的画布渲染成图像时，我们简单地遍历我们的数组，以便使用DrawingContext绘制每个元素——像这样:
struct Canvas {
var shapes: [Shape]
func render() -> Image {
let context = DrawingContext()
shapes.forEach(context.draw)
return context.makeImage()
}
}
在线性绘制所有形状时，就像我们上面所做的，使用数组是一个完美的选择。 数组不仅以非常有效的方式存储它们的元素，它们还具有保证的迭代顺序，这为我们提供了一个可预测的绘制顺序，而不需要做任何额外的工作。
然而，就像所有其他数据结构一样，数组也有缺点。在我们的例子中，当我们想要从画布上移除形状时，我们就会遇到这样的缺点。由于数组元素是通过索引存储的，所以在删除给定形状之前，我们总是需要查找它与哪个索引相关联:
extension Canvas {
mutating func remove(_ shape: Shape) {
guard let index = shapes.firstIndex(of: shape) else {
return
}
shapes.remove(at: index)
}
}
乍一看，上面的代码似乎没有什么问题，但它很可能成为任何包含大量形状的画布的性能瓶颈-因为firstIndex在时间复杂度上是线性的(O(n))。
当我们使用画布类型时，我们可以绕过这个限制——例如，总是通过索引来引用形状，而不是通过值或ID - 这样做会使我们的代码更加复杂和脆弱，因为我们总是需要确保我们的索引不会在画布发生变化时变得陈旧。
The speed of sets
相反，让我们看看是否可以通过改变底层数据结构来优化Canvas本身。看看上面的问题，我们最初的想法之一可能是使用集合而不是数组。就像我们在“The power of sets in Swift”中看到的那样，集合比数组最大的优点之一是插入和删除操作都可以在常数(O(1))时间内执行， 因为成员是通过散列值而不是索引来存储的。
将画布更新为使用set来代替，它看起来像这样:
struct Canvas {
var shapes: Set<Shape>
func render() -> Image {
let context = DrawingContext()
shapes.forEach(context.draw)
return context.makeImage()
}
mutating func remove(_ shape: Shape) {
shapes.remove(shape)
}
}
同样，上面的代码可能看起来是正确的，甚至编译起来也没有问题。然而，在我们解决了移除问题的同时，我们也失去了稳定的拉拔顺序-因为与数组不同，集合不能保证迭代的顺序-在这种情况下，这是一个交易的障碍，因为我们开始在一个看似随机的顺序绘制用户的形状。
Indexing indexes
我们继续尝试。接下来，让我们看看是否可以通过引入一个词典来优化Canvas，该词典允许我们根据形状的ID查找其索引。我们首先将形状数组设为私有，以便能够控制如何插入元素——使用一个新的add方法-每次添加一个新形状时，我们也会把它的索引添加到字典中:
struct Canvas {
private var shapes = [Shape]()
private var indexes = [Shape.ID : Int]()
func render() -> Image {
let context = DrawingContext()
shapes.forEach(context.draw)
return context.makeImage()
}
mutating func add(_ shape: Shape) {
let index = shapes.count
indexes[shape.id] = index
shapes.append(shape)
}
}
因为我们现在总是知道给定形状存储在哪个索引上，所以我们可以在固定的时间内快速执行删除操作，就像我们使用set时一样:
extension Canvas {
mutating func remove(_ shape: Shape) {
guard let index = indexes[shape.id] else {
return
}
shapes.remove(at: index)
indexes[shape.id] = nil
}
}
然而，我们的新画布实现有一个相当严重的bug。每次我们删除一个形状时，实际上是在使所有比刚才删除的形状更高的索引无效——因为每个元素都将向数组的开始移动一步。 虽然我们可以通过在每次移除后调整这些索引来解决这个问题，但这将再次将我们置于O(n)区域中，这是我们一开始就试图避免的。
不过，我们的最后一个实现确实有优点。通常，在这种情况下，使用两种数据结构的组合是一个很好的主意 -因为我们经常能够使用一种数据结构的优点来弥补另一种数据结构的缺点，反之亦然。
因此，让我们再次尝试另一种组合，但这一次，让我们先回顾一下我们的实际需求是什么:
我们需要插入和删除都具有恒定的时间复杂度，并且应该可以在不知道其底层索引的情况下删除形状。
我们需要一个保证的迭代顺序，才能保持一个稳定的绘制顺序。
看看上面的需求，当我们需要一个稳定的迭代顺序时，我们实际上并不需要索引——索引会使链表最适合我们的用例。
链表由节点组成，其中每个节点包含对列表中下一个节点的引用(或链接)，这意味着可以以可预测的方式对其进行迭代 —删除元素时不需要任何索引更新。然而，Swift标准库(目前)还没有包含链表类型，所以如果我们想要使用一个链表类型——我们首先必须构建它。
Building a linked list
让我们从声明一个列表结构开始，它将跟踪列表中的第一个和最后一个节点。在类型之外，我们将这两个属性设置为只读，以确保数据一致性:
struct List<Value> {
private(set) var firstNode: Node?
private(set) var lastNode: Node?
}
接下来，让我们创建节点类型——我们将创建一个类，因为我们希望能够通过引用来引用节点，而不是通过值。我们的列表将是双向链接的，这意味着每个节点都将包含对其下一个邻居和前一个节点的引用。 每个节点也将存储一个值-像这样:
extension List {
class Node {
var value: Value
fileprivate(set) weak var previous: Node?
fileprivate(set) var next: Node?
init(value: Value) {
self.value = value
}
}
}
我们将上述属性设为弱的原因是为了避免保留循环，如果我们在两个方向上都保持强引用，就会发生这种情况。
实际上，这就是我们在允许链表存储值方面所需要的所有代码。但这只是谜题的第一部分，就像任何其他集合一样，我们也希望能够遍历它并改变它的内容。让我们从迭代开始，由于Swift非常面向协议的设计，可以通过遵循序列和实现makeIterator方法轻松实现迭代:
extension List: Sequence {
func makeIterator() -> AnyIterator<Value> {
var node = firstNode
return AnyIterator {
// Iterate through all of our nodes by continuously
// moving to the next one and extract its value:
let value = node?.value
node = node?.next
return value
}
}
}
由于上面的迭代非常简单，所以我们使用标准库的AnyIterator来避免必须实现自定义迭代器类型-对于更高级的用例，可以通过遵循IteratorProtocol来实现。
接下来，让我们添加一些api来改变我们的链表——从插入开始。我们将使用一个append方法扩展List，该方法为插入的值添加一个新节点，然后返回该节点——如下所示:
extension List {
@discardableResult
mutating func append(_ value: Value) -> Node {
let node = Node(value: value)
node.previous = lastNode
lastNode?.next = node
lastNode = node
if firstNode == nil {
firstNode = node
}
return node
}
}
上面我们使用了@discardableResult属性，它告诉编译器在调用方法的结果没有被使用时不要生成任何警告-因为我们可能并不总是对所创建的实际节点感兴趣。
由于链表不是基于索引，而是通过引用来维护一个值链， 实现移除只是更新被移除节点的下一个和之前的邻居，使它们现在互相指向对方:
extension List {
mutating func remove(_ node: Node) {
node.previous?.next = node.next
node.next?.previous = node.previous
// Using "triple-equals" we can compare two class
// instances by identity, rather than by value:
if firstNode === node {
firstNode = node.next
}
if lastNode === node {
lastNode = node.previous
}
// Completely disconnect the node by removing its
// sibling references:
node.next = nil
node.previous = nil
}
}
有了上面的内容，我们列表的初始版本就完成了，现在我们可以开始运行它了。让我们更新Canvas来使用我们的新列表-以及一个字典，让我们快速查找哪个节点对应一个给定的形状ID -作为它的数据结构的新组合:
struct Canvas {
private var shapes = List<Shape>()
private var nodes = [Shape.ID : List<Shape>.Node]()
func render() -> Image {
let context = DrawingContext()
shapes.forEach(context.draw)
return context.makeImage()
}
mutating func add(_ shape: Shape) {
nodes[shape.id] = shapes.append(shape)
}
mutating func remove(_ shape: Shape) {
guard let node = nodes.removeValue(forKey: shape.id) else {
return
}
shapes.remove(node)
}
}
我们现在有了快速的插入和删除操作，以及可预测的迭代顺序，而不需要在调用站点上增加任何额外的复杂性——非常酷! 而且，由于我们将新列表设置为完全泛型的类型，现在我们可以在再次需要以线性方式存储没有索引的值时重用它。
Conclusion
尽管数据结构是如此的基本，以至于在各种编程语言中都可以找到它们，但在任何给定的情况下决定使用哪一种仍然需要大量的思考、测试和实验 -特别是如果我们想要我们的代码保持高效，因为它使用的数据越来越多。
随着需求的发展，任何特定情况下正确的数据结构也很可能会随着时间的推移而改变，有时还会使用多种数据结构的组合——而不仅仅是一个——可能是实现我们需要的性能特征的方法。
在接下来的文章中，我们将继续探索数据结构的世界——特别是那些还没有在标准库中实现的。就像很多其他事情一样，为了在每种情况下选择正确的数据结构，有时需要超越Swift扩展我们的思维。