聚集 — Rust的STL
CPP —> Standard Template Library
Rust 标准库包含多个聚集，这些聚集是泛型范例，用于在内存中存储各种数据。
Rust 的聚集与其他语言的聚集之间的一些系统性差别：
- 首先，移动和借用无处不在。Rust 利用移动来避免对值做深拷贝。这就是 Vec::push(item) 方法会按值而非按引用来获取参数的原因。这样值就会 移动到向量中。将 Rust String 压入 Vec 中会很快，因为 Rust 不必复制字符串的字符数 据，而且字符串的所有权始终是明白的。
- 其次，Rust 没有失效型错误，也就是当程序仍持有指向聚集内部数据的指针时，聚集被重新调整巨细或发生其他变化而导致的那种悬空指针错误。失效型错误是 C++ 中未定义行为的另一个来源，即使在内存安全的语言中，它们也会偶尔导致ConcurrentModificationException。Rust 的借用检查器在编译期就可以排除这些错误。
Rust 没有 null，因此在其他语言利用 null 的地方 Rust 会利用 Option。
本文介绍Rust 的 8 个标准聚集，它们都是泛型范例
- Vec（普通向量） 可增长的、分配在堆上的 T 范例值数组。
- VecDeque（双端队列向量） 与 Vec 类似，但更适适用作先入先出队列。它支持在列表的前面和后面高效地添加值和移除值，但代价是会让所有其他的操作都稍微变慢一些。
- BinaryHeap（二叉堆） 优先级队列。BinaryHeap 中的值是精心组织过的，因此始终可以高效地 查找和移除其最大值。
- HashMap（哈希 Map） 由键-值对构成的表。通过键查找值很快。其条目会以任意顺序存储。
- BTreeMap（B 树 Map） 与 HashMap 类似，但它会根据键来对条目进行排序。 BTreeMap 会以 String 的比较顺序来存储其条目。除非需要让条目保持排序状态，否则用 HashMap 更快一些。
- HashSet（哈希 Set） 由 T 范例的值组成的 Set。它既能很快地添加值和移除值，也能很快地查 询给定值是否在此 Set 中。
- BTreeSet（B 树 Set） 与 HashSet 类似，但它会让元素按值排序。同样，除非需要让数据保 持排序状态，否则用 HashSet 更快一些。
- 因为 LinkedList 很少利用（对于大多数用例，在性能和接口方面有更好的更换方案），以是这里就不展开讲解了。
Vec<T>向量
创建向量的最简单方法是利用 vec! 宏：
- // 创建一个空向量
- let mut numbers: Vec<i32> = vec![];// 使用给定内容创建一个向量
- let words = vec!["step", "on", "no", "pets"];
- let mut buffer = vec![0u8; 1024]; // 1024个内容为0的字节
Vec 也实现了 std::iter::FromIterator，以是可以使 用迭代器的 .collect() 方法从任意迭代器创建向量
- // 把另一个集合转换成向量
- let my_vec = my_set.into_iter().collect::<Vec<String>>();
通过索引来获取数组、切片或向量的元素非常简单，越界就会Panic
下面这些方法可以轻松访问向量或切片的特定元素（请注意，所有的切片方法也 都实用于数组和向量）：
- slice.first()（第一个） 返回对 slice 的第一个元素的引用（如果有的话）。 返回范例为 Option<&T>，以是如果 slice 为空则返回值为 None，如果 不为空则返回 Some(&slice[0])。
- slice.last()（末了一个） 与 first 类似，但会返回对末了一个元素的引用。
- slice.get(index)（获取） 如果其存在，就返回 slice[index] 引用的 Some 值。如果 slice 的元 素少于 index+1 个，则返回 None。
- slice.first_mut()（第一个可变）、slice.last_mut()（末了一个 可变）和 slice.get_mut(index)（获取指定索引可变） 这些方法是前述 slice.first() 等方法的变体，但借入的是可变引用。因为按值返回 T 就意味着移动它，以是一些需要当场访问元素的方法通常会按 引用返回这些元素。.to_vec() 方法是一个例外，它会复制这些元素。
- slice.to_vec()（转向量） 克隆整个切片，返回一个新向量：
迭代
向量、数组和切片是可迭代的，要么按值迭代 ，要么按引用迭代
- 遍历Vec<T> 或数组 [T; N] 会生成 T 范例的条目。这些元素会逐个从向量或数组中移动出来并被斲丧掉。
- 遍历 &[T; N]、&[T] 或 &Vec <T>范例的值（对数组、切片或向量的引 用）会生成 &T 范例的条目，即对单个元素的引用，这些元素不会移动出 3 3来。
- 遍历 &mut [T; N]、&mut [T] 或 &mut Vec<T> 范例的值会生成 &mut T 范例的条目。
数组、切片和向量也有 .iter() 方法和 .iter_mut() 方，以用于创建一个会生成对其元素的引用的迭代器。
扩大向量与紧缩向量
数组、切片或向量的长度是它们已经包含的元素数量。
- 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 还有很多用来添加或移除元素的方法，它们可以改变向量的长度。所有 这些方法都可以通过可变引用获取其 self 参数。 下面这两个方法会在向量的末尾添加或移除单个值。
- vec.push(value)（推入） 将给定 value 添加到 vec 的末尾。
- vec.pop()（弹出） 移除并返回末了一个元素。返回范例是 Option。如果弹出的元素是 x，则返回 Some(x)；如果向量已经为空，则返回 None。 请注意，.push() 会按值而不是按引用接受其参数。同样，.pop() 会返回弹出的值，而不是引用。本节中剩下的大部分方法也是如此。它们可以将值移动进 和移动出向量。 下面这两个方法会在向量的任意位置添加或移除一个值。
- vec.insert(index, value)（插入） 在 vec[index] 处插入给定的 value，将 vec[index…] 中的所有当前 值向右平移一个位置以腾出空间。 如果 index > vec.len()，则会引发 panic。
- vec.remove(index)（移除） 移除并返回 vec[index]，将 vec[index+1…] 中的所有当前值向左平 移一个位置以填补空缺。 如果 index >= vec.len()，则会引发 panic，因为在这种情况下要移除 的 vec[index] 元素并不存在。 向量越长，这个操作就越慢。如果需要经常执行 vec.remove(0)，请思量 利用 VecDeque来代替 Vec。 需要移动的元素越多，.insert() 和 .remove() 的速度就会越慢。 下面这 4 个方法可以把向量的长度更改为特定值。
- vec.resize(new_len, value)（调整巨细） 将 vec 的长度设置为 new_len。如果该操作会增长 vec 的长度，则以 value 的副本填补新空间。元素范例必须实现 Clone 特型。
- vec.resize_with(new_len, closure)（以……调整巨细） 与 vec.resize 类似，但会调用闭包来构造每个新元素。它能用于不可 Clone 的元素构成的向量。
- vec.truncate(new_len)（截断） 将 vec 的长度镌汰到 new_len，丢弃 vec[new_len…] 范围内的任何元 素。 如果 vec.len() 已经小于或等于 new_len，则什么也不会发生。
- vec.clear()（清空） 从 vec 中移除所有元素。此方法的结果和 vec.truncate(0) 一样。 下面这 4 个方法可以一次添加或移除多个值。
- vec.extend(iterable)（扩展） 按顺序在 vec 末尾添加来自给定 iterable 值的所有条目。此方法就像 .push() 的多值版本。iterable 参数可以是实现了 IntoIterator 的任何值。此方法非常有效，以是我们为其定义了一个标准特型 Extend，所有标准集 合都实现了该特型
- vec.split_off(index)（拆分出） 与 vec.truncate(index) 类似，但此方法会返回一个 Vec，此中包 含从 vec 末尾移除的那些值。此方法就像是 .pop() 的多值版本。
- vec.append(&mut vec2)（追加） 这会将 vec2 的所有元素移动到 vec 中，此中 vec2 是 Vec 范例的另 一个向量。之后，vec2 会被清空。 此方法与 vec.extend(vec2) 类似，不同之处在于调用 extend 之后 vec2 仍然存在，其容量也不受影响。
- vec.drain(range)（抽取） 这将从 vec 中移除 range 范围内的切片 vec[range]，并返回对所移除 元素的迭代器，此中 range 是范围值，类似 .. 或 0..4。 还有一些略显古怪的方法可以从向量中选择性地移除一些元素。
- vec.retain(test)（留下） 移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&T) -> bool 的函数或闭包。针对 vec 的每个元素，此方法都会调用 test(&element)，如果函数或闭包返回了 false，就会从向量中移除并丢弃 此元素。除了性能上略有差别，此方法和下面的写法很像：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");
- 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<Box<dyn Error>>，你可以这样写：
- // 移除带有相同信息的多余错误（error）
- errors.dedup_by_key(|err| err.to_string());
上面所有方法，只有 .resize() 会克隆值，其他方法都是将值从一 个地方移动到另一个地方。
联结
以下两个方法可用于数组的数组，即其元素本身也是数组、切片或向量的数组、 切片或向量。
- 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]);
拆分
同时得到多个对数组、切片或向量中元素的不可变引用是比较轻易的，但获取多个可变引用就不那么轻易了
Rust 有几种方法可以同时借入对数组、切片或向量的两个或多个部分的可变引用。与前面的代码不同，这些方法是安全的，因为根据计划，它们总会把数据拆 分成几个不重叠的地区。这里的大部分方法在处置惩罚非 mut 切片时也很方便，因此每个方法都有 mut 版本和非 mut 版本
slice.split(|&x|x==0) 输出 中的小矩形是由于存在两个相邻的分隔符而生成的空切片，而且 rsplitn 会按 从后向前的顺序生成其输出，这与别的几个方法不同
这些方法都没有直接修改数组、切片或向量，它们只是返回了对内部数据中各部 分的新引用。
- slice.iter()（迭代器）和 slice.iter_mut()（可变迭代器） 生成对 slice 中每个元素的引用。
- 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<_>>();
交换
- slice.swap(i, j)（交换元素） 交换 slice 和 slice[j] 这两个元素。
- slice_a.swap_with_slice(slice_b)（交换内容） 交换 slice_a 和 slice_b 的全部内容。slice_a 和 slice_b 的长度必须相同。 向量有一个关联方法，该方法可以高效地移除任何元素。
- vec.swap_remove(i)（交换后移除） 移除并返回 vec。与 vec.remove(i) 类似，但此方法不会将向量中 剩余的元素平移过来以填补空缺，而是简单地将 vec 的末了一个元素移动到空缺中。如果不关心向量中剩余条目的顺序，那么此方法会很有效，因为性能更高。
添补
- slice.fill(value)（添补） 用 value 的克隆体添补切片。
- slice.fill_with(function)（以 function 回调添补） 利用调用给定函数生成的值来添补切片。这对于实现了 Default 但未实现 Clone 的范例很有效，比如当 T 为不可复制范例时的 Option<T> 或 Vec<T>。
排序与搜刮
切片提供的 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); // 错误：无法推断生命周期
以上 3 个方法都会执行稳定排序
反序排序：要想以相反的顺序排序，可以将 sort_by 与交换了两个参数的 cmp 闭包一起 利用。传入参数 |b, a| 而不是 |a, b| 可以有效地生成相反的顺序。或者， 也可以在排序之后调用 slice.reverse() 方法。
搜刮
- slice.binary_search(&value)（二分搜刮）
- slice.binary_search_by(&value, cmp)（按 cmp 回调二分搜刮）
- slice.binary_search_by_key(&value, key)（按 key 闭包二分 搜刮）
这些方法的返回范例是 Result<usize, usize>。如果在指定排序顺序 中 slice[index] 等于 value，那么这些方法就会返回 Ok(index)。如果找不到这样一个索引，那么这些方法就会返回 Err(insertion_point)，这样当你在 insertion_point 中插入 value 后，向量仍然会保持排好序的状态。
固然，只有在切片确实已经按指定顺序排序时二分搜刮才有效。否则，结果将是没故意义的。
由于 f32 和 f64 具有 NaN 值，因此它们无法实现 Ord 而且不能直接用作排序 和二分搜刮方法的键。要得到实用于浮点数据的类似方法，请利用 ord_subset crate。
可以用另一个方法在未排过序的向量中搜刮。 slice.contains(&value)（包含） 如果 slice 中有任何元素等于 value，则返回 true。这会简单地检查切片的每个元素，直到找到匹配项。value 同样是按引用通报的。 如果要在切片中查找值的位置（类似 JavaScript 中的 array.indexOf(value)），请利用迭代器：
slice.iter().position(|x| *x == value)返回 Option<usize>
比较切片
如果范例 T 支持 == 运算符和!=运算符（PartialEq 特型）， 那么数组 [T; N]、切片[T] 和向量 Vec<T> 也会支持这两个运算符。如果两 个切片的长度相同而且对应的元素也相等，那它们就是相等的。数组和向量也是 如此。
如果 T 支持运算符 <、<=、> 和 >=（PartialOrd 特型），那 么 T 的数组、切片和向量也会支持这些运算符。切片之间是按字典序比较的 （从左到右逐个比较）。 下面是执行常见的切片比较的两个便捷方法。
- slice.starts_with(other)（以 other 开头） 如果 slice 的起始值序列等于 other 切片中的相应元素，则返回 true。
- slice.ends_with(other)（以 other 结尾） 与上一个方法类似，但会检查 slice 的结尾值
随机元素
随机数并未内置在 Rust 标准库中，但在 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());
python迭代器失效：
- my_list = [1, 3, 5, 7, 9]
- for index, val in enumerate(my_list):
- if val > 4:
- del my_list[index] # bug：在迭代过程中修改列表
- print(my_list)
在 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);
- }
最简单的修改方法：my_vec.retain(|&val| val <= 4); 也可以像在 Python 或任何其他语言中那样利用 filter 创建一个新向量。
VecDeque<T>双端队列向量
Vec 只支持在末尾高效地添加元素和移除元素。当程序需要一个地方来存储“排队等候”的值时，Vec 可能会很慢。 Rust 的 std::collections::VecDeque 是一个双端队列（deque， double-ended queue）,支持在首端和尾端进行高效 的添加操作和移除操作。
- deque.push_front(value)（队首推入） 在队列的首端添加一个值。
- deque.push_back(value)（队尾推入） 在队列的尾端添加一个值。（此方法比 .push_front() 更常用，因为队 列通常的习惯是在尾端添加值，在首端移除值，就像人们在排队等候一样。）
- deque.pop_front()（队首弹出） 移除并返回队列的首端值，如果队列为空则返回一个为 None 的 Option，就像 vec.pop() 那样。
- deque.pop_back()（队尾弹出） 移除并返回队列的尾端值，同样返回 Option。
- deque.front()（队首）和 deque.back()（队尾） 与 vec.first() 和 vec.last() 类似，这两个方法会返回对队列首端或 尾端元素的引用。返回值是一个 Option<&T>，如果队列为空则为 None。
- deque.front_mut()（队首，可变版）和 deque.back_mut()（队尾， 可变版） 与 vec.first_mut() 和 vec.last_mut() 类似，这两个方法会返回 Option<&mut T>。
和 Vec 一样，VecDeque 用一块分配在堆上的内存来存储元素。与 Vec 不同， VecDeque 的数据并不总是从该地区的开头开始，它可以“回绕”到末尾。
这个双 端队列的元素按顺序排列是 [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]。VecDeque 有 两个私有字段 start 和 stop，用于记住数据在缓冲区 中的首端位置和尾端位置。
从任一端向队列中添加一个值都意味着占用一个未利用的插槽。如果需要，可以回绕或分配更大的内存块。 VecDeque 会管理回绕，因此你不必费心于此。
通常，当你需要用到双端队列时，根本上只是需要 .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 实现了From<VecDeque<T>>，因此 Vec::from(deque) 能将 双端队列酿成向量。这个操作的时间复杂度是 O(n)，因为可能要重新排列元 素。
- VecDeque::from(vec)（来自向量） VecDeque 实现了 From<Vec<T>>，因此 VecDeque::from(vec) 能把向量酿成双端队列。这个操作的时间复杂度是 O(1)，因为 Rust 会直接把向量缓冲区转移给 VecDeque，而不会重新分配。 这个方法使得创建具有指定元素的双端队列变得很轻易，哪怕并没有标准的 vec_deque![] 宏。
- use std::collections::VecDeque;
- let v = VecDeque::from(vec![1, 2, 3, 4]);
BinaryHeap（二叉堆）
BinaryHeap（二叉堆）是一种元素组织会保持疏松的聚集，这样最大值便能总是冒泡到队列的首部。以下是 3 个最常用的 BinaryHeap 方法。
- heap.push(value)（压入） 向堆中添加一个值。
- heap.pop()（弹出） 从堆中移除并返回最大值。如果堆为空，则会返回一个为 None 的 Option<T>。
- heap.peek()（窥视） 返回对堆中最大值的引用。返回范例是 Option<&T>。
- heap.peek_mut()（窥视，可变版）返回一个 PeekMut，它会返回对堆中最大值的可变引用，并提供范例 关联函数 pop() 以从堆中弹出该值。利用此方法，我们可以根据最大值来决定 是否将其从堆中弹出。
- 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)。
- use std::collections::BinaryHeap;
- let mut heap = BinaryHeap::from(vec![2, 3, 8, 6, 9, 5, 4]);
- assert_eq!(heap.peek(), Some(&9));
- assert_eq!(heap.pop(), Some(9));
固然，BinaryHeap 并不局限于数值。它可以包含实现了内置特型 Ord 的任意 范例的值。 这使得 BinaryHeap 可用作工作队列。你可以定义一个基于优先级实现 Ord 的 任务布局体，以便高优先级任务比低优先级任务大一些。然后，创建一个 BinaryHeap 来生存所有待处置惩罚的任务。它的 .pop() 方法将始终返回最重要的条目，也就是你的程序下一步就应该处置惩罚的任务。
注意：BinaryHeap 是可迭代的，它有一个.iter()方法，但此迭代器会以任意顺序而不是从大到小生成堆的元素。要按优先顺序斲丧 BinaryHeap 中的 值，利用 while 循环：
- while let Some(task) = heap.pop() {
- handle(task);
- }
Map 是键-值对［称为条目（entry）］的聚集。
任何两个条目都不会有相同的 键，而且这些条目会始终按某种数据布局【B树】进行组织，从而使你可以通过键在 Map 中高效地查找对应的值。简而言之，Map 就是一个查找表。
Rust 提供了两种 Map 范例：HashMap<K,V> 和 BTreeMap<K,V>。这两种范例共享很多相同的方法，区别在于它们如何组织条目以便进行快速查找。
- HashMap 会将键和值存储在哈希表中，因此它需要一个实现了 Hash 和 Eq 的 键范例 K，即用来求哈希与判定相等性的标准库特型。所有 键、值和缓存的哈希码都存储在一个分配在堆上的表中。添加条目最终会迫使 HashMap 分配一个更大的表并将所有数据移入此中。
- BTreeMap 会在树布局中按键的顺序存储条目，因此它需要一个实现了 Ord 的 键范例 K。BTreeMap 中存储条目的单元称为节点。BTreeMap 中的大多数节点仅包含键值对。非叶节点中也有一些空间用于存储指向子节点的指针。(20, ‘q’) 和 (30, ‘r’) 之间的指针会指向包含 20 和 30 之间所有键的子节点。添加条目通常需要将节点的一些现有条目向右平移，以保持它们的顺序，而且偶尔需要创建新节点。 真正的 BTreeMap 节点会有 11 个条目的空间，而不是 4 个。
Rust 标准库采用了 B 树而不是平衡二叉树，因为 B 树在今世硬件上速度更快。 两相对比，二叉树固然在每次搜刮时的比较次数较少，但 B 树具有更好的局部性（也就是说，内存访问被分组在一起，而不是分散在整个堆中）。这使得 CPU 缓存未命中的情况更为稀有。这会带来显著的速度提拔。
创建 Map 的几种方法：
- HashMap::new()（新建）和 BTreeMap::new()（新建） 创建新的空 Map。
- iter.collect()（收集） 可用于从键-值对创建和添补新的 HashMap 或 BTreeMap。iter 必须是 Iterator 范例的。
- HashMap::with_capacity(n)（自带容量） 创建一个新的空 HashMap，此中至少有 n 个条目的空间。与向量一样， HashMap 会将数据存储在分配在堆上的单块内存中，因此它们有容量及其相干 方法 hash_map.capacity()、hash_map.reserve(additional) 和 hash_map.shrink_to_fit()。BTreeMap 则没有这些。
处置惩罚键和值的焦点方法：
- map.len()（长度） 返回条目数。
- map.is_empty()（为空？） 如果 map 没有条目，则返回 true。
- map.contains_key(&key)（包含 key？） 如果 map 具有给定 key 的条目，则返回 true。
- map.get(&key)（按 key 获取） 在 map 中搜刮具有给定 key 的条目。如果找到匹配的条目，就返回 Some®，此中 r 是对相应值的引用。如果没找到，则返回 None。
- map.get_mut(&key)（按 key 获取，可变版） 与 map.get(&key) 类似，但此方法会返回对值的可变引用。 一样寻常来说，Map 允许对其存储的值进行可变访问，但不允许对键进行可变访问。你可以随意修改这些值，但键属于 Map 本身，需要确保它们不会改变，因 为条目是根据对应的键来组织的。对键进行当场修改是错误的。
- map.insert(key, value)（插入） 将条目 (key, value) 插入 map 并返回旧值（如果有的话）。返回范例 是 Option<T>。如果 Map 中已有 key 条目，则新插入的 value 会覆盖旧值。
- map.extend(iterable)（用 iterable 扩展） 遍历 iterable 中的 (K, V) 项并将这些键和值逐个插入 map 中。
- map.append(&mut map2)（从 map2 追加） 将所有条目从 map2 移动到 map 中。之后，map2 会变空。
- map.remove(&key)（按 key 移除值） 从 map 中查找并移除具有给定 key 的任何条目，如果存在，就返回刚刚移 除的值。返回范例是 Option。
- map.remove_entry(&key)（按 key 移除条目） 从 map 中查找并移除具有给定 key 的任何条目，返回刚刚移除的键和值 （如果有的话）。返回范例是 Option<(K, V)>。
- map.retain(test)（留下） 移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&K, &mut V) -> bool 的函数或闭包。对于 map 中的每个元素，都会调用 test(&key, &mut value)，如果此函数或闭包返回 false，则从 map 中移除并丢弃该元 素。 除了性能上有些许区别，此方法类似于：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<String,Fish> 上调用 fish_map.contains_key("conger")，即便 “conger” 不是确切的 String 范例也没问题，因为 String 实现了 Borrow<&str>[看做为]。
因为 BTreeMap 会始终保持其条目是根据键排序的，以是它支持一些额 外的操作：
btree_map.split_off(&key)（拆分出） 把 btree_map 一分为二。将键小于 key 的条目留在 btree_map 中。返回包含其他条目的新 BTreeMap。
条目
Entry 范例是为 HashMap 专门定义的一个枚举（BTreeMap 也类似）：
- // (in std::collections::hash_map)
- pub enum Entry<'a, K, V> {
- Occupied(OccupiedEntry<'a, K, V>),
- Vacant(VacantEntry<'a, K, V>)
- }
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();
- ...
对于这些条目，我们应该只进行一次查找，生成一个 Entry 值，然后将其用于 所有后续操作。
- let record = student_map.entry(name.to_string()).or_insert_with(Student::new);
- pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
遗憾的是，如果 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;
- }
- 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());
- }
- }
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);
- }
- 按值迭代（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 的顺序访问它们。
HashSet哈希Set & BTreeSetB树Set
Set 是用于快速进行元素存在性测试的聚集：Set 中值都是单一的 不会重复。
Set 就像一个只有键（而非键-值 对）的 Map。事实上，Rust 的两个 Set 范例 HashSet 和 BTreeSet 都是通过对 HashMap 和 BTreeMap 的浅层包装实现的
- HashSet::new()（新建）和 BTreeSet::new()（新建） 创建新 Set。
- iter.collect()（收集） 可用于从任意迭代器创建出新 Set。如果 iter 多次生成了同一个值，则重 复项将被丢弃。
- HashSet::with_capacity(n)（自带容量） 创建一个至少有 n 个值空间的空 HashSet。
HashSet 和 BTreeSet 有以下几个公共的根本方法：
- set.len()（长度） 返回 set 中值的数量。
- set.is_empty()（为空？） 如果 set 不包含任何元素，就返回 true。
- set.contains(&value)（包含） 如果 set 包含给定 value，就返回 true。
- set.insert(value)（插入） 向 set 中添加一个 value。如果新增了一个值，就返回 true；如果它先 前已是此 set 的成员，则返回 false。
- set.remove(&value)（移除） 从 set 中移除一个 value。如果移除了一个值，就返回 true；如果它之 前不是此 set 的成员，则返回 false。
- set.retain(test)（留下） 移除所有未通过给定测试的元素。test 参数是实现了 FnMut(&T) -> bool 的函数或闭包。对于 set 中的每个元素，此方法都会调用 test(&value)，如果它返回 false，则该元素将被从此 set 中移除并丢弃。 除了性能上略有差别，类似于： set = set.into_iter().filter(test).collect();
与 Map 一样，通过引用查找值的方法对于可以从 T 借用来的范例都是通用的。
对 Set 进行迭代
- 按值迭代（for v in set）会生成 Set 的成员并斲丧掉此 Set。
- 按共享引用（for v in &set）迭代会生成对 Set 成员的共享引用。
不支持通过可变引用迭代 Set。无法获取对存储在 Set 中的值的可变引用。
set.iter()（迭代器） 返回 set 中成员引用的迭代器。
与 HashMap 迭代器类似，HashSet 迭代器会以任意顺序生成它们的值。 BTreeSet 迭代器会按顺序生成值，就像一个排好序的向量。
当相等的值不完全相同时
两个内容相同的 String 值会将它们的字符存 储在内存中的不同位置：
- let s1 = "hello".to_string();
- let s2 = "hello".to_string();
- println!("{:p}", &s1 as &str); // 0x7f8b32060008
- println!("{:p}", &s2 as &str); // 0x7f8b32060010
- set.get(&value)（取值） 返回对等于 value 的 set 成员的共享引用（如果有的话）。返回范例是 Option<&T>。
- set.take(&value)（拿出值） 与 set.remove(&value) 类似，但此方法会返回所移除的值（如果有的 话）。返回范例是 Option<T>。
- set.replace(value)（更换为） 与 set.insert(value) 类似，但如果 set 已经包含一个等于 value 的 值，那么此方法就会更换并返回原来的值。返回范例是 Option<T>。
针对整个 Set 的运算
- set1.intersection(&set2)（交集） 返回同时出现在 set1 和 set2 中的值的迭代器。
- for student in brain_class.intersection(&rocket_class) {
- println!("{}", student);
- }
- 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 包含完全相同的一组值，那它们就是相等的。
哈希
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 {
- ...
- }
- struct Artifact {
- id: MuseumNumber,
- name: String,
- cultures: Vec<Culture>,
- date: RoughTime, ...
- }
- impl PartialEq for Artifact {
- fn eq(&self, other: &Artifact) -> bool {
- self.id == other.id
- }
- }
- impl Eq for Artifact {}
- use std::hash::{Hash, Hasher};
- impl Hash for Artifact {
- fn hash<H: Hasher>(&self, hasher: &mut H) {
- // 把哈希工作委托给藏品编号
- self.id.hash(hasher);
- }
- }
完成上述工作 允许我们创建一个 Artifact 的 HashSet：
- let mut collection = HashSet::<Artifact>::new();
利用自定义哈希算法
hash 方法是泛型的
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
- }
Rust 的默认哈希算法是闻名的 SipHash-1-3 算法。SipHash 的速度很快，而且非常善于镌汰哈希冲突。事实上，它也是一个加密算法：现在还没有已知的有效方法能刻意生成与 SipHash-1-3 冲突的值。只要每个哈希表利用不同且无法推测的 密钥，Rust 就可以安全地抵御一种称为 HashDoS 的拒绝服务攻击，在这种攻击 中，攻击者会故意利用哈希冲突来触发服务器的最坏性能。 不过，也许你的应用程序不需要此算法。如果要存储诸如整数或非常短的字符串之类的小型键，则可以实现更快的哈希函数，但代价是要牺牲 HashDoS 的安全性。fnv crate 实现了这样的一个算法，即 Fowler-Noll-Vo (FNV) 哈希。要实验 此算法，请将如下依赖添加到你的 Cargo.toml 中：
- [dependencies]
- fnv = "1.0"
- use fnv::{FnvHashMap, FnvHashSet};
- /// 使用默认FNV哈希器的`HashMap`
- pub type FnvHashMap<K, V> = HashMap<K, V, FnvBuildHasher>;
- /// 使用默认FNV哈希器的`HashSet`
- pub type FnvHashSet<T> = HashSet<T, FnvBuildHasher>;
自定义聚集
在 Rust 中创建一个新的自定义聚集范例和在其他语言中非常相似。通过组合语言提供的部件（布局体和枚举、标准聚集、Option、Box 等）来组织数据。
如果你习惯于在 C++ 中实现数据布局，利用裸指针、手动内存管理、定位放置 （placement）new 和显式析构函数调用来得到最佳性能，那么你无疑会发现这 在安全的 Rust 中处处受限。所有这些工具本质上都是不安全的。可以在 Rust 中 利用它们，但条件是要利用不安全的代码【unsafe块】。
但这些标准聚集的 API 让你尽可能少写unsafe代码。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。 |
