iT邦幫忙

2025 iThome 鐵人賽
DAY 20
0
Rust

用刷題來練RUST系列 第 20 篇

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

17th鐵人賽
20 瀏覽

  • 分享至 

  • 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 共 21 篇
  1. 17
    用刷題來練RUST Day17 如何自訂義Priority Queue Top K比較方式
  2. 18
    用刷題來練RUST Day18 Priority Queue 多來源合併、多任務佇列
  3. 19
    用刷題來練RUST Day19 Linked List
  4. 20
    用刷題來練RUST Day20 Rust智慧指標
  5. 21
    用刷題來練RUST Day21 裸指標 raw point & unsafe
完整目錄
圖片
  熱門推薦
圖片
{{ item.channelVendor }} | {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

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