Rust·算法·二叉树

 

二叉树 前中后序遍历 最大宽度 判断完全、平衡、搜索、满二叉树 Rust的HashMap特性

  • 二叉树
    • 前中后序遍历
    • 最大宽度
    • 判断完全、平衡、搜索、满二叉树
  • Rust的HashMap特性

反序列化

前序遍历的字符串为:”1_2_4_N_N_5_N_N_3_6_N_N_7_N_N”, 创建一棵二叉树

type TreeLink = Option<Rc<RefCell<TreeNode>>>;

fn create_bitree_cursive(node_values: &mut VecDeque<&str>) -> TreeLink {
    let val = node_values.pop_front().unwrap();
    if val == "N" {
        return None;
    }

    let mut node: TreeNode = TreeNode::new(val.parse::<i32>().unwrap());
    node.borrow_mut().left = create_bitree_cursive(node_values);
    node.borrow_mut().right = create_bitree_cursive(node_values);
    Some(Rc::new(RefCell::new(node)))
}

/* 前序遍历的方式创建二叉树 */
fn create_bitree(s: &str) -> TreeLink {
    let mut node_values: VecDeque<&str> = s.split('_').collect();
    create_bitree_cursive(&mut node_values)
}

二叉树

  • 递归序
    • 递归过程中每个节点都会顺序的出入3次
  • 前序
    • 先进入头,再进左子树,再进右子树
  • 中序
    • 先左、再中、再右
  • 后序
    • 先左、再右、再头
    • 先右、再左、再头

前序遍历

递归方式

fn preorder_cursive(root: TreeLink, res: &mut Vec<i32>) {
    if root.is_none() {
        return;
    }

    if let Some(node) = root {
        res.push(node.borrow().elem);
        preorder_cursive(node.borrow().left.clone(), res);
        preorder_cursive(node.borrow().right.clone(), res);
    }
}

fn preorder_traversal(root: TreeLink) {
    let mut res: Vec<i32> = Vec::new();
    preorder_cursive(root, &mut res);
    println!("res: {:?}", res);
}

非递归方式

  • 算法
    • 每次栈弹出一个节点
    • 打印这个节点
    • 先右、再左节点入栈
    • 循环
  • 实现代码

      fn preorder_traversal2(root: &TreeLink) -> Vec<i32> {
          if root.is_none() {
              return vec![];
          }
    
          let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
          let mut res: Vec<i32> = vec![];
    
          stack.push(root.clone().unwrap());
          while let Some(cur) = stack.pop() {
              res.push(cur.borrow().elem);
              if let Some(node) = cur.borrow().right.clone() {
                  stack.push(node);
              }
              if let Some(node) = cur.borrow().left.clone() {
                  stack.push(node)
              }
          }
          res
      }
    

中序遍历

  • 算法
    • 每棵左子树进栈
    • 依次弹出
    • 再将弹出的节点的右侧左子树进栈
  • 代码实现

      fn inorder_uncursive(root: &TreeLink) -> Vec<i32> {
          let mut res: Vec<i32> = vec![];
          if root.is_none() {
              return res;
          }
    
          let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
          let mut head = root.clone();
          while !stack.is_empty() || head.is_some() {
              if let Some(node) = head {
                  stack.push(node.clone());
                  head = node.borrow().left.clone();
              } else {
                  if let Some(node) = stack.pop() {
                      res.push(node.borrow().elem);
                      head = node.borrow().right.clone();
                  }
              }
          }
    
          res
      }
    

后序遍历

  • 算法流程
    • 头节点入栈
    • 栈弹出节点
    • 先左再右/先右再左
    • 循环
  • 先左后右的代码实现

      fn posorder1_uncursive(root: &TreeLink) -> Vec<i32> {
          let mut res: Vec<i32> = vec![];
          if root.is_none() {
              return res;
          }
          // 这里使用TreeLink的类型,代码更简单,但算法不直观 
          let mut stack: Vec<TreeLink> = vec![];
          let mut support: Vec<TreeLink> = vec![];
          stack.push(root.clone());
          while !stack.is_empty() {
              if let Some(Some(node)) = stack.pop() {
                  support.push(Some(node.clone()));
                  stack.push(node.borrow().left.clone());
                  stack.push(node.borrow().right.clone());
              }
          }
          while !support.is_empty() {
              if let Some(Some(node)) = support.pop() {
                  res.push(node.borrow().elem)
              }
          }
    
          res
      }
    
  • 先右后左的代码实现

      fn posorder_uncursive2(root: &TreeLink) -> Vec<i32> {
          let mut res: Vec<i32> = vec![];
          if root.is_none() {
              return res;
          }
          // 这里用Rc<RefCell<>>类型,代码繁琐
          let mut stack: Vec<Rc<RefCell<TreeNode>>> = vec![];
          let mut support: Vec<Rc<RefCell<TreeNode>>> = vec![];
          stack.push(root.clone().unwrap());
          while !stack.is_empty() {
              if let Some(node) = stack.pop() {
                  support.push(node.clone());
                  if let Some(left_node) = node.borrow().right.clone() {
                      stack.push(left_node);
                  }
                  if let Some(right_node) = node.borrow().left.clone() {
                      stack.push(right_node);
                  }
              }
          }
          while let Some(node) = support.pop() {
              res.push(node.borrow().elem)
          }
    
          res
      }
    

宽度优先遍历

  • 算法
    • 用队列
    • 先进头节点
    • 弹出节点就打印
    • 再把它的节点先左后右入队
    • 循环
  • 算法实现

      fn width_traversial(root: &TreeLink) -> Vec<i32> {
          let mut res: Vec<i32> = vec![];
          let mut queue: VecDeque<TreeLink> = VecDeque::new();
    
          queue.push_back(root.clone());
          while !queue.is_empty() {
              if let Some(Some(node)) = queue.pop_front() {
                  res.push(node.borrow().elem);
                  queue.push_back(node.borrow().left.clone());
                  queue.push_back(node.borrow().right.clone());
              }
          }
    
          res
      }
    

求二叉树的最大宽度

用HashMap

  • 数据结构

      type TreeLink = Option<Box<TreeNode>>;
      #[derive(Debug, Hash, PartialEq, Eq)]
      struct TreeNode {
          elem: i32,
          left: TreeLink,
          right: TreeLink,
      }
    
    • 由于RefCell<T>不能实现Hash特性
    • 所以使用了Box<T>的方案
  • 算法
    • 初始状态
      • 当前统计的层cur_level = 1
      • 最大宽度 max_level_nodes = 0
      • 当前层宽度 cur_level_nodes = 0
      • HashMap<节点, 此节点对应的层>
      • 队列queue<节点>
      • 将root节点入队列
      • 将root节点和它对应的层1入HashMap.insert(root, 1)
    • 队列弹出节点
    • 从HashMap中取得此节点对应的层
    • 如果当前层 == 节点对应层
      • 当前层宽度加上1
    • 如果当前层 != 节点对应层
      • 说明节点已经到下层
      • 当前层+=1
      • 统计最大宽度
      • 当前层宽度 = 1
    • 把节点的左、右非空节点入队列
    • 把节点的左、右非空节点对应的层入HashMap
  • 算法实现

      fn max_width_hash(root: &TreeLink) -> i32 {
          let mut map: HashMap<Option<&Box<TreeNode>>, usize> = HashMap::new();
          let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
          let mut cur_level: usize = 1;
          let mut cur_level_nodes = 0;
          let mut max_level_nodes: i32 = 0;
          queue.push_back(root.as_ref());
          map.insert(root.as_ref(), 1);
    
          while let Some(link) = queue.pop_front() {
              let node_level = *map.get(&link).unwrap();
              if let Some(cur) = link {
                  if node_level == cur_level {
                      cur_level_nodes += 1;
                  } else {
                      max_level_nodes = max(max_level_nodes, cur_level_nodes);
                      cur_level_nodes = 1;
                      cur_level += 1;
                  }
                  if cur.left.is_some() {
                      map.insert(cur.left.as_ref(), cur_level + 1);
                      queue.push_back(cur.left.as_ref());
                  }
                  if cur.right.is_some() {
                      map.insert(cur.right.as_ref(), cur_level + 1);
                      queue.push_back(cur.right.as_ref());
                  }
              }
          }
    
          max(max_level_nodes, cur_level_nodes)
      }
    

不用HashMap

  • 算法
    • 队列弹出节点
    • 当前节点是不是本层最后一个节点
      • 不是:增加本层节点数
      • 是:更新最大宽度,更新下一层最后一个节点
  • 算法实现

      fn max_width_unhash(root: &TreeLink) -> i32 {
          let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
          let mut max_level_nodes = 0;
          let mut cur_level_nodes = 0;
          let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
          let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
          queue.push_back(root.as_ref());
    
          while let Some(Some(node)) = queue.pop_front() {
              cur_level_nodes += 1;
              if node.left.is_some() {
                  queue.push_back(node.left.as_ref());
                  next_end = node.left.as_ref().unwrap();
              }
              if node.right.is_some() {
                  queue.push_back(node.right.as_ref());
                  next_end = node.right.as_ref().unwrap();
              }
    
              if node == cur_end {
                  max_level_nodes = max(max_level_nodes, cur_level_nodes);
                  cur_level_nodes = 0;
                  cur_end = next_end;
              }
          }
    
          max_level_nodes
      }
    
    

二叉树的属性判断

判断是否是搜索二叉树

  • 搜索二叉树
    • 左节点 < root
    • 右节点 > root
  • 算法流程
    • 中序遍历一定是升序
  • 递归算法实现

      fn check_bts(root: Option<&Box<TreeNode>>) -> BtsInfo {
          if let Some(node) = root {
              let left = check_bts(node.left.as_ref());
              if !left.isbts || left.max_val >= node.elem {
                  return BtsInfo::new(false);
              }
    
              let right = check_bts(node.right.as_ref());
              if !right.isbts || node.elem >= right.min_val {
                  return BtsInfo::new(false);
              } else {
                  let mut info = BtsInfo::new(true);
                  info.min_val = min(node.elem, left.min_val);
                  info.max_val = max(node.elem, right.max_val);
                  return info;
              }
          } else {
              BtsInfo::new(true)
          }
      }
    
      fn is_bts(root: &TreeLink) -> bool {
          let info = check_bts(root.as_ref());
          info.isbts
      }
    

判断是否是完全二叉树

  • 完全二叉树
    • 完整齐全的二叉树
    • 每一层都是全的
    • 最后一层也是先有左子再有右子
  • 算法流程
    • 宽度优先遍历
    • 若出现无左有右则不是
    • 满足上面条件的情况下
      • 若出现左右子不全
      • 则后面的节点必须为叶子节点
  • 算法实现

      fn is_cbt_uncursive(root: &TreeLink) -> bool {
          let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
          queue.push_back(root.as_ref());
          let mut must_leaf: bool = false;
    
          while let Some(Some(node)) = queue.pop_front() {
              if node.left.is_none() && node.right.is_some() {
                  return false;
              }
              if node.left.is_some() && node.right.is_none() {
                  must_leaf = true;
              }
              if must_leaf && !is_leaf(node) {
                  return false;
              }
    
              queue.push_back(node.left.as_ref());
              queue.push_back(node.right.as_ref());
          }
    
          true
      }
    

判断是否是满二叉树

  • 满二叉树
    • 树的最大深度deep和节点数N有关系:deep = 2^N - 1
  • 递归算法实现

      fn fbts_cursive(root: Option<&Box<TreeNode>>) -> FbtsInfo {
          if let Some(node) = root {
              let left = fbts_cursive(node.left.as_ref());
              let right = fbts_cursive(node.right.as_ref());
    
              FbtsInfo {
                  nodes: left.nodes + right.nodes + 1,
                  deep: max(left.deep, right.deep) + 1,
              }
          } else {
              FbtsInfo { nodes: 0, deep: 0 }
          }
      }
    
      fn is_fbts_cursive(root: &TreeLink) -> bool {
          if root.is_none() {
              return true;
          }
          let info = fbts_cursive(root.as_ref());
          info.nodes == (1 << info.deep) - 1
      }
    
  • 非递归算法实现

      fn is_fbts_uncursive(root: &TreeLink) -> bool {
          let mut queue: VecDeque<Option<&Box<TreeNode>>> = VecDeque::new();
          let mut cur_end: &Box<TreeNode> = root.as_ref().unwrap();
          let mut next_end: &Box<TreeNode> = root.as_ref().unwrap();
          let mut deep: u32 = 0;
          let mut total_nodes: i32 = 0;
          queue.push_back(root.as_ref());
    
          while let Some(Some(node)) = queue.pop_front() {
              total_nodes += 1;
              if node.left.is_some() {
                  queue.push_back(node.left.as_ref());
                  next_end = node.left.as_ref().unwrap();
              }
              if node.right.is_some() {
                  queue.push_back(node.right.as_ref());
                  next_end = node.right.as_ref().unwrap();
              }
    
              if node == cur_end {
                  cur_end = next_end;
                  deep += 1;
              }
          }
    
          total_nodes == (1 << deep) - 1
      }
    

判断是否是平衡二叉树

  • 平衡二叉树
    • 左、右子树都是平衡的
    • 左子树与右子树的高度差不超过1
  • 算法实现

      struct BlInfo {
          is_balance: bool,
          deep: i32,
      }
    
      fn balance_cursive(root: Option<&Box<TreeNode>>) -> BlInfo {
          if let Some(node) = root {
              let left = balance_cursive(node.left.as_ref());
              let right = balance_cursive(node.right.as_ref());
              BlInfo {
                  deep: max(left.deep, right.deep) + 1,
                  is_balance: left.is_balance && right.is_balance && (left.deep - right.deep).abs() < 2,
              }
          } else {
              BlInfo {
                  deep: 0,
                  is_balance: true,
              }
          }
      }
    
      fn is_balance(root: &TreeLink) -> bool {
          let info = balance_cursive(root.as_ref());
          info.is_balance
      }
    

寻找最近的公共祖先节点

  • 算法1
    • 将二叉树中每个结点的祖先节点都放到HashMap中
    • 针对node1收集从它到根节点的父节点
    • 针对node2查看它的父节点是否有node1父节点的共同节点
  • 算法1实现

      fn find_lca<'a>(
      root: &'a TreeLink,
      node1: TreeNodeLink,
      node2: TreeNodeLink,
      ) -> Option<&'a Box<TreeNode>> {
          let mut lca: TreeNodeLink = None;
          let mut fmap: HashMap<TreeNodeLink, TreeNodeLink> = HashMap::new();
          let mut set: HashSet<TreeNodeLink> = HashSet::new();
          fmap.insert(root.as_ref(), root.as_ref());
          // 创建所有节点的父节点集合{子节点:父节点}
          get_fmap(root.as_ref(), &mut fmap);
          // 将所有node1的父节点收集到set中
          let mut node = node1;
          while let Some(&Some(father)) = fmap.get(&node) {
              if father != root.as_ref().unwrap() {
                  set.insert(Some(father.clone()));
                  node = Some(father);
              } else {
                  break;
              }
          }
    
          // 检查node2的所有父节点是不是在set中,是则找到共同最低父节点
          node = node2;
          while let Some(&Some(father)) = fmap.get(&node) {
              if father == root.as_ref().unwrap() {
                  break;
              }
              if !set.contains(&Some(father)) {
                  node = Some(father);
              } else {
                  lca = Some(father);
                  break;
              }
          }
    
          lca
      }
    
  • 算法2递归实现

      fn find_lca_cursive<'a>(
          root: TreeNodeLink<'a>,
          node1: TreeNodeLink<'a>,
          node2: TreeNodeLink<'a>,
      ) -> TreeNodeLink<'a> {
          if root.is_none() || root == node1 || root == node2 {
              return root;
          }
          if let Some(node) = root {
              // 左子树有节点、右子树有节点
              let left = find_lca_cursive(node.left.as_ref(), node1, node2);
              let right = find_lca_cursive(node.right.as_ref(), node1, node2);
              match (left, right) {
                  (Some(_), Some(_)) => return root,
                  (Some(l), _) => return Some(l),
                  (None, Some(r)) => return Some(r),
                  (None, None) => return None,
              }
          }
          None
      }
    

寻找一个节点的后继节点

  • 后继节点
    • 中序遍历中,排在一个节点后面的节点是后继节点
    • 排在一个节点的前面节点是前趋节点
    • 中序遍历: DBEAFCG->Null
  • 如果节点的结构如下,能否缩短找后继节点的复杂度

      class Node {
          int elem;
          Node left;
          Node right;
          Node parent;
      }
    
  • 算法流程
    • 如果节点x有右树
      • x的后继是右树的最左叶节点
    • 如果节点x无右树
      • 向上看是否是父节点的左孩子
      • 不是继续向上找
      • 是则后继就是这个父节点
    • 整棵树最后一个节点特殊
  • 算法伪代码实现

      // 找最左侧节点
      fn left_leaf(root: TreeNodeLink) -> TreeNodeLink {
          if let Some(node) = root {
              while node.left.is_some() {
                  node = node.left.as_ref().unwrap();
              }
              Some(node)
          } else {
              None
          }
      }
    
      fn node_successor(head: TreeNodeLink) -> TreeNodeLink {
          if let Some(node) = head {
              // 如果节点有右子树,后继节点为右子树最左侧节点
              if node.right.is_some() {
                  return left_leaf(node.right.as_ref());
              }
    
              // 如果没有右子树,当前节点是父节点的右孩子,继续向上找
              let mut parent = node.parent;
              while parent.is_some && parent.left != node {
                  node = parent;
                  parent = node.parent;
              }
              // 当parent是空时,说明node是整棵树最右侧结点,没有后继节点
              return parent;
          } else {
              None
          }
      }
    

将长条纸对折N次,打印凹凸顺序

折纸就是一棵二叉树,所有凸节点的左节点为凸,右节点为凹

  • 算法
    • 中序遍历
  • 算法实现

      fn print_cursive(curlevel: i32, level: i32, down: bool) {
          if curlevel > level {
              return;
          }
          print_cursive(curlevel + 1, level, true);
          if down {
              print!("凹");
          } else {
              print!("凸");
          }
          print_cursive(curlevel + 1, level, false)
      }
    
      // 对折n次
      fn print_all_folds(n: i32) {
          print_cursive(1, n, true);
      }
    

HashMap

要求键值实现Eq和Hash特性,尽管这经常可以通过使用#[derive(PartialEq, Eq, Hash)]实现。如果你自己实现了这些,重要的是以下属性成立:

k1 == k2 => hash(k1) == hash(k2)

换句话说,如果两个键相等,它们的哈希值也必须相等

自定义的key类型需要Eq和Hash特性,Eq又需要PartialEq

ParitalEq和Eq

Eq完成的是相等和不相等的判断,ParitalEq可以实现A和B是否相等的判断,但不能与自己比较,因为NaN != NaN;而Eq则是表示可以和自己进行相等判断(有点类似异或交换的感觉,通过异或交换a、b的前提是他们在不同的内存空间中,否则就会失效)

通过#[driver(ParitalEq, Eq)]系统会自动实现相等性,它是把结构体中所有字段如果相等,则判定相等

Hash 特性

pub trait Hash {
    fn hash<H>(&self, state: &mut H)
    where H: Hasher;

    fn hash_slice<H>(data: &[Self], state: &mut H)
    where H: Hasher,
    { ... }
}

一个可散列的类型:

实现Hash的类型能够用Hasher的一个实例进行散列。

如何实现Hash特性

系统自动实现

如果所有字段都实现了Hash,你可以用#[derive(Hash)]来派生Hash。产生的哈希值将是在每个字段上调用哈希值的组合。

#[derive(Hash)]
struct Rustacean {
    name: String,
    country: String,
}

实现自己的Hash特性

use std::hash::{Hash, Hasher};

struct Person {
    id: u32,
    name: String,
    phone: u64,
}

impl Hash for Person {
    // 将state此值提供给给定的散列器 Hasher
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.id.hash(state);
        self.phone.hash(state);
    }
}
  • fn hash<H>(&self, state: &mut H)
    • 将state此值提供给给定的散列计算器Hasher
    • 使用

      use std::collections::hash_map::DefaultHasher;
      use std::hash::{Hash, Hasher};
      
      let mut hasher = DefaultHasher::new();
      7920.hash(&mut hasher);
      println!("Hash is {:x}!", hasher.finish());
      
  • fn hash_slice<H>(data: &[Self], state: &mut H)
    • 将Self这种类型的切片输入给定的散列器
    • 这个方法是作为一种便利,但它的实现也明确地没有被指定。
    • 它并不保证等同于对hash的重复调用,Hash的实现应该记住这一点
    • 如果切片在PartialEq的实现中没有被当作一个整体单元,就应该自己调用hash。
    • 例如
      • 一个VecDeque的实现可能会天真地调用as_slices
      • 然后在每个slice上进行hash_slice
      • 但这是错误的
      • 因为这两个slice可以通过调用make_contiguous来改变Key的值
      • 而不会影响PartialEq的结果
      • 由于这些切片没有被当作单一的单位
      • 而是一个更大的deque的一部分
      • 所以这个方法不能使用
    • 使用

      let mut hasher = DefaultHasher::new();
      let numbers = [6, 28, 496, 8128];
      Hash::hash_slice(&numbers, &mut hasher);
      println!("Hash is {:x}!", hasher.finish());
      

其中Hasher也是一个特性,它是一个用于散列任意字节流的特性。Hasher的实例通常代表在散列数据时改变的状态。

Hasher提供了一个相当基本的接口,用于检索生成的哈希值(用finish),以及将整数和字节切片写进实例(用writewrite_u8等)。大多数情况下,Hasher实例是与Hash特性一起使用的。

Hasher主要有两个方法:

pub trait Hasher {
    // 返回到目前为止所写数据的哈希值
    fn finish(&self) -> u64;
    // 将一些数据写入哈希器
    fn write(&mut self, bytes: &[u8]);
}

Hasher Hash计算器的使用方法:

let mut hasher = DefaultHasher::new();
hasher.write_u32(1989);
hasher.write_u8(11);
hasher.write_u8(9);
hasher.write(b"Huh?");
println!("Hash is {:x}!", hasher.finish());

Cell

共享的可变容器。 rust内存安全基于以下规则:给定对象T,只能有以下之一:

  • 对对象有几个不可变的引用(&T)(也被称为别名)。
  • 对象有一个可变引用(&mut T)(也称为可变性)。

这是由Rust编译器强制执行的。然而,在有些情况下,这个规则不够灵活。有时需要对一个对象有多个引用,但又要对其进行突变。

可共享的可变容器的存在是为了允许以可控的方式进行修改,甚至在存在别名的情况下。Cell和RefCell都允许以单线程的方式来做这个。然而,Cell和RefCell都不是线程安全的(它们没有实现Sync)。如果你需要在多个线程之间进行别名和变异,可以使用Mutex、RwLock或原子类型。

Cell和RefCell类型的值可以通过共享引用(即常见的&T类型)进行变异,而大多数Rust类型只能通过唯一的(&mut T)引用进行变异。我们说Cell和RefCell提供了 "内部可变性",而典型的Rust类型则表现为 "继承的可变性"。

Cell类型有两种风格。Cell和RefCell。Cell通过将值移入和移出Cell来实现内部可变性。要使用引用而不是值,必须使用RefCell类型,在变异之前获得一个写锁。Cell提供了检索和改变当前内部值的方法。

  • 对于实现Copy的类型,get方法检索当前的内部值
  • 对于实现Default的类型,take方法用Default::default()替换当前的内部值并返回替换后的值
  • 对于所有的类型,替换方法替换当前的内部值并返回替换后的值,into_inner方法消耗Cell并返回内部值。此外,set方法替换了内部值,放弃了被替换的值

RefCell使用Rust的生命期来实现 "动态借用",在这个过程中,人们可以要求对内部值进行临时的、独占的、可改变的访问。RefCell的借用是在 "运行时 "跟踪的,而不像Rust的本地引用类型那样,完全是在编译时静态跟踪的。因为RefCell的借用是动态的,所以有可能试图借用一个已经被可变借用的值;当这种情况发生时,会导致线程恐慌。

更常见的继承可变性,即一个人必须有唯一的访问权才能变异一个值,这是一个关键的语言元素,使Rust能够强烈地推理指针别名,静态地防止崩溃的错误。正因为如此,继承的可变性是首选,而内部可变性是最后的手段。由于Celll类型可以在不允许的地方进行变异,所以在某些情况下,内部变异可能是合适的,甚至是必须使用的,比如说

  • 在不可变的东西的 “内部 “引入可变性
  • 逻辑上不可变的方法的实现细节。
  • 克隆的变异实现

在不可变的东西内部引入了可变性

许多共享的智能指针类型,包括Rc和Arc,提供了可以在多方之间克隆和共享的容器。因为所包含的值可能是多重aliased的,它们只能用&,而不是&mut来借用。如果没有Cell,就根本不可能对这些智能指针内的数据进行变异。

那么,在共享指针类型内放置一个RefCell来重新引入可变性是非常常见的。

use std::cell::{RefCell, RefMut};
use std::collections::HashMap;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    // 创建一个新块来限制动态借用的范围
    {
        let mut map: RefMut<_> = shared_map.borrow_mut();
        map.insert("africa", 92388);
        map.insert("kyoto", 11837);
        map.insert("piccadilly", 11826);
        map.insert("marbles", 38);
    }

    // 如果前面没有新建代码块,这里就会出问题
    // 这就是使用`RefCell'的主要危害
    let total: i32 = shared_map.borrow().values().sum();
    println!("{}", total);
}

逻辑不可变方法的实现细节

偶尔,我们可能不希望在API中暴露出 “引擎盖 “下正在发生的变异。这可能是因为逻辑上的操作是不可变的,但是例如缓存迫使实现方法执行突变;或者是因为你必须使用突变来实现一个最初定义为取自&self的特征方法。