我有一个功能齐全的单链表。我唯一想做的额外事情是添加一个值来排序，以便当您推送（）一个项目时，它会抓取列表并将节点插入到正确的位置，以便当弹出列表时，排名最低的节点是总是先弹出。
这是操场上的链接。我该怎么做？
这里的代码片段，add() 方法是：
// Push will insert according to rank - rank is ordered lowest first
pub fn push(&mut self, elem: T, rank: i32) {
for ranked_node in self.head.iter_mut() {
if let Some(next) = ranked_node.next.as_mut() {
if next.rank >= rank {
// If the next is larger, add here
let new_node = Box::new(Node {
rank: rank,
elem: elem,
// New node points to next
next: Some(*next),
});
// set current node to our new noded
ranked_node.next = Some(new_node);
break;
}
// Else iterate to next
} else {
// There is no higher next node, add at end
let new_node = Box::new(Node {
rank: rank,
elem: elem,
next: None,
});
ranked_node.next = Some(new_node);
break;
}
}
}
当前形式的错误是
Compiling playground v0.0.1 (/playground)
error[E0507]: cannot move out of `*next` which is behind a mutable reference
--> src/lib.rs:29:36
|
29 | next: Some(*next),
| ^^^^^ move occurs because `*next` has type `Box<Node<T>>`, which does not implement the `Copy` trait
For more information about this error, try `rustc --explain E0507`.
error: could not compile `playground` (lib) due to previous error
warning: build failed, waiting for other jobs to finish...
error: could not compile `playground` (lib test) due to previous error
我尝试使用 mem::take() 但这需要实现默认值，这似乎不对。链接是参考，为什么不能直接复制呢？我必须实施复制吗？
实际上，我在解决这个问题上已经取得了一些进展。本质上，我的问题的直接答案是使用 Option::take()。你正在用“无”交换一些东西。
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
rank: i32,
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
// Push will insert according to rank - rank is ordered lowest first
pub fn push(&mut self, elem: T, rank: i32) {
if Option::is_none(&self.head) {
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
self.head = Some(new_node);
} else {
for ranked_node in self.head.iter_mut() {
if let Some(ref next) = ranked_node.next {
if next.rank >= rank {
// If the next is larger, add here
let new_node = Box::new(Node {
rank,
elem,
// New node points to next
next: Option::take(&mut ranked_node.next),
});
// set current node to our new noded
ranked_node.next = Some(new_node);
break;
}
// Else iterate to next
} else {
// There is no higher next node, add at end
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
ranked_node.next = Some(new_node);
break;
}
}
}
}
pub fn pop(&mut self) -> Option<T> {
self.head.take().map(|node| {
self.head = node.next;
node.elem
})
}
pub fn peek(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}
pub fn peek_mut(&mut self) -> Option<&mut T> {
self.head.as_mut().map(|node| {
&mut node.elem
})
}
pub fn into_iter(self) -> IntoIter<T> {
IntoIter(self)
}
pub fn iter(&self) -> Iter<'_, T> {
Iter { next: self.head.as_deref() }
}
pub fn iter_mut(&mut self) -> IterMut<'_, T> {
IterMut { next: self.head.as_deref_mut() }
}
}
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut cur_link = self.head.take();
while let Some(mut boxed_node) = cur_link {
cur_link = boxed_node.next.take();
}
}
}
pub struct IntoIter<T>(List<T>);
impl<T> Iterator for IntoIter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
// access fields of a tuple struct numerically
self.0.pop()
}
}
pub struct Iter<'a, T> {
next: Option<&'a Node<T>>,
}
impl<'a, T> Iterator for Iter<'a, T> {
type Item = &'a T;
fn next(&mut self) -> Option<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref();
&node.elem
})
}
}
pub struct IterMut<'a, T> {
next: Option<&'a mut Node<T>>,
}
impl<'a, T> Iterator for IterMut<'a, T> {
type Item = &'a mut T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node.next.as_deref_mut();
&mut node.elem
})
}
}
这是 Rust Playground 中的半工作代码link
但是，这里要么存在更高级别的逻辑问题，要么存在生锈错误。该代码仅适用于 2 个元素。当我添加第三个元素时，for 循环在到达最后一项之前退出，因此永远不会添加第三个元素。我是否因替换而破坏了记忆？
我认为在上面的行中
if let Some(ref next) = ranked_node.next {
破坏了迭代器？我只想在迭代时向前看一个链接！
因此，我尝试向 Node 添加一个访问器方法，该方法将向前查看并从下一个 Node 中复制 i32。
impl<T> Node<T> {
pub fn next_rank(&self) -> Option<i32> {
self.next.as_ref().map(|node| {
node.rank
})
}
}
然后像这样使用它...
if let Some(next_rank) = ranked_node.next_rank() {
但是迭代器的行为是一样的。它不会迭代到第三个元素。
这是另一个变体，它很丑陋，但它更明确并且显示了相同的问题..对我来说这看起来像是 Rust 中的一个错误。
一个前瞻函数，将排名值返回为 i32 :
impl<T> Node<T> {
pub fn next_rank(&self) -> i32 {
match self.next.as_ref() {
Some(n) => {n.rank},
_ => -1
}
}
}
迭代器现在只使用 next() :
// Push will insert according to rank - rank is ordered lowest first
pub fn push(&mut self, elem: T, rank: i32) {
if Option::is_none(&self.head) {
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
self.head = Some(new_node);
} else {
let mut miter = self.head.iter_mut();
loop {
let ranked_node = miter.next();
if ranked_node.is_some() {
let curr_node = ranked_node.unwrap();
let next_rank = curr_node.next_rank();
if next_rank >= 0 {
// If the current value to insert is less than
// the next node's value, insert here
if next_rank >= rank {
// If the next is larger, add here
let new_node = Box::new(Node {
rank,
elem,
// New node points to next
next: Option::take(&mut curr_node.next),
});
// set current node to our new noded
curr_node.next = Some(new_node);
break;
}
} else {
// There is no higher next node, add at end
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
curr_node.next = Some(new_node);
break;
}
} else {
// There is no higher next node, add at end
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
// This fails - ranked_node is None but it should be the 2nd element
ranked_node.unwrap().next = Some(new_node);
break;
}
}
}
}
关键点是使用
Option::take最终的推送方法是这样的，可能不太漂亮，但是很管用：
impl<T> Node<T> {
fn look_forward_node_rank(&mut self) -> Option<i32> {
self.next.as_ref().map(|node| {
node.rank
})
}
}
//...
pub fn push(&mut self, elem: T, rank: i32) {
if self.head.is_none() {
// A new list, push first node
let new_node = Box::new(Node {
rank,
elem,
next: self.head.take(),
});
self.head = Some(new_node);
} else {
let mut find_node = self.iter_mut();
loop {
let curr_node = find_node.ptr.as_deref_mut();
match curr_node {
Some(node) => {
match node.look_forward_node_rank() {
Some(next_rank) => {
if next_rank > rank {
let new_node = Box::new(Node {
rank,
elem,
next: Option::take(&mut node.next),
});
node.next = Some(new_node);
break;
}
},
_ => {
// At the end of the list
let new_node = Box::new(Node {
rank,
elem,
next: None,
});
node.next = Some(new_node);
break;
}
}
},
_ => { panic!("iter_mut()") } // Should not get here
}
find_node.next(); // want side effect of incrementing ptr
}
}
}
游乐场的最终答案：游乐场链接