Я только начинаю работать с ржавчиной и пытаюсь реализовать некоторые простые структуры данных. Я получаю следующую ошибку в итераторе для двусвязного списка и не могу понять, почему это происходит.
use std::cell::RefCell;
use std::rc::Rc;
struct Node<T> {
value: T,
next: Option<Rc<RefCell<Node<T>>>>,
prev: Option<Rc<RefCell<Node<T>>>>,
}
impl<T> Node<T> {
fn new(value: T) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Node {
value,
next: None,
prev: None,
}))
}
}
pub struct DoublyLinkedList<T> {
head: Option<Rc<RefCell<Node<T>>>>,
tail: Option<Rc<RefCell<Node<T>>>>,
len: usize,
}
impl<T> DoublyLinkedList<T> {
pub fn new() -> Self {
DoublyLinkedList {
head: None,
tail: None,
len: 0,
}
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn push_front(&mut self, value: T) {
let new_node = Node::new(value);
match self.head.take() {
Some(old_head) => {
old_head.borrow_mut().prev = Some(new_node.clone());
new_node.borrow_mut().next = Some(old_head);
self.head = Some(new_node);
}
None => {
self.head = Some(new_node.clone());
self.tail = Some(new_node);
}
}
self.len += 1;
}
pub fn push_back(&mut self, value: T) {
let new_node = Node::new(value);
match self.tail.take() {
Some(old_tail) => {
old_tail.borrow_mut().next = Some(new_node.clone());
new_node.borrow_mut().prev = Some(old_tail);
self.tail = Some(new_node);
}
None => {
self.head = Some(new_node.clone());
self.tail = Some(new_node);
}
}
self.len += 1;
}
pub fn pop_front(&mut self) -> Option<T> {
self.head.take().map(|old_head| {
match old_head.borrow_mut().next.take() {
Some(new_head) => {
new_head.borrow_mut().prev = None;
self.head = Some(new_head);
}
None => {
self.tail = None;
}
}
self.len -= 1;
Rc::try_unwrap(old_head).ok().unwrap().into_inner().value
})
}
pub fn pop_back(&mut self) -> Option<T> {
self.tail.take().map(|old_tail| {
match old_tail.borrow_mut().prev.take() {
Some(new_tail) => {
new_tail.borrow_mut().next = None;
self.tail = Some(new_tail);
}
None => {
self.head = None;
}
}
self.len -= 1;
Rc::try_unwrap(old_tail).ok().unwrap().into_inner().value
})
}
pub fn iter(&self) -> Iter<T> {
Iter {
next: self.head.as_ref().map(|node| node.clone()),
}
}
}
pub struct Iter<T> {
next: Option<Rc<RefCell<Node<T>>>>,
}
impl<T> Iterator for Iter<T> {
type Item = T;
fn next(&mut self) -> Option<Self::Item> {
self.next.take().map(|node| {
self.next = node
.borrow()
.next
.as_ref()
.map(|next_node| next_node.clone());
node.borrow().value
// Rc::try_unwrap(node).ok().unwrap().into_inner().value
})
}
}
Я бы подумал, что заимствование сможет получить внутреннее значение RefCell, но я получаю следующую ошибку:
cannot move out of dereference of `Ref<'_, Node<T>>`
node.borrow().value
move occurs because value has type `T`, which does not implement the `Copy` trait
Однако закомментированный код ниже работает.
Вы также можете поделиться структурой Node, чтобы мы могли протестировать код
Вероятно, должно быть type Item = &'a T; с заменой Iter<T> на Iter<'a, T>, а затем next() может вернуть ссылку.
@Yilmaz Я обновил его, чтобы показать весь код.
@cdhowie Я тоже пошел по этому пути, получая другую ошибку, но все еще не работая. Я бы разместил полный код, но я не думаю, что он поместится здесь.
@Cerberus На самом деле я прошел через половину этого, прежде чем начать самостоятельно, это помогло мне многое понять, поэтому я сбит с толку этим.
Общий принцип в Rust:
&T
, вы можете читать из T
. Это ситуация, в которой вы находитесь.&mut T
, вы можете читать, а также видоизменять T
; и вы можете убрать T
, но только если вы поменяете замену (с std::mem::swap
или одним из его родственников).T
то вы можете сделать все что позволяет &mut T
и тоже съехать без замены.Чтобы переместить значение из RefCell без замены, ваш
Rc::try_unwrap(node).ok().unwrap().into_inner().value
Это правильный способ сделать это; деконструировать обертки, пока у вас не будет значения. Многие типы Rust будут иметь методы в стиле into_inner() именно для того, чтобы такие вещи были возможны.
Спасибо за объяснение, что мне не ясно, так это то, что это будет работать только в том случае, когда есть значение, но в противном случае будет паника. Я знаю, потому что я написал простой тест, который вызывает это, когда значение равно «Нет». Итак, как мне сделать это так, чтобы не вызвать панику и, по сути, не предполагать «ok ()». Кроме того, я здесь запутался, потому что, если я вызываю «заимствование ()», почему это «перемещает» значение? Я думал, что «заимствование» — это неизменяемая ссылка, которая может быть передана и не вызовет «перемещения». В противном случае название «заем» вводит в заблуждение.
@Джон О, я вижу настоящую проблему. Я думал, что ваш итератор намеревался использовать список (вернуть значения и уничтожить узлы). Если вы хотите выполнить итерацию по списку, не уничтожая его, вам нужно будет изменить итератор так, чтобы он возвращал либо Ref<T>s, а не Ts, либо clone каждый элемент списка.
Спасибо, мне придется обработать это, потому что все это время, пока я учился, я думал, что «одолжить» было на самом деле «одолжить». Вы только что перевернули все, что я думал, что знал с ног на голову :).
@John Заимствование - это заимствование, но ход нельзя сделать с помощью заимствования, и вы пытались сделать ход.
Не ответ, а популярная ссылка по теме, которой рекомендуется следовать, если вы все равно делаете что-то подобное: rust-unofficial.github.io/too-many-lists