【Rust 笔记】14-集合（下）

集合14.3

14.3-VecDeque<T>

• Vec 可以实现在队列两端高效添加和移除元素。如果要把值保存在队列中间，Vec 的处理效率就相对较慢。

• 双端队列 std::collections::VecDeque<T>：实现了环形缓冲区，支持前端和后端的高效添加和移除操作。

  • deque.push_front(value)：在队列前面添加值。
  • deque.push_back(value)：在队列后面添加值。
  • deque.pop_front()：移除并返回队列前面的值，返回 Option<T>，队列为空时返回 None。
  • deque.pop_back：移除并返回队列后面的值，返回 Option<T>，队列为空时返回 None。
  • deque.front() 和 deque.back()：返回队列前端和后端元素的共享引用，返回 Option<T>，队列为空时返回 None。
  • deque.front_mut() 和 deque.back_mut：返回队列前端和后端元素的可修改引用引用，返回 Option<&mut T>。

• 队列在内存中不是连续存储的，并没有继承切片的所有方法。如果要在队列数据上执行向量和切片的操作，需要把 VecDeque 转换为 Vec，执行完操作后，再转换回去。

  • Vec<T> 实现了 From<VecDeque<T>>，因此 Vec::from(deque) 可以将队列转换为向量。

  • VecDeque<T> 实现了 From<Vec<T>>，因此 VecDeque::from(vec) 可以将向量转换为队列。

    // 通过指定元素来创建队列的方法
    use std::collections::VecDeque;
    
    let v = VecDeque::from(vec![1, 2, 3, 4]);
    

14.4-LinkedList<T>

• 链表的每个值都存储在独立的堆内存中，是一种存储序列值的方式。

• std::collections::LinkedList<T> 是双向链表

• 支持

  VecDeque
  

  的部分方法：

  • 操作序列前后端的方法；
  • 迭代器方法；
  • LinkedList::new() 等

• 支持把两个列表非常快速地组合到一起：list1.append(&mut list2)，把 list2 中的元素都转移到 list1 中。vec 和 VecDeque 也支持 append 方法，但是会把很多值从一个堆阵列转移到另一个。

14.5-BinaryHeap<T>

• BinaryHeap<T> 用于存储松散元素，最大值始终会冒泡到队列前端。

• 常用的方法：

  • heap.push(value)：向堆中添加值。
  • heap.pop()：从堆中移除并返回最大值。返回类型为 Option<T>，如果堆为空则返回 None。
  • heap.peek()：返回堆中最大值的引用。返回类型为 Option<&T>。

• 也支持 Vec 的部分方法：

  • BinaryHeap::new()；
  • heap.len()；
  • heap.is_empty()；
  • heap.capacity()；
  • heap.clear()；
  • heap.append(&mut heap2)。

• 实现了内置特型 Ord 的任何类型，都可以保存在 BinaryHeap 中。

• 常用于制作工作队列：

  • 定义一个任务结构体，基于优先级实现 Ord，让高优先级任务大于低优先级任务。然后，创建一个 BinaryHeap 保存所有带完成的任务。可以调用.pop() 方法始终返回接下来要做的最重要的任务。

  • 可以使用 while 循环消费：

    while let Some(task) = heap.pop() {
            
      handle(task);
    }
    

• BinaryHeap 是可迭代类型，也有自己的.iter() 方法，迭代器的顺序是任意的。

14.6-HashMap<K, V> 和 BTreeMap<K, V>

• 映射（map）是一种键 — 值对（称为条目）集合。

• HashMap<K, V> 把键和值保存在一个分配在堆上的散列表里，因此要求键的类型 K 实现标准的散列和相等性特型 Hash 和 Eq。

• BTreeMap<K, V> 按照键的顺序存储条目，总体为树形结构，因此要求键的类型 K 实现 Ord。

• Rust 的标准库使用 B 树，而不是平衡二叉树。二叉树每次搜索所必须的次数，比 B 树少；但搜索 B 树的领域性（locality）更好。B 树可以使得内存访问的集合在一起，而不是分散到整个堆上。这样 CPU 缓存就很少错失，从而显著提高速度。

• 创建映射的方法：

  • HashMap::new() 和 BTreeMap::new() 创建新的空映射；
  • iter.collect()：用于从键 — 值对创建和填充新的 HashMap 或 BTreeMap。iter 必须是一个 Iterator<Item=(K, V)> 的迭代器。
  • HashMap::with_capacity(n)：可以创建新的空散列表，至少能容纳 n 个条目。
  • HashMap 单独支持容量相关的方法：hash_map.capacity()、hash_map.reserve(additional) 和 hash_map.shrink_to_fit()。

• HashMap
  

  和

  BTreeMap
  

  共同支持以下核心方法：

  • map.len()：返回条目数量。
  • map.is_empty()：在 map 没有条目时返回 true。
  • map.contains_key(&key)：在映射又条目的键为 key 时返回 true。
  • map.get(&key)：搜索 map 中具有给定 key 的条目。如果找到匹配的条目，返回 Some(r)，其中 r 是相对应的引用。否则返回 None。
  • map.get_mut(&key)：功能与上同，但是返回对值的可修改引用。对于值可以随意修改，但键鼠鱼映射本身，不能修改。
  • map.insert(key, value)：向 map 中插入条目 (key, value)。如果映射中已经存在为 key 的条目，则会插入新的值 value，覆盖原来的值。如果覆盖了原来的值，会返回原来的值，返回类型为 Option<V>。
  • map.extend(iterable)：迭代 iterable 的 (K, V) 条目，并将每个键 — 值对插入 map 中。
  • map.append(&mut map2)：将 map2 的所有条目转移到 map 中，map2 会变为空。
  • map.remove(&key)：查找并移除 map 中键为 key 的条目。如果有值被移除，则返回移除的值。返回类型为 Option<V>。
  • map.clear()：移除所有条目。
  • map[&key]：用方括号语法查询映射。如果不存在为 key 的条目，则会诧异，类似数组访问越界。

• BTreeMap<K, V>
  

  因为可以按键排序并存储条目，还支持

  btree_map.split_off(key)
  

  ：

  • 可以将 btree_map 一分为二；
  • 键小于 key 的条目会留在 btree_map 中。
  • 返回的新 BTreeMap<K, V> 包含其他条目。

14.6.1 - 条目

• Entry 条目类型：用于消除多余的映射查找。

  let record = student_map.entry(name.to_string()).or_insert_with(Student);
  

  • student_map.entry(name.to_string) 返回的 Entry 值类似于指向映射中某个位置的可修改引用；

  • 如果引用为空，则.or_insert_with() 方法会插入一个新的 Student。

  • Entry 是一个枚举类型：

    // std::collections::hash_map
    pub enum Entry<'a, K: 'a, V: 'a> {
            
      Occupied(OccupiedEntry<'a, K, V>),
      Vacant(VacantEntry<'a, K, V>)
    }
    

• 创建 Entry 值的方法：map.entry(key)。

  • 返回键为 key 的 Entry。

  • 如果映射中没有，则返回一个空的 Entry。

  • 接收自己的可修改引用，返回生命期匹配的 Entry：

    pub fn entry<'a>(&'a mut self, key: K) -> Entry<'a, K, V>
    

  • 如果映射的键是 String 类型，则不能给这个方法传入 &str 类型的引用。此时要给.entry() 方法传入真正的 String。

• 填充空条目的方法：

  • 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;   // count的类型为&mut usize。
    }
    

  • map.entry(key).or_insert_with(default_fn)：功能与上同，但是在需要创建新条目时会调用 default_fn() 函数，以产生默认值。如果 map 中已经存在了为 key 的条目，则不会用到 default_fn()。

    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());
      }
    }
    

14.6.2 - 映射迭代

• HashMap 迭代器支持以任意顺序访问映射的条目；BTreeMap 迭代器，必须按键顺序访问条目。
• 映射的迭代有以下方式：
  • 按值迭代（for (k, v) in map）：产生 (K, V) 对。这样会消费映射。
  • 按共享引用迭代（for (k, v) in &map）：产生 (&K, &V) 对。
  • 按可修改引用迭代（for (k, v) in &mut map）：产生 (&K, &mut v) 对。
• 映射的迭代有以下常用方法：
  • .iter() 和.iter_mut()：返回迭代器且产生值引用的方法；
  • map.keys()：返回产生键引用的迭代器。
  • map.values()：返回产生值引用的迭代器。
  • map.values_mut()：返回产生可修改值引用的迭代器。

14.7-HashSet<T> 和 BTreeSet<T>

• Set 集：支持快速测试成员关系而组织值。集中永远不会包含同一个值的多个副本。

  let b1 = large_vector.contains("needle");  // 在向量中查找元素比较慢，需要检查每个元素
  let b2 = large_hash_set.contains("needle"); // 在集中查找元素比较快，支持散列查找
  

• 集类似于只有键的映射。HashSet<T> 和 BTreeSet<T> 都是以的包装类型形式实现的：

  • HashSet::new() 和 BTreeSet::new() 创建新集。
  • iter.collect() 可用于从任何迭代器创建新集。如果产生了重复值，则重复的值会被清除。
  • HashSet::with_capacity(n) 创建空的 HashSet，至少容纳 n 个值。

• HashSet<T> 和 BTreeSet<T> 共有的方法：

  • set.len()：返回 set 中值的数量。
  • set.is_empty()：在集中不包含元素值返回 true。
  • set.contains(&value)：在集中包含给定值 value 时返回 true。
  • set.insert(value)：向集中添加 value。如果添加成功就返回 true，如果集里面已经存在同样的值就返回 false。
  • set.remove(&value)：从集里面移除 value。如果移除成功就返回 true。如果没有这个值，则返回 false。

• 与映射类似，按引用查询值的方法也是通用的，只要可以从 T 借用到该类型。

14.7.1 - 集迭代

• 迭代集有两种方式：
  • 按值迭代：for v in set 产生集的成员，并且消费集。
  • 按共享引用迭代：for v in &set 产生集成员的共享引用。
• 不支持按可修改引用迭代集。即不能从集中取得值的可修改引用。set.iter() 返回迭代器，产生 set 成员的引用。
• HashSet 迭代器支持以任意顺序访问映射的条目；BTreeSet 迭代器，必须按键顺序访问条目。

14.7.2 - 相等的值不相同 —— 在内存中存储不同位置

取得存储在集中的实际值的方法：这些方法都返回 Option，如果 set 不包含匹配的值，则返回 None。

• set.get(&value)：返回 set 中等于 value 的成员的共享引用，返回类型是 Option<&T>。
• set.take(&value)：类似于 set.remove(&value)，但返回移除的值，返回类型是 Option<T>。
• set.replace(value)：类似于 set.insert(value)，但如果 set 中已经包含等于 value 的值，那么就返回原来的值。返回类型是 Option<T>

14.7.3 - 整集操作

• 对整个集操作的方法：
  • set1.intersection(&set2)：返回同时包含在 set1 和 set2 中的所有值的迭代器。
  • &set1 & &set2：返回 set1 和 set2 的交集。
  • set1.union(&set2)：返回同时包含在 set1 和 set2 种，或只在 set1 或 set2 的值的迭代器。
  • &set1 | &set2：返回包含这两个集中所有值的新集。
  • set1.difference(&set2)：返回包含在 set1 但不包含在 set2 中的值的迭代器。
  • &set1 - &set2：返回包含在 set1 但不包含在 set2 的所有这些值的新集。
  • set1.symmetric_difference(&set2)：返回只包含在 set1 中，或只包含在 set2 中，但不同时包含在两个集中的值的迭代器。
  • &set1 ^ &set2：返回只包含在 set1 中，或只包含在 set2 中，但不同时包含在两个集中的值的新集。
• 测试集与集之间关系的 3 种方法：
  • set1.is_disjoint(set2)：如果交集为空，则返回 true。
  • set1.is_subset(set2)：如果 set1 是 set2 的子集，则返回 true。
  • set1.is_superset(set2)：如果 set1 是 set2 的超集，则返回 true。
• 集也支持 == 和 != 的相等性测试：两个集包相同的值，那么它们相等。

14.8 - 散列

14.8.1 - 概述

• std::hash::Hash 是标准库中可散列类型的特型。

• 一个值无论保存在哪里，或者怎么指向它，都应该有相同的散列码。

  • 引用与它指向的值有相同的散列码；
  • Box 与装箱的值有相同的散列码；
  • 向量 vec 与包含所有其数据的切片 &ved[..] 有相同的散列码；
  • String 与引用相同字符的 &str 有相同的散列码。

• 结构体和枚举默认没有实现 Hash，但可以派生一个实现：

  #[derive(Clone, PartialEq, Eq, Hash)]
  enum MN {
        
    ...
  }
  

• 如果手工为一个类型实现了 PartialEq，那么必须为它实现 Hash。

14.8.2 - 使用自定义散列算法

• hash 方法是泛型的。

• 计算散列码的完整协议：

  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(); // 算法开始
    value.hash(&mut hasher);                 // 传入数据
    hasher.finish()                          // 算法完成，产生u64值。
  }
  

• Rust 默认使用 SipHash-1-3 算法作为散列算法。只要有不同之处，每个散列表就会使用无法预测的键。因此可以防止 HashDoS 的拒绝服务攻击，即攻击者故意使用散列冲突来出发服务器中最差的性能。

• 如果为了想要更快的散列实现，而牺牲安全性，那么可以使用 fnv 包实现的 Fowler-Noll-Vo 散列算法。

  // 在Cargo.toml中添加：
  [dependencies]
  fnv = "1.0"
  
  // 导入映射和散列类型
  extern crate fnv;
  use fnv::{
        FnvHashMap, FnvHashSet}; // 代替HashMap和HashSet。
  

14.9 - 其他集合

Rust 支持在 unsafe 块中实现 C++ 的数据结构：原始指针、手工内存管理、放置 new、显示调用析构函数。

---

详见《Rust 程序设计》（吉姆 - 布兰迪、贾森 - 奥伦多夫著，李松峰译）第十六章
原文地址