Как создать рекурсивную очередь?
Я пытаюсь реализовать рекурсивную очередь, используя trait Element<T> в качестве контейнера для всех функций различных узлов очереди и двух реализующих ее структур, называемых Node<T> и End.
Структура Node<T> должна обрабатывать все функциональные возможности самой очереди, а цель структуры End — работать с последним узлом.
У меня есть следующий код:
trait Element<T> {
fn append_item(self, item: T) -> Node<T>;
}
struct Node<T> {
data: T,
successor: Box<dyn Element<T>>
}
impl<T> Element<T> for Node<T> {
fn append_item(mut self, item: T) -> Node<T> {
self.successor = Box::new(self.successor.append_item(item));
self
}
}
struct End;
impl<T> Element<T> for End {
fn append_item(self, item: T) -> Node<T> {
Node { data: item, successor: Box::new(self) }
}
}
Проблема в том, что я получаю две ошибки:
- Невозможно переместить значение типа
dyn Element<T> - Тип параметра
Tможет не прожить достаточно долго
оба на одной строке в Node::append_item.
Теперь я понимаю, почему возникает первая ошибка (потому что размер dyn Element<T> не может быть определен статически), но я не знаю, как это обойти, и я понятия не имею, почему возникает вторая ошибка.
Если я позволю append_item взять изменяемую ссылку на себя, я потеряю возможность возвращать (принадлежащее) себе и, следовательно, я не могу вернуть новый узел в End::append_item
Ваш код мне не подходит. В append_item() разве не нужно создавать новый узел? successor инициализируется Box::new(), но внутри Box мы пытаемся сослаться на successor.
Ответы 2
error[E0161]: cannot move a value of type `dyn Element<T>`
--> src/lib.rs:12:35
|
12 | self.successor = Box::new(self.successor.append_item(item));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ the size of `dyn Element<T>` cannot be statically determined
Проблема здесь в том, что fn append_item(self, item: T) принимает self по значению, но в данном случае self имеет тип dyn Element<T>, который не имеет размера и поэтому никогда не может быть передан по значению.
Самое простое решение здесь — просто взять self: Box<Self> вместо этого. Это означает, что этот метод определен для Box<E> вместо прямого. Он будет прекрасно работать с типаж-объектами, такими как dyn Element<T>, и не требует изменения размера типа.
(Кроме того, в обновленном коде ниже я изменил тип возвращаемого значения на Box<Node<T>> для удобства, но это не обязательно, просто немного удобнее.)
trait Element<T> {
fn append_item(self: Box<Self>, item: T) -> Box<Node<T>>;
}
impl<T> Element<T> for Node<T> {
fn append_item(mut self: Box<Self>, item: T) -> Box<Node<T>> {
self.successor = self.successor.append_item(item);
self
}
}
impl<T> Element<T> for End {
fn append_item(self: Box<Self>, item: T) -> Box<Node<T>> {
Box::new(Node { data: item, successor: self })
}
}
error[E0310]: the parameter type `T` may not live long enough
--> src/lib.rs:12:26
|
12 | self.successor = Box::new(self.successor.append_item(item));
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...so that the type `T` will meet its required lifetime bounds
|
Проблема здесь в том, что dyn Trait имеет неявное время жизни. На самом деле это dyn '_ + Trait. Какое именно это время жизни, зависит от контекста, и вы можете прочитать точные правила в справочнике по Rust, но если ни содержащий тип, ни сам трейт не имеют ссылок, то время жизни всегда будет 'static.
Это случай с Box<dyn Element<T>>, который на самом деле Box<dyn 'static + Element<T>>. Другими словами, любой тип, содержащийся в Box, должен иметь 'static время жизни. Чтобы это имело место для Node<T>, также должно быть, что T имеет 'static время жизни.
Однако это легко исправить: просто следуйте совету компилятора добавить границу T: 'static:
impl<T: 'static> Element<T> for Node<T> {
// ^^^^^^^^^
// ...
}
Frxstrem уже разработал как обойти необходимость двигаться, используя Box<Self> в качестве приемника. Если вам нужна большая гибкость в типе параметра (т. е. иметь возможность хранить ссылки, а также собственные типы), вместо требования T: 'static вы можете ввести именованное время жизни:
trait Element<'a, T: 'a> {
fn append_item(self: Box<Self>, item: T) -> Node<'a, T>;
}
struct Node<'a, T: 'a> {
data: T,
successor: Box<dyn Element<'a, T> + 'a>,
}
impl<'a, T: 'a> Element<'a, T> for Node<'a, T> {
fn append_item(self: Box<Self>, new_data: T) -> Node<'a, T> {
Node {
successor: Box::new(self.successor.append_item(new_data)),
..*self
}
}
}
struct End;
impl<'a, T: 'a> Element<'a, T> for End {
fn append_item(self: Box<Self>, data: T) -> Node<'a, T> {
Node {
data,
successor: self,
}
}
}
Я бы сказал, что интерфейс весь испорчен. Я бы не использовал черты, я бы использовал перечисление. Я бы взял
append_itemизменяемую ссылку на себя вместо права собственности.