Общее поле структуры Rust для Deref<Target=Self>
Я пытаюсь создать код Rust, который манипулирует рекурсивной (древовидной) структурой данных. Наивно можно было бы определить его как
struct ALinkedList {
value: i32,
next: Option<Box<Self>>
}
Чтобы поэкспериментировать с различными макетами памяти и отдельным дизайном алгоритма от хранилища, я хотел бы обобщить определение до чего-то вроде
struct ALinkedList<D: Deref<Target=Self>> {
value: i32,
next: Option<D>
}
но при попытке создать экземпляр ALinkedList я получаю
64 | let t: ALinkedList<Box<_>> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
| ^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size
Мои вопросы:
- Можно ли заставить эти рекурсивные определения типов работать в Rust?
- Если нет, то какие другие шаблоны проектирования я могу использовать для представления древовидной структуры без жесткого кодирования того, как ее дочерние элементы хранятся и разыменовываются в памяти?
Ответы 1
К сожалению, в настоящее время Rust не может работать с бесконечно глубокими дженериками.
Есть способ использовать GAT (Generic Associated Types), к сожалению, все еще только по ночам (игровая площадка):
#![feature(generic_associated_types)]
use std::ops::Deref;
struct ALinkedList<A: Allocator> {
value: i32,
next: Option<A::Allocated<Self>>
}
impl<A: Allocator> ALinkedList<A> {
fn set_next(&mut self, next: Self) {
self.next = Some(next.into()) // create a new allocation via From
}
}
trait Allocator {
type Allocated<T>: Deref<Target=T> + From<T>;
}
struct BoxAllocator;
impl Allocator for BoxAllocator {
type Allocated<T> = Box<T>;
}
fn main() {
let mut t: ALinkedList<BoxAllocator> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
t.set_next(ALinkedList{value: 1, next: None});
}
Это было предназначено для создания выделений из реализации LinkedList. Глядя на это, я думаю, что чище использовать From. Обновлен код и добавлен пример того, как это работает.
Спасибо! Я играл с этим и пытался заменить структуру перечислением, и в некоторых случаях она работает нормально, как в вашем примере, но в других она не компилируется: площадка. В частности, enum CLinkedList<A: Allocator> { Head, Next(A::Allocated<Self>) } не компилируется и выдает overflow evaluating the requirement '...: Sized' . Является ли это ошибкой компилятора из-за того, что GAT неполные, или я что-то неправильно понимаю в размерах?
Это действительно странная ошибка. Мне кажется, это ошибка, сообщите о проблеме с Rust!
Похоже, что метод типажа
allocateнигде в вашем коде не используется.