任务分解

pop_front 应该和 push_front 的基本逻辑相同，但是是反向的：

pub fn pop_front(&mut self) -> Option<T> {
    // need to take the old head, ensuring it's -2
    self.head.take().map(|old_head| {                         // -1 old
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {                               // -1 new
                // not emptying list
                new_head.borrow_mut().prev.take();            // -1 old
                self.head = Some(new_head);                   // +1 new
                // total: -2 old, +0 new
            }
            None => {
                // emptying list
                self.tail.take();                             // -1 old
                // total: -2 old, (no new)
            }
        }
        old_head.elem
    })
}

> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

确认 RefCells。我想要再次借用...

pub fn pop_front(&mut self) -> Option<T> {
    self.head.take().map(|old_head| {
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {
                new_head.borrow_mut().prev.take();
                self.head = Some(new_head);
            }
            None => {
                self.tail.take();
            }
        }
        old_head.borrow_mut().elem
    })
}

cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |

叹气

cannot move out of borrowed content

看来 Box 真的把我们宠坏了。borrow_mut 只能给我们一个 &mut Node，但是我们不能离开它！

我们需要一个可以接受 RefCell<T> 并且给我们一个 T 的东西。让我们检查一下文档，看看有没有类似的东西：

fn into_inner(self) -> T
Consumes the RefCell, returning the wrapped value.

看起来很有希望！

old_head.into_inner().elem

> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

当 into_inner 想要移出 RefCell，但我们不能，因为它在Rc中。正如我们在上一章中所看到的，Rc 仅允许我们获取其内部的共享引用。这很有意义，因为这就是引用计数指针的全部要点：它们是共享的！

当我们想为引用计数列表实现 Drop 时，这对我们来说是个问题，解决方案是相同的：Rc::try_unwrap，如果引用计数为1，则将Rc的内容移出。

Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::try_unwrap 将返回Result<T, Rc<T>> 。结果是泛型的Option，其中无案例有相关的数据。在这种情况下，您试图打开的 Rc。由于我们不关心它失败的情况(如果我们正确地编写了程序，那么它必须成功) ，我们只是调用 unwrap。

不管怎样，让我们看看接下来会出现什么样的编译错误(让我们面对现实吧，肯定会有一个)。

> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

对 Result 进行解包要求可以 Debug 打印错误情况。 RefCell 仅在 T 执行时才实现Debug。 Node 未实现Debug。

与其这样做，不如通过将 Result 转换为带有 ok 的 Option 来解决：

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

cargo build

是的

我们成功了

我们实现了 push 和 pop。

让我们通过窃取旧的链堆的测试代码进行测试（因为这是我们到目前为止已实现的全部）：

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

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

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

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

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

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

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

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

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 9 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::basics ... ok
test fifth::test::iter_mut ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok

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

现在我们可以正确地从列表中删除一些东西，我们可以实现 Drop。这次 Drop 在概念上更有趣一些。以前我们为了避免无限递归而为堆栈实现 Drop，现在我们需要实现 Drop 来实现任何事情。

Rc 不能处理循环。如果有一个循环，所有的东西都会保持存活。事实证明，一个双向链表只是一个由小循环组成的大链！所以当我们删除我们的列表时，两个末端节点的拒绝计数将减少到1... 然后什么也不会发生。如果我们的列表只包含一个节点，我们就可以开始了。但理想情况下，如果列表包含多个元素，那么它应该正常工作。也许那只是我的想法。

正如我们所看到的，删除元素有点痛苦。所以对我们来说最简单的事情就是 pop，直到我们得到 None：

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

cargo build

(实际上，我们可以使用可变堆栈来实现这一点，但是快捷方式是为理解事物的人准备的!)

我们可以考虑实现 push 和 pop 的 _back 版本，但它们只是复制粘贴作业，我们将在本章后面讨论。现在让我们来看看更有趣的事情！

Previous构建 NextPeek

Last updated 4 years ago

Was this helpful?