基础

我们现在已经学习了很多 Rust 基础知识，所以我们可以再做很多简单的东西。

对于构造函数，我们可以再次复制粘贴：

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

Push 和 pop 已经没有意义了。相反，我们可以提供 append 和 tail，它们提供了大致相同的东西。

让我们从 append 开始。它接受一个 List 和一个元素，并返回一个 List。与可变列表一样，我们希望创建一个新节点，它的下一个值是旧列表。唯一新奇的事情是如何得到下一个值，因为我们不允许修改任何东西。

我们祈祷的答案是 Clone 特质。 每种类型几乎都实现了 Clone，并且提供了一种通用的方式来获得 “另一种类似的副本”，这种共享在逻辑上不相交（仅给出了共享引用）。 它就像C ++中的副本构造函数，但从未被隐式调用。

Rc 特别使用 Clone 作为增加引用计数的方法。因此，我们不需要移动一个 Box 到子列表中，而是克隆旧列表的head。我们甚至不需要在head上匹配，因为Option 公开了一个完全符合我们需要的克隆实现。

好吧，让我们来试一试：

pub fn append(&self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
        elem: elem,
        next: self.head.clone(),
    }))}
}

> cargo build

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

哇，Rust在实际使用字段方面确实很费劲。 它不能告诉任何消费者实际上可以观察到这些字段的使用！ 不过，到目前为止我们看起来还不错。

tail 是此操作的逆逻辑。 它获取一个列表，并返回删除了第一个元素的整个列表。 所有操作就是克隆列表中的第二个元素（如果存在）。 让我们尝试一下：

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().map(|node| node.next.clone()) }
}

cargo build

error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

嗯，我们搞砸了。 map 希望我们返回 Y，但是在这里我们返回 Option<Y> 。 幸运的是，这是另一个常见的 Option 模式，我们可以使用and_then 来返回 Option。

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}

> cargo build

太好了。

既然有了tail，我们应该提供 head，它返回对第一个元素的引用。这只是从可变列表中 peek 一下：

pub fn head(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem )
}

> cargo build

很好。

这些功能已经足够我们测试了：

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.append(1).append(2).append(3);
        assert_eq!(list.head(), Some(&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();
        assert_eq!(list.head(), None);

    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured

好极了！

Iter也与我们的可变列表相同：

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

impl<T> List<T> {
    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head.as_ref().map(|node| &**node) }
    }
}

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

    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.as_ref().map(|node| &**node);
            &node.elem
        })
    }
}

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

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

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured

注意，我们不能为这种类型实现 IntoIter 或 IterMut，我们只能共享对元素的访问。