iT邦幫忙

2025 iThome 鐵人賽
DAY 20
0
Rust

用刷題來練RUST系列 第 20 篇

用刷題來練RUST Day20 Rust智慧指標

17th鐵人賽
49 瀏覽

  • 分享至 

  • xImage
    •  

在先前Linked List、stack的深度優先搜尋(Depth First Search)和佇列Queue廣度優先搜尋中我們在leetcode題目上會看到，Box、Rc、ReCell，為何不用&就好。

pub struct ListNode {
   pub val: i32,
   pub next: Option<Box<ListNode>>
}

pub struct TreeNode {
   pub val: i32,
   pub left: Option<Rc<RefCell<TreeNode>>>,
   pub right: Option<Rc<RefCell<TreeNode>>>,
 }

為何需要BOX<T>

在一個LinkList中，ListNode串接著下一個ListNode，下一個ListNode串著下下一個，在編譯無法得知code佔多大的空間就會報錯。

https://ithelp.ithome.com.tw/upload/images/20251002/20142205J2UmLHevQ6.png

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<ListNode>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
     let head = Box::new(ListNode::new(1));
     println!("{:?}",*head);
}

Compiling playground v0.0.1 (/playground)
error[E0072]: recursive type `ListNode` has infinite size
 --> src/lib.rs:2:1
  |
2 | pub struct ListNode {
  | ^^^^^^^^^^^^^^^^^^^
3 |   pub val: i32,
4 |   pub next: Option<ListNode>
  |                    -------- recursive without indirection
  |
help: insert some indirection (e.g., a `Box`, `Rc`, or `&`) to break the cycle
  |
4 |   pub next: Option<Box<ListNode>>

這時加入Box<ListNode>，因為Box<T>是個指標能確定他佔Usize空間，裡面存的是下一個ListNode的位置，這樣在編譯時就能知道ListNode大小就是i32+usize

https://ithelp.ithome.com.tw/upload/images/20251002/20142205gEfNPWA3hE.png

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}
fn main() {
     let head = Box::new(ListNode::new(1));
     println!("{:p}",head);
     println!("{:?}",*head);
}
//印出 
//指標 0x63f7a8218d00
//ListNode { val: 1, next: None }

為何需要Rc<T>

今天如果同時兩個ListNode 下一個剛好要串同一個node，我們可以看到，編譯器跳出建議clone，但用clone複製會把整串linked list複製一份

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}
fn main() {
    let head = Box::new(ListNode::new(3));
    let mut new_head1 = ListNode::new(1);
    let mut new_head2 = ListNode::new(2);
    new_head1.next = Some(head);
    new_head2.next = Some(head);
}

Compiling playground v0.0.1 (/playground)
error[E0382]: use of moved value: `head`
  --> src/main.rs:21:27
   |
17 |     let head = Box::new(ListNode::new(3));
   |         ---- move occurs because `head` has type `Box<ListNode>`, which does not implement the `Copy` trait
...
20 |     new_head1.next = Some(head);
   |                           ---- value moved here
21 |     new_head2.next = Some(head);
   |                           ^^^^ value used here after move
   |
help: consider cloning the value if the performance cost is acceptable
   |
20 |     new_head1.next = Some(head.clone());
   |                               ++++++++

For more information about this error, try `rustc --explain E0382`.
error: could not compile `playground` (bin "playground") due to 1 previous error

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}
fn main() {
    let head = Box::new(ListNode::new(3));
    let mut new_head1 = ListNode::new(1);
    let mut new_head2 = ListNode::new(2);
    new_head1.next = Some(head);
    new_head2.next = Some(head);
}

Rc<T>解決了指標共用，每當借用時就會記錄目前多少人

use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Rc<Box<ListNode>>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
    let head = Rc::new(Box::new(ListNode::new(3)));
    println!("建立 head 後的計數 = {}", Rc::strong_count(&head));//建立 head 後的計數 = 1
    
    let mut new_head1 = ListNode::new(1);
    
    let clone_head1=Rc::clone(&head);
    println!("{:p}",clone_head1);//0x6543aa7c9d30
    new_head1.next = Some(clone_head1);
    println!("new_head1 指向head後的計數 = {}", Rc::strong_count(&head));//new_head1 指向head後的計數 = 2
    
    {
        let clone_head2=Rc::clone(&head);
        println!("{:p}",clone_head2);//0x6543aa7c9d30
        let mut new_head2 = ListNode::new(2);
        new_head2.next = Some(clone_head2);
        println!("new_head2 指向head後的計數 = {}", Rc::strong_count(&head));//new_head2 指向head後的計數 = 3
    }
    println!("new_head2 釋放head後的計數 = {}", Rc::strong_count(&head));//new_head2 釋放head後的計數 = 2
}

為何需要RefCell<T>

還記得Rust為了防止多個共用變數同時修改導致資料損壞或競爭，所以在編譯執行借用檢查(borrow checker)，如果想改變Rc<T>的值，可以看到Rc只提供不可變解參考，沒有可變解參考（沒有 DerefMut）。

use std::rc::Rc;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Rc<Box<ListNode>>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
    let head = Rc::new(Box::new(ListNode::new(3)));
    let mut new_head1 = ListNode::new(1);
    new_head1.next = Some(Rc::clone(&head));
    *head = Box::new(ListNode::new(4));
}


Compiling playground v0.0.1 (/playground)
error[E0594]: cannot assign to data in an `Rc`
  --> src/main.rs:23:5
   |
23 |     *head = Box::new(ListNode::new(4));
   |     ^^^^^ cannot assign
   |
   = help: trait `DerefMut` is required to modify through a dereference, but it is not implemented for `Rc>`

For more information about this error, try `rustc --explain E0594`.
error: could not compile `playground` (bin "playground") due to 1 previous error

RefCell<T>不會在編譯時執行借用檢查規則，如果執行時錯了會panic!。

use std::rc::Rc;
use std::cell::RefCell;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Rc<RefCell<Box<ListNode>>>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
    let head = Rc::new(RefCell::new(Box::new(ListNode::new(3))));

    let mut new_head1 = ListNode::new(1);
    new_head1.next = Some(Rc::clone(&head));
    
    let mut new_head2 = ListNode::new(2);
    new_head2.next = Some(Rc::clone(&head));
    
    println!("修改前 new_head1 {:?}",new_head1);
    println!("修改前 new_head2 {:?}",new_head2);
    
    *head.borrow_mut() = Box::new(ListNode::new(4));
    
    println!("修改後 new_head1 {:?}",new_head1);
    println!("修改後 new_head2 {:?}",new_head2);
}
//印出
//修改前 new_head1 ListNode { val: 1, next: Some(RefCell { value: ListNode { val: 3, next: None } }) }
//修改前 new_head2 ListNode { val: 2, next: Some(RefCell { value: ListNode { val: 3, next: None } }) }
//修改後 new_head1 ListNode { val: 1, next: Some(RefCell { value: ListNode { val: 4, next: None } }) }
//修改後 new_head2 ListNode { val: 2, next: Some(RefCell { value: ListNode { val: 4, next: None } }) }

因為RefCell<T>可變所以不能重複借用，所以讓他重複借用執行時會出現panic!

use std::rc::Rc;
use std::cell::RefCell;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Rc<RefCell<Box<ListNode>>>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
    let head = Rc::new(RefCell::new(Box::new(ListNode::new(3))));
    let mut new_head1 = ListNode::new(1);
    new_head1.next = Some(Rc::clone(&head));
    
    let _mut_ref1 = head.borrow_mut();
    let _mut_ref2 = head.borrow_mut();
    
}

 Compiling playground v0.0.1 (/playground)
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.54s
     Running `target/debug/playground`

thread 'main' panicked at src/main.rs:26:26:
RefCell already borrowed
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace

Rc<RefCell<T>>用法，讓共用變數可以修改，並且都是改同一個位址的值

use std::rc::Rc;
use std::cell::RefCell;

#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Rc<RefCell<Box<ListNode>>>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

fn main() {
    let head = Rc::new(RefCell::new(Box::new(ListNode::new(3))));
    let mut new_head1 = ListNode::new(1);
    new_head1.next = Some(Rc::clone(&head));
    
    let _mut_ref1 = Rc::clone(&head);
    let _mut_ref2 = Rc::clone(&head);
    
    println!("#######head=3#######");
    println!("head={:?}", head.borrow());
    println!("_mut_ref1={:?}", _mut_ref1.borrow());
    println!("_mut_ref2={:?}", _mut_ref2.borrow());

    _mut_ref1.borrow_mut().val =4;
    
    println!("#######修改_mut_ref1=4#######");
    println!("head={:?}", head.borrow());
    println!("_mut_ref1={:?}", _mut_ref1.borrow());
    println!("_mut_ref2={:?}", _mut_ref2.borrow());

    _mut_ref2.borrow_mut().val =5;
    println!("#######修改_mut_ref2=5#######");
    println!("head={:?}", head.borrow());
    println!("_mut_ref1={:?}", _mut_ref1.borrow());
    println!("_mut_ref2={:?}", _mut_ref2.borrow());
}

// #######head=3#######
// head=ListNode { val: 3, next: None }
// _mut_ref1=ListNode { val: 3, next: None }
// _mut_ref2=ListNode { val: 3, next: None }

// #######修改_mut_ref1=4#######
// head=ListNode { val: 4, next: None }
// _mut_ref1=ListNode { val: 4, next: None }
// _mut_ref2=ListNode { val: 4, next: None }

// #######修改_mut_ref2=5#######
// head=ListNode { val: 5, next: None }
// _mut_ref1=ListNode { val: 5, next: None }
// _mut_ref2=ListNode { val: 5, next: None }

Day20總結

  1. &借用回傳記憶體位置，可以在編譯時檢查可變與不可變借用，只能有一個擁有者。

  2. Box<T> 能有不可變或可變的借用並在編譯時檢查，只能有一個擁有者。

  3. Rc<T>只能有不可變借用並在編譯時檢查，讓數個擁有者能共享相同資料

  4. RefCell<T> 在執行時檢查不可變或可變借用。

所有權 mut ? 何時檢查
& 1 可 編譯時
Box<T> 1 可 編譯時
Rc<T> 多個 不可 編譯時
RefCell<T> 1 可 執行時

上一篇
用刷題來練RUST Day19 Linked List 介紹
下一篇
用刷題來練RUST Day21 裸指標 raw point & unsafe
系列文
用刷題來練RUST 共 30 篇
  1. 26
    用刷題來練RUST Day26 Binary Tree BFS
  2. 27
    用刷題來練RUST Day27 Graph DFS & BFS
  3. 28
    用刷題來練RUST Day28 Implicit Graph & Adjacency List & Adjacency Matrix
  4. 29
    用刷題來練RUST Day29 Disjoint Set
  5. 30
    用刷題來練RUST Day30 總結目錄 ＆延伸
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
902 組
團體組數
37 組
累計文章數
19736 篇
完賽人數
529 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 17th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# linux windows server css react
熱門問題
熱門回答
熱門文章
IT邦幫忙