第 11 章特型与泛型(2)

11.4 定义类型之间关系的特型

迄今为止，我们看到的每个特型都是独立的：特型是类型可以实现的一组方法。特型也可以用于多种类型必须协同工作的场景中。它们可以描述多个类型之间的关系。

std::iter::Iterator 特型会为每个迭代器类型与其生成的值的类型建立联系。
std::ops::Mul 特型与可以相乘的类型有关。在表达式 a * b 中，值 a 和 b 可以是相同类型，也可以是不同类型。
rand crate 中包含随机数生成器的特型（ rand::Rng）和可被随机生成的类型的特型（ rand::Distribution）。这些特型本身就准确地定义了它们是如何协同工作的。

你不需要每天都创建这样的特型，但它们在整个标准库和第三方 crate 中随处可见。本节将展示每一个示例是如何实现的，并根据需要来展开讲解相关的 Rust 语言特性。你需要掌握的关键技能是能够阅读这些特型和方法签名，并理解它们对所涉及的类型意味着什么。

11.4.1 关联类型（或迭代器的工作原理）

接下来我们从迭代器讲起。迄今为止，每种面向对象的语言都内置了某种对迭代器的支持，迭代器是用以遍历某种值序列的对象。

Rust 有一个标准的 Iterator 特型，定义如下：

pub trait Iterator {
 type Item;

 fn next(&mut self) -> Option<Self::Item>;
 ...
}

这个特型的第一个特性（ type Item;）是一个 关联类型。实现了 Iterator 的每种类型都必须指定它所生成的条目的类型。

第二个特性（ next() 方法）在其返回值中使用了关联类型。 next() 会返回一个 Option<Self::Item>：或者是序列中的下一个值 Some(item)，或者当没有更多值可供访问时返回 None。该类型要写成 Self::Item，而不仅仅是无修饰的 Item，因为这里的 Item 是每个迭代器类型下的一个特性，而不是一个独立的类型。同样， self 和 Self 类型在代码中任何使用了其字段、方法等的地方都要像这样显式写出来。

下面是为一个类型实现 Iterator 的范例：

//（来自标准库中std::env模块的代码）
impl Iterator for Args {
 type Item = String;

 fn next(&mut self) -> Option<String> {
 ...
 }
 ...
}

std::env::Args 是我们在第 2 章中用来访问命令行参数的标准库函数 std::env::args() 返回的迭代器类型。它能生成 String 值，因此这个 impl 声明了 type Item = String;。

泛型代码可以使用关联类型：

/// 遍历迭代器，将值存储在新向量中
fn collect_into_vector<I: Iterator>(iter: I) -> Vec<I::Item> {
 let mut results = Vec::new();
 for value in iter {
 results.push(value);
 }
 results
}

在这个函数体中，Rust 为我们推断出了 value 的类型，这固然不错，但我们还必须明确写出 collect_into_vector 的返回类型，而 Item 关联类型是唯一的途径。（用 Vec<I> 肯定不对，因为那样是在宣告要返回一个由迭代器组成的向量。）

前面示例中的代码并不需要你自己编写，因为在阅读第 15 章之后，你会知道迭代器已经有了一个执行此操作的标准方法： iter.collect()。在继续之前，再来看一个例子：

/// 打印出迭代器生成的所有值
fn dump<I>(iter: I)
 where I: Iterator
{
 for (index, value) in iter.enumerate() {
 println!("{}: {:?}", index, value); // 错误
 }
}

这几乎已经改好了。但还有一个问题： value 不一定是可打印的类型。

error: `<I as Iterator>::Item` doesn't implement `Debug`
 |
8 | println!("{}: {:?}", index, value); // 错误
 | ^^^^^
 | `<I as Iterator>::Item` cannot be formatted
 | using `{:?}` because it doesn't implement `Debug`
 |
 = help: the trait `Debug` is not implemented for `<I as Iterator>::Item`
 = note: required by `std::fmt::Debug::fmt`
help: consider further restricting the associated type
 |
5 | where I: Iterator, <I as Iterator>::Item: Debug
 | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

由于 Rust 使用了语法 <I as Iterator>::Item（ I::Item 的一种明确但冗长的说法），因此错误消息被弄得稍微有点儿乱。虽然这是有效的 Rust 语法，但实际上你很少需要以这种方式书写类型。

这个错误消息的要点是，要编译此泛型函数，就必须确保 I::Item 实现了 Debug 特型，也就是用 {:?} 格式化值时要求的特型。正如错误消息所暗示的那样，我们可以通过在 I::Item 上设置一个限界来做到这一点：

use std::fmt::Debug;

fn dump<I>(iter: I)
 where I: Iterator, I::Item: Debug
{
 ...
}

或者，我们可以说“ I 必须是针对 String 值的迭代器”：

fn dump<I>(iter: I)
 where I: Iterator<Item=String>
{
 ...
}

Iterator<Item=String> 本身就是一个特型。如果将 Iterator 视为所有迭代器类型的全集，那么 Iterator<Item=String> 就是 Iterator 的子集：生成 String 的迭代器类型的集合。此语法可用于任何可以使用特型名称（包括特型对象类型）的地方：

fn dump(iter: &mut dyn Iterator<Item=String>) {
 for (index, s) in iter.enumerate() {
 println!("{}: {:?}", index, s);
 }
}

具有关联类型的特型（如 Iterator）与特型对象是兼容的，但前提是要把所有关联类型都明确写出来，就像此处所展示的那样。否则， s 的类型可能是任意类型，同样，这会导致 Rust 无法对这段代码进行类型检查。

我们已经展示了很多涉及迭代器的示例。之所以花了这么多篇幅，是因为迭代器是迄今为止使用关联类型的最主要场景。但当特型需要包含的不仅仅是方法的时候，关联类型会很有用。

在线程池库中， Task 特型表示一个工作单元，它可以包含一个关联的 Output 类型。
Pattern 特型表示一种搜索字符串的方式，它可以包含一个关联的 Match 类型，后者表示将模式与字符串匹配后收集到的所有信息。
```
trait Pattern {
 type Match;

 fn search(&self, string: &str) -> Option<Self::Match>;
}

/// 你可以在字符串中找一个特定的字符
impl Pattern for char {
 /// Match只是找到的字符的位置
 type Match = usize;

 fn search(&self, string: &str) -> Option<usize> {
 ...
 }
}
```
如果你熟悉正则表达式，那么很容易看出 impl Pattern for RegExp 应该有一个更精细的 Match 类型，它可能是一个结构体，其中包含此匹配的开始位置和长度、圆括号组匹配的位置等。
用于处理关系型数据库的库可能具有 DatabaseConnection 特型，其关联类型表示事务、游标、已准备语句等。

关联类型非常适合每个实现都有一个特定相关类型的情况：每种类型的 Task 都会生成特定类型的 Output，每种类型的 Pattern 都会寻找特定类型的 Match。然而，如你所见，类型之间的某些关系并不是这样的。

11.4.2 泛型特型（或运算符重载的工作原理）

Rust 中的乘法使用了以下特型：

/// std::ops::Mul，用于标记支持`*`（乘号）的类型的特型
pub trait Mul<RHS> {
 /// 在应用了`*`运算符后的结果类型
 type Output;

 /// 实现`*`运算符的方法
 fn mul(self, rhs: RHS) -> Self::Output;
}

Mul 是一个泛型特型。类型参数 RHS 是 右操作数（right-hand side）的缩写。

这里的类型参数与它在结构体或函数上的含义是一样的： Mul 是一个泛型特型，它的实例 Mul<f64>、 Mul<String>、 Mul<Size> 等都是不同的特型，就像 min::<i32> 和 min::<String> 是不同的函数， Vec<i32> 和 Vec<String> 是不同的类型一样。

单一类型（如 WindowSize）可以同时实现 Mul<f64>、 Mul<i32>，等等。然后你就可以将 WindowSize 乘以许多其他类型。每个实现都有自己关联的 Output 类型。

泛型特型在涉及孤儿规则时会得到特殊豁免：你可以为外部类型实现外部特型，只要特型的类型参数之一是当前 crate 中定义的类型即可。因此，如果你自己定义了 WindowSize，则可以为 f64 实现 Mul<WindowSize>，即使你既没有定义 Mul 也没有定义 f64。这些实现甚至可以是泛型的，比如 impl<T> Mul<WindowSize> for Vec<T>。这是可行的，因为其他 crate 不可能在任何东西上定义 Mul<WindowSize>，因此实现之间不可能出现冲突。（11.2.2 节介绍过孤儿规则。）这就是像 nalgebra 这样的 crate 能为向量定义算术运算的原理。

前面展示的特型缺少一个小细节。真正的 Mul 特型是这样的：

pub trait Mul<RHS=Self> {
 ...
}

语法 RHS=Self 表示 RHS 默认为 Self。如果我写下 impl Mul for Complex，而不指定 Mul 的类型参数，则表示 impl Mul<Complex> for Complex。在类型限界中，如果我写下 where T: Mul，则表示 where T: Mul<T>。

在 Rust 中，表达式 lhs * rhs 是 Mul::mul(lhs, rhs) 的简写形式。所以在 Rust 中重载 * 运算符就像实现 Mul 特型一样简单。第 12 章会展示相关示例。

11.4.3 `impl Trait`

如你所料，由许多泛型类型组合而成的结果可能会极其凌乱。例如，使用标准库的组合器组合上几个迭代器，就会迅速把你的返回类型变成一个“丑八怪”：

use std::iter;
use std::vec::IntoIter;
fn cyclical_zip(v: Vec<u8>, u: Vec<u8>) ->
 iter::Cycle<iter::Chain<IntoIter<u8>, IntoIter<u8>>> {
 v.into_iter().chain(u.into_iter()).cycle()
}

我们可以很容易地用特型对象替换这个“丑陋的”返回类型：

fn cyclical_zip(v: Vec<u8>, u: Vec<u8>) -> Box<dyn Iterator<Item=u8>> {
 Box::new(v.into_iter().chain(u.into_iter()).cycle())
}

然而，在大多数情况下，如果仅仅是为了避免“丑陋的”类型签名，就要在每次调用这个函数时承受动态派发和不可避免的堆分配开销，可不太划算。

Rust 有一个名为 impl Trait 的特性，该特性正是为应对这种情况而设计的。 impl Trait 允许我们“擦除”返回值的类型，仅指定它实现的一个或多个特型，而无须进行动态派发或堆分配：

fn cyclical_zip(v: Vec<u8>, u: Vec<u8>) -> impl Iterator<Item=u8> {
 v.into_iter().chain(u.into_iter()).cycle()
}

现在， cyclical_zip 的签名中再也没有那种带着迭代器组合结构的嵌套类型了，而只是声明它会返回某种 u8 迭代器。返回类型表达了函数的意图，而非实现细节。

这无疑清理了代码并提高了可读性，但 impl Trait 可不止是一个方便的简写形式。使用 impl Trait 意味着你将来可以更改返回的实际类型，只要返回类型仍然会实现 Iterator<Item=u8>，调用该函数的任何代码就能继续编译而不会出现问题。这就为库作者提供了很大的灵活性，因为其类型签名中只编码了有意义的功能。

如果库的第一个版本像前面那样使用迭代器的组合器，但后来发现了针对同一过程的更好算法，则库作者可能会改用不同的组合器，甚至会创建一个能实现 Iterator 的自定义类型，但只要当初使用了 impl Trait 来编写签名，库的用户根本不必更改代码就能获得性能改进。

使用 impl Trait 来为面向对象语言中常用的工厂模式模仿出一个静态派发版本可能是个诱人的想法。例如，你可能会想定义如下特型：

trait Shape {
 fn new() -> Self;
 fn area(&self) -> f64;
}

在为几种类型实现了 Shape 之后，你可能希望根据某个运行期的值（比如用户输入的字符串）使用不同的 Shape。但以 impl Shape 作为返回类型并不能实现这一目标：

fn make_shape(shape: &str) -> impl Shape {
 match shape {
 "circle" => Circle::new(),
 "triangle" => Triangle::new(), // 错误：不兼容的类型
 "shape" => Rectangle::new(),
 }
}

从调用者的角度来看，这样的函数没有多大意义。 impl Trait 是一种静态派发形式，因此编译器必须在编译期就知道从函数返回的类型，以便在栈上分配正确的空间数量并正确访问该类型的字段和方法。在这里，这个类型可能是 Circle、 Triangle 或 Rectangle，它们可能占用不同的空间大小，并且有着不同的 area() 实现。

这里的要点是，Rust 不允许特型方法使用 impl Trait 作为返回值。要支持这个特性，就要对语言的类型系统进行一些改进。在这项工作完成之前，只有自由函数和关联具体类型的函数才能使用 impl Trait 作为返回值。

impl Trait 也可以用在带有泛型参数的函数中。例如，考虑下面这个简单的泛型函数：

fn print<T: Display>(val: T) {
 println!("{}", val);
}

它与使用 impl Trait 的版本完全相同：

fn print(val: impl Display) {
 println!("{}", val);
}

但有一个重要的例外。使用泛型时允许函数的调用者指定泛型参数的类型，比如 print::<i32>(42)，而如果使用 impl Trait 则不能这样做。

每个 impl Trait 参数都被赋予了自己独有的匿名类型参数，因此，只有在最简单的泛型函数中才能把 impl Trait 参数用作类型，参数的类型之间不能存在关系。

11.4.4 关联常量

与结构体和枚举一样，特型也可以有关联常量。你可以使用与结构体或枚举相同的语法来声明带有关联常量的特型：

trait Greet {
 const GREETING: &'static str = "Hello";
 fn greet(&self) -> String;
}

不过，关联常量在特型中具有特殊的功能。与关联类型和函数一样，你也可以声明它们，但不为其定义值：

trait Float {
 const ZERO: Self;
 const ONE: Self;
}

之后，特型的实现者可以定义这些值：

impl Float for f32 {
 const ZERO: f32 = 0.0;
 const ONE: f32 = 1.0;
}

impl Float for f64 {
 const ZERO: f64 = 0.0;
 const ONE: f64 = 1.0;
}

你可以编写使用这些值的泛型代码：

fn add_one<T: Float + Add<Output=T>>(value: T) -> T {
 value + T::ONE
}

请注意，关联常量不能与特型对象一起使用，因为为了在编译期选择正确的值，编译器会依赖相关实现的类型信息。

即使是没有任何行为的简单特型（如 Float），也可以提供有关类型的足够信息，再结合一些运算符，以实现像斐波那契数列这样常见的数学函数：

fn fib<T: Float + Add<Output=T>>(n: usize) -> T {
 match n {
 0 => T::ZERO,
 1 => T::ONE,
 n => fib::<T>(n - 1) + fib::<T>(n - 2)
 }
}

在 11.5 节和 11.6 节中，我们将展示用特型描述类型之间关系的不同方式。所有这些都可以看作避免虚方法开销和向下转换的方法，因为它们允许 Rust 在编译期了解更多的具体类型。

11.5 逆向工程求限界

当没有特型可以满足你的所有需求时，编写泛型代码可能会是一件真正的苦差事。假设我们编写了下面这个非泛型函数来进行一些计算：

fn dot(v1: &[i64], v2: &[i64]) -> i64 {
 let mut total = 0;
 for i in 0 .. v1.len() {
 total = total + v1[i] * v2[i];
 }
 total
}

现在我们想对浮点值使用相同的代码，因此可能会尝试像下面这么做。

fn dot<N>(v1: &[N], v2: &[N]) -> N {
 let mut total: N = 0;
 for i in 0 .. v1.len() {
 total = total + v1[i] * v2[i];
 }
 total
}

运气不佳：Rust 会报错说乘法（ *）的使用以及 0 的类型有问题。我们可以使用 Add 和 Mul 的特型要求 N 是支持 + 和 * 的类型。但是，对 0 的用法需要改变，因为 0 在 Rust 中始终是一个整数，对应的浮点值为 0.0。幸运的是，对于具有默认值的类型，有一个标准的 Default 特型。对于数值类型，默认值始终为 0：

use std::ops::;

fn dot<N: Add + Mul + Default>(v1: &[N], v2: &[N]) -> N {
 let mut total = N::default();
 for i in 0 .. v1.len() {
 total = total + v1[i] * v2[i];
 }
 total
}

离成功更近了，但仍未完全解决：

error: mismatched types
 |
5 | fn dot<N: Add + Mul + Default>(v1: &[N], v2: &[N]) -> N {
 | - this type parameter
...
8 | total = total + v1[i] * v2[i];
 | ^^^^^^^^^^^^^ expected type parameter `N`,
 | found associated type
 |
 = note: expected type parameter `N`
 found associated type `<N as Mul>::Output`
help: consider further restricting this bound
 |
5 | fn dot<N: Add + Mul + Default + Mul<Output = N>>(v1: &[N], v2: &[N]) -> N {
 | ^^^^^^^^^^^^^^^^^

我们的新代码中假定将两个 N 类型的值相乘会生成另一个 N 类型的值。但事实并非如此。你可以重载乘法运算符以返回想要的任意类型。我们需要以某种方式让 Rust 知道这个泛型函数只适用于那些支持正常乘法规范的类型，其中 N * N 一定会返回 N。错误消息中的建议几乎是正确的：我们可以通过将 Mul 替换为 Mul<Output=N> 来做到这一点，对 Add 的处理也是一样的：

fn dot<N: Add<Output=N> + Mul<Output=N> + Default>(v1: &[N], v2: &[N]) -> N
{
 ...
}

此时，类型限界积累得越来越多，使得代码难以阅读。我们来把限界移动到 where 子句中：

fn dot<N>(v1: &[N], v2: &[N]) -> N
 where N: Add<Output=N> + Mul<Output=N> + Default
{
 ...
}

漂亮！但是 Rust 仍然会对这行代码报错：

error: cannot move out of type `[N]`, a non-copy slice
 |
8 | total = total + v1[i] * v2[i];
 | ^^^^^
 | |
 | cannot move out of here
 | move occurs because `v1[_]` has type `N`,
 | which does not implement the `Copy` trait

由于我们没有要求 N 是可复制的类型，因此 Rust 将 v1[i] 解释为试图将值从切片中移动出去（Rust 中禁止这样做）。但是我们根本就没想修改切片，只是想将这些值复制出来以便对它们进行操作。幸运的是，Rust 的所有内置数值类型都实现了 Copy，因此可以简单地将其添加到对 N 的约束中：

where N: Add<Output=N> + Mul<Output=N> + Default + Copy

这样代码就可以编译并运行了。最终代码如下所示：

use std::ops::;

fn dot<N>(v1: &[N], v2: &[N]) -> N
 where N: Add<Output=N> + Mul<Output=N> + Default + Copy
{
 let mut total = N::default();
 for i in 0 .. v1.len() {
 total = total + v1[i] * v2[i];
 }
 total
}

#[test]
fn test_dot() {
 assert_eq!(dot(&[1, 2, 3, 4], &[1, 1, 1, 1]), 10);
 assert_eq!(dot(&[53.0, 7.0], &[1.0, 5.0]), 88.0);
}

上述现象在 Rust 中偶有发生：虽然经历了一段与编译器的激烈拉锯战，但最后代码看起来相当不错，就仿佛这场拉锯战从未发生过一样，运行起来也很令人满意。

我们在这里所做的就是对 N 的限界进行逆向工程，使用编译器来指导和检查我们的工作。这个过程有点儿痛苦，因为标准库中没有那么一个 Number 特型包含我们想要使用的所有运算符和方法。碰巧的是，有一个名为 num 的流行开源 crate 定义了这样的一个特型。如果我们能提前知道，就可以将 num 添加到 Cargo.toml 中并这样写：

use num::Num;

fn dot<N: Num + Copy>(v1: &[N], v2: &[N]) -> N {
 let mut total = N::zero();
 for i in 0 .. v1.len() {
 total = total + v1[i] * v2[i];
 }
 total
}

就像在面向对象编程中正确的接口能令一切变得美好一样，在泛型编程中正确的特型也能令一切变得美好。

不过，为什么要这么麻烦呢？为什么 Rust 的设计者不让泛型更像 C++ 模板中的“鸭子类型”那样在代码中隐含约束呢？

Rust 的这种方式的一个优点是泛型代码的前向兼容性。你可以更改公共泛型函数或方法的实现，只要没有更改签名，对它的用户就没有任何影响。

类型限界的另一个优点是，当遇到编译器错误时，至少编译器可以告诉你问题出在哪里。涉及模板的 C++ 编译器错误消息可能比 Rust 的错误消息要长得多，并且会指向许多不同的代码行，因为编译器无法判断谁应该为此问题负责：是模板，还是其调用者？而调用者也可能是模板，或者 调用者模板 的模板……

也许明确写出限界的最重要的优点是限界就这么写在代码和文档中。你可以查看 Rust 中泛型函数的签名，并准确了解它能接受的参数类型。而使用模板则做不到这些。在像 Boost 这样的 C++ 库中完整记录参数类型的工作比我们在这里经历的还要艰巨得多。Boost 开发人员可没有能帮他们检查工作成果的编译器。

11.6 以特型为基础

特型成为 Rust 中最主要的组织特性之一是有充分理由的，因为良好的接口在设计程序或库时尤为重要。

本章是关于语法、规则和解释的“狂风骤雨”。现在我们已经奠定了基础，可以开始讨论在 Rust 代码中使用特型和泛型的多种方式了。事实上，我们才刚刚开始入门。接下来的第 12 章和第 13 章将介绍标准库提供的公共特型。之后的各章将涵盖闭包、迭代器、输入 /输出和并发。特型和泛型在所有这些主题中都扮演着核心角色。

Rust程序设计(第二版)