Praxisteil & Übungen: Generische Programmierung

In diesem Praxisteil werden wir die mächtige Welt der Generics in Rust betreten. Bisher haben wir meist mit konkreten Datentypen gearbeitet (wie i32, String oder festen Strukturen). Doch in der realen Softwareentwicklung wollen wir oft Algorithmen und Datenstrukturen schreiben, die unabhängig vom konkreten Datentyp funktionieren – ohne dabei Code duplizieren zu müssen.

Wir werden Schritt für Schritt einen generischen Datencache entwerfen, der beliebige Schlüssel-Wert-Paare im Hauptspeicher zwischenspeichert. Dabei lernen wir, wie wir Typparameter einschränken (Trait Bounds), wie wir mit dem Borrow Checker interagieren und wie der Rust-Compiler unter der Haube generischen Code in hocheffizienten, konkreten Maschinencode übersetzt.

1. Praxis-Szenario: Ein flexibler In-Memory-Datencache

Stellen wir uns vor, wir bauen eine Anwendung, die Daten aus verschiedenen Quellen lädt: Benutzerdaten aus einer Datenbank (Schlüssel: u32 ID, Wert: User), Konfigurationsdateien aus dem Dateisystem (Schlüssel: String Dateipfad, Wert: String Inhalt) oder Wetterdaten von einer Web-API (Schlüssel: String Stadtname, Wert: WetterInfo).

Es wäre extrem ineffizient und fehleranfällig, für jeden dieser Anwendungsfälle eine eigene Cache-Struktur zu schreiben (z. B. einen UserCache, einen ConfigCache und einen WetterCache).

Unsere Aufgabe ist es daher, eine einzige, wiederverwendbare Struktur namens Cache<K, V> zu erstellen. Dieser Cache soll:

Beliebige Schlüssel vom Typ K und Werte vom Typ V aufnehmen können.
Über eine Methode insert Werte hinzufügen.
Über eine Methode get Werte sicher als Referenz auslesen.
Über eine Methode get_or_compute einen Wert dynamisch berechnen lassen, falls er noch nicht im Cache existiert.

Die Übungsaufgabe befindet sich im Verzeichnis:

exercises/14_generics/src/main.rs (Vervollständigen Sie dort die vorbereitete Struktur und deren Implementierung)

2. Didaktische Alltagsanalogie: Das universelle Sortiersystem

Bevor wir Code schreiben, betrachten wir eine Analogie aus dem echten Leben: Die universelle Lagerbox.

Stellen wir uns eine transparente Kunststoffbox vor. Diese Box ist ein “generischer Behälter”. Auf der Box steht kein Schild “Nur für Bananen”. Sie kann alles aufnehmen: Werkzeuge, Dokumente, Äpfel oder Socken. In der Sprache von Rust definieren wir diese Box als Box<T>, wobei T für das steht, was wir hineinlegen.

Doch was passiert, wenn wir diese Boxen in einem großen Lagerregal sortieren wollen? Wenn wir die Boxen stapeln möchten, müssen sie eine bestimmte Eigenschaft erfüllen: Sie müssen stapelbar sein. Wir können keine weichen, runden Boxen stapeln. Das Lagerregal stellt also eine Bedingung an die Box: “Ich kann jede Box aufnehmen, vorausgesetzt, sie implementiert die Eigenschaft ‘Stapelbar’.”

In Rust ist das ein Trait Bound. Wenn wir eine HashMap für unseren Cache verwenden, fordert die HashMap eine Bedingung an unsere Schlüssel-Box K: Sie muss eindeutig identifizierbar und vergleichbar sein. Auf Rust-Deutsch: Der Typ K muss die Traits Hash (zur Berechnung des Hashwerts) und Eq (zum exakten Vergleich bei Kollisionen) implementieren. Nur dann akzeptiert das “Lagerregal” (die HashMap) unseren Schlüssel.

3. Strukturierte Praxis-Einheiten

3.1 Get Started: Die generische Struktur definieren

Eine generische Struktur deklarieren wir, indem wir nach dem Strukturnamen spitze Klammern mit Platzhalter-Buchstaben (meist K für Key und V für Value) einfügen.

Beispiel:

#![allow(unused)]
fn main() {
use std::collections::HashMap;

// Eine generische Struktur mit zwei Typparametern
struct Cache<K, V> {
    store: HashMap<K, V>,
}
}

Erklärung:

Cache<K, V>: Das <K, V> signalisiert dem Compiler, dass diese Struktur generisch ist. K und V sind freie Variablen für Typen. Erst wenn wir eine Instanz von Cache erzeugen (z. B. mit String und i32), füllt der Compiler diese Platzhalter mit konkreten Typen aus.
store: HashMap<K, V>: Intern lagern wir die Daten in einer Standard-HashMap aus. Diese HashMap verwendet denselben Schlüsseltyp K und denselben Werttyp V.

Aufgabe: Definieren Sie in Ihrer Übungsdatei die Struktur Cache<K, V> mit dem privaten Feld store vom Typ HashMap<K, V>.

3.2 Die Geburtsstunde der Fehler: Trait Bounds und CDD

Nun wollen wir Methoden für unseren Cache definieren. Wir beginnen mit die Konstruktor-Funktion new() und einer Methode insert().

Der CDD-Ansatz: Wir provozieren den Compilerfehler

Lassen Sie uns versuchen, die Methoden naiv ohne Einschränkungen zu implementieren:

#![allow(unused)]
fn main() {
// Wir deklarieren die Implementierung generisch für K und V
impl<K, V> Cache<K, V> {
    // Konstruktor zum Erstellen eines neuen Caches
    fn new() -> Self {
        Cache {
            store: HashMap::new(),
        }
    }

    // Methode zum Einfügen eines Werts
    fn insert(&mut self, key: K, value: V) {
        self.store.insert(key, value);
    }
}
}

Wenn wir diesen Code kompilieren (z. B. mit cargo check), schlägt uns der Rust-Compiler diesen Code mit folgender Fehlermeldung um die Ohren:

error[E0599]: no function or associated item named `new` found for struct `HashMap<K, V>` in the current scope
 --> src/main.rs:9:29
  |
9 |             store: HashMap::new(),
  |                             ^^^ function or associated item not found in `HashMap<K, V>`
  |
  = note: the associated item was found, but its trait bounds were not satisfied
  = note: the following trait bounds were not satisfied:
          `K: Eq`
          `K: Hash`

Warum lehnt der Compiler das ab?

Die Fehlermeldung verrät uns das Problem: Eine HashMap berechnet den Speicherort ihrer Einträge mithilfe eines Hash-Algorithmus. Damit das funktioniert, müssen die Schlüssel (K) in der Lage sein, einen Hash-Wert zu generieren. Außerdem muss bei einer eventuellen Hash-Kollision (wenn zwei unterschiedliche Schlüssel denselben Hash-Wert liefern) geprüft werden können, ob zwei Schlüssel absolut identisch sind.

Der Compiler sagt uns: “Du hast mir nicht garantiert, dass der Typ K diese Eigenschaften besitzt! Was ist, wenn jemand versucht, einen Cache mit einem Typ für K zu erstellen, der nicht gehasht werden kann (wie z. B. eine andere HashMap oder ein komplexer mathematischer Vektor)?”

Rust geht hier auf Nummer sicher. Es erlaubt keinen Code, der potenziell zu Typfehlern führt. Wir müssen dem Compiler versprechen, dass K diese Eigenschaften besitzt.

Die Reparatur (Trait Bounds)

Wir fügen dem impl-Block eine Bedingung hinzu. In Rust nutzen wir dafür die where-Klausel, die den Code übersichtlicher macht als das direkte Schreiben in den spitzen Klammern.

#![allow(unused)]
fn main() {
use std::hash::Hash;

impl<K, V> Cache<K, V>
where
    K: Eq + Hash, // Trait Bound: K MUSS Eq und Hash implementieren!
{
    fn new() -> Self {
        Cache {
            store: HashMap::new(),
        }
    }

    fn insert(&mut self, key: K, value: V) {
        self.store.insert(key, value);
    }
}
}

Jetzt gibt sich der Compiler zufrieden. Wir haben das Versprechen eingelöst!

Aufgabe: Implementieren Sie die Methoden new und insert für Ihre Cache-Struktur. Nutzen Sie eine where-Klausel, um sicherzustellen, dass der Schlüsseltyp K die Traits Eq und Hash erfüllt.

3.3 Werte auslesen und Referenzen zurückgeben

Beim Auslesen eines Werts aus unserem Cache stehen wir vor einer wichtigen Entscheidung des Ownership-Modells: Sollen wir den Wert kopieren, klonen oder eine Referenz zurückgeben?

Da unser Cache die Daten besitzt, würde eine Rückgabe des Werts per Value (Besitzübergabe) bedeuten, dass wir den Wert aus dem Cache entfernen müssten. Das wollen wir nicht – der Cache soll die Daten behalten! Also müssen wir eine Referenz auf den Wert zurückgeben. Da der Wert eventuell gar nicht im Cache existiert, verpacken wir das Ergebnis in einer Option.

Beispiel:

#![allow(unused)]
fn main() {
impl<K, V> Cache<K, V>
where
    K: Eq + Hash,
{
    // Wir nehmen den Schlüssel als Referenz entgegen, um ihn nicht zu verbrauchen.
    // Wir geben eine Option zurück, die eine unveränderliche Referenz auf den Wert enthält.
    fn get(&self, key: &K) -> Option<&V> {
        self.store.get(key)
    }
}
}

Erklärung:

key: &K: Wir übergeben den Suchschlüssel als Referenz. Wenn der Schlüssel beispielsweise ein großer String ist, vermeiden wir so eine teure Kopie.
Option<&V>: Liefert entweder Some(&V) (eine Referenz auf den im Cache gespeicherten Wert) oder None (Wert nicht vorhanden).
Lifetimes (Lebensdauern): Hier greift das implizite Lifetime Elision von Rust. Der Compiler ergänzt im Hintergrund: fn get<'a>(&'a self, key: &K) -> Option<&'a V>. Das bedeutet: Die zurückgegebene Referenz auf den Wert darf nicht länger leben als der Cache selbst. Das verhindert “Dangling Pointer” (Zeiger ins Leere).

Aufgabe: Implementieren Sie die Methode get in Ihrer Struktur. Achten Sie auf die korrekte Verwendung von Referenzen.

3.4 Dynamische Berechnung: Closures in Generics integrieren

Ein fortgeschrittenes Feature eines guten Caches ist die Fähigkeit, Werte “On-Demand” (bei Bedarf) zu berechnen. Wenn ein Schlüssel nicht existiert, soll der Cache nicht einfach None zurückgeben, sondern eine vom Benutzer bereitgestellte Funktion aufrufen, die den Wert berechnet, diesen Wert im Cache abspeichert und eine Referenz darauf zurückgibt.

Hierfür benötigen wir ein weiteres generisches Konzept: Generische Closures (Funktionsobjekte).

Beispiel:

#![allow(unused)]
fn main() {
impl<K, V> Cache<K, V>
where
    K: Eq + Hash + Clone, // K muss Clone implementieren, da wir es für den Insert-Fall kopieren müssen
    V: Clone,             // V muss Clone implementieren, um den berechneten Wert zurückgeben zu können
{
    // F ist ein generischer Typ für eine Funktion/Closure.
    // FnOnce(&K) -> V bedeutet: Die Funktion wird einmal aufgerufen, nimmt &K und gibt V zurück.
    fn get_or_compute<F>(&mut self, key: K, generator: F) -> V
    where
        F: FnOnce(&K) -> V,
    {
        if let Some(value) = self.store.get(&key) {
            value.clone()
        } else {
            // Wenn der Wert fehlt, berechnen wir ihn
            let computed_value = generator(&key);
            // Wir müssen den Schlüssel klonen, da wir ihn in die Map einfügen
            self.store.insert(key.clone(), computed_value.clone());
            computed_value
        }
    }
}
}

Erklärung:

get_or_compute<F>: Die Methode selbst führt einen neuen Typparameter F ein.
F: FnOnce(&K) -> V: Dies schränkt F auf Closures ein, die eine Referenz auf den Schlüssel entgegennehmen und den Wert V erzeugen. FnOnce bedeutet, dass die Closure den Besitz ihrer Umgebung übernehmen und mindestens einmal aufgerufen werden kann.
Clone-Bedingungen: Da wir bei einem Cache-Miss den Schlüssel key in die Map einfügen (self.store.insert(key, ...)), müssen wir ihn klonen, falls wir ihn vorher für die Suche oder spätere Rückgaben benötigen. Deshalb verlangen wir zusätzlich K: Clone und V: Clone.

Aufgabe: Implementieren Sie die Methode get_or_compute in Ihrer Cache-Struktur. Stellen Sie sicher, dass alle notwendigen Trait Bounds deklariert sind.

4. Genaue Code-Erklärung der Musterlösung

Der vollständige und kompilierbare Code der Musterlösung befindet sich im Übungs-Workspace unter solutions/14_generics/src/main.rs.

1: // Musterlösung zu Übung 14: Generischer Datencache
2: // Zeigt den Einsatz von Generics, Trait Bounds und Closures.
3: 
4: use std::collections::HashMap;
5: use std::hash::Hash;
6: 
7: // Die generische Cache-Struktur
8: pub struct Cache<K, V> {
9:     store: HashMap<K, V>,
10: }
11: 
12: // Implementierung der grundlegenden Methoden
13: impl<K, V> Cache<K, V>
14: where
15:     K: Eq + Hash,
16: {
17:     // Konstruktor für einen leeren Cache
18:     pub fn new() -> Self {
19:         Cache {
20:             store: HashMap::new(),
21:         }
22:     }
23: 
24:     // Wert in den Cache einfügen
25:     pub fn insert(&mut self, key: K, value: V) {
26:         self.store.insert(key, value);
27:     }
28: 
29:     // Wert als Referenz auslesen
30:     pub fn get(&self, key: &K) -> Option<&V> {
31:         self.store.get(key)
32:     }
33: }
34: 
35: // Zusätzliche Implementierung für get_or_compute mit Klon-Unterstützung
36: impl<K, V> Cache<K, V>
37: where
38:     K: Eq + Hash + Clone,
39:     V: Clone,
40: {
41:     // Holt einen Wert oder berechnet ihn dynamisch über eine Closure
42:     pub fn get_or_compute<F>(&mut self, key: K, generator: F) -> V
43:     where
44:         F: FnOnce(&K) -> V,
45:     {
46:         if let Some(value) = self.store.get(&key) {
47:             value.clone()
48:         } else {
49:             let computed = generator(&key);
50:             self.store.insert(key.clone(), computed.clone());
51:             computed
52:         }
53:     }
54: }
55: 
56: fn main() {
57:     // 1. Instanziierung mit Schlüssel: String, Wert: i32
58:     let mut alter_cache = Cache::new();
59:     alter_cache.insert(String::from("Thorsten"), 35);
60:     alter_cache.insert(String::from("Max"), 28);
61: 
62:     if let Some(alter) = alter_cache.get(&String::from("Thorsten")) {
63:         println!("Thorsten ist {} Jahre alt.", alter);
64:     }
65: 
66:     // 2. Instanziierung mit Schlüssel: u32, Wert: String (andere Typen!)
67:     let mut user_cache = Cache::new();
68:     
69:     // get_or_compute verwenden
70:     let name = user_cache.get_or_compute(42, |id| {
71:         println!("Lade User mit ID {} aus der 'Datenbank'...", id);
72:         format!("User_{}", id)
73:     });
74:     println!("Erhalten: {}", name);
75: 
76:     // Zweiter Aufruf: Wert kommt nun direkt aus dem Cache (keine erneute Berechnung!)
77:     let name_cached = user_cache.get_or_compute(42, |_| {
78:         panic!("Dieser Code sollte nicht aufgerufen werden, da 42 gecached ist!");
79:     });
80:     println!("Erneut erhalten: {}", name_cached);
81: }

Zeilen-Analyse der Lösung:

Zeile 4-5: use std::collections::HashMap; und use std::hash::Hash; – Importiert die notwendigen Typen und Traits.
Zeile 8-10: pub struct Cache<K, V> { store: HashMap<K, V> } – Definiert unsere Struktur. Das Schlüsselwort pub macht die Struktur und ihr Verhalten für andere Module zugänglich, während das Feld store privat bleibt (Datenkapselung).
Zeile 13: impl<K, V> Cache<K, V> – Leitet den Implementierungsblock für die generischen Typen K und V ein. Beachten Sie, dass wir das <K, V> sowohl nach impl als auch nach Cache schreiben müssen. Das erste <K, V> deklariert die Typparameter für den Block, das zweite bindet sie an die Struktur.
Zeile 14-16: where K: Eq + Hash – Schränkt die Implementierung auf Typen ein, die für HashMaps geeignet sind. Dies sind die sogenannten Trait Bounds.
Zeile 18: pub fn new() -> Self – Der Konstruktor. Self (mit großem S) ist ein Typ-Alias für den aktuellen Typ inklusive seiner Parameter, also Cache<K, V>.
Zeile 20: store: HashMap::new() – Erstellt die leere HashMap. Da K und V durch die Trait Bounds eingeschränkt sind, weiß Rust hier, dass HashMap::new() gültig ist.
Zeile 25: pub fn insert(&mut self, key: K, value: V) – Methode zum Hinzufügen. Sie konsumiert key und value (Besitzübertragung).
Zeile 30: pub fn get(&self, key: &K) -> Option<&V> – Die Lesemethode. Sie nimmt eine Referenz auf den Schlüssel &K und liefert eine optionale Referenz auf den Wert Option<&V>.
Zeile 36-40: Ein zweiter impl-Block. Hier fordern wir zusätzlich K: Clone und V: Clone. Dies trennt sauber die Funktionalitäten: Ein einfacher Cache braucht kein Clone (erster Block), erst die Spezialmethode get_or_compute erfordert das Klonen (zweiter Block).
Zeile 42: pub fn get_or_compute<F>(&mut self, key: K, generator: F) -> V – Deklaration der Berechnungsmethode. Sie führt den generischen Typparameter F für die Closure ein.
Zeile 44: F: FnOnce(&K) -> V – Schränkt F ein. Die Closure erhält eine Referenz auf den Schlüssel und gibt einen neuen Wert vom Typ V zurück.
Zeile 46: if let Some(value) = self.store.get(&key) – Prüft, ob der Schlüssel bereits in der HashMap liegt.
Zeile 47: value.clone() – Gefunden! Wir klonen den Wert und geben ihn zurück.
Zeile 49: let computed = generator(&key); – Nicht gefunden! Wir rufen die Closure generator auf und übergeben ihr die Referenz auf den Schlüssel. Das Ergebnis speichern wir in computed.
Zeile 50: self.store.insert(key.clone(), computed.clone()); – Wir speichern das berechnete Ergebnis im Cache ab. Da wir den Schlüssel key und den berechneten Wert computed auch gleich als Rückgabewert verwenden, müssen wir sie an dieser Stelle klonen, um die Ownership-Regeln einzuhalten.
Zeile 51: computed – Rückgabe des berechneten Werts.
Zeile 58: let mut alter_cache = Cache::new(); – Rust nutzt hier Typinferenz. Beim Aufruf von new() weiß Rust noch nicht, welche Typen genutzt werden. Erst in Zeile 59 und 60 sieht der Compiler, dass wir String und i32 hineinstecken. Er legt den Typ von alter_cache somit fest auf Cache<String, i32>.
Zeile 70: user_cache.get_or_compute(42, |id| { ... }) – Hier rufen wir get_or_compute auf. Wir übergeben die ID 42 und eine Closure. Da 42 noch nicht im Cache existiert, wird die Closure ausgeführt und "User_42" berechnet.
Zeile 77: Beim zweiten Aufruf mit 42 ist der Wert bereits im Cache vorhanden. Die Closure, die ein panic! auslösen würde, wird gar nicht erst ausgeführt. Der Cache liefert direkt den gespeicherten Wert.

5. Tiefere Einblicke: Was ist Monomorphisierung?

Sie fragen sich vielleicht: Kostet uns diese Flexibilität Leistung zur Laufzeit? In vielen anderen Sprachen wie Java oder C# ist das der Fall (z. B. durch Boxing/Unboxing oder Virtual Method Tables zur Laufzeit).

Rust geht einen anderen Weg: Die Monomorphisierung.

Das Wort stammt aus dem Griechischen (mono = einteilig/einzig; morphe = Gestalt/Form) und bedeutet: “In eine einzige Gestalt bringen”.

Wenn der Rust-Compiler Ihr Programm übersetzt, sucht er nach allen konkreten Typ-Kombinationen, mit denen Sie Cache<K, V> aufgerufen haben. In unserem main-Programm sieht er zwei Verwendungen:

Cache<String, i32>
Cache<u32, String>

Der Compiler dupliziert nun im Hintergrund den Code des Caches und erstellt zwei vollkommen eigenständige, konkrete Maschinencode-Strukturen:

Eine Struktur, die exakt auf String und i32 optimiert ist.
Eine Struktur, die exakt auf u32 und String optimiert ist.

Das bedeutet für Sie: Null Laufzeitkosten (Zero-Cost Abstractions). Der generierte Maschinencode ist exakt so schnell und kompakt, als hätten Sie von Anfang an zwei separate Klassen (StringI32Cache und U32StringCache) von Hand geschrieben. Der einzige “Nachteil” ist eine minimal längere Kompilierzeit und eine geringfügig größere ausführbare Binärdatei – ein absolut lohnenswerter Tausch für Typsicherheit und Performance!

Keyboard shortcuts

Rust-Lernpfad & Lehrbuch