布局

那么单链队列是什么样的呢？当我们有一个单链接的堆栈时，我们把它推到列表的一端，然后从同一端弹出。堆栈和队列之间的唯一区别是队列从另一端弹出。因此，从我们的堆栈实现中，我们可以看到:

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

为了建立队列，我们只需要决定移动到列表末尾的操作：push还是pop？因为我们的列表是单链的，我们实际上可以用同样的工作方式将任何一个操作移到最后。

要将 push 移动到结尾，我们只需要一直走到 None，并将新元素将其设置为 Some。

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

要将pop移到末尾，我们一直走到None之前的节点，然后取走：

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

我们今天就可以做到这一点，然后结束。但那会很糟糕！这两个操作都会遍历整个列表。有些人会认为这样的队列实现实际上是一个队列，因为它公开了正确的接口。不过，我保证接口的性能。我不关心精确的渐近界，只关心“快”与“慢”。队列保证了push和pop的速度很快，而遍历整个列表绝对不是很快。

一个关键的观察是，我们重复做同样的事情浪费了大量的工作。我们能记住这个工作吗？为什么，是的！我们可以存储一个指向列表末尾的指针，然后直接跳到那里！

事实证明，只有 push 和 pop 的一种反转才可以使用。要反转 pop，我们必须将 “tail” 指针向后移动，但是由于我们的列表是单链链接，因此我们无法有效地做到这一点。如果我们取反推，则只需向前移动 “head” 指针，这很容易。

让我们试试这个:

use std::mem;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // swap the old tail to point to the new tail
        let old_tail = mem::replace(&mut self.tail, Some(new_tail));

        match old_tail {
            Some(mut old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
            }
        }
    }
}

我现在将更详细地介绍隐含的细节，因为我们应该对这种事情很满意。并不是说您一定一定希望在第一次尝试时就产生此代码。我只是略过了我们之前必须处理的反复试验。实际上，在编写此代码时我犯了很多错误，但我没有显示出来。您只能看到我离开 mut 或 ; 如此反复才停止启发性。不用担心，我们还会看到许多其他错误消息！

> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move

使用 move value: new tail

没有实现 Copy，所以我们不能把它分配到两个位置。更重要的是，Box 拥有它所指向的东西，并且会在它 drop 时释放它。如果我们编译了 push 实现，我们就可以双倍释放列表的尾部了！实际上，正如我们所写的那样，我们的代码会在每次推送时释放 old_tail。哎呀！

好吧，我们知道如何制作一个非所有权指针。那只是参考！

pub struct List<T> {
    head: Link<T>,
    tail: Option<&mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}

这里没有什么棘手的问题。与之前的代码相同的基本思想，不同之处在于，无论使用什么填充实际Box的位置，我们都使用一些隐式的返回善意来提取尾部引用。

> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter

哦，对了，我们需要在类型生命周期中提供引用。嗯...这个引用的生命周期是多少？好吧，这看起来像IterMut，对吗？让我们尝试一下为IterMut做的事情，然后添加一个通用的 'a：

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

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

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_mut().map(|node| &mut **node)
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_mut().map(|node| &mut **node)
            }
        };

        self.tail = new_tail;
    }
}

cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                           ^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // When you push onto the tail, your next is always None
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_mut().map(|node| &mut **node)
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>

哇，这是一个非常详细的错误消息。这有点令人担忧，因为这意味着我们正在做一些真正混乱的事情。这里有一个有趣的部分:

必须在 impl 上定义有效生命周期 'a

我们借用了self，但是编译器希望我们能持续到 'a，如果我们告诉它self能持续那么长时间呢。。？

    pub fn push(&'a mut self, elem: T) {

cargo build

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

哦，嘿，成功了! 太好了！

让我们也做一下 pop 吧:

pub fn pop(&'a mut self) -> Option<T> {
    // Grab the list's current head
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        // If we're out of `head`, make sure to set the tail to `None`.
        if self.head.is_none() {
            self.tail = None;
        }

        head.elem
    })
}

并为此写一个快速测试:

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

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

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

        // Check normal removal
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

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

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);
    }
}

cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** WAY MORE LINES OF ERRORS **

....

error: aborting due to 11 previous errors

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

我的天啊。

编译器对我们所有人的呕吐没有错。我们刚犯了一个主要的Rust罪过：我们在自己的内部存储了对自己的引用。不知何故，我们设法说服了Rust，这在我们的push和pop实施中是完全合理的（我们确实为之震惊）。我相信原因是Rust不能仅仅通过 push 和 pop 来告诉引用是对我们自己的引用，或者更确切地说，Rust根本没有这个概念。引用失败的行为只是一种新出现的行为。

一旦我们尝试使用我们的列表，一切都会很快崩溃。当我们调用push或pop时，我们会立即在自己中存储对自己的引用并陷入困境。我们实际上是在借用自己。

我们的 pop 实现提示了为什么这可能是非常危险的：

// ...
if self.head.is_none() {
    self.tail = None;
}

如果我们忘记这样做怎么办？然后，我们的尾巴将指向已从列表中删除的某个节点。这样的节点将立即释放，并且我们将有一个悬空的指针，Rust应该保护它免受攻击！

的确，Rust 正在保护我们远离那种危险，只是以一种非常... 迂回的方式。

那么我们能做什么呢? 回到 Rc<refcell> 地狱？

求你了不要。

相反，我们将偏离正轨，使用原始指针。我们的布局将是这样的：

pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>, // DANGER DANGER
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

就是这样。这些无聊的引用计数动态借阅检查都是胡说八道！真实。硬。未检查的指针。

让我们成为C。让我们整天成为C。

我回来了，我准备好了。

Hello unsafe。

Previous一个不安全的队列 NextUnSafe

Last updated 5 years ago

Was this helpful?