Matrice come campo struct

Question

Vorrei creare una struttura ad albero non binaria in Rust. Ecco una prova

struct TreeNode<T> { 
    tag : T, 
    father : Weak<TreeNode<T>>, 
    childrenlists : [Rc<TreeNode<T>>] 
} 

Sfortunatamente, questo non viene compilato.

main.rs:4:1: 8:2 error: the trait `core::marker::Sized` is not implemented for the type `[alloc::rc::Rc<TreeNode<T>>]` [E0277] 
main.rs:4 struct TreeNode<T> { 
main.rs:5  tag : T, 
main.rs:6  father : Weak<TreeNode<T>>, 
main.rs:7  childrenlist : [Rc<TreeNode<T>>] 
main.rs:8 } 
main.rs:4:1: 8:2 note: `[alloc::rc::Rc<TreeNode<T>>]` does not have a constant size known at compile-time 
main.rs:4 struct TreeNode<T> { 
main.rs:5  tag : T, 
main.rs:6  father : Weak<TreeNode<T>>, 
main.rs:7  childrenlist : [Rc<TreeNode<T>>] 
main.rs:8 } 
error: aborting due to previous error 

Il codice viene compilato se si sostituisce un array con un Vec. Tuttavia, la struttura è immutabile e non ho bisogno di un numero Vec.

Ho sentito che potrebbe essere possibile avere un campo struct con dimensioni sconosciute al momento della compilazione, a condizione che sia univoco. Come possiamo farlo?

Answer 1

Rust non ha il concetto di una matrice di lunghezza variabile (stack), che sembra si stia tentando di utilizzare qui.

Rust ha un paio di tipi diversi di array.

• Vec<T> ("vettore"): Dinamicamente dimensionato; allocata dinamicamente sull'heap. Questo è probabilmente che cosa vuoi usare. Inizializzalo con Vec::with_capacity(foo) per evitare la sovrassegnazione (questo crea un vettore vuoto con la capacità specificata).
• [T; n] ("array"): dimensioni statiche; vive in pila.Devi conoscere le dimensioni al momento della compilazione, quindi questo non funzionerà per te (a meno che non abbia analizzato male la tua situazione).
• [T] ("slice"): Unsized; di solito utilizzato da &[T]. Questa è una vista in un insieme contiguo di T s in memoria da qualche parte. Puoi ottenerlo prendendo come riferimento un array o un vettore (chiamato "prendere una fetta di un array/vettore"), o anche prendendo una vista in un sottoinsieme dell'array/vettore. Essendo unsized, [T] non può essere utilizzato direttamente come variabile (può essere utilizzato come membro di una struct non isolata), ma è possibile visualizzarlo da dietro un puntatore. I riferimenti a [T] sono grassi; cioè hanno un campo in più per la lunghezza. &[T] sarebbe utile se si desidera memorizzare un riferimento a un array esistente; ma non penso che sia quello che vuoi fare qui.

Answer 2

Se non si conosce la dimensione della lista in anticipo, sono disponibili due opzioni:

1. &[T] che è solo un riferimento a qualche pezzo di memoria che non si possiede
2. Vec<T> che è il tuo spazio di archiviazione.

La cosa corretta qui è utilizzare un Vec. Perché? Perché vuoi che l'elenco dei bambini (array di Rc) sia effettivamente di proprietà di TreeNode. Se hai usato uno &[T], significa che qualcun altro avrebbe mantenuto l'elenco, non lo TreeNode. Con alcuni trucchi di durata, potresti scrivere del codice valido, ma dovresti andare molto lontano per compiacere il compilatore perché il riferimento preso in prestito dovrebbe essere valido almeno fino allo TreeNode.

Infine, una frase in questione mostra un equivoco:

Tuttavia, la struttura è immutabile e non ho bisogno di un Vec sovrassegnata.

Si confondono la mutevolezza e la proprietà. Certo, puoi avere un Vec immutabile. Sembra che tu voglia evitare di allocare memoria dall'heap, ma questo non è possibile, proprio perché non conosci la dimensione dell'elenco dei bambini. Ora, se si è interessati alla sovrastimazione, è possibile perfezionare l'archiviazione vettoriale con metodi come with_capacity() e shrink_to_fit().

Una nota finale: se si conosce effettivamente la dimensione dell'elenco perché è stato risolto in fase di compilazione, è sufficiente utilizzare uno [T; n] in cui è noto n in fase di compilazione. Ma non è lo stesso di [T].