构建

好了，我们将从构建 list 开始。对于这个新系统，这非常简单。 new 仍然微不足道，所有字段中都是 None。另外，由于它有点笨拙，我们也来介绍一下 Node 构造函数：

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

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

> cargo build

**A BUNCH OF DEAD CODE WARNINGS BUT IT BUILT**

耶！

现在让我们尝试写一下 push_front。因为双向链表要复杂得多，我们需要做更多的工作。在单链表操作可以简化为单线程的情况下，双链表操作相当复杂。

特别是，我们现在需要特别处理一些与空列表有关的边界情况。大多数操作只触及头部或尾部指针。但是，当转换到空列表或从空列表转换时，我们需要同时编辑这两个列表。

要验证我们的方法是否有意义，一个简单的方法是我们保持以下不变量: 每个节点应该有两个指向它的指针。列表中间的每个节点由其前置节点和后续节点指向，而末端的节点则由列表本身指向。

让我们来试一试:

pub fn push_front(&mut self, elem: T) {
    // new node needs +2 links, everything else should be +0
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // non-empty list, need to connect the old_head
            old_head.prev = Some(new_head.clone()); // +1 new_head
            new_head.next = Some(old_head);         // +1 old_head
            self.head = Some(new_head);             // +1 new_head, -1 old_head
            // total: +2 new_head, +0 old_head -- OK!
        }
        None => {
            // empty list, need to set the tail
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // total: +2 new_head -- OK!
        }
    }
}

cargo build

error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

编译器错误。好的开始。好的开始。

为什么我们不能访问节点上的 prev 和 next 字段？以前我们只有一个 Rc<node> 的时候，它是有效的。似乎 RefCell 正在妨碍我们的工作。

我们应该检查一下文件。

Google 一下 "rust refcell"。

点击第一个链接

具有动态检查借用规则的可变内存位置
有关更多信息，请参见模块级文档。

点击链接

可共享的可变容器。
Cell 和 RefCell 类型的值可以通过共享引用（即常见的 &T类型）进行更改，而大多数 Rust 类型只能通过唯一（&mut T）引用进行更改。我们说 Cell 和 RefCell 提供了“内部可变性”，而典型的Rust类型则表现出“继承的可变性”。
Cell 类型有两种：Cell 和 RefCell 。 Cell 提供 get 和 set 方法，这些方法可以通过单个方法调用来更改内部值。 Cell 仅与实现 Copy 的类型兼容。对于其他类型，必须使用 RefCell 类型，在进行更改之前获取写锁定。
RefCell<T> 使用Rust的生命周期来实现“动态借用”，这是一个可以请求对内部值进行临时、独占、可变访问的过程。RefCell<T> 的借用是在“运行时”进行跟踪的，这与 Rust 的本机参考类型不同，后者在编译时是完全静态跟踪的。由于RefCell<T> 借用是动态的，因此可以尝试借用已经可变借用的值。发生这种情况时，将导致线程崩溃。
什么时候选择内部易变性

更常见的继承易变性是一个关键的语言元素，它使 Rust 能够对指针别名进行强有力的推理，静态地防止崩溃错误。因此，继承的易变性是首选，而内部的易变性则是最后的手段。由于 Cell 型使得可变可能被禁止，所以有时候内部可变可能是适当的，甚至必须使用，例如：
将继承的可变性根源引入共享类型
逻辑不可变方法的实现细节
改变 Clone 的实现

将继承的可变性根源引入共享类型
共享的智能指针类型（包括 Rc<T> 和 Arc<T> ）提供了可以在多方之间克隆和共享的容器。由于包含的值可能是多重别名，因此只能借用它们作为共享引用，而不是可变引用。没有 cell，根本不可能在共享盒内对数据进行修改！

在共享指针类型中加入 RefCell<T> 来重新引入可变性是很常见的:
use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}
注意，这个例子使用 Rc<T> 而不是 Arc<T> 。RefCell<T> 用于单线程方案。如果在多线程环境中需要共享可变性，请考虑使用 Mutex<T> 。

嘿，Rust的文档仍然很棒。

我们关心的是这句话:

shared_map.borrow_mut().insert("africa", 92388);

特别是 borrow_mut 这个词。看来我们需要明确地借用一个 RefCell。这个 "." 操作不会为我们做的。真奇怪。让我们试试：

pub fn push_front(&mut self, elem: T) {
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        }
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

> cargo build

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

嘿，它构建成功了！文档再次胜利。

Previous布局 Next任务分解

Last updated 4 years ago

Was this helpful?