我们都像物理学假想中的麦克斯韦妖一样活动。正是在日常经验中，我们可以发现一向冷静的物理学家在两个世纪里对这个卡通形象一直难以忘怀的原因。生物体（organism），顾名思义，时刻在组织（organize）。我们分拣邮件、堆造沙堡、拼凑拼图、复盘棋局、收集邮票、给麦穗脱粒、按字母表顺序排列图书、创造对称形式、创作十四行诗和奏鸣曲，以及整理自己的房间。所有这些活动并不需要巨大的能量，只需保障我们能够发挥智能便可。 ——James Gleick，《信息简史》1
1此书已由人民邮电出版社出版，详见 http://ituring.cn/book/731。——编者注
Rust 标准库包含多个集合，这些集合是泛型类型，用于在内存中存储各种数据。在本书中，我们已经用到了一些集合，比如 Vec 和
HashMap。本章将详细介绍这两种类型的方法，以及另外 6 个标准集合。在开始之前，我们先来辨析一下 Rust 的集合与其他语言的集合之间的一些系统性差异。
首先，移动和借用无处不在。Rust 使用移动来避免对值做深拷贝。这就是 Vec
ConcurrentModificationException 。Rust 的借用检查器在编译期就可以排除这些错误。 2这是 Java 中的异常类。——译者注 最后，Rust 没有 null，因此在其他语言使用 null 的地方 Rust 会使用 Option。 除了这些差异，Rust 的集合与你预期的差不多。如果你是一位经验丰富的程序员，而且时间有限，那么可以快速浏览本章，但不要错过 16.5.1 节。
16.1 概述
表 16-1 展示了 Rust 的 8 个标准集合，它们都是泛型类型。 表 16-1：标准集合汇总表 集合 描述 其他语言中类似的集合类型
C++ Java Python
Vec
HashMap<K, V> where K: Eq +
Hash 键值哈希表 unordered_map HashMap dict
BTreeMap<K, V> where K:
Ord 有序键值表 map TreeMap —
HashSet<T> where T: Eq +
Hash 无序的、基于哈希的集 unordered_set HashSet set
BTreeSet
16.2 Vec
因为本书中一直在使用 Vec，所以我们假设你对它已经比较熟悉了。有关介绍，请参阅 3.6.2 节。下面我们将详细讲解 Vec 的方法及内部工作原理。创建向量的 简单方法是使用 vec! 宏：
// 创建一个空向量
let mut numbers: Vec<i32> = vec![];
// 使用给定内容创建一个向量
let words = vec!["step", "on", "no", "pets"];
let mut buffer = vec![0u8; 1024]; // 1024个内容为0的字节
如第 4 章所述，向量具有 3 个字段：长度、容量和指向用于存储元素的堆分配内存的指针。图 16-1 展示了前面的向量在内存中的布局方式。空向量 numbers 初的容量为 0。直到添加第一个元素之前，不会为其分配堆内存。
图 16-1：向量的内存布局：words 的每个元素都是一个由指针和长度组成的 &str 值 与所有集合一样，Vec 也实现了 std::iter::FromIterator，所以可以使用迭代器的 .collect() 方法从任意迭代器创建向量，详情请参阅 15.4.13 节。
// 把另一个集合转换成向量
let my_vec = my_set.into_iter().collect::<Vec<String>>();
16.2.1 访问元素通过索引来获取数组、切片或向量的元素非常简单：
// 获取某个元素的引用
let first_line = &lines[0];
// 获取某个元素的副本
let fifth_number = numbers[4]; // 要求实现了Copy特型 let second_line = lines[1].clone(); // 要求实现了Clone特型
// 获取切片的引用
let my_ref = &buffer[4..12];
// 获取切片的副本
let my_copy = buffer[4..12].to_vec(); // 要求实现了Clone特型
如果索引超出了范围，则所有这些形式都会引发 panic。 Rust 对数值类型很挑剔，对向量也不例外。向量的长度和索引都是 usize 类型。试图用 u32、u64 或 isize 作为向量索引会导致出错。可以根据需要使用 n as usize 来转换，详情请参阅 6.14 节。 下面这些方法可以轻松访问向量或切片的特定元素（请注意，所有的切片方法也都适用于数组和向量）。 slice.first()（第一个） 返回对 slice 的第一个元素的引用（如果有的话）。 返回类型为 Option<&T>，所以如果 slice 为空则返回值为 None，如果不为空则返回 Some(&slice[0])。
if let Some(item) = v.first() {
println!("We got one! {}", item);
}
slice.last()（ 后一个） 与 first 类似，但会返回对 后一个元素的引用。 slice.get(index)（获取） 如果其存在，就返回 slice[index] 引用的 Some 值。如果 slice 的元素少于 index+1 个，则返回 None。
let slice = [0, 1, 2, 3];
assert_eq!(slice.get(2), Some(&2));
assert_eq!(slice.get(4), None);
slice.first_mut()（第一个可变）、slice.last_mut() （ 后一个可变）和 slice.get_mut(index)（获取可变） 这些方法是前述 slice.first() 等方法的变体，但借入的是可变引用。
let mut slice = [0, 1, 2, 3];
{
let last = slice.last_mut().unwrap(); // last的类型是&mut i32 assert_eq!(*last, 3);
*last = 100;
}
assert_eq!(slice, [0, 1, 2, 100]);
因为按值返回 T 就意味着移动它，所以一些需要就地访问元素的方法通常会按引用返回这些元素。 .to_vec() 方法是一个例外，它会复制这些元素。 slice.to_vec()（转向量） 克隆整个切片，返回一个新向量：
let v = [1, 2, 3, 4, 5, 6, 7, 8, 9];
assert_eq!(v.to_vec(), vec![1, 2, 3, 4, 5, 6, 7, 8, 9]);
assert_eq!(v[0..6].to_vec(), vec![1, 2, 3, 4, 5, 6]);
此方法只能用在元素可以克隆的情况下，也就是需满足 where T: Clone 限界。
16.2.2 迭代
向量、数组和切片是可迭代的，要么按值迭代3，要么按引用迭代，但都要遵循 15.2.2 节描述的模式。
作者在这里只是泛泛而言，其实除非元素是 Copy 类型，否则切片并不能按值迭代（情形
1）。——译者注
遍历 Vec
16.2.3 扩大向量与收缩向量
数组、切片或向量的长度是它们所包含的元素数量。
slice.len()（长度）
返回 slice 的长度，类型为 usize。
slice.is_empty()（为空？）
如果 slice 未包含任何元素（slice.len() == 0）则为真。
本节中的其余方法是关于扩大向量和收缩向量的。但数组和切片中没有这些方法，因为数组和切片一旦创建就无法调整大小。
向量的所有元素都存储在连续的、分配在堆上的内存块中。向量的容量就是该内存块可以容纳的 大元素数量。Vec 通常会替你管理容量，当需要更多空间时它会自动分配更大的缓冲区并将元素移入其中。下面是一些显式管理容量的方法。
Vec::with_capacity(n)（自带容量）
创建一个容量为 n 的新的空向量。
vec.capacity()（取容量）
返回 vec 的容量，类型为 usize。vec.capacity() >= vec.len() 始终是成立的。
vec.reserve(n)（预留）
确保向量至少有足够的备用容量来容纳另外 n 个元素，也就是说，vec.capacity() 至少等于 vec.len() + n。如果已经有足够的空间，就什么也不做。如果没有，则会分配一个更大的缓冲区并将向量的内容移入其中。
vec.reserve_exact(n)（精确预留）
与 vec.reserve(n) 类似，但要求 vec 不要为未来的增长分配任何多于 n 的额外容量。调用此方法后，vec.capacity() 应该精确等于 vec.len() + n。
vec.shrink_to_fit()（缩小到刚好够）
如果 vec.capacity() 大于 vec.len()，则尝试释放额外的内存。
Vec
vec = vec.into_iter().filter(test).collect();
vec.dedup()（去重） 丢弃重复的元素，类似于 Unix shell 实用程序 uniq。此方法会扫描 vec 以查找彼此相等的相邻元素，然后会从这些相等值中保留一个并丢弃多余的值：
let mut byte_vec = b"Misssssssissippi".to_vec();
byte_vec.dedup();
assert_eq!(&byte_vec, b"Misisipi");
请注意，输出中仍然有两个 ’s’ 字符。这是因为此方法只会移除相邻的重复项。要想消除所有重复项，你有 3 个选择：在调用 .dedup() 之前对向量进行排序、将数据移动到一个 Set 中，或者 （为了保持元素的原始顺序）使用如下 .retain() 技巧：
let mut byte_vec = b"Misssssssissippi".to_vec();
let mut seen = HashSet::new();
byte_vec.retain(|r| seen.insert(*r));
assert_eq!(&byte_vec, b"Misp");
上述代码的工作原理是当 Set 已经包含我们要插入的条目时
.insert() 就会返回 false。
vec.dedup_by(same)（根据 same 调用结果去重）
与 vec.dedup() 类似，但此方法会使用函数或闭包
same(&mut elem1, &mut elem2) 而不是 == 运算符来检查两个元素是否应被视为相等。
vec.dedup_by_key(key)（根据 key 属性去重）
与 vec.dedup() 类似，但此方法会在 key(&mut elem1) == key(&mut elem2) 时将两个元素视为相等。
如果 errors 是一个 Vec
// 移除带有相同信息的多余错误（error）
errors.dedup_by_key(|err| err.to_string());
在本节涵盖的所有方法中，只有 .resize() 会克隆值，其他方法都是将值从一个地方移动到另一个地方。 16.2.4 联结 以下两个方法可用于数组的数组，即其元素本身也是数组、切片或向量的数组、切片或向量。 slices.concat()（串联） 返回通过串联所有切片组装成的新向量。
assert_eq!([[1, 2], [3, 4], [5, 6]].concat(), vec![1, 2, 3, 4, 5, 6]);
slices.join(&separator)（联结） 与 concat 类似，只是在这些切片之间插入了值 separator 的副本。
assert_eq!(
[[1, 2], [3, 4], [5, 6]].join(&0),
vec![1, 2, 0, 3, 4, 0, 5, 6]
);
16.2.5 拆分
同时获得多个对数组、切片或向量中元素的不可变引用是比较容易的：
let v = vec![0, 1, 2, 3];
let a = &v[i];
let b = &v[j];
let mid = v.len() / 2;
let front_half = &v[..mid];
let back_half = &v[mid..];
但获取多个可变引用就不那么容易了：
let mut v = vec![0, 1, 2, 3];
let a = &mut v[i];
let b = &mut v[j]; // 错误：不能同时把`v`借入为多个可变引用
*a = 6; // 这里用到了引用`a`和引用`b`，
*b = 7; // 所以它们的生命周期必然重叠
Rust 禁止这样做，因为如果 i == j，那么 a 和 b 就是对同一个整数的两个可变引用，这违反了 Rust 的安全规则。（参见 5.4 节。） Rust 有几种方法可以同时借入对数组、切片或向量的两个或多个部分的可变引用。与前面的代码不同，这些方法是安全的，因为根据设 计，它们总会把数据拆分成几个不重叠的区域。这里的大部分方法在 处理非 mut 切片时也很方便，因此每个方法都有 mut 版本和非 mut 版本。 图 16-2 展示了这些方法。
图 16-2：对几个拆分型方法的说明（注意： slice.split(|&x|x==0) 输出中的小矩形是由于存在两个相邻的分隔符而生成的空切片，并且 rsplitn 会按从后向前的顺序生成其输出，这与另外几个方法不同） 这些方法都没有直接修改数组、切片或向量，它们只是返回了对内部数据中各部分的新引用。 slice.iter()（迭代器）和 slice.iter_mut()（可变迭代器） 生成对 slice 中每个元素的引用。16.2.2 节介绍过它们。 slice.split_at(index)（拆分于）和 slice.split_at_mut(index)（可变拆分于） 将一个切片分成两半，返回一个值对。 slice.split_at(index) 等价于 (&slice[..index], &slice[index..])。如果 index 超出了限界，这两个方法就会发生 panic。 slice.split_first()（拆分首个）和 slice.split_first_mut()（可变拆分首个） 同样会返回一个值对：对首个元素（slice[0]）的引用和对所有其余元素（slice[1..]）的切片的引用。 .split_first() 的返回类型是 Option<(&T, &[T])>，如果 slice 为空，则结果为 None。 slice.split_last()（拆分末尾）和 slice.split_last_mut()（可变拆分末尾） 与 slice.split_first() 和 slice.split_first_mut() 类似，但这两个方法拆分出的是 后一个元素而不是首个元素。 .split_last() 的返回类型是 Option<(&T, &[T])>。 slice.split(is_sep)（拆分）和 slice.split_mut(is_sep)（可变拆分） 将 slice 拆分为一个或多个子切片，使用函数或闭包 is_sep 确定拆分位置。这两个方法会返回一个遍历这些子切片的迭代器。 当你消耗此迭代器时，这些方法会为切片中的每个元素调用 is_sep(&element)。如果 is_sep(&element) 为 true，则认为该元素是分隔符。分隔符不会包含在输出的任何子切片中。 输出总是至少包含一个子切片，每遇到一个分隔符就额外加一个。如果有多个分隔符彼此相邻，或者有分隔符出现在 slice 的两端，则每对分隔符和两端的分隔符分别会对应输出一个空的子切片。 slice.split_inclusive(is_sep)（拆分，含分隔符）和 slice.split_inclusive_mut(is_sep)（可变拆分，含分隔 符） 与 split 和 split_mut 类似，但这两个方法会在前一个子切片的结尾包含分隔符而不会排除它。 slice.rsplit(is_sep)（右起拆分）和 slice.rsplit_mut(is_sep)（右起可变拆分） 与 split 和 split_mut 类似，但这两个方法会从切片的末尾开始往前拆分。 slice.splitn(n, is_sep)（拆分为 n 片）和 slice.splitn_mut(n, is_sep)（可变拆为 n 片） 与 slice.rsplit(is_sep) 和 slice.rsplit_mut(is_sep) 类似，但这两个方法 多会生成 n 个子切片。在找到前 n-1 个切片后，不会再调用 is_sep。 后一个子切片中会包含剩下的所有元素。 slice.rsplitn(n, is_sep)（右起拆分为 n 片）和 slice.rsplitn_mut(n, is_sep)（右起可变拆分为 n 片） 与 .splitn() 和 .splitn_mut() 类似，但是在使用这两个 方法时，切片会以相反的顺序扫描。也就是说，这两个方法会在切片中的最后而不是 前 n-1 个分隔符上进行拆分，并且子切片是从末尾开始向前生成的。 slice.chunks(n)（分为长度为 n 的块）和 slice.chunks_mut(n)（分为长度为 n 的可变块） 返回长度为 n 的非重叠子切片上的迭代器。如果 n 不能被 slice.len() 整除，则 后一个块包含的元素将不足 n 个。 slice.rchunks(n)（右起分为长度为 n 的块）和 slice.rchunks_mut(n)（右起分为长度为 n 的可变块） 与 slice.chunks 和 slice.chunks_mut 类似，但会从切片的末尾开始向前拆分。 slice.chunks_exact(n)（精确分为长度为 n 的块）和 slice.chunks_exact_mut(n)（精确分为长度为 n 的可变 块） 返回长度为 n 的非重叠子切片上的迭代器。如果 n 不能被 slice.len() 整除，则 后一个块（少于 n 个元素）可以在其结果的 remainder() 方法中获取。 slice.rchunks_exact(n)（右起精确分为长度为 n 的块）和 slice.rchunks_exact_mut(n)（右起精确分为长度为 n 的 可变块） 与 slice.chunks_exact 和 slice.chunks_exact_mut 类似，但会从切片的末尾开始拆分。 还有一个迭代子切片的方法。 slice.windows(n)（滑动窗口） 返回一个其行为类似于 slice 中数据的“滑动窗口”的迭代器。这个迭代器会生成一些横跨此 slice 中 n 个连续元素的子切片。它生成的第一个值是 &slice[0..n]，第二个值是 &slice[1..n+1]，以此类推。 如果 n 大于 slice 的长度，则不会生成任何切片。如果 n 为 0，则此方法会发生 panic。 如果 days.len() == 31，那么就可以通过调用 days.windows(7) 来生成 days 中所有相隔 7 天的时间段。 大小为 2 的滑动窗口可用于探究数据序列如何从一个数据点变化到下一个数据点：
let changes = daily_high_temperatures
.windows(2) // 获得两个相邻的 高气温
.map(|w| w[1] - w[0]) // 气温变化了多少？
.collect::<Vec<_>>();
因为各个子切片会重叠，所以此方法并没有返回可变引用的变体。 16.2.6 交换下面是交换切片内容的一些便利方法。
slice.swap(i, j)（交换元素）
交换 slice[i] 和 slice[j] 这两个元素。
slice_a.swap_with_slice(slice_b)（互换内容）
交换 slice_a 和 slice_b 的全部内容。slice_a 和 slice_b 的长度必须相同。向量有一个关联方法，该方法可以高效地移除任何元素。
vec.swap_remove(i)（交换后移除）
移除并返回 vec[i]。与 vec.remove(i) 类似，但此方法不会将向量中剩余的元素平移过来以填补空缺，而是简单地将 vec 的后一个元素移动到空缺中。如果不关心向量中剩余条目的顺序，那么此方法会很有用，因为性能更高。 16.2.7 填充下面是替换可变切片内容的两种便利方法。 slice.fill(value)（填充）
用 value 的克隆体填充切片。
slice.fill_with(function)（以 function 回调填充）
使用调用给定函数生成的值来填充切片。这对于实现了 Default 但未实现 Clone 的类型很有用，比如当 T 为不可复制类型时的
Option
16.2.8 排序与搜索下面是切片提供的 3 个排序方法。
slice.sort()（排序） 将元素按升序排列。此方法仅当元素类型实现了 Ord 时才存在。 slice.sort_by(cmp)（按 cmp 回调排序） 对 slice 中的元素按函数或闭包 cmp 指定的顺序进行排序。 cmp 必须实现 Fn(&T, &T) -> std::cmp::Ordering。 手动实现 cmp 是一件痛苦的事，不过可以把它委托给别的.cmp() 方法来实现：
students.sort_by(|a, b| a.last_name.cmp(&b.last_name));
如果想按一个字段排序，但当该字段相同时按另一个字段判定先后，则可以先把它们做成元组然后再进行比较。
students.sort_by(|a, b| {
let a_key = (&a.last_name, &a.first_name);
let b_key = (&b.last_name, &b.first_name);
a_key.cmp(&b_key)
});
slice.sort_by_key(key)（按 key 回调排序） 使用由函数或闭包型参数 key 给出的排序键对 slice 的元素按 递增顺序排序。key 的类型必须实现 Fn(&T) -> K，这里要满足K: Ord。 这在 T 包含一个或多个有序字段时会很有用，因此它可以按多种方式排序：
// 按平均学分绩点排序，低分在前
students.sort_by_key(|s| s.grade_point_average());
请注意，在排序过程中不会缓存这些排序键值，因此 key 函数可能会被调用 n 次以上。 出于技术原因，key(element) 无法返回从元素借来的任何引用。下面这种写法行不通：
students.sort_by_key(|s| &s.last_name); // 错误：无法推断生命周期
Rust 无法推算出生命周期。但在这些情况下，很容易把
.sort_by() 作为后备方案。
以上 3 个方法都会执行稳定排序。
要想以相反的顺序排序，可以将 sort_by 与交换了两个参数的 cmp 闭包一起使用。传入参数 |b, a| 而不是 |a, b| 可以有效地生成相反的顺序。或者，也可以在排序之后调用 .reverse() 方法。
slice.reverse()（逆转）
就地逆转切片。
一旦切片排序完毕，就可以高效地进行搜索了。
slice.binary_search(&value)（二分搜索）、 slice.binary_search_by(&value, cmp)（按 cmp 回调二分搜索）和 slice.binary_search_by_key(&value, key)（按 key 闭包二分搜索）
以上 3 个方法都会在给定的已排序 slice 中搜索 value。请注意，value 是按引用传递的。
这些方法的返回类型是 Result
slice.iter().position(|x| *x == value)
这将返回 Option
16.2.9 比较切片
如果类型 T 支持 == 运算符和 != 运算符（PartialEq 特型，参见 12.2 节），那么数组 [T; N]、切片 [T] 和向量 Vec
assert_eq!([1, 2, 3, 4].starts_with(&[1, 2]), true);
assert_eq!([1, 2, 3, 4].starts_with(&[2, 3]), false);
slice.ends_with(other)（以 other 结尾） 与上一个方法类似，但会检查 slice 的结尾值。
assert_eq!([1, 2, 3, 4].ends_with(&[3, 4]), true);
16.2.10 随机元素
随机数并未内置在 Rust 标准库中，但在 rand crate 中可以找到它们。rand crate 提供了以下两个方法，用于从数组、切片或向量中获取随机输出。 slice.choose(&mut rng)（随机选取） 返回对切片中随机元素的引用。与 slice.first() 和 slice.last() 类似，此方法会返回 Option<&T>，只有当切片为空时才返回 None。 slice.shuffle(&mut rng)（随机洗牌） 就地随机重排切片中的元素。切片必须通过可变引用传递。 这两个都是 rand::Rng 特型的方法，所以你需要一个 Rng（random number generator，随机数生成器），以便调用它们。幸运的是，通过调用 rand::thread_rng() 很容易得到一个生成器。要对向量 my_vec 进行洗牌，可以像下面这样写。
use rand::seq::SliceRandom;
use rand::thread_rng;
my_vec.shuffle(&mut thread_rng());
16.2.11 Rust 中不存在失效型错误
大多数主流编程语言有集合和迭代器，它们为排除失效型错误做了一点儿变化：不要在迭代集合时修改它。例如，在 Python 中，与向量等价的是列表：
my_list = [1, 3, 5, 7, 9]
#假设我们试图从 my_list 中移除所有大于 4 的值：
for index, val in enumerate(my_list):
if val > 4:
del my_list[index] # bug：在迭代过程中修改列表
print(my_list)
（Python 中的 enumerate 函数相当于 Rust 中的 .enumerate() 方法，参见 15.3.11 节。） 令人惊讶的是，这个程序打印出了 [1, 3, 7]。但是 7 显然大于 4。为什么失控了？这就是失效型错误：程序在迭代数据时修改了数据，让迭代器失效了。在 Java 中，结果将是一个异常。在 C++ 中，这是未定义行为。在 Python 中，虽然此行为有明确定义，但不直观：迭代器会跳过一个元素。这样一来，val 永远不会等于 7，因此也就没有机会删除它了。 我们试着在 Rust 中重现这个 bug：
fn main() {
let mut my_vec = vec![1, 3, 5, 7, 9];
for (index, &val) in my_vec.iter().enumerate() {
if val > 4 {
my_vec.remove(index); // 错误：不能把`my_vec`借用为可变的
}
}
println!("{:?}", my_vec);
}
当然，Rust 在编译时就会拒绝这个程序。当我们调用 my_vec.iter() 时，它借用了一个共享（非 mut）的向量引用。引用与迭代器的生命周期一样长，直到 for 循环结束。当存在不可变引用时，不能通过调用 my_vec.remove(index) 来修改向量。 帮你指出错误固然有用，但你还是得想方设法达成自己的目标。 简单的修复方法是写成如下形式：
my_vec.retain(|&val| val <= 4);
或者，也可以像在 Python 或任何其他语言中那样使用 filter 创建一个新向量。
16.3 VecDeque
Vec 只支持在末尾高效地添加元素和移除元素。当程序需要一个地方来存储“排队等候”的值时，Vec 可能会很慢。
Rust 的 std::collections::VecDeque
图 16-3：VecDeque 在内存中的存储情况
和 Vec 一样，VecDeque 用一块分配在堆上的内存来存储元素。与
Vec 不同，VecDeque 的数据并不总是从该区域的开头开始，它可以
“回绕”到末尾。这个双端队列的元素按顺序排列是 [‘A’, ‘B’,
‘C’, ’D’, ‘E’]。VecDeque 有两个私有字段，在图 16-3 中被标
记为 start 和 stop，用于记住数据在缓冲区中的首端位置和尾端位置。
从任一端向队列中添加一个值都意味着占用一个未使用的插槽，如图
16-3 中的深灰色色块所示。如果需要，可以回绕或分配更大的内存块。
VecDeque 会管理回绕，因此你不必费心于此。图 16-3 展示了 Rust 如何让 .pop_front() 更快的幕后原理。
通常，当你需要用到双端队列时，基本上只是需要 .push_back() 和 .pop_front() 这两个方法。用于创建队列的类型关联函数
VecDeque::new() 和 VecDeque::with_capacity(n) 和它们在 Vec 中的对应函数一样。VecDeque 还实现了 Vec 中的许多方法，比如 .len() 和 .is_empty()、.insert(index, value)、.remove(index)、.extend(iterable) 等。
和向量一样，双端队列可以按值、共享引用或可变引用进行迭代。它们有 3 个迭代器方法，即 .into_iter()、.iter() 和
.iter_mut()。它们可以按通常的方式通过索引来访问： deque[index]。
因为双端队列不会将自己的元素存储在连续的内存中，所以它们无法继承切片的所有方法。但是，如果你愿意承受移动内容的开销，则可以通过 VecDeque 提供的如下方法来解决此问题。
deque.make_contiguous()（变连续）
获取 &mut self 并将 VecDeque 重新排列到连续的内存中，返回 &mut [T]。
Vec 和 VecDeque 紧密相关，为了轻松地在两者之间进行转换，标准库提供了两个特型实现。
Vec::from(deque)（来自双端队列）
Vec
use std::collections::VecDeque;
let v = VecDeque::from(vec![1, 2, 3, 4]);
16.4 BinaryHeap
BinaryHeap（二叉堆）是一种元素组织会保持松散的集合，这样最大值便能总是冒泡到队列的首部。以下是 3 个最常用的
BinaryHeap 方法。 heap.push(value)（压入）
向堆中添加一个值。
heap.pop()（弹出）
从堆中移除并返回最大值。如果堆为空，则会返回一个为 None 的 Option
use std::collections::binary_heap::PeekMut;
if let Some(top) = heap.peek_mut() {
if *top > 10 {
PeekMut::pop(top);
}
}
BinaryHeap 还支持 Vec 上的部分方法，包括 BinaryHeap::new()、.len()、.is_empty()、.capacity() 、.clear() 和 .append(&mut heap2)。假设我们用一堆数值填充了 BinaryHeap：
use std::collections::BinaryHeap;
let mut heap = BinaryHeap::from(vec![2, 3, 8, 6, 9, 5, 4]);
值 9 会位于堆顶：
assert_eq!(heap.peek(), Some(&9));
assert_eq!(heap.pop(), Some(9));
移除了 9 之后也会稍微重新排列其他元素，以便让 8 位于最前面，以此类推：
assert_eq!(heap.pop(), Some(8));
assert_eq!(heap.pop(), Some(6));
assert_eq!(heap.pop(), Some(5));
当然，BinaryHeap 并不局限于数值。它可以包含实现了内置特型 Ord 的任意类型的值。 这使得 BinaryHeap 可用作工作队列。你可以定义一个基于优先级实现 Ord 的任务结构体，以便高优先级任务比低优先级任务大一些。然后，创建一个 BinaryHeap 来保存所有待处理的任务。它的 .pop() 方法将始终返回最重要的条目，也就是你的程序下一步就应该处理的任务。 注意：BinaryHeap 是可迭代的，它有一个 .iter() 方法，但此迭代器会以任意顺序而不是从大到小生成堆的元素。要按优先顺序消耗 BinaryHeap 中的值，请使用 while 循环。
while let Some(task) = heap.pop() {
handle(task);
}
16.5 HashMap 与 BTreeMap
Map 是键-值对［称为条目（entry）］的集合。任何两个条目都不会有相同的键，并且这些条目会始终按某种数据结构进行组织，从而使你可以通过键在 Map 中高效地查找对应的值。简而言之，Map 就是一个查找表。
Rust 提供了两种 Map 类型：HashMap
图 16-4：内存中的 HashMap BTreeMap 会在树结构中按键的顺序存储条目，因此它需要一个实现了 Ord 的键类型 K。图 16-5 展示了一个 BTreeMap。同样，深灰色区域表示未使用的备用容量。 BTreeMap 中存储条目的单元称为节点。BTreeMap 中的大多数节点仅包含键-值对。非叶节点（比如图 16-5 中所示的根节点）中也有一些空间用于存储指向子节点的指针。(20, ‘q’) 和 (30, ‘r’) 之间的指针会指向包含 20 和 30 之间所有键的子节点。添加条目通常需要将节点的一些现有条目向右平移，以保持它们的顺序，并且偶尔需要创建新节点。 为了适合页面大小，图 16-5 已略作简化。例如，真正的 BTreeMap 节点会有 11 个条目的空间，而不是 4 个。 Rust 标准库采用了 B 树而不是平衡二叉树，因为 B 树在现代硬件上速度更快。两相对比，二叉树固然在每次搜索时的比较次数较少，但 B 树具有更好的局部性（也就是说，内存访问被分组在一起，而不是分散在整个堆中）。这使得 CPU 缓存未命中的情况更为罕见。这会带来显著的速度提升。
图 16-5：内存中的 BTreeMap 下面是创建 Map 的几种方法。
HashMap::new()（新建）和 BTreeMap::new()（新建）
创建新的空 Map。
iter.collect()（收集）
可用于从键-值对创建和填充新的 HashMap 或 BTreeMap。 iter 必须是 Iterator
map = map.into_iter().filter(test).collect();
map.clear()（清空）
移除所有条目。
也可以使用方括号来查询 Map，比如 map[&key]。也就是说，Map 实现了内置特型 Index。但是，如果给定 key 还没有条目（就像越界数组访问），则会出现 panic，因此只有在要查找的条目肯定已填充过时才应使用此语法。
.contains_key()、.get()、.get_mut() 和 .remove() 的
key 参数不必具有确切的类型 &K。这些方法对可以从 K 借用来的类型来说是通用的。可以在 HashMap
16.5.1 条目
HashMap 和 BTreeMap 都有其对应的 Entry（条目）类型。条目的作用旨在消除冗余的 Map 查找。例如，下面是一些获取或创建学生记录的代码：
// 已经有关于此学生的记录了吗？
if !student_map.contains_key(name) {
// 没有：创建一个
student_map.insert(name.to_string(), Student::new());
}
// 现在，肯定存在一条记录了
let record = student_map.get_mut(name).unwrap();
这固然可以正常工作，但它会访问 student_map 两次或 3 次，每次都进行同样的查找。 对于这些条目，我们应该只进行一次查找，生成一个 Entry 值，然后将其用于所有后续操作。下面这个单行代码等效于上一段代码，但它只会执行一次查找：
let record = student_map
.entry(name.to_string())
.or_insert_with(Student::new);
student_map.entry(name.to_string()) 返回的 Entry 值就 像对 Map 中某个位置的可变引用，该位置要么由键-值对占用着，要么是空的（意味着那里还没有条目）。如果为空，那么条目的 .or_insert_with() 方法就会插入一个新的 Student。Entry 的大多数用法也是这样的：小而美。所有 Entry 值都是由同一个方法创建的。 map.entry(key)（按 key 取条目） 返回给定 key 的 Entry。如果 Map 中没有这样的键，则返回一个空的 Entry。 此方法会通过可变引用获取其 self 参数并返回与其生命周期一 致的 Entry：
pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
Entry 类型有一个生命周期参数 ‘a，因为它实际上是一种奇特的对 Map 的可变引用。只要 Entry 存在，它就拥有对此 Map 的独占访问权。 通过 5.3.5 节，我们已经了解了如何在类型中存储引用以及这会如何影响生命周期。现在我们正在从用户的视角来看待它。Entry 就是一例。 遗憾的是，如果 Map 具有 String 型的键，则无法将 &str 类型的引用传给此方法。在这种情况下，.entry() 方法需要一个真正的 String 型的值。 Entry 值提供了以下 3 个方法来处理空条目。 map.entry(key).or_insert(value)（取条目或插入） 确保 map 包含具有给定 key 的条目，如果需要，就插入具有给定 value 的新条目。此方法会返回对新值或现有值的可变引用。 假设我们需要统计选票。可以这样写：
let mut vote_counts: HashMap<String, usize> = HashMap::new();
for name in ballots {
let count = vote_counts.entry(name).or_insert(0);
*count += 1;
}
.or_insert() 会返回一个可变引用，所以 count 的类型是 &mut usize。 map.entry(key).or_default()（取条目或插入默认值） 确保 map 包含具有给定键的条目，如果需要，就插入一个具有 Default::default() 返回值的新条目。这仅适用于实现了 Default 的类型。与 or_insert 类似，此方法会返回对新值或现有值的可变引用。 map.entry(key).or_insert_with(default_fn)（取条目或借助 default_fn 插入） 与前两个方法类似，不过当需要创建一个新条目时，此方法会调 用 default_fn() 来生成默认值。如果 map 中已经有了 key 条目，则不会调用 default_fn。 假设我们想知道哪些词出现在了哪些文件中。可以这样写：
// 对于每个单词，这个`Map`包含一组曾出现过此单词的文件
let mut word_occurrence: HashMap<String, HashSet<String>> = HashMap::new();
for file in files {
for word in read_words(file)? {
let set = word_occurrence.entry(word).or_insert_with(HashSet::new);
set.insert(file.clone());
}
}
Entry 还提供了一个仅修改现有字段的便捷方法。 map.entry(key).and_modify(closure)（取条目并修改） 如果存在具有键 key 的条目，则调用 closure，并传入对该值的可变引用。此方法会返回 Entry，因此可以与其他方法做链式调用。 例如，可以使用此方法来计算字符串中单词出现的次数：
// 这个`Map`包含给定字符串的所有单词以及单词的出现次数
let mut word_frequency: HashMap<&str, u32> = HashMap::new();
for c in text.split_whitespace() {
word_frequency
.entry(c)
.and_modify(|count| *count += 1)
.or_insert(1);
}
Entry 类型是为 HashMap 专门定义的一个枚举（BTreeMap 也类似）：
// (in std::collections::hash_map) pub enum Entry<'a, K, V> {
Occupied(OccupiedEntry<'a, K, V>),
Vacant(VacantEntry<'a, K, V>) }
OccupiedEntry 类型和 VacantEntry 类型都有一些无须重复查找即可插入、移除和访问条目的方法。可以在在线文档中找到这些方法。这些额外的方法有时可用于消除一两次冗余查找，不过 .or_insert() 和 .or_insert_with() 已经涵盖了几种常见情况。
16.5.2 对 Map 进行迭代
以下几个方法可以对 Map 进行迭代。 按值迭代（for (k, v) in map）以生成 (K, V) 对。这会消耗 Map。 按共享引用迭代（for (k, v) in &map）以生成 (&K, &V) 对。 按可变引用迭代（for (k, v) in &mut map）以生成 (&K, &mut V) 对。（同样，无法对存储在 Map 中的键进行可变访问，因为这些条目是通过它们的键进行组织的。） 与向量类似，Map 也有 .iter() 方法和 .iter_mut() 方法，它们会返回针对“条目引用”的迭代器，可用来迭代 &map 或 &mut map。此外，还有以下迭代方法。 map.keys()（所有键的迭代器） 返回只有“键引用”的迭代器。 map.values()（所有值的迭代器） 返回只有“值引用”的迭代器。 map.values_mut()（所有值的可变迭代器） 返回只有“值可变引用”的迭代器。 map.into_iter()（转为迭代器）、map.into_keys()（转为键迭代器）和 map.into_values()（转为值迭代器） 消耗此 Map，分别返回遍历键值元组 (K, V)、键或值的迭代器。 所有 HashMap 迭代器都会以任意顺序访问 Map 的条目，而 BTreeMap 迭代器会按 key 的顺序访问它们。
16.6 HashSet 与 BTreeSet Set 是用于快速进行元素存在性测试的集合：
let b1 = large_vector.contains(&"needle"); // 慢，会检查每一个元素 let b2 = large_hash_set.contains(&"needle"); // 快，会按哈希查找
Set 中永远不会包含相同值的多个副本。
Map 和 Set 有一些不同的方法，但在幕后，Set 就像一个只有键
（而非键-值对）的 Map。事实上，Rust 的两个 Set 类型
HashSet
set = set.into_iter().filter(test).collect();
与 Map 一样，通过引用查找值的方法对于可以从 T 借用来的类型都是通用的。有关详细信息，请参阅 13.8 节。 16.6.1 对 Set 进行迭代以下两个方法可以迭代 Set。 按值迭代（for v in set）会生成 Set 的成员并消耗掉此 Set。 按共享引用（for v in &set）迭代会生成对 Set 成员的共享引用。 不支持通过可变引用迭代 Set。无法获取对存储在 Set 中的值的可变引用。 set.iter()（迭代器） 返回 set 中成员引用的迭代器。 与 HashMap 迭代器类似，HashSet 迭代器会以任意顺序生成它们的值。BTreeSet 迭代器会按顺序生成值，就像一个排好序的向量。 16.6.2 当相等的值不完全相同时 Set 有一些奇怪的方法，只有当你关心“相等”的值之间的差异时才需要使用这些方法。 这种差异确实经常存在。例如，两个内容相同的 String 值会将它们的字符存储在内存中的不同位置：
let s1 = "hello".to_string();
let s2 = "hello".to_string();
println!("{:p}", &s1 as &str); // 0x7f8b32060008 println!("{:p}", &s2 as &str); // 0x7f8b32060010
通常，我们不必在乎这种差异。
但如果确实需要关心这两个 String 的存储位置，就可以用以下方法访问存储在 Set 中的实际值。如果 set 不包含匹配值，则每个方法都会返回一个为 None 的 Option。
set.get(&value)（取值）
返回对等于 value 的 set 成员的共享引用（如果有的话）。返回类型是 Option<&T>。
set.take(&value)（拿出值）
与 set.remove(&value) 类似，但此方法会返回所移除的值（如果有的话）。返回类型是 Option
16.6.3 针对整个 Set 的运算
迄今为止，我们看到的大多数 set 方法专注于单个 Set 中的单个值。Set 还有一些对整个 Set 进行运算的方法。 set1.intersection(&set2)（交集） 返回同时出现在 set1 和 set2 中的值的迭代器。 如果想打印同时参加脑外科和火箭科学课程的所有学生的姓名，可以这样写：
for student in &brain_class {
if rocket_class.contains(student) {
println!("{}", student);
}
}
或者，再精简一些：
for student in brain_class.intersection(&rocket_class) {
println!("{}", student);
}
令人惊讶的是，有一个运算符能实现同样的效果。 &set1 & &set2 会返回一个新 Set，该 Set 是 set1 和 set2 的交集。这是把“二进制按位与”运算符应用在了两个引用之间。这样就会找到同时存在于 set1 和 set2 中的值。
let overachievers = &brain_class & &rocket_class;
set1.union(&set2)（并集） 返回存在于 set1 或 set2 中或者同时存在于两者中的值的迭代器。 &set1 | &set2 会返回包含所有这些值的新 Set。它会找出所有存在于 set1 或 set2 中的值。 set1.difference(&set2)（差集） 返回存在于 set1 但不在于 set2 中的值的迭代器。 &set1 - &set2 会返回包含所有此类值的新 Set。 set1.symmetric_difference(&set2)（对称差集，异或） 返回存在于 set1 或 set2 中但不同时存在于两者中的迭代器。 &set1 ^ &set2 会返回包含所有此类值的新 Set。 以下是测试 Set 之间关系的 3 个方法。 set1.is_disjoint(set2)（有交集？） 如果 set1 和 set2 没有共同的值，就返回 true——它们之间的交集为空。 set1.is_subset(set2)（是子集？） 如果 set1 是 set2 的子集，就返回 true。也就是说，set1 中的所有值都在 set2 中。 set1.is_superset(set2)（是超集？） 与上一个方法相反：如果 set1 是 set2 的超集，就返回 true。 Set 还支持使用 == 和 != 进行相等性测试。如果两个 Set 包含完全相同的一组值，那它们就是相等的。
16.7 哈希
std::hash::Hash 是可哈希类型的标准库特型。HashMap 的键和 HashSet 的元素都必须实现 Hash 和 Eq。 大多数实现了 Eq 的内置类型也会实现 Hash。整数、char 和 String 都是可哈希的。对元组、数组、切片和向量来说，只要它们的元素是可哈希的，它们自身就是可哈希的。 标准库的一个设计原则是，无论将值存储在何处或如何指向它，都应具有相同的哈希码。因此，引用与其引用的值具有相同的哈希码，而 Box 与其封装的值也具有相同的哈希码。向量 vec 与包含其所有数据的切片 &vec[..] 具有相同的哈希码。String 与具有相同字符的 &str 具有相同的哈希码。 默认情况下，结构体和枚举没有实现 Hash，但可以派生一个实现：
/// 大英博物馆藏品中某件物品的ID号
#[derive(Clone, PartialEq, Eq, Hash)] enum MuseumNumber {
... }
只要此类型的字段都是可哈希的，就可以这样用。 如果为一个类型手动实现了 PartialEq，那么也应该手动实现 Hash。假设我们有一个代表无价历史宝藏的类型：
struct Artifact {
id: MuseumNumber,
name: String,
cultures: Vec<Culture>,
date: RoughTime,
}
如果两个 Artifact 具有相同的 ID，那么就认为它们是相等的：
impl PartialEq for Artifact {
fn eq(&self, other: &Artifact) -> bool {
self.id == other.id
}
}
impl Eq for Artifact {}
由于我们仅是根据这些收藏品的 ID 来比较它们，因此也必须以相同的方式对这些收藏品进行哈希处理：
use std::hash::{Hash, Hasher};
impl Hash for Artifact {
fn hash<H: Hasher>(&self, hasher: &mut H) {
// 把哈希工作委托给藏品编号
self.id.hash(hasher);
}
}
（否则，HashSet
let mut collection = HashSet::<Artifact>::new();
如上述代码的前一段代码所示，即使要手动实现 Hash，也不需要了解任何有关哈希算法的知识。.hash() 会接收一个表示哈希算法的 Hasher 引用作为参数。你只需将与 == 运算符相关的所有数据提供给这个 Hasher 即可。Hasher 会根据你提供的任何内容计算哈希码。
16.8 使用自定义哈希算法
hash 方法是泛型的，因此 16.7 节展示的 Hash 实现可以将数据提 供给实现了 Hasher 的任何类型。这就是 Rust 支持可替换哈希算法的方式。 第三个特型 std::hash::BuildHasher 是表示哈希算法初始状态的类型的特型。每个 Hasher 都是单次使用的，就像迭代器一样：用过一次就扔掉了。而 BuildHasher 是可重用的。 每个 HashMap 都包含一个 BuildHasher，每次需要计算哈希码时都会用到。BuildHasher 值包含哈希算法每次运行时所需的键、初始状态或其他参数。 计算哈希码的完整协议如下所示：
use std::hash::{Hash, Hasher, BuildHasher};
fn compute_hash<B, T>(builder: &B, value: &T) -> u64 where B: BuildHasher, T: Hash
{
let mut hasher = builder.build_hasher(); // 1. 开始此算法 value.hash(&mut hasher); // 2. 填入数据 hasher.finish() // 3. 结束，生成u64 }
HashMap 每次需要计算哈希码时都会调用这 3 个方法。所有的方法都是可内联的，所以速度非常快。 Rust 的默认哈希算法是著名的 SipHash-1-3 算法。SipHash 的速度很快，而且非常擅长减少哈希冲突。事实上，它也是一个加密算法：目前还没有已知的有效方法能刻意生成与 SipHash-1-3 冲突的值。只要每个哈希表使用不同且无法预测的密钥，Rust 就可以安全地抵御一种称为 HashDoS 的拒绝服务攻击，在这种攻击中，攻击者会故意使用哈希冲突来触发服务器的 坏性能。不过，也许你的应用程序不需要此算法。如果要存储诸如整数或非常短的字符串之类的小型键，则可以实现更快的哈希函数，但代价是要 牺牲 HashDoS 的安全性。fnv crate 实现了这样的一个算法，即 Fowler-Noll-Vo (FNV) 哈希。要尝试此算法，请将如下内容添加到你的 Cargo.toml 中：
[dependencies] fnv = "1.0"
然后从 fnv 中导入 Map 类型和 Set 类型：
use fnv::{FnvHashMap, FnvHashSet};
可以使用这两种类型作为 HashMap 和 HashSet 的无缝替代品。浏览一下 fnv 源代码，就会发现它们是如何定义的：
/// 使用默认FNV哈希器的`HashMap`
pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;
/// 使用默认FNV哈希器的`HashSet`
pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;
标准的 HashMap 集合和 HashSet 集合会接受一个可选的额外类型 参数来指定哈希算法，FnvHashMap 和 FnvHashSet 是 HashMap 和 HashSet 的泛型类型别名，用于为那个参数指定一个 FNV 哈希器。
16.9 在标准集合之外
在 Rust 中创建一个新的自定义集合类型和在其他语言中非常相似。
你可以通过组合语言提供的部件（结构体和枚举、标准集合、
Option、Box 等）来组织数据。有关示例，请参阅 10.1.4 节定义的 BinaryTree
