too-many-lists/persistent-stack/layout

[giscus[bot]]

too-many-lists/persistent-stack/layout

https://course.rs/too-many-lists/persistent-stack/layout.html

[it-ailen]

求 iterMut 实现，已投降 - -!

[PuffMeow]

@it-ailen 可能这个得去用RefCell了

[it-ailen]

unsafe + 裸指针，爽歪歪

[guanguoliang]

IntoIter怎么实现。。。

[wzwmzm]

我用AI能实现, 现在的AI太强大了

[veyron5810]

感觉先去看一遍《通过例子学Rust》再来看这个例子比较好，现在看的有点懵

[guanguoliang]

pub fn prepend(&self, elem: T) -> List {
List { head: Some(Rc::new(Node {
elem: elem,
next: self.head.clone(),
}))}
}
这里面的clone不是rc的，是option的吧

[guanguoliang]

看了一下的确是option的clone，但是它的实现最后还是调用了里面包裹数据的clone方法

#[inline]
    fn clone(&self) -> Self {
        match self {
            Some(x) => Some(x.clone()),
            None => None,
        }
    }

[ggchengyu]

这里做个小分析，纯粹是个人填下之前没有完全理解的坑；

self.head.as_ref() => Option<&Rc<Node>
self.head.as_ref().map(|node| node.next.clone()) => Option<Option<Rc<Node>>

map desugaring =>
self.head.as_ref().map::<Option<Rc<Node>>,_>(|node| node.next.clone())

and_then desugaring =>
self.head.as_ref().and_then::<Rc<Node>,_>(|node| node.next.clone())

嵌套的Option应该是由于map返回的类型为LInk /* Option<Rc<Node>>*/；

本质上是符合官方对两个方法的定义：
即and_then返回闭包的Option value，map返回Option

[ggchengyu]

补充两点：
1、and_then和map的区别之一是对待闭包的表达式，and_then要求表达式为Option，取result U作为链式调用的结果；而map不挑表达式，Option和其他类型U均可，但取Option<_>作为返回值，（对应Option<Option>和Option）;
2、desugaring不是很完整，意会意会

[GmwEnterprise]

map().unwrap() 是一样的

[theCodedMike]

未经充分测试，简单测试是通过的

IntoIter

pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.head.take().and_then(|rc_node| {
            if let Ok(mut node) = Rc::try_unwrap(rc_node) {
                self.0.head = node.next.take();
                Some(node.elem)
            } else {
                None
            }
        })
    }
}
// 测试
    #[test]
    fn into_iter() {
        let mut list = List::new();
        assert_eq!(list.head(), None);
        list = list.prepend(4).prepend(5).prepend(6);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(6));
        assert_eq!(iter.next(), Some(5));
        assert_eq!(iter.next(), Some(4));
        assert_eq!(iter.next(), None);
    }

IterMut

pub fn iter_mut(&mut self) ->  IterMut<T> {
    let mut next = None;
    if let Some(ref mut rc_node) = self.head {
        next = Rc::get_mut(rc_node);
    }
    IterMut { next }
}
pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().and_then(|node| {
            if let Some(ref mut rc_node) = node.next {
                self.next = Rc::get_mut(rc_node);
            }
            Some(&mut node.elem)
        })
    }
}
// 测试
    #[test]
    fn iter_mut() {
        let mut list = List::new().prepend(2).prepend(3).prepend(4);
        let mut iter = list.iter_mut();
        if let Some(node) = iter.next() {
            *node = 6;
        }
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), None);
        println!("now list: {:?}", list);  // 6 3 2
    }

[minminm]

IntoIter的实现有问题，try_unwrap只有在强引用计数为1的时候才是安全的，如果考虑两个链表共享相同节点的情况，就会出错。比如下面这个例子：

    #[test]
    fn into_iter() {
        let mut list = List::new();
        assert_eq!(list.head(), None);
        list = list.prepend(4).prepend(5).prepend(6);
        let list2 = list.prepend(7).prepend(8).prepend(9);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(6));
        assert_eq!(iter.next(), Some(5));
        assert_eq!(iter.next(), Some(4));
        assert_eq!(iter.next(), None);

        let mut iter = list2.into_iter();
        assert_eq!(iter.next(), Some(9));
        assert_eq!(iter.next(), Some(8));
        assert_eq!(iter.next(), Some(7));
        assert_eq!(iter.next(), Some(6));
        assert_eq!(iter.next(), Some(5));
        assert_eq!(iter.next(), Some(4));
        assert_eq!(iter.next(), None);
    }

[max201904]

以现有的结构是没有办法使用 safe 方法实现这两个迭代器的, 因为 Rc 是可以共享所有权的.
Rc 虽然提供了 try_unwrap 方法获得节点所有权和 get_mut 方法获得节点可变引用, 但是这两个方法成功返回的前提是只有调用方法的 Rc 对象单独拥有节点的所有权. 只要有其他变量也拥有了这个节点的所有权, 那上述方法就会获取失败, 导致迭代器意外中断, 不能完整遍历整个 List.

[JMILI]

我有个疑问：为什么tail方法移除元素时，要用clone()方法？这不是会让强引用数+1吗？是和drop方法有关吗？
我写了测试代码：

let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.prepend(1).prepend(2).prepend(3);
        let list2 = list.prepend(5).prepend(6).prepend(7);
        /// list的结构：3-2-1
        list.prepend(*list2.head().unwrap());
        /// list2的结构：7-6-5-3-2-1

        assert_eq!(list.head(), Some(&3));

        // 将3移除
        let list = list.tail();
       
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // Make sure empty tail works
        let list = list.tail();
        // 此时list 为none了，list2 :7-6-5-3-2-1
        assert_eq!(list.head(), None);

当list中的所有节点tail之后，list2中的7-6-5-3-2-1的强引用依次是：1-1-1-2-2-2
两个List在drop时为什么没有出错？

[minminm]

首先，使用Rc肯定要用clone才能拿到同一个引用的对象，不然你还有别的方法吗。
其次，Rc的drop只有当引用计数为0的时候才会被调用，不会出现多次释放内存的错误。

[max201904]

因为 tail 方法返回时 self 的 List 和返回的 List 共同拥有了节点的所有权, 所以要用 clone 使引用计数器加一.

[YanHeDoki]

这个开头提出的数据布局我居然都没操作出来

[ziyoung]

对列表进行迭代时，将 self.head.as_deref 换成 self.head.as_ref 效果也是一样的。如果用 as_ref 的话， Iter 这个 struct 略微调整一下。

pub struct Iter<'a, T> {
  next: Option<&'a Rc<Node<T>>>,
}

[paletteOvO]

看了一下原文，

Note that we can't implement IntoIter or IterMut for this type. We only have shared access to elements.
我還思考了一下Rc根本沒法安全拿到ownership

[sswybd]

为什么新链表一定是不可变的，然后push 和 pop 没有意义呢？可以按照push pop的方式写啊，像下面这样：

    pub fn prepend(&mut self, elem: T) {
        let new_node = Rc::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

        let mut list = List::new();

        list.prepend(1);
        list.prepend(2);
        list.prepend(3);

测试可以通过的

[sswybd]

明白了，尽管如下，push 可以实现，但由于 Rc 只有 shared reference ，没有真正拥有数据，因此 pop 无法实现：

pub fn push(&mut self, elem: T) {
    let new_node = Rc::new(Node {
        elem: elem,
        next: self.head.take(),
    });

    self.head = Some(new_node);
}

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|node| {
        self.head = node.next.clone();
        node.elem  // !ERROR!: cannot move !!!
    })
}