Rust 标准库学习:LinkedList

图片来自pexels.com

继续 Rust 标准库 学习系列, 这次是 LinkedList<T>。注意,实现来自 Rust stable v1.33.0.

拥有节点的双向列表。
LinkedList 永许在常量时间内从两端 pushpop 元素。
大多数情况最好用 VecVecDeque 替代 LinkedList。通常,基于数组的容器更快,内存效率更高,并且更好的利用 CPU 缓存。

Rust std doc

Vec<T> 不同的是

  1. 通过索引访问一个元素需要对列表进行线性迭代。
  2. append is O(1)。
  3. 有趣的是 linked_list::Iterlinked_list::IterMut 的不同之处。IterMut的不可变性用 &mutPhantomData<&'a Node<T>> 确保健全性 (更多关于 PhantomData,稍后说明)。

这儿有 一本书 (如果你没读过这本书,我强烈建议你去阅读它的细节) 向读者解释了为什么单链表难以实现,而且对于 Rust 新用户来说不是个好主意。

由于 Rust 的类型系统/所有权,实际上很难实现双向列表。 主要原因是一个节点似乎需要来自相邻节点的两个所有者。然而, 不过,这对于 NonNull<T> 是可能的,我们在 Vec<T> 学习 中讨论过。

这是简化的定义

// Note: NonNull<T> does NOT own the referent
#[repr(transparent)] // <-- enforces the same type representation as *const T
struct NonNull<T: ?Sized> {
    pointer: *const T,
}

struct Node<T> {
    next: Option<NonNull<Node<T>>>, // Not Option<Box<Node<T>>>
    prev: Option<NonNull<Node<T>>>,
    element: T,
}

struct LinkedList<T> {
    head: Option<NonNull<Node<T>>>,
    tail: Option<NonNull<Node<T>>>,
    len: usize,
    marker: PhantomData<Box<Node<T>>>, // <-- sound dropck
}

为什么不是 Option<Box<Node<T>>> ?

如果我们用 Box<Node<T>> 来代替,看看有什么不同,这可能是个好主意。 我们讨论了什么是 Unique<T> 以及它与 NonNull<T> 有何不同,但作为一个快速提醒, Unique<T> 拥有 referent 而 NonNull<T> 没有, 实际上, Box<T> (用于堆分配的指针类型) 包装了 Unique<T> 提供了与 Unique<T> 交互的新的接口。

让我们考虑 Node<T> 使用 Box (playpen link)

struct Node<T> {
    prev: Option<Box<Node<T>>>,
    next: Option<Box<Node<T>>>,
    element: T,
}

fn main() {
    let mut head_node = Node {
        prev: None,
        next: None,
        element: 1,
    };
    
    let next_node = Node {
        prev: Some(Box::new(head_node)), // <-- head_node is moved here
        next: None,
        element: 2,
    };
    
    head_node.next = Some(Box::new(next_node)); // Not good!
}

这要求 Use-After-Free (UAF) 所以我们直到我们不应该进一步推进 Undefined Behavior (UB) 的行为。 不过, 使用一个 non-owning NonNull<T> 可以解决以下问题 (playpen link)

use std::ptr::NonNull;

struct Node<T> {
    prev: Option<NonNull<Node<T>>>,
    next: Option<NonNull<Node<T>>>,
    element: T,
}

fn main() {
    let mut head_node = Node {
        prev: None,
        next: None,
        element: 1,
    };
    
    let next_node = Node {
        prev: NonNull::new(&mut head_node as *mut _),
        next: None,
        element: 2,
    };
    
    head_node.next = NonNull::new(&next_node as *const _ as *mut _);
}

但是我们如何确保这是合理的, 特别是把它用于 LinkedList<T>。确切的说

然而 PhantomData 和 dropck 有什么关系?

我一直在试图理解 PhantomData 和 dropck 之间的深层关系(LinkedList<T> 也是如此),但是找不到任何明确的解释,所以我在用户频道问了它并得到了一个 令人惊奇的答案 可以被推广到 Vec, LinkedList 等。

本文翻译自 Rust std study series: LinkedList

发表评论

电子邮件地址不会被公开。 必填项已用*标注

− 9 = 1