Container
Unter Containern verstehen wir Typen, die mehrere Elemente beinhalten und Iteration über diese erlauben. Viele Container sind
generische Typen, da sie für verschiedene Elementtypen funktionieren. Wir kennen bereits die Container String, Vec<T> und
[T; n]. Es gibt in Rust noch weitere Container, die nicht Gegenstand dieses Skripts sind. Wir beschränken uns hier auf
die Container, die 99% aller Use-Cases im Programmiererleben des Autors abdecken.
Quiz
Worin unterscheiden sich Arrays und Vektoren?
Container mit zusammenhängendem Speicher
Arrays und Vektoren legen ihre Elemente in zusammenhängenden Speicherbereichen ab. Das hat einige Vorteile.
- Die CPU liest Elemente aus dem Speicher in Blöcken gewisser Größe ein. Diese Blöcke heißen auch Cache-Lines. Bei der Iteration über Container mit zusammenhängendem Speicher ist die Wahrscheinlichkeit höher, dass auch Elemente die als nächstes gebraucht werden, bereits mit der aktuellen Cache-Line eingelesen wurden.
- Die Allokation von Speicher am Stück ist oft effizienter.
- Oft erhöht das die Interoperabilität zwischen System oder Sprachen. Ein Beispiel ist die Verarbeitung von in Python allokierten NumPy-Arrays mit Rust aus Effizienzgründen.
Neben den Containern bieten auch ihre Slices wie [T] die Möglichkeit über die beinhalteten Elemente zu iterieren.
Quiz
Wie heißen Slices von Strings?
Welchen Nachteil haben Container zusammenhängenden Speichers zumindest in der Theorie?
Um beispielsweise einen Vec<i32> mit den Werten 1, 3, 5 und 7 zu erstellen gibt es verschiedene Möglichkeiten.
- Das Makro
vec!ist uns schon begegnet.#![allow(unused)] fn main() { let v = vec![1, 3, 5, 7]; } - Iteratoren sind eine weitere Möglichkeit.
#![allow(unused)] fn main() { let v = (1..=7).filter(|i| i % 2 == 1).collect::<Vec<_>>(); assert_eq!(v, vec![1, 3, 5, 7]); } - Wir können uns der Veränderlichkeit via
mutbedienen, einen leerenVecanlegen und die gewünschten Werte hinzufügen.#![allow(unused)] fn main() { let mut v = Vec::new(); v.push(1); v.push(3); v.push(5); v.push(7); assert_eq!(v, vec![1, 3, 5, 7]); }
Wir haben bereits die Methoden sort und sort_by_key kennen gelernt. Wir wollen nun einen Vektor aus Gleitkommazahlen
der Größe nach sortieren.
#![allow(unused)] fn main() { let mut v = vec![2.3, 1.2, 4.3, 9.6]; v.sort(); println!("{v:?}", v); }
Die Fehlermedlung, die wir bei der Ausführung bekommen, besagt, Gleitkommazahlen implementierten den Trait Ord nicht.
Typen die Ord implementieren sind total geordert. Das gilt aber für Gleitkommazahlen nicht, da
#![allow(unused)] fn main() { let x = 0.0/0.0; }
den Wert f64::NAN annimmt. Die Abkürzung NAN steht für not a number und es gilt
#![allow(unused)] fn main() { assert!(!(f64::NAN == f64::NAN)); assert!(f64::NAN != f64::NAN); assert!(!(f64::NAN >= f64::NAN)); assert!(!(f64::NAN <= f64::NAN)); }
Gleitkommazahlen können miteinander verglichen werden und bei den meisten Werten kommt sogar etwas sinnvolles heraus. Sie
implementieren den Trait PartialOrd. Wegen PartialOrd implementiert
f64 die Methode
#![allow(unused)] fn main() { fn partial_cmp(&self, other: &Rhs) -> Option<Ordering>; }
Der Rückgabetyp
Ordering
ist ein Aufzählungstyp mit den Varianten Less, Equal und Greater. Wenn self größer ist als other erwarten
wir dementsprechend den Wert Some(Ordering::Greater). Wenn die Werte nicht vergleichbar sind, gibt partial_cmp den
Wert None zurück.
Des Weiteren gibt es neben sort und sort_by_key es die Methode sort_by, die wie
sort_by_key eine Funktion als Parameter bekommt. Während sort_by_key die Elemente des Vektors in etwas
Vergleichbares1
transformiert, erwartet sort_by eine Vergleichsfunktion vom Typ FnMut(&T, &T) -> Ordering.
Wir können also einen Vec<f64> sortieren.
#![allow(unused)] fn main() { use std::cmp::Ordering; let mut v: Vec<f64> = vec![2.3, 1.2, f64::NAN, 4.3, 9.6]; v.sort_by(|a, b| match a.partial_cmp(b) { Some(o) => o, None => { if a.is_nan() { Ordering::Less } else { Ordering::Greater } } } ); println!("{v:?}"); }
Falls f64::NAN auftritt, entscheiden wir in diesem Fall, dass diese Werte an den Anfang kommen, also die Kleinsten sind.
Sowohl Arrays vom Typ [T; n] als auch Slices lassen sich ebenfalls sortieren.
Um Elemente aus einem Vec<T> zu entfernen, stellt Rust pop und remove bereit. Ersteres entfernt das letzte Element, letzteres
ein Beliebiges. Bei der Verwendung von remove werden alle Werte mit größerem Index als das Entfernte verschoben,
damit sie nach wie vor zusammenhängend im Speicher liegen.
Elemente entfernen mit remove
Es sei v ein Vec<i32> mit folgenden Inhalt
Wert |5|7|2|4|5|6|
Index |0|1|2|3|4|5|
Um das Element mit Index 1 zu entfernen, verwenden wir v.remove(1) und bekommen 7 zurück. v
wird zu
Elemente verschoben
< < < <
Wert |5|2|4|5|6|
Index |0|2|3|4|5|
|
Element wurde entfernt
Falls der Index-Parameter zu groß ist im Vergleich zur Länge des Vecs, bricht das Programm ab.
Elemente entfernen mit pop
Es sei v ein Vec<i32> mit folgenden Inhalt
Wert |5|7|2|4|5|6|
Index |0|1|2|3|4|5|
Das letzte Element entfernen wir mit v.pop() und bekommen Some(5) zurück. v
wird zu
Wert |5|7|2|4|5|
Index |0|1|2|3|4|
|
Element wurde entfernt
Falls v leer ist, gibt pop den Wert None zurück.
HashMaps
Eine HashMap<K, V> speichert Key-Value-Paare2.
Auf die Values des Typs V kann per Key des Typs K zugegriffen werden. Die Keys
können beispielsweise Zahlen, Strings oder &strs sein.
Beim Zugriff auf eine HashMap wird der Key durch eine Hashfunktion \( h: S \rightarrow I \) auf einen Index in einem dynamischen Array abgebildet.
Die Menge der hashbaren Keys \( S \) ist üblicherweise eine Menge deutlich größerer Kardinalität als die Menge der Möglichen Indizes
\( I\subseteq \{0, \dots, n\} \). Die Hashfunktion impliziert eine Grenze für die Typen, die als Keys verwendet werden können.
Der entsprechende Trait heißt std::hash::Hash. Ein weiterer Trait
den Keys implementieren müssen ist std::cmp::Eq.
Eq stellt sicher, dass alle Werte x,
die ein Typ annehmen kann, per == verglichen werden können und dass (x == x) == true für alle x gilt.
Quiz
Welcher allgegenwärtige Typ kann nicht als Key verwendet werden und warum nicht?
In seltenen Fällen kann es passieren, dass die Hashfunktion zwei Keys auf den selben Index abbildet. In diesem Fall
spricht man von einer Kollision. Es gibt verschiedene Strategien mit Kollisionen umzugehen.
Für unsere Zwecke reicht es zu verstehen, dass Kollisionen
Zeit kosten. Theoretisch kann man einen Wert in konstanter Zeit aus einer HashMap lesen und in ablegen, wenn es keine Kollision gibt.
Konstante Zeit bedeutet unabhängig von der Anzahl der Elemente im Container. Da die Berechnung der Hashes Zeit kostet, sind HashMaps in
der Praxis nicht immer die effizienteste Lösung, selbst wenn es zu keiner Kollision kommen sollte.
Es folgen einige Beispiele zur Initialisierung von HashMaps. Die dunkle Seite der Veränderlichkeit steht mit einer einfachen
Lösung Gewehr bei Fuß.
#![allow(unused)] fn main() { use std::collections::HashMap; let mut h = HashMap::new(); h.insert("a", 1); h.insert("b", 10); h.insert("c", 100); h.insert("d", 1000); println!("{h:?}"); }
Um ohne mut auszukommen, existiert die Implementierung des From-Traits. Die entsprechende Methode from erwartet
einen Array von Key-Value-Tupeln.
#![allow(unused)] fn main() { use std::collections::HashMap; let h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); println!("{h:?}"); }
Iteratoren über Paare vom Typ (T, U) können in einer HashMap gesammelt werden.
#![allow(unused)] fn main() { use std::collections::HashMap; let h = ["a", "b", "c", "d"] .iter() .enumerate() .map(|(i, c)| (c, 10i32.pow(i as u32))) .collect::<HashMap<_, _>>(); println!("{h:?}"); }
Um einzelne Werte auszulesen, können wir Dank der Index
-Trait-Implementierung eckige Klammern verwenden und bekommen direkt den Wert zurück.
#![allow(unused)] fn main() { use std::collections::HashMap; let h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); println!("{}", h["b"]); }
Vorsicht! Falls wir mit
[]nach einem Key fragen, der nicht vorhanden ist, bricht das Programm ab.
Wir können die Methode get verwenden, wenn wir herausfinden wollen, ob der Key existiert. Diese gibt
einen Wert vom Typ Option<&V> zurück.
#![allow(unused)] fn main() { use std::collections::HashMap; let h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); assert_eq!(Some(&10), h.get("b")); assert_eq!(None, h.get("e")); }
Die Methode insert mit der wir oben neue Werte hinzugefügt haben, überschreibt bestehende Werte.
#![allow(unused)] fn main() { use std::collections::HashMap; let mut h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); assert_eq!(10, h["b"]); h.insert("b", 20); assert_eq!(20, h["b"]); }
Da IndexMut nicht implementiert ist, können die in Python populäre Syntax
h["b"] = 20; nicht verwenden. Anstatt dessen gibt uns get_mut eine Option auf eine veränderliche Referenz.
Wenn man einen Wert nur hinzufügen will, falls er noch nicht existiert, ist die entry-Methode von Interesse.
#![allow(unused)] fn main() { use std::collections::HashMap; let mut h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); h.entry("b").or_insert(50); h.entry("e").or_insert(50); assert_eq!(10, h["b"]); assert_eq!(50, h["e"]); }
Die entry Methode gibt eine Instanz des Entry-Typen zurück,
der noch mehr Methoden zur Manipulation eines Eintrags bereit stellt. Zum Entfernen gibt es die Methode remove.
Iteratoren über Container
Neben iter gibt es noch die Methoden into_iter, iter_mut um über Vecs zu iterieren. Das Argument von iter
ist &self und das Argument von iter_mut ist &mut self. Die Methode iter gibt uns in jeder Iteration ein &T
und entsprechend bekommen wir von iter_mut in jeder Iteration ein &mut T. Der Trait IntoIter der die
Methode into_iter mitbringt, ist implementiert
für &Vec<T>, &mut Vec<T> und Vec<T>. Auf einem &Vec<T> verhält sich into_iter wie iter und auf einem
&mut Vec<T> wie iter_mut. Auf einer nicht-Referenz führt into_iter einen Move des Vecs durch. into_iter wird
auch bei einer for-Schleife verwendet.
Der folgende Schnipsel kompiliert nicht, da nach der for-Schleife v verschoben wurde.
#![allow(unused)] fn main() { let v = vec![1, 2, 3]; for i in v { println!("{i}"); } println!("{v:?}"); }
Wir können aber &Vec<i32>::into_iter verwenden, indem wir über eine Referenz iterieren.
#![allow(unused)] fn main() { let v = vec![1, 2, 3]; for i in &v { println!("{i}"); } assert_eq!(v, vec![1, 2, 3]); }
Die Methoden sind ebenfalls für [T; n] implementiert und verhalten sich vergleichbar. Nur falls T den Trait Copy implementiert,
wird die Instanz von [T; n] nicht verschoben sondern kopiert. Für Slices vom Typ [T; n] sind diese Methoden ebenfalls vorhanden.
Die Ausnahme ist [T]::into_iter. Erstens ergibt es nicht viel Sinn, Slices zu konsumieren, da sie Fenster in Container sind. Zweitens
können Slices nur als Referenzen verwendet werden. Iterator-Methoden über HashMaps sind
analog zu denen über Vecs vorhanden. Nur erzeugen sie Iteratoren über Tupel bestehend aus Key und Value.
Zusätzlich gibt es die Möglichkeit über Keys oder Values separat zu iterieren.
#![allow(unused)] fn main() { use std::collections::HashMap; let mut h = HashMap::from([("a", 1), ("b", 10), ("c", 100), ("d", 1000)]); for (k, v) in &h { println!("{k}: {v}"); } for k in h.keys() { println!("{k}"); } for v in h.values() { println!("{v}"); } }
Referenz
In der Rust Dokumentation findet sich eine vollständige Beschreibung der Container und ihrer Methoden, die wir von der Rust Standardbibliothek zur Verfügung gestellt bekommen.
1: Etwas, das verglichen werden kann.
2: Wir verwenden hier des öfteren die englischen Wörter Key und Value anstatt der
deutschen Wörter Schlüssel und Wert, da diese Begriffe in der Programmierwildnis insbesondere nahe HashMaps allgegenwärtig sind.