当前位置:网站首页>【Rust 笔记】14-集合(下)

【Rust 笔记】14-集合(下)

2022-07-05 05:50:00 phial03

集合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 中。vecVecDeque 也支持 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 实现标准的散列和相等性特型 HashEq

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

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

  • 创建映射的方法:

    • HashMap::new()BTreeMap::new() 创建新的空映射;
    • iter.collect():用于从键 — 值对创建和填充新的 HashMapBTreeMapiter 必须是一个 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)

    • 返回键为 keyEntry

    • 如果映射中没有,则返回一个空的 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):返回同时包含在 set1set2 中的所有值的迭代器。
    • &set1 & &set2:返回 set1set2 的交集。
    • set1.union(&set2):返回同时包含在 set1set2 种,或只在 set1set2 的值的迭代器。
    • &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):如果 set1set2 的子集,则返回 true
    • set1.is_superset(set2):如果 set1set2 的超集,则返回 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 程序设计》(吉姆 - 布兰迪、贾森 - 奥伦多夫著,李松峰译)第十六章
原文地址

原网站

版权声明
本文为[phial03]所创,转载请带上原文链接,感谢
https://blog.csdn.net/feiyanaffection/article/details/125575093