user02：RUST实现链表（linkedlist using RUST）

carloscn commented 1 year ago

实现链表的基本功能

carloscn commented 1 year ago

实现链表的迭代

实现一个迭代器，可以通过实现3个trait：

1.对象所有权IntoIter
2.对象可变引用IterMut
3.对象不可变引用Iter

我们不能说遍历完链表，链表就没了，而获取所有权的迭代器会把链表消耗掉的，因为要把链表所有权转给迭代器，然后迭代器进行消耗，这就没意义了。如果我们想要通过迭代并实现元素的更新，那就必须实现对象可变的引用，当你想要修改链表的时候（不管是插入数据，删除数据，还是更新数据）都是要做mut操作。

part1.实现获取所有权类型的迭代器：IntoIter.

首先定义trait，只要实现这个trait就可以进行next操作进行下一个元素的迭代，因此要有一个next方法。（这里还用了关联类型，实际上使用泛型也可以，不过泛型有他的局限性，并且每个实现它的对象都要重写泛型的定义）

pub trait Iterator {
    type Item; // 这里的 Item 是关联类型，用于在trait中指代某个类型
    fn next(&mut self) -> Option<Self::Item>; // 由于next最后一个为None，因此元素用Option包裹一层
}

创建一个元组结构体IntoIter (List)，并为这个元组结构体实现Iterator的trait。这里定义一个元组的原因是方便Intolter访问和索引，通过.0就可以索引到List。

pub struct IntoIter<T> (List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<T> List<T> {
    // type: List<T> ---> (List<T>)
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

此时，可以测试一下迭代器：

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);
        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(1));
    }

carloscn commented 1 year ago

part2，实现不可变的引用迭代器： Iter

要实现这个不可变的引用，我们不能和part1一样，获取链表List，然后用List的pop方法了，那我们就必须要创建一个能存储一个节点指针信息的对象，获取该节点，并且通过该节点的next属性，查到下一个节点的指针对象，之所以是指针对象，是因为我们是要引用（&）节点，才能不影响对象的移动。

这里会有一个新的api：as_deref: 可以将Option的数据取出来，然后返回一个里面对象的引用：

通过上面的分析，我们知道这个Iter对象不能和之前的IntoIter一样，它应该是一个有属性的结构体，因为他要存放节点的指针信息，用于展示。

pub struct Iter<T> {
    info: Option<&Node<T>>,
}

这么写之后，编译会爆：Option<&Node>中的typeTmay not live long enough，也就是我们最早分析的，这里要涉及到生命周期的指定。原因就是struct中的元素如果是引用类型的，那就必须要求这个引用的生命长于这个struct，否则这个指针可能会悬垂。考虑给&Node加一个'a的生命周期参数：

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

接下来就是要给他实现之前定义的iterator的trait：

impl<'a, T>Iterator for Iter<'a, T> {
    type Item = &T;
    // 这里的self是Node节点的引用，因此是&self，而又因为这个next要随着取出下一个换掉，因此还要是mut类型
    fn next(&mut self) -> Option<Self::Item> {
       todo!()
    }
}

这里Item要指定是T类型的指针，因为定义好的next返回的是一个Option<&Node<T>>，但是当这么修改后type Item = &T;会报错缺少生命参数，因此最后改成：type Item = &'a T;

最终code：

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

impl<'a, T>Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.info.map(|node|{
            self.info = node.next.as_deref();
            &node.value
        })
    }
}

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter{ info: self.head.as_deref() }
    }
}

测试用例：

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

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(list.pop(), Some(3)); // 因为是引用迭代，因此并不影响源List可以pop()数据
        assert_eq!(list.pop(), Some(2));
        assert_eq!(list.pop(), Some(1));
    }

carloscn commented 1 year ago

part3: 可变引用: IterMut

分析和part2一样，只不过这个变成了mut类型，因此，只需要按部就班的和part2一样，现将struct创建出来，多加一个mut即可。然后按照编译器的要求添加相应的生命周期参数

注：为什么可变的引用(&mut T)不可以Copy，因为一个引用说白了就是一个指针，拷贝一个指针就是多一个指向某值的拷贝，而如果这个值是可变的，那很可能它在某次变化后它的地址就变了（比如vec元素增加的时候，超过cap值进行扩容，此时它会选一块新的内存地址，将原来的数据拷贝过去），这样就会产生悬垂引用，即一个指向无效内存的指针。

由于self.info中的&mut T是没有满足copy的trait，因此这里就会move，但是我们又不能move这个值
这里使用self.info.take()将self.info临时拿出来，然后放进去一个None，然后在对拿出来的数据做map操作
不用担心self.info变成None会指向空，因为里面会重新把下一个元素取出来放到这个self.info中

pub struct IterMut<'a, T> {
    info: 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.info.take().map(|node| {
            self.info = node.next.as_deref_mut();
            &mut node.value
        })
    }
}

impl<T> List<T> {
    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut{ info: self.head.as_deref_mut() }
    }
}

测试用例:

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

    let mut iter = list.iter_mut();
    assert_eq!(iter.next(), Some(&mut 3));
    assert_eq!(iter.next(), Some(&mut 2));
    assert_eq!(iter.next(), Some(&mut 1));
}

carloscn commented 1 year ago

https://review.gerrithub.io/c/carloscn/structstudy/+/551253

carloscn commented 1 year ago

本文参考：https://blog.csdn.net/oHeiDou/article/details/128237632

carloscn / structstudy