Swift 泛型 (扩展版)

大家好 我是 Ben 我是 Swift 标准程序库的员工 今天我要和来自编译团队的同事 Doug 一起 跟大家分享关于 Swift 通用型的信息 Swift 最近发布的版本添加了一些重要的新特性 包括条件一致性和递归协议约束条件

其实在 Swift 发布的每个版本中 我们都会改善通用型系统 让它变得更有表现性 我们觉得 4.2 版本是一个重要节点

从这个节点开始 我们终于可以完全实施 许多期待应用到标准程序库的设计中了 这在达到 Swift 中 ABI 的稳定性的目标方面 对于我们来说非常重要

因此我们之前也针对通用型做了很多次演讲 但我们一直没有往后退一步 将通用型作为一个整体来讲 今天我们要给大家分享一些不同的功能 关于通用型系统 有新功能也有老功能 以便帮你们理解它们如何共同协作 我要快速回顾一下通用型的动机

我们会谈到设计协议 给出一系列具体类型 通过从标准程序库中获取的示例 我们会回顾一下协议继承 并谈谈条件一致性的新功能 以及它如何与协议继承相互作用 最后我们会通过对类和通用型的讨论 总结一下今天的内容 为何通用型对于 Swift 是如此重要的部分？ 了解它们之间相互影响的一个方式 是通过设计简单的集合 比如类型

我们把它叫做缓冲器 它类似于标准程序库中的数组类型

现在对于缓冲器的可读部分来说 最简单的 API 可能包括元素的一个计数 以及把每个元素获取到索引中指定位置的方式 但我们怎么让它返回类型呢？ 现在如果我们没有通用型 我们得做一个 有些类型可以表达 我们想在缓冲器内放置的一切东西 你可以调用那个类型 ID 或对象或 Void Star Swift 中 我们把它叫做 Any 它是一个可以在 Swift 中 代替任意不同类型的类型 因此若你想在缓冲器中处理任意一个元素 你可以让自定义下标返回 Any 但是当然了 你很可能知道 那会营造一种令用户愉悦的体验 那会营造一种 你不得不把那个类型从方框内拿出来 以便能实际使用它

这不仅烦人 还容易出错 如果你代码中的某个位置也许是偶然 如果你代码中的某个位置放了一个整型会怎么样呢？ 但那不仅仅关系到易用性 我们还想解决一些问题 关于如何在内存中表达这些值 现在对于字符串的缓冲器来说 最理想的表达方式 就是内存的连续块 每个元素之间用线隔开 但如果是无类型方法 这就不会那么有效了 因为缓冲器不会提前知道 它将会包含哪种类型 它得使用一种像 Any 一样的类型 那可以涵盖任意一个可能性 并且在那个 Any 中 在追踪类型、把类型装盒 和把类型从箱中取出方面 还有许多消耗

在这里 我可能只想要一个整型缓冲器 但我不能在编译器中表达它 因此我必须为灵活性付出代价 即使我对它并不感兴趣 另外 因为 Any 得解释任意一种不同的类型 包括那些太大以至于 不能在自己内部存储器内存储的类型 它有时候不得不使用间接存储 它得给值保留一个指针 那个值可以在整个内存中定位找到

我们真的想要解决这些问题 不仅仅是为了易用性和正确性 还为了性能原因 并且我们通过一种叫做参数多态性的技术来实现 它就是 Swift 中通用型的另一个术语 通过通用型方法 我们可以在缓冲器中存放更多信息 用于表达缓冲器即将要包含的类型

我们那个类型叫做元素

元素是类型的一个通用型参数 这就是术语参数多态性 你可以把它看作类似一个编译时间参数 它会告诉缓冲器即将要包含什么

现在它有一种方式可以提及那个元素类型 它可以使用那个元素类型 而以前它用的是 Any

那意味着不再需要任何转换 当你从缓冲器中获取类型时 如果你意外分配了错误的类型 或者类似的情况 编译器会捕捉你

现在并没有这种不带相关联的 元素类型的缓冲器类型了 如果你尝试声明一个那样的类型 你会得到一个编译错误 你可能会感觉有点吃惊 因为有时候你会看到 你可以声明不带任何元素类型的类型 比如缓冲器 但那仅仅是因为编译器 可以根据情境推断 应该是哪种元素类型 在本例中 是从右手边这儿的字面进行推断

元素仍然还在那里 就是有点含蓄

到底包含哪种类型 诸如缓冲器一样的类型 可以应用在编译和运行期的整个过程中 这意味着我们可以实现在内存的 连续块中保留全部元素的目标 而不会超前 即使那些类型任意大 因为编译器始终能直接了解 关于缓冲器具体包含哪种元素类型 它就有机会进行优化 而其它时候却没有 那么在本例中 在我声明整型缓冲器的位置 一个类似这样的循环应该被编译为 仅仅应用于某些非常有效的 CPU 指令 现在如果你正在一个常规基础上写一个这样的循环 用于总计整型缓冲器 把它提取到一个方法中可能会有意义 缓冲器上的扩展单位-可测试性更好 把它提取到一个方法中也可读性也更强 但你很可能知道 如果你像这样写代码 你会出现编译问题 因为并不是所有的元素类型 都可以像这样总计起来 我们需要告诉编译器 更多关于元素所需要具备的性能的信息 以便让这个方法在缓冲器上可用 现在最简单的方式就是 通过限制元素类型 为指定类型实现 就好像原始循环中的整型 如果你采用这种简单的方法来实现 并和扩展一起运行 那么稍后的推广会很简单 当你发现你需要做一些不同的操作时 比如总计双精度浮点型缓冲器 或单精度浮点型缓冲器

请看看你所限制的类型 查看它所遵循的协议 并保持追踪 直到你获得最通用的协议 那你就万事俱备了 在本例中 数字协议 给我们提供了 我们在这里所依赖的两个功能 创建值为 0 的新元素的能力 以及添加新元素的能力 这是数字协议的一部分 现在让我们谈谈 从不同类型中析出协议的过程 那么我们一直在谈这个缓冲器类型 我们可以让它在不同的元素之间通用 但是要在不同用法中通用的通用代码要怎么写呢？ 一段可以在任意不同种类的集合中使用的代码？ 比如数组 非常类似于我们的缓冲器类型 但拥有更多不同种类的类型 比如字典 它是关键值对的一个集合 或者也许是不通用的类型 或者不同的元素类型 比如数据或字符串 返回特定的元素类型 我们想要创建一个协议 可以捕捉它们全部常见的功能 我们要创建一个简化版本 标准程序库自己的集合协议

那么请注意 我们首先要考虑到 各式各样的具体类型 现在我们正在思考一种协议 可以把它们全部结合在一起 有必要以这种方式进行思考 我们要从一些具体类型开始 然后尝试通过一个协议把它们统一起来

那些类型共同拥有什么？ 它们不共同拥有什么？ 当你正设计一个这样的协议时 你可以把它看作是一种诸如合约谈判一样的东西 这里有一个很常见的拉锯战 在一致性类型之间 一方面 在执行那个约束方面 想要尽可能多的灵活性 而协议的用户 想要一个漂亮、紧凑、简单的协议 以便实现他们的扩展 这就是为什么非常重要的原因 同时考虑到 尽可能多的种类的一致性类型 和一系列不同用例 当你正在设计协议时 因为它是一种平衡做法 那么让我们开始具体化集合协议吧 那么首先我们需要表达元素类型 现在在协议中 我们使用了一个相关联类型 每个一致性类型 都需要对元素进行适当的设置 在缓冲器或数组的例子中 对于 Swift 4.2 来说 这是自动发生的 因为我们也把它们的通用参数命名为元素 这是一很棒的附带利益 可以赋予你的通用参数一个有意义的名字 遵循共同的惯例 就像元素这个词一样

而不是随意给它们一个名字 比如 T 你要分别陈述的是元素类型 对于其它数据类型 你可能需要做的更具体一些 比如字典 需要把元素类型设置为 它的关键值对和值类型 接下来让我们谈谈添加自定义下标

接下来让我们谈谈诸如数组类型一样的协议 我们可能会让自定义下标 以整型作为它的参数 但是让自定义下标用整型 可能会意味着非常强的约束 每个一致性类型都要提供 把元素取到由整数表达的指定位置的功能 那对于像数组一样的类型来说没问题 对于协议的用户来说也非常容易理解 但它对于稍微有些复杂的类型来说灵活性够吗？ 比如字典？

现在无论你如何处理它 字典很可能会被阻碍 被一些非常复杂的内部数据结构 在从一个元素移动到下一个元素方面 有特定逻辑的数据结构 比如它可能会被某种内部缓冲器阻碍 它可以使用在那个缓冲器中存储有位移的索引类型 然后它会把参数作为自定义下标 以便把元素获取到那个位置 使用那个位移 但有一点很重要 字典的索引类型 是一个隐含类型 只有字典可以控制 你不希望别人在你的位移中添加 1 那未必会在字典中移动到下一个元素 它可能会移动到任意元素 也许会移动到字典的内部存储器中 未初始化的部分

因此我们希望字典能控制继续向前移动 通过集合 通过改善索引实现 那么为此我们添加了另一个提供索引的方法 为你提供一个可以在它之后标记位置的索引 一旦你采取了这个步骤 你需要更多的东西 你需一个 startIndex 属性 和一个 endIndex 属性 因为简单的计数不再起作用了 不能再告诉我们是否已经到达末端 现在我们不再在索引类型中使用整型了

那么让我们把这些带回到集合协议中

那么我们得到了一个自定义下标 让某个索引类型 表示一个位置 并给你提供一个元素 我们还有一种 可以向前移动那个位置的方法

但我们还需要类型提供 它们即将在索引中使用的类型 我们通过另一个相关联类型实现

一致性类型可以提供适当的类型 因此数组或数据可以提供一个整型 作为它们的索引类型 然而字典可以提供 它自己的自定义实施 处理它自己的内部逻辑 那么让我们返回到一分钟之前我们所讲的内容 以便推广我们的索引模型 它仍然是一个非常有用的属性 因此我们很想把它重新添加到集合中 作为一个扩展 可以跨过集合 让索引向前移动 让计数器增长然后就返回 现在如果我们尝试实施它 我们就遇到了另一个漏掉的要求 因为我们把整型移动到一个通用的索引类型 我们再也不能假定索引类型是等同的了 整型是 但任意索引类型却没有必要 并且我们需要它 以便了解我们是否到达了末端

现在我们可以用之前所采用过的 同样的方法来解决这个问题 约束我们的扩展 比如它只能在索引类型是等同时使用

但感觉似乎不对劲

我们想要一个易用的协议 但看起来非常非常烦人 如果我们不得不经常在我们所写的每一个扩展上 应用这个约束 因为我们几乎总是需要比较两个索引 相反 它作为协议的要求 很可能更好地进行表述 作为我们索引相关联类型的约束

把这个约束应用到协议上 意味着遵循协议的全部类型 都需要向它们的索引提供一个 等同的类型 那样你就不需要在每次写扩展时都要指定它了

这是协商协议约束的另一个例子 协议的用户有一个要求 他们需要能比较索引 一致性协议 他们查看了一下 他们可以很合理地进行调整 而不需要放弃太多的灵活性

在本例中他们当然可以

并且通过 Swift 4.2 的 新功能自动合成等同的一致性 字典可以很简单地把它的索引类型变为等同

接下来让我们谈谈优化这个计数操作 通过一个自定义点

那么我们已经写了一个版本的计数 计算集合中元素的数量 通过跨过整个集合 但很明显 许多集合很可能做得更快 比如 假如字典在内部保留 它所持有的元素数量 用于实现自己的目的 如果它拥有这个信息 它就可以在它自己的计数实施中使用它 那意味着当人们在字典上调用计数时 他们会获得快速、恒定的时间 而不是线性时间 是指那个适用于任意集合的原始版本 所需要的线性时间 但当添加这样的优化时 你需要注意几点 即旅行协议的要求之间的不同点 和仅在指定类型上添加大量负载 直到现在 这个字典上的计数新版本 就是一个负载 那意味着当你有一个字典时 你知道它是一个字典 你将会获得更新、更好的计数版本 但如果在通用算法内部调用它会怎么样呢？

那么假如我们希望 比如说 写一个标准程序库的地图版本？ 如果你还不熟悉它 它真的是一个很有用的操作 可以转换集合中的每一个元素 并给你返回一个新数组 这个实施非常简单 它只是创建一个新数组 在集合内部移动 转换每一个元素 然后把它添加到数组中 现在随着你在像这样的数组中添加元素 数组会自动增长 它随着需要增长 有时候会重新分配它的内部存储 以便拥有更多的空间来容纳新元素 在一个这样的循环中 可能会多次执行上述过程 取决于它要变得多大 那么这个过程需要时间 分配内存的消耗非常大 有一个很棒的优化小技巧 我们可以应用于这种实施上 我们已经了解 最终的数组具体会有多大了 它会跟我们原始集合的尺寸一样大 那么我们可以提前在数组中储备好空间 在我们开始添加之前 这是一次很漂亮的加速 为此我们要调用计数 但我们在这里调用计数 在通用情境中 也就是集合类型是完全通用的情境 而不是特定的情境 可以是一个数组或字典或链表或任意 那么我们不知道有一个 更好的计数实施可用 当编译器编译这段代码时 那么在这种情况下 即将被调用的计数版本 实际上是计数的通用版本 可以应用在任意集合上 并会在整个集合上进行迭代 如果你在字典上调用地图 就不会调用我们刚写的计数的新版本

为了在通用情境中调用 像这样的自定义方法或属性 它需要在协议上 把自己声明为一个要求 我们已经确定一定有一种方式 它需要在协议上提供计数的优化版本 这样它在协议上 把自己声明为一个要求就有意义了 现在即便我们把它作为 一个要求来实施 所有集合都不需要提供它们自己的实施 因为我们已经通过我们的扩展 提供了一个 可以应用在任意集合上

向协议中添加一个要求 并且在旁边 通过一个扩展添加一个默认实施 这就是我们称为自定义点的东西 通过一个扩展 编译器可以了解 有一个可用的方法 或属性的更好的实施 因此在通用情境中 它会在协议中动态地调遣那个实施 那么现在如果你在字典上调用地图 即便是一个完全通用的函数 你将会得到计数的更好的实施

添加这样的自定义点 同时通过扩展添加默认实施 是一种很强大的方式 可以获得同样的好处 跟你用类获得的好处一样 实施继承和方法重写 但这个技巧可以用在 结构和枚举以及类上 现在并不是每一个方法 都可以像这样进行优化 并且自定义点在你的二进制尺寸上 有一个小但非零的影响 你的编译器运行时间的性能 那么只有当明确有机会自定义时 添加自定义点才有意义 比如在我们刚写的地图操作中 并没有合理的方式让任意种类的集合 提供更好的实施 因此把它添加为一个自定义点就没有意义 仅仅保持为一个扩展就可以了 那么我们已经创建了这个集合类型 且它其实已拥有了完整的功能 它有尽可能多的不同的一致性类型 你可以为它写许多不同但有用的算法 但有时候 你不是只需要一个单一的协议 为了将各种类型进行分类 你需要协议继承 为了让大家了解更多信息 请 Doug 上台来

谢谢 Ben

那么协议继承自 Swift 创建之初就有了 为了考虑我们在哪里需要协议继承 让我们看一下 我们一直在创建的这个集合协议 它是一个很好的协议 设计很棒 它描述了一组一致性类型 可以让你在类型上写一些有趣的通用算法 但我们不用做太多 就能找到其它类似集合的算法 依据目前的集合协议 我们不能实施 比如如果我们想在集合中找到 匹配某谓语的最后一个元素索引 最佳方式就是从末端开始 然后倒着进行 集合协议不允许我们这样做 或者加入我们想创建一个洗牌操作 以便在集合中的元素之间随机洗牌 嗯 那需要突变 而集合不允许这样 现在并不是因为集合协议错了

而是我们需要更多的东西 来描述这些额外的通用算法 这就需要协议继承 这是 BidirectionalCollection 协议 继承自集合或者继承集合 意思就是 遵循 BidirectionalCollection 协议的 任意类型 同样也会遵循集合 你可以使用那些集合算法 但是 BidirectionalCollection 添加了这个额外要求 就是能在集合中倒着操作 有一个重点需要注意 并不是每个集合都可以实施 这个特定的要求 思考一下 SinglyLinkedList 你只能让这些指针 从一个位置跳到下一个位置 并没有一种有效的方式 可以按照这个顺序倒着进行 因此它不能是 BidirectionalCollection 那么一旦我们引入了继承 你就已经限制了一致性类型 但你也允许你自己实施更多有趣的算法 那么这是这个 lastIndex(where:) 操作背后的代码 非常简单 我们只是在集合中倒着进行 使用这个来自 BidirectionalCollection 协议的新要求 让我们看一个更有意思的算法 那么这是一个洗牌操作 那么它在 Swift 4.2 中 针对集合进行了引入 你不需要自己实施它 我们会查看算法自身 了解它引入了哪些要求 从而算出如何有意义地将那些归类到协议中 Fisher-Yates 洗牌算法是一个很古老的算法 它也非常简单

然后随机选择 集合中另一个元素 并把这两个元素交换一下

在下一次迭代中 你把左边的索引向前移动一个 在那个和最后一个之间随机选择 然后交换那些元素 那么算法非常简单 只是集合中的线性移动 随机选择另一个元素进行交换 在最后你会得到一个经过漂亮洗牌的集合 那么我们可以看一下代码 有一点复杂 但不要担心 我们要在某个集合上实施它 那么让我们看一下这里的核心操作 那么首先我们需要能获取 随机编号在我们目前在集合中的位置 和集合末端之间 通过这个随机功能 但那儿有一个整型 我们需要的是集合中的索引 我们知道那是不同的 所以我们需要一些操作 让我们把它叫做 Index offsetBy 从 startIndex 迅速跳到 我们所选择的任意位置 我们所需要的另一个操作是 可以交换两个元素 很棒 我们有两个操作 我们需要添加 到集合的概念中 以便可以实施洗牌 因此我们有一个 新的 ShuffleCollection 协议

请不要这样做 那么这是一个反面模式 这里的反面模式是我们有一个算法 我们找到它的要求 然后我们把它打包到一个协议中 就是那个… 描述那一个算法 如果你这样做了 你就拥有了许多协议 但并没有任何意义 你并不是在从那些协议中学习什么 因此你应该做的是注意 我们实际上在这里有不同的功能 那么洗牌使用的是随机存取 并使用了突变 但这些是不同的 并且我们可以 把它们归类为不同的协议 比如 RandomAccessCollection 协议 就是可以让我们在集合中跳来跳去的协议 可以迅速移动索引 还有像 UnsafeBufferPointer 的类型 可以给你提供随机存取 但不允许任何突变 这是不同的功能 我们这里还有 MutableCollection 协议 我们可以认为这里的类型允许突变 但不允许随机获取 就像我们刚讲过的 SinglyLinkedList 一样 现在请注意我们已经从根本上分离了继承等级

我们有用于随机存取双向作用等等的存取端 然后我们有这个突变端 非常完美 因为客户自己可以编写多个协议 用来实施他们所写的通用算法 那么让我们返回到我们的洗牌算法 它可以在 RandomAccessCollection 上 作为一个扩展 带有自类型 所以这是一个既遵循 RandomAccessCollection 又遵循 MutableCollection 协议的类型 现在我们把这两个协议的功能放在了一起 现在当你拥有许多一致性类型时 以及许多通用算法时 你常常会形成协议等级 这些等级不应该太长 不应该太深入 因为你其实是希望要少量的协议 只要能描述在域名中出现的类型即可 对吧？ 现在你一定注意到了 当你着手创建这些协议等级时 那么随着你从等级的底层到顶层 你得到的协议会拥有较少的要求 因此有更多的一致性类型 可以实施那些要求 现在从另一方面说 随着你往等级的底层移动 并结合等级中不同的协议 你就要实施更复杂、更专业的算法 要求更高级的功能 但实际上只能用于较少的一致性类型上

好的 让我们谈谈条件一致性 这是 当然了 Swift 中的一个较新的功能 让我们首先从切片开始看 对于你所拥有的任意一个集合 你可以形成那个集合的一个切片 通过带有指定 索引范围的自定义下标实现 并且那个切片 其实是集合的某一个部分的视图 现在你在切片集合中所得到的一种默认类型 叫做切片 并且切片是一个通用的适配器类型 那么它在基础集合类型上参数化了 它自己就是一个集合 所以我们对于切片的期待就是 你可以对切片做任何 你能对下面的集合所做的事 这个要求很合理 我们当然可以使用向前搜索操作 比如 index(where:) 来查找匹配某个谓语的东西 那适用于集合以及那个集合的任意切片 我们想用向后搜索来做同样的事 但在这里我们会产生一个问题 即便缓冲器是一个 BidirectionalCollection 并没说切片也是一个 BidirectionalCollection 我们可以修复这个问题 让我们把切片扩展一下 使它遵循 BidirectionalCollection 协议 我们需要实施这个 index(before:) 操作 这样我们可以按照下面的基础集合进行实施 除非编译器会在这里进行约束

关于基础集合 我们所了解的唯一一件事就是 它是一个集合 它并没有 index(before:) 操作

我们知道如何修复这个问题 我们所需要做的就是在这个扩展中引入一个要求 换句话说就是基础集合需要是 BidirectionalCollection 这是条件一致性 其实就是扩展声明遵循某个协议 然后那个协议下的约束条件实际上就有意义了 关于条件一致性的最棒的事就是 当你拥有这些协议等级时 它会漂亮地进行堆栈 所以我们还可以说切片是一个 RandomAccessCollection 当它下面的基础类型是 RandomAccessCollection 时

现在请注意 我在这里写了两个不同的扩展

它是常见的 Swift 样式 写扩展 让它遵循某个协议 这样你就知道该扩展是干什么的 你就了解了它的意思 它有条件一致性特别重要 因为你在这些扩展上有不同的要求 这就允许有可组合性 无论下面的基层集合可以做什么 切片类型同样也可以做

那么让我们看看条件一致性的另一个 App 也是在标准程序库中 也是在标准程序库中 这些是范围 那么范围永远存在于 Swift 中 你可以形成一个范围 比如说这些操作符 因此你可以形成双精度浮点型范围 也可以形成整型范围 但有些范围比另外一些更强大 那么你可以在整型范围内迭代元素 为什么你能这样做呢？ 那是因为 intRange 遵循集合 现在如果你查看一下类型 由那个运算符创建的类型 它适当地命名了范围类型 它相对于下面的绑定类型来说是通用的 这种情况下 我们有一系列双浮点精度型 它仅仅存储较低和较高的绑定型 非常简单 但在 Swift 4.2 之前 你从整型范围中得到的 实际上是一个不同的类型 这是 CountableRange 类型 现在请注意 它与范围类型的结构一模一样 它有一个类型参数 它有较低和较高绑定型 但它在那个绑定型上增加了一些额外的要求 那个绑定型是可跨过的 对吧？ 意思是你可以枚举全部元素 现在这是你所需要的功能 从而可以 让 CountableRange 遵循 RandomAccessCollection

那就启用了 forEach 迭代循环 和其它功能

但是通过条件一致性 当然了 我们可以做得更好 让我们把基础范围类型变成一个集合 当绑定类型拥有这些额外的可跨过的要求时 它是条件一致性的简单 App 但它让范围类型变得更强大 当和更好的类型参数一起使用时

现在请注意我只是遵循 RandomAccessCollection 我其实没有提到集合 或 BidirectionalCollection

这是无条件顺应 没问题 声明遵循 RandomAccessCollection 暗示着遵循它所继承的任何协议 在本例中是 BidirectionalCollection 和集合 然而对于条件一致性 这实际上是个错误 现在如果你回想一下切片例子 我们需要有不同的约束 来处理那些不同的等级 针对集合与 BidirectionalCollection 与 RandomAccessCollection 因此编译器会强制执行 你要考虑到这个 并确保你拥有正确的约束条件 对于条件一致性来说 在本例中 整个等级的约束条件都是相同的 我们可以只明确写出集合 和 BidirectionalCollection 以宣称这就是全部一致性的位置 或者我们可以做得更好 分离不同的一致性 现在这点上 我们的范围类型非常强大 它会做一切 CountableRange 所能做的工作 我们应该如何使用 CountableRange 呢？ 我们可以把它丢到一边去 在本例中我们讲的是标准程序库 有许多代码实际上使用了 CountableRange 因此我们可以把它作为通用类型别名 保留下来

这是一个很棒的方案 那么通用类型别名添加了 让范围可计数所需要的全部额外要求 你需要把这些要求放在集合中 但它只是下面范围类型的一个可替换的名字

这对于源兼容性来说很棒 因为代码仍可使用 CountableRange 从另一方面说 它还可以 给那些拥有额外功能的范围取一个漂亮的名字 额外功能只是成为 RandomAccessCollection 事实上我们可以用此来清理其它代码 比如 我们知道什么是 CountableRange 它是带有这种额外跨越功能的范围 因此我们可以扩展 CountableRanges 这就是我们拥有 RandomAccessCollection 一致性的情况 Swift 4.2 中引入了这个 用于帮助简化我们要处理的类型 并让现有核心类型 比如范围 组合性更强 也更灵活

递归约束描述了协议 及其关联类型之间的关系 这是我们在 WWDC 的版本中 没有涉及的话题 它是标准库使用 Swift 泛型系统的重要组成部分 让我们直接开始吧 递归约束不过是涉及到相同协议 的一个协议中的约束 这里 集合具有一个名为子序列的关联类型 它本身就是一个集合 那么你为什么需要它呢 让我们来看一个基于它的泛型算法 这里是一个给定的已经排序过的集合 我们想要找到应该插入一个新值的索引 从而保持排序的顺序 我们将要计算值为 11 的排序插入点 当我们在索引处插入 11 时 结果仍然是一个排序好的数组 函数的排序插入点是通过二进制搜索实现的 是通过二进制搜索实现的 二进制搜索是一种经典的分治算法 这意味着在每个步骤中它都会做出一个决策 从而显著地减小问题的规模 需要考虑的下一步是对于二进制查找 我们首先观察中间元素 8 然后与我们要插入的值进行比较 也就是 11 因为 11 大于 8 所以 11 需要在 8 之后插入 在集合的后半部分 所以我们把搜索空间限制了一半

在下一步中我们找到新的中间值 14 并将其与我们想要插入的值进行比较 11 小于 14 所以插入点必须在中间值之前 再把剩下的集合部分分成两半 继续将我们观察的集合分成两半 直到我们指向到合适的插入点 这就是我们的解决方案

像这样的分治算法十分出色 因为它们的效率非常高 二进制搜索所需的时间呈对数变化 这意味着把输入的大小加倍 并不会像线性算法一样 使算法的运行慢两倍 对于像二进制搜索 只需要执行一个额外的步骤 就可以再次将问题的规模减半 现在我们把它转换成代码 首先要做的是找到中间元素的索引 我们可以通过一个函数使用 randomAccessCollections 指数偏移 接下来 我们需要检查值是否位于中间元素之前 所以我们知道了集合的哪一半包含插入点

在我们的示例中要插入的值大于中间的元素 我们从中间值之后的索引中取出集合的一个切片 直到完成 然后递归地调用切片上的排序和插入点 这在分治算法中很常见 也就是减少问题的规模 然后递归 为了使它能够使用 现在我们需要那个切片的语法 为了提供集合中适当的切片 我们可以为所有的集合引入一个 获取一系列索引 并生成切片的通用操作 就像这样

现在请记住我们前面讨论的适配式切片 适用于任何集合 提供基础集合中元素的视图 而基础集合本身就是集合 这就使得 我们的分治算法适用于任何集合 以及为所有集合提供切片语法 这的确很棒 但有一个问题 有些集合不需要这种特殊的切片类型 它们真正想要提供自己的切片操作 来产生不同的类型 字符串是最常见的例子 当你切片一个字符串时 你会得到一个子字符串

如果你把分治算法应用到字符串集合中 它们将会是子字符串的形式 而不是其他 字符串切片之类的类型 区间是另一个有趣的例子 因为它的切片操作 返回的将是带有不同的边界 却是相同区间类型的实例 因此 为了在符合集合的不同类型之间 捕获这种变量 我们可以在集合协议中引入新的要求 尤其是切片 因此在这里 我们将切片下标作为要求 引入到集合协议本身中 现在请注意 这个下标的结果类型 由一个新的关联类型来描述 它就是子序列

现在字符串类型和区间类型 都满足了这些新的集合要求 对于字符串 子序列类型是子字符串

对于区间子序列类型将是区间本身 这对于字符串类型和区间类型来说都很适用 但是对于所有其他不想定制实际的 子序列类型的集合类型而言 我们可以提供切片的默认限制 因此这些集合类型的构建者 实际上不需要做任何额外的工作 来符合这些集合 他们可以免费获得所有的切片行为 那么我们从子序列开始 关联类型本身可以具有默认值 记录在等号的后面 对于子序列来说 适配式切片类型是一个完美的默认类型 因为它适用于所有集合 因此这个默认值将用于 不提供自己的子序列类型的 任何符合的集合类型 这与前面从切片下标开始的实现匹配得很好 在集合协议的扩展中进行编写 它还可以作为默认的实现 提供返回切片的切片下标操作 我们甚至可以更进一步 在选择默认子序列类型的情况下 限制默认切片下标实现的适用性 因此这种模式可以防止默认实现 显示为对自定义子序列的 集合类型的重载 比如字符串和区间类型 所以这种模式很好地符合了各种类型 它们可以免费得到切片 或者根据需要自定义切片

但请记住我们的目标 我们希望编写出针对集合协议的分治算法 针对集合协议的分治算法 所以我们必须回答一个非常重要的问题 子序列的作用是什么 关于子序列 我们现在所知道的就是 它是切片下标操作的结果类型 但我们需要了解更多从而真正地使用它 为了回答这个问题 我们必须回顾刚才 我们想要用子序列表示的算法 我们的算法是递归的 它形成一个切片 也就是现在的子序列类型的值 然后递归地调用切片上的排序插入点 只有当返回的子序列类型本身就是一个集合时 它才有意义 当它执行该调用时 我们将传递集合的元素类型的值 但是递归调用本身期望 这个子序列的元素类型的值 唯有这些元素类型相同时算法才有意义 当从递归调用返回一个索引时 也会出现相同的问题 递归调用将由子序列计算 但是返回的索引 也需要是当前集合的有效索引 我们可以在集合协议中捕获所有这些要求 现在我们要做的第一件事是定义集合的子序列 本身就是一个集合 这就是所谓的“递归约束” 因为关联的类型符合它自己的封闭协议 然后我们可以使用关联类型 where 子句来进一步约束我们的子序列 如前所述它有一个元素类型 这个元素类型需要与原始集合相同 我们可以用同样的类型约束来表示 子序列元素与元素相同 由此也可以推及到索引类型 这些覆盖了我们通过观察算法的 排序插入点的实现而发现的所有属性 这就引出了一个有趣的问题 你能切片一个子序列吗 每个子序列都是一个集合 每个集合都有一个切片操作 因此你当然可以切片一个子序列 结果将是子序列的一个子序列

现在你可以再执行一次得到一个子序列的 一个子序列的一个子序列 如此一直继续下去 有趣的是 在每一点 我们都可以得到一个全新的类型 于是我们就拥有了这个潜在的无尽的模型塔 这实际上很好理解 我们的泛型算法中的每个递归步骤 都可以创建一个基于当前集合类型的新类型 只要递归最终在运行时终止就没有问题 然而 通常情况下 我们可以使分治算法不具备递归特性 从而更有效地实现 这里是算法的排序和插入点的非递归实现 我们来看看核心的算法并没有不同 但它是用这个 while 循环迭代 而不是递归表示的 所以我们要做的第一件事 就是获取整个集合的一个切片 这个切片变量将表示我们在每次 迭代中看到的集合的一部分 现在我们看到了熟悉的分治模式 找到切片的中间位置 然后将插入值与切片中的中间元素进行比较 然后 在再次进入循环之前 我们通过分割切片来缩小搜索范围

然而 我们碰到了一个问题 我们对切片变量赋值为子序列类型 另一个方面 右边是切片的切片 正如我们之前讨论过的 子序列的子序列可能是一个完全不同的类型 我们会得到一个编译错误 告诉我们这两种类型不一定相同 这一点很不方便 因为它阻止我们编写这个非递归算法 它并不能真正反映特定集合类型的行为 考虑一下字符串 当你切片一个字符串时 你会得到一个子字符串 如果你切片一个子字符串 你并不会得到子字符串的子字符串 你只会得到子字符串的另一个实例 让我们讨论之前的 这个适配型切片的工作方式 来概括这个概念 我们有一个集合 命名为 Self 并将其分割为 I 到 J 几个切片 现在将构建一个 Self 的类型切片 它只是底层 Self 集合的一个视图 如果我们分割这个切片 我们将得到 Self 的切片的一个切片 它是一个相同的基础 Self 集合上的视图 的一个视图 这就是我们在实践中得到的无限塔 然而也可以不必这样 请记住 切片类型使用与其基础集合 相同的索引 它们了解自己的基础集合 所以当我们切片的时候 我们可以取那些新的索引 I2 和 J2 将它们置入原始的基础集合 并从那里形成新的切片 它的作用是 当你分割一个切片的时候 你会得到相同的切片类型 有效地约束了递归 这和子字符串的行为完全一样 并且有理由预想所有子序列类型 都以这种方式运行 让我们将其建模为集合协议需求的 一个显式部分 这里我们定义一个子序列的子序列 和子序列的类型是一样的 换句话说 当你分割切片的时候 你会得到相同类型的切片 这样我们的非递归 分治算法将得以运行 而且简化了集合协议的使用 不再需要对无尽的类型塔进行推理 最后一个问题 涉及子序列 我们说过它需要是一个集合 但是我们需要子序列类型 是一个随机访问集合 来执行这个索引偏移操作 为了描述这一点 我们可以使用协议 where 子句 因此当 bidirectionalCollection 从集合承继时 它可以在子序列上添加一个新的约束 要求它遵守 bidirectionalCollection 协议 这又是一个递归约束 但现在它在 bidirectionalCollection 协议上表示 对于 randomAccessCollection 也是同理 例如随机访问集合的子序列 其本身也符合 randomAccessCollection 注意子序列的约束是如何遵循封闭协议的 这听起来有点耳熟 递归约束和条件一致性都倾向于像这样 跟踪协议层级结构 并且这些特性相互支持 这一点特别重要 因为我们希望子序列 也就是 Self 的切片 的默认关联类型 能够适用于集合的每一层级结构 切片总是一个集合 当我们继续创建 bidirectionalCollection 协议时 那么子序列类型也需要符合 bidirectionalCollection 适配式切片与 bidirectionalCollection 的 条件一致性 在任何时候都被认为是 bidirectionalCollection 满足这一要求 RandomAccessCollection 也是如此 子序列获得一个 randomAccessCollection 需求 然后切片与 randomAccessCollection 的条件一致性 将满足该需求 也就是 randomAccessCollection 本身 这种关联类型默认适用于层级结构中的 每个协议的行为指示了一个优秀的内聚设计 如果你发现 你在集合层级结构中的不同位置 需要不同的默认关联类型 那么你的设计可能出现了问题 递归约束是一个强大的工具 协同关联类型以及协议 where 子句 它们帮助我们编写协议需求 从而能够用泛型代码 自然地表达分治算法 现在我们回到 WWDC 演讲的最后一部分

那么 Swift 是一个多范式语言 现在我们一直在专心讲通用型 但是当然了 Swift 也支持面向对象的编程 那么我想花一些时间谈谈这两个功能 之间的相互影响 以及它们如何在 Swift 语言中协同合作 那么对于类继承 我们知道类继承是如何运作的 非常简单 你可以声明一个超类 比如汽车 你可以声明某些子类 比如出租车和警车 它们都继承自汽车 一旦你这么做了 你就拥有了这个面向对象的等级 你期望那些子类可以在哪里使用 那么如果我要用一个新方法扩展汽车 让它变成驱动器 我非常期待我可以在我的一个子类上 调用那个方法 比如出租车 那么这是面向对象编程中的一个根本方面 Barbara Liskov 其实很好地描述了相关信息 在 80 年代的一场演讲中 自那时起 我们就把这个叫做 Liskov 替换原则 理念其实很简单 那么如果你的程序中有一些地方 引用了一个超类型或超类 比如汽车 你就应该可以获取它的子类型 或子类的任意实例 比如出租车或汽车子类 并使用它 程序应该仍然继续监测类型 并正常运行 那么这里的替换是作为子类的实例 应该可以去到子类所能去到的任何地方 这是一个很简单的原则 我们把它内在化了 但它仍然很强大 如果你思考一下的话 请考虑你程序中的任何一点 如果我得到一个不同的子类 会发生什么 也许是一个我没有想到的子类？ 那么返回到通用型 当在通用型系统上应用 Liskov 替换原则时 我们期待什么呢？ 也许我们添加了一个新协议 可驾驶 无论是什么 并把汽车扩展为可驾驶 我们期待发生什么呢？ 我们期待你可以使用协议一致性 把汽车的一致性 用于可驾驶的一致性 并用在它的某些子类上 比如你在可驾驶协议中添加了一个 简单的通用算法 比如 sundayDrive 现在你应该可以在警车上使用 那个 API 了 即使这并不是最好的方式 那么子类有效地继承了协议一致性 并且这在一致性上添加了约束 你所写的那个一致性 就是让汽车可驾驶的东西 现在必须适用于汽车的全部子类 以及稍后出现的子类 大部分时候就是有用 然而在某些情况下 它会在子类上添加一些新要求 最常见的就是 当处理初始化程序要求时 那么如果你查看了可解协议 它有一个有趣的要求 就是初始化程序要求从解码器中 创建符合型的新实例 我们要如何使用它呢？ 让我们继续向可解协议中 添加一个便捷方法 它是一个静态方法解码 从解码器中生成新实例 其实就是初始化程序的一个包装 让它简单易用 关于这个特定的方法 你需要注意两个有意思的事情 首先它是否一个带大写字母 S 的 Self 请记住这是一致性类型 它与你在静态方法上调用的类型相同

现在第二件有意思的事是 我们要如何实施它？ 我们调用上边那个初始化程序 来创建一个全新的实例 是我们所拥有的可解码类型的实例 然后返回它 很公平 我们可以继续并让汽车类型可解码 然后我们期待当应用 Liskov 替换原理时 我们可以使用汽车的任意子类 带有我们通过协议一致性 创建的这些新 API 那么我们可以在出租车子类上调用解码 而我们得到的不是汽车 也不是任意汽车实例 而是出租车 出租车的实例

很棒 但应该如何使用它？ 让我们看看出租车会包含什么？ 也许这里有一个按小时计费的工具 当我们调用 Taxi.decode(from:) 时 我们就会通过协议 通过协议初始化程序要求 它其实只能调用一个初始化程序 就是在汽车类内部声明的初始化程序 在这里的超类中 那么那个初始化工具 它知道如何解码汽车的全部状态 但它并不了解出租车子类 那么如果我们要直接使用这个初始化程序 我们会产生一个问题 hourlyRate 完全未被初始化 那会导致一些更不幸的误解 当你在最后得到账单时 我们该如何解决这个？ 看起来 Swift 不会让你陷入这个问题中 它会在你尝试让汽车遵循可解码协议时进行判断 是指那个初始化程序中 有问题的可解码协议 它应该被标记为必需

现在必须在全部超类中实施所必需的初始化程序 不仅仅是直接的超类 而是任意一个超类 以及你现在还不知道的将来可能会出现的超类

现在通过添加那个要求 意味着当出租车从汽车中继承时 它还需要引入一个 拥有相同名称的初始化程序 现在这非常重要 因为这个初始化程序负责解码 hourlyRate 然后锁住超类初始化程序 以便解码剩余的汽车类型

好的 现在如果你快速阅读了那些红色方框 你可能会注意到子短语并不是最终 那么从定义上说最终类没有子类 因此从本质上说它稍后会让它们免于替换

意思是拥有一个必需初始化程序没有意义 因为你知道那儿没有子类 因此最终类用起来稍微简单点儿 当处理诸如可解码或其它初始化程序要求方面 因为它们不需遵循这些规则 即拥有必需初始化程序 那么当你用类引用语义时 考虑使用最终类 当你不再需要自定义类时 通过集成机制 现在这并不意味着 你稍后不能自定义你的类 你仍然可以在类上写扩展 与你扩展结构或枚举的方式一样 你还可以给它添加一致性 以获取更加动态的调遣 但最终类可以通过通用系统简化相互作用 也会解锁在运行时间内 优化编译器的机会

我们今天谈了谈 Swift 的通用型

Swift 通用型背后的理念 是提供重复使用代码的能力 同时保持静态类型信息 使得写正确的程序变得较为简单 并把这些有效地编译到执行程序中 当你设计协议时 让这个进行拉锯战 在你想要写的协议的通用算法之间 并且一致性类型需要实施那个协议 以便指导你的设计成为一个有意义的提取

引入协议继承 当你需要更多特定功能来实施新的通用算法时 只有一致性类型的子集支持那些算法

还有条件一致性 当你写通用类型时 以便它们可以编写得很漂亮 尤其是当与协议继承一起使用时 最后 当你针对棘手的相互作用产生疑问时 在类继承和通用系统之间 返回到 Liskov 替换原理 思考一下这里发生了什么 如果我引入子类而不是超类 我在子类而非超类上写了一个一致性

非常感谢 还有一些关于拥抱算法的相关演讲 你可以了解它们会如何帮助你创建更好的代码 以及如何在你的日常编程中 有效地使用 Swift 集合 谢谢 [ 掌声 ]