Home Rhyylen
Contatto
 
 
   
Rust Language
Capitolo 40
Altre stutture dati

Rust non si limita alle strutture dati che abbiamo incontrato finora. Ce ne sono molte altre utili magari per scopi specifici. In questa sede le presentiamo rapidamente senza aver la pretesa di sviscerarle in maniera completa, tutti i metodi sono disponibili nella documentazione ufficiale, ma tenetele presente quando ideate i vostri programmi. In questa sezione userò un metodo di esposizione (non esaustiva) molto simile ad un reference allo scopo di fornire una strada facile per lavorare con questi costrutti.

VecDeque<T>
Si tratta sostanzialmente di un buffer circolare simile in tutto e per tutto ad un Vec! ma che per la sua particolare conformazione è molto vantaggioso in termini prestazionali per quanto riguarda gli inserimenti all'inizio ed alla fine mentre è più lento per quanto concerne gli accessi randomici. Evidentemente è ottimo per gestire code.

use std::collections::VecDeque;
fn main() {    
  let mut deque = VecDeque::new();    
  deque.push_back(1); // Inserimento alla fine    
  deque.push_front(2); // Inserimento all'inizio    
  println!("{:?}", deque.pop_front()); // Rimozione dall'inizio
}

LinkedList<T>
E' una lista doppiamente linkata. Generalmente offre buone prestazioni per gli inserimento e le cancellazioni al centro ma è abbastanza inefficiente per quanto riguarda gli accessi casuali. Il suo uso è sconsigliato sul sito ufficiale e anche altrove, in favore di Vec o VecDeque mentre si può usare quando si è assolutamente certi di dover lavorare al centro della sequenza.

use std::collections::LinkedList;
fn main() {
  let mut list: LinkedList<i32> = LinkedList::new();
  list.push_back(10); // Inserisce alla fine
  list.push_front(20); // Inserisce all'inizio
  println!("{:?}", list.pop_front()); // Rimuove dall'inizio (20)
  println!("{:?}", list.pop_back()); // Rimuove dalla fine (10)
}

HashMap<K,V>
Questo costrutto è molto interessante. Si tratta di una collezione chiave - valore quindi è ottimale per associare valori randomici a chiavi randomiche. Di seguito lacune regole di base:

  -- per ogni chiave vi deve essere uno e un solo valore
  -- le chiavi devono implementare i trait Hash ed Eq.
  -- gli elementi non sono ordinati, attenzione in particolare a questo punto perchè ne riparleremo.

L'uso di questo costrutto è molto ampio, in questa sede presento le operazioni fondamentali per il suo utilizzo:

costruzione tramite  new + insert:

use std::collections::HashMap;
fn main() {    
    let mut map = HashMap::new();    
    map.insert(1, "uno"); // Inserisce (1, "uno");    
    map.insert(2, "due"); // Inserisce (2, "due");    
    println!("{:?}", map);
}

Il problema usando insert è che se una coppia chiave valore esiste già viene sovrascritta. Più avanti vedremo una soluzione.

costruzione tramite from:

use std::collections::HashMap;
fn main() {
    let map = HashMap::from([
    (1, "uno"),
    (2, "due"),
    (3, "tre"),
    ]);
    println!("{:?}", map);
}

costruzione tramite collect

use std::collections::HashMap;
fn main() {
    let pairs = vec![
    (1, "uno"),
    (2, "due"),
    (3, "tre"),
    ];
    let map: HashMap<_, _> = pairs.into_iter().collect();
    println!("{:?}", map);
}

Quest'ultimo metodo è molto usato, da notare l'istruzione  HashMap<_, _> che sfrutta l'inferenza di tipo per determinare il tipo delle coppie chiave valore, ovviamente i tipi devono essere chiaramente definiti ma in questo caso eviterete di esplicitarli a mano.

rimozione di una chiave - remove(&chiave)
questa istruzione restituisce un option che ci dà o il valore corrispondente alla chiave rimossa oppure none se questa non esiste. Quest'ultima cosa mi piace molto, in altri linguaggi l'accesso alla chiave non esistente è più complesso da gestire. Vediamo un esempio completo:

   
1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::HashMap;
fn main() {
    let vett = vec![
        (1, "uno"),
        (2, "due"),
        (3, "tre"),
    ];
    let mut map: HashMap<_, _> = vett.into_iter().collect();
    let x = map.remove(&1);
    println!("{:?}", x);
    let y = map.remove(&8);
    println!("{:?}", y);
}

Trovare una chiave ed estrarne il valore - get(&chiave)
del tutto analogo al caso precedente tuttavia va sottolineato che restituisce un riferimento al valore della chiave che abbiamo trovato.

   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashMap;
fn main() {
    let vett = vec![
    (1, "uno"),
    (2, "due"),
    (3, "tre"),
    ];
    let map: HashMap<_, _> = vett.into_iter().collect();
    if let Some(value) = map.get(&2) {
    println!("Valore trovato: {}", value);
    } else {
        println!("Chiave non trovata");
    }
}

Si può provare a sostituire un altro numero diverso da 1, 2 o 3 alla riga 9 per avere il messaggio alla riga 12

Iterare gli elementi di un HashMap
Ovviamente si può utilizzare un normale iteratore:

use std::collections::HashMap;
fn main() {    
    let vett = vec![(1, "uno"),(2, "due"),(3, "tre"),];    
    let map: HashMap<_, _> = vett.into_iter().collect();    
    for (key, value) in &map {        
    println!("Chiave: {}, Valore: {}", key, value);    
    }
}

A questo punto dobbiamo affrontare il problema dell'inserimento di una chiave già esistente e della modifica di una chiave presente. Per il primo punto usiamo il seguente metodo:
entry(key).or_insert(value)  che appunto effettua l'inserimento solo se la chiave non esiste:

use std::collections::HashMap;
fn main() {
    let vett = vec![
        (1, "uno"),
        (2, "due"),
        (3, "tre"),
    ];
    let mut map: HashMap<_, _> = vett.into_iter().collect();
    map.entry(2).or_insert("nuovo");
    println!("{:?}", map);
    map.entry(4).or_insert("nuovo");
    println!("{:?}", map);
}

Con il seguente output:

{2: "due", 3: "tre", 1: "uno"}
{2: "due", 1: "uno", 4: "nuovo", 3: "tre"}

Se invece dobbiamo sostituire un valore dobbiamo ricorrere a
entry(key).and_modify(|val| ...) che effettua la modifica solo se esiste la chiave.

use std::collections::HashMap;
fn main() {
    let vett = vec![
        (1, "uno"),
        (2, "due"),
        (3, "tre"),
    ];
    let mut map: HashMap<_, _> = vett.into_iter().collect();
    map.entry(2).and_modify(|val| *val = "modificato");
    println!("{:?}", map);
}

che ci fornisce quanto segue:

{3: "tre", 1: "uno", 2: "modificato"}

Da notare che facciamo uso di una chiusura e successiva dereferenziazione necessaria in quanto val è un riferimento mutabile, come da definizione del metodo:

pub fn and_modify(self, f: F) -> Self
where
F: FnOnce(&mut V),
 
Se la chiave non esiste il metodo non fa nulla.

Banale dirlo ma questa struttura merita un'occhiata approfondita anche sul sito ufficiale.

Come avevo detto, attenzione al fatto che in una HashMap gli elementi non sono ordinati. Esiste una struttura simile che rimedia a questo fatto stiamo parlando dei
BTreeMap

Rispetto a HashMap si basa su un albero bilanciato permettendo un ordinamento degli elementi. Vediamo in dettaglio le differenze

HashMap

  • Implementazione: Basata su una tabella hash.

  • Prestazioni: Offre tempi di accesso molto rapidi, con operazioni di inserimento, cancellazione e ricerca che hanno una complessità media di O(1).

  • Ordinamento: Non mantiene le chiavi in ordine. L'ordine delle chiavi dipende dalla funzione di hash.

  • Uso tipico: Adatta per casi in cui è necessario l'accesso rapido ai dati e l'ordinamento delle chiavi non è importante.

BTreeMap

  • Implementazione: Basata su un albero B.

  • Prestazioni: Offre tempi di accesso più lenti rispetto a HashMap, con operazioni di inserimento, cancellazione e ricerca che hanno una complessità di O(log n).

  • Ordinamento: Mantiene le chiavi in ordine. Le chiavi sono ordinate in base all'ordine naturale o in base a un comparatore fornito.

  • Uso tipico: Adatta per casi in cui è necessario mantenere le chiavi ordinate o quando è necessario eseguire operazioni di range query (come trovare tutte le chiavi in un intervallo specifico).


I metodi da usare su un BTreeMap sono del tutto simili a quelli usati con HashMap e pertanto mostro solo un esempio standard:

   
1
2
3
4
5
6
7
8
9
10
11
12
13
use std::collections::BTreeMap;
fn main() {
    // 1) Creazione di un BTreeMap vuoto
    let mut map = BTreeMap::new();  
    // 2) Inserimento di due elementi
    map.insert(1, "uno");
    map.insert(2, "due");  
    println!("Dopo inserimento: {:?}", map);  
    // 3) Cancellazione del primo elemento (chiave 1)
    map.remove(&1);  
    // 4) Stampa finale del BTreeMap
    println!("Dopo rimozione: {:?}", map);
}

Esistono poi altri metodi utili come:

clear - che rimuove tutti gli elementi
len   - che restituisce la lunghezza

Interessante ora è introdurre la struttura detta HashSet. In Rust, questa è una collezione di elementi unici non ordinati. È implementato utilizzando una tabella hash, il che lo rende efficiente per le operazioni di inserimento, rimozione e ricerca. HashSet è ideale quando abbiamo bisogno di memorizzare un insieme di valori distinti e non ci interessa l'ordine in cui sono memorizzati. Un "insieme", appunto. Utile quando ci serve un accesso rapido e non un ordine preciso. Anche qui diamo una carrellata di metodi utili:

Creazione: usiamo in questo caso il solito new():

use std::collections::HashSet;
fn main() {    
  let set: HashSet = HashSet::new();    
  println!("HashSet vuoto: {:?}", set);
}

Per popolare il nostro insieme possiamo ricorrere a insert,

use std::collections::HashSet; fn main() {    
  let mut set: HashSet = HashSet::new();    
  println!("HashSet vuoto: {:?}", set);    
  set.insert(1);    
  set.insert(2);    
  set.insert(2); // Duplicato, ignorato
  println!("{:?}", set);
}

Come evidenziato nel commento, insert non fa nulla se l'elemento che cerca di inserire esiste già.

Oppure si può ricorrere a collect ovvero ad un iteratore:

use std::collections::HashSet;
fn main() {    
  let set: HashSet<_> = [1, 2, 3, 4].iter().cloned().collect();    
  println!("{:?}", set);
}

Per cercare un elemento possiamo usare contains:

use std::collections::HashSet;
fn main() {    
  let set: HashSet<_> = [1, 2, 3, 4].iter().cloned().collect();    
  println!("{:?}", set);    
  if set.contains(&1) {    
  println!("L'elemento 1 è presente nel set");    
}
}

mentre per rimuoverlo abbiamo remove:

use std::collections::HashSet;
fn main() {    
  let mut set: HashSet<_> = [1, 2, 3, 4].iter().cloned().collect();    
  println!("{:?}", set);    
  if set.contains(&1) {    
    println!("L'elemento 1 è presente nel set");    
  }    
  set.remove(&1);    
  println!("{:?}", set);
}

mentre per iterare possiamo fare come segue:

use std::collections::HashSet;
fn main() {    
  let set: HashSet<_> = [1, 2, 3, 4].iter().cloned().collect();    
  for value in &set {    
    println!("{}", value);    
  }
}

Come nel caso precedente, abbiamo anche BTreeSet che si basa su un albero invece che su una tabella hash. Esso mantiene gli elementi ordinati secondo l'ordine naturale degli stessi (o un comparatore fornito). E anche in questo caso valgono gli stessi metodi visti per HashSet. E anche in questo caso metodi come clean() e len() rispettivamente svuotano la struttura e ne restituiscono la lunghezza. Ecco un po' di codice:
use std::collections::BTreeSet;
fn main() {
    // 1) Creazione di un BTreeSet
    let mut set = BTreeSet::new();
    // 2) Inserimento di elementi
    set.insert(10);
    set.insert(20);
    set.insert(30);
    set.insert(20); // Duplicato, verrà ignorato
    // 3) Calcolare la lunghezza
    let lunghezza = set.len();
    // 4) Stampa del BTreeSet e della lunghezza
    println!("BTreeSet: {:?}", set);
    println!("Lunghezza del BTreeSet: {}", lunghezza);
}

Siamo andati via veloci e altre cose sarebbero da dire, ad esempio la copia e la possibilità di switchare tra un costrutto e l'altro ma lo faremo caso mai in una seconda edizione di queste lezioni....