我正在尝试用 Rust 编写一个双向链表。主要的两种类型定义为:
struct IntList {
head: *mut Node,
tail: *mut Node,
size: usize,
}
#[derive(Copy)]
#[derive(Clone)]
struct Node {
data: i32,
prev: *mut Node,
next: *mut Node,
}
我使用了 2 个 util 函数:
pub unsafe fn raw_into_box<T>(raw: *mut T) -> Box<T> {
mem::transmute(raw)
}
pub fn box_into_raw<T>(b: Box<T>) -> *mut T {
unsafe { mem::transmute(b) }
}
而且,我想为列表类型创建一个插入方法:
impl IntList {
fn new() -> Self {
IntList {
head: ptr::null_mut(),
tail: ptr::null_mut(),
size: 0,
}
}
unsafe fn add_last(&mut self, v: i32) {
let node = Node { data: v, prev: self.tail, next: ptr::null_mut() };
let raw = box_into_raw(Box::new(node));
let node = *raw;
match self.size {
0 => {
self.head = raw;
self.tail = raw;
}
_ => unsafe {
// let mut last = *self.tail; // Notice here
// last.next = raw;
// not work
self.tail = raw;
}
}
self.size += 1;
println!("added:{}", node);
}
// ...
看哪,注释的行没有按预期工作。列表中的元素只有一种大小。然而,我改变了它们,如下所示:
(*self.tail).next = raw;
结果将是正确的。
所以我的问题是,二分法有什么区别:
(*self.tail).next = raw;
对
let mut last = *self.tail;
last.next = raw;
前者有效,后者无效。为什么我不能使用中间对象?
默认情况下,标识符模式将变量绑定到匹配值的副本或从匹配值中移动,具体取决于匹配值是否实现
。可以使用Copy
关键字将其更改为绑定到引用,或使用ref
绑定到可变引用。ref mut
在您的情况下,匹配的值是
Node
类型,它确实实现了 Copy
,因此在 let mut last = *self.tail;
中,mut last
标识符模式将 last
变量绑定到 Node
的 copy
*self.tail
。然后,您对该副本进行变异,当 last
超出范围时,该副本将被删除; *self.tail
中的内存保持不变。
要通过引用绑定来实现您的预期,您可以显式使用
ref mut
绑定,如上面引用中所述:
let ref mut last = *self.tail;
Rust 参考继续在绑定模式下进行记录:
为了更好地实现人体工程学,模式以不同的“绑定模式”运行,以便更轻松地将引用绑定到值。当参考值与非参考模式匹配时,它将自动被视为
ref
或绑定。 因此,您仍然可以通过首先创建对ref mut
*self.tail
的引用来使用非引用模式:
let last = &mut *self.tail;
在这两种情况下,如果您考虑
last
的类型,则发生的情况会更加明显:在您最初的尝试中,
last
属于 Node
类型,而在上述两种情况中,它属于 &mut Node
类型。
总而言之,实际上根本没有必要使用原始指针和 unsafe
代码(我会
强烈 鼓励您不要这样做)。例如,您可以按照以下方式执行操作:use std::{cell::{Cell, RefCell}, rc::Rc};
struct IntList {
head: Option<Rc<Node>>,
tail: Option<Rc<Node>>,
size: usize,
}
#[derive(Clone)]
struct Node {
data: Cell<i32>,
prev: RefCell<Option<Rc<Node>>>,
next: RefCell<Option<Rc<Node>>>,
}
impl IntList {
fn new() -> Self {
IntList {
head: None,
tail: None,
size: 0,
}
}
fn add_last(&mut self, v: i32) {
let prev = RefCell::new(self.tail.take());
let next = RefCell::new(None);
let node = self.tail.insert(Rc::new(Node { data: Cell::new(v), prev, next }));
if self.size == 0 {
self.head = Some(Rc::clone(node));
}
self.size += 1;
println!("added:{node}");
}
}
不可否认,这确实增加了存储和更新引用计数以及进行运行时借用检查的相当微不足道的成本,而基于原始指针的版本则不会。然而,即使您想避免这种情况,当标准库为您提供
(“具有自有节点的双向链表”)时,为什么要重新发明轮子呢?无论如何,请注意它的内容: 注意:使用
或VecDeque
几乎总是更好,因为基于数组的容器通常速度更快,内存效率更高,并且可以更好地利用 CPU 缓存。