too-many-lists/bad-stack/final-code

[giscus[bot]]

too-many-lists/bad-stack/final-code

https://course.rs/too-many-lists/bad-stack/final-code.html

[zihaojin]

while let Link::More(mut boxed_node) = cur_link

赋值语句可以在while后面用是什么语法呀，官方文档里面有提到过吗？

[mumumusuc]

while let 条件循环，本书2.6.3节

[Fomalhauthmj]

提前优化的好处，建议看原文体会一下，这里的用词“拷贝”会让人产生歧义，原文意指移动开销不同。

[SethWen]

使用 Option 的实现

use std::mem;

struct Node {
    item: i32,
    next: Box<Option<Node>>,
}

impl Node {
    fn new(item: i32, next: Option<Node>) -> Self {
        Node { item, next: Box::new(next) }
    }
}

pub struct List {
    head: Option<Node>,
}

impl List {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, item: i32) {
        let node = Node::new(item, mem::replace(&mut self.head, None));
        self.head = Some(node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match mem::replace(&mut self.head, None) {
            Some(node) => {
                self.head = *node.next;
                Some(node.item)
            }
            None => None,
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_node = mem::replace(&mut self.head, None);

        while let Some(mut boxed_node) = cur_node {
            cur_node = mem::replace(&mut boxed_node.next, None);
        }
    }
}

#[test]
fn test() {
    let mut list = List::new();

    // Check empty list behaves right
    assert_eq!(list.pop(), None);

    // Populate list
    list.push(1);
    list.push(2);
    list.push(3);

    // Check normal removal
    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(2));

    // Push some more just to make sure nothing's corrupted
    list.push(4);
    list.push(5);

    // Check normal removal
    assert_eq!(list.pop(), Some(5));
    assert_eq!(list.pop(), Some(4));

    // Check exhaustion
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), None);
}

[Jisu-Woniu]

mem::replace(opt, None) 可以直接写成 opt.take()，更简洁

[FLAYhhh]

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = std::mem::replace(&mut self.head, Link::Empty);
        while let Link::More(node) = cur_link { //move cur_link

-- //cur_link = std::mem::replace(&mut node.next, Link::Empty); // why use mem::replace
++ cur_link = node.next;
}
}
}
由于node有所有权，这里可以直接使用partial move拿node.next, 不用std::mem::replace也行。

[axzsd]

学习了

[montmorill]

struct Node<T> {
    value: T,
    next: Link<T>,
}
pub struct List<T> {
    head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, value: T) {
        self.head = Some(Box::new(Node {
            value,
            next: self.head.take(),
        }));
    }

    pub fn pop(&mut self) -> Option<T> {
        let boxed_node = self.head.take()?;
        self.head = boxed_node.next;
        Some(boxed_node.value)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut boxed_node) = current {
            current = boxed_node.next.take();
        }
    }
}

[wzwmzm]

我用ai帮我实现的impl Drop for List, 更加简洁
impl Drop for List {
fn drop(&mut self) {
// 清理所有节点
while let Some(_) = self.pop() {}
}
}

[wyswill]

use std::cell::{RefCell, RefMut};
use std::hash::Hash;
use std::rc::Rc;
type TNode = Option<Rc<RefCell>>;

#[derive(Debug, Clone, )]
struct Node {
data: i32,
next: TNode,
}

impl Node {
fn default(data: i32) -> Self {
Node { data, next: None }
}
}

#[derive(Debug, Clone, )]
struct TList {
head: TNode,
tail: TNode,
}

impl TList {
fn new() -> Self {
TList {
head: None,
tail: None,
}
}

fn push(&mut self, data: i32) {
    let new_node = Rc::new(RefCell::new(Node::default(data)));
    if self.head.is_none() {
        self.head = Some(new_node.clone());
    } else {
        // 直接拿tail指向的堆数据
        // 此时self.tail 指向null
        let tail = self.tail.take();
        if tail.is_some() {
            let tmp = tail.unwrap();
            // 利用Rc 和 RefCell的内部可变性修改next指针
            tmp.borrow_mut().next = Some(new_node.clone());
        }
    }
    // 重新将self.tail 指向new node
    self.tail = Some(new_node.clone());
}

fn delete(&mut self, value: i32) {
    let head = self.head.as_ref();
    // 获取当前head的ref
    let mut node = Some(head.unwrap().clone());
    let mut pre: TNode = None;
    while let Some(curr) = node {
        if curr.borrow().data == value {
            match pre.take() {
                Some(p) => {
                    p.borrow_mut().next = None;
                    self.tail = Some(p);
                }
                None => {
                    self.head = None;
                    self.tail = None;
                }
            }
        } else {
            match pre.take() {
                Some(p) => {
                    p.borrow_mut().next = Some(curr.clone());
                    pre = p.borrow().to_owned().next;
                }
                None => {
                    pre = Some(curr.clone());
                }
            }
        }

        node = curr.borrow().to_owned().next;
    }
}

fn change(&mut self, old_val: i32, new_val: i32) {
    self.find(|mut val| {
        if val.data == old_val {
            val.data = new_val;
        }
        None
    })
}

fn find<T>(&self, cb: T)
where
    T: FnOnce(RefMut<Node>) -> TNode + Copy,
{
    let head = self.head.as_ref();
    let mut node = Some(head.unwrap().clone());
    while let Some(curr) = node {
        cb(curr.borrow_mut());
        node = curr.borrow().to_owned().next;
    }
}

}

pub fn main() {}

#[test]
fn inset() {
let mut list = TList::new();
list.push(1);
list.push(2);
list.push(3);
list.push(4);
assert_eq!(list.tail.unwrap().borrow().data, 4)
}

#[test]
fn delete() {
let mut list = TList::new();
list.push(1);
list.push(2);
list.push(3);
list.push(4);

list.delete(2);

assert_eq!(list.tail.unwrap().borrow().data, 1)

}

#[test]
fn change() {
let mut list = TList::new();
list.push(1);
list.push(2);
list.push(3);
list.push(4);

list.change(2, 3);
println!("{:#?}", list)

}
内部可变性的实现

[wyswill]

use std::cell::{RefCell, RefMut};
use std::hash::Hash;
use std::rc::Rc;
type TNode = Option<Rc<RefCell<Node>>>;

#[derive(Debug, Clone, )]
struct Node {
    data: i32,
    next: TNode,
}

impl Node {
    fn default(data: i32) -> Self {
        Node { data, next: None }
    }
}

#[derive(Debug, Clone, )]
struct TList {
    head: TNode,
    tail: TNode,
}

impl TList {
    fn new() -> Self {
        TList {
            head: None,
            tail: None,
        }
    }

    fn push(&mut self, data: i32) {
        let new_node = Rc::new(RefCell::new(Node::default(data)));
        if self.head.is_none() {
            self.head = Some(new_node.clone());
        } else {
            // 直接拿tail指向的堆数据
            // 此时self.tail 指向null
            let tail = self.tail.take();
            if tail.is_some() {
                let tmp = tail.unwrap();
                // 利用Rc 和 RefCell的内部可变性修改next指针
                tmp.borrow_mut().next = Some(new_node.clone());
            }
        }
        // 重新将self.tail 指向new node
        self.tail = Some(new_node.clone());
    }

    fn delete(&mut self, value: i32) {
        let head = self.head.as_ref();
        // 获取当前head的ref
        let mut node = Some(head.unwrap().clone());
        let mut pre: TNode = None;
        while let Some(curr) = node {
            if curr.borrow().data == value {
                match pre.take() {
                    Some(p) => {
                        p.borrow_mut().next = None;
                        self.tail = Some(p);
                    }
                    None => {
                        self.head = None;
                        self.tail = None;
                    }
                }
            } else {
                match pre.take() {
                    Some(p) => {
                        p.borrow_mut().next = Some(curr.clone());
                        pre = p.borrow().to_owned().next;
                    }
                    None => {
                        pre = Some(curr.clone());
                    }
                }
            }

            node = curr.borrow().to_owned().next;
        }
    }

    fn change(&mut self, old_val: i32, new_val: i32) {
        self.find(|mut val| {
            if val.data == old_val {
                val.data = new_val;
            }
            None
        })
    }

    fn find<T>(&self, cb: T)
    where
        T: FnOnce(RefMut<Node>) -> TNode + Copy,
    {
        let head = self.head.as_ref();
        let mut node = Some(head.unwrap().clone());
        while let Some(curr) = node {
            cb(curr.borrow_mut());
            node = curr.borrow().to_owned().next;
        }
    }
}

pub fn main() {}

#[test]
fn inset() {
    let mut list = TList::new();
    list.push(1);
    list.push(2);
    list.push(3);
    list.push(4);
    assert_eq!(list.tail.unwrap().borrow().data, 4)
}

#[test]
fn delete() {
    let mut list = TList::new();
    list.push(1);
    list.push(2);
    list.push(3);
    list.push(4);

    list.delete(2);

    assert_eq!(list.tail.unwrap().borrow().data, 1)
}

#[test]
fn change() {
    let mut list = TList::new();
    list.push(1);
    list.push(2);
    list.push(3);
    list.push(4);

    list.change(2, 3);
    println!("{:#?}", list)
}

内部可变性的实现