Collections

Die Stdlib-Sammlung im Überblick

Bevor wir in die Detail-Artikel einsteigen, lohnt ein Blick auf die gesamte Sammlung. Die Auswahl der Stdlib-Container folgt einer klaren Logik: für jede wichtige Zugriffs-Charakteristik gibt es einen Standard-Container, nicht mehrere überlappende. Brauchst du einen sequenziellen Zugriff mit Index, ist es Vec. Brauchst du Key-Lookup, hast du die Wahl zwischen HashMap (schneller, ungeordnet) und BTreeMap (langsamer, sortiert). Brauchst du Doppel-End-Push/Pop, ist es VecDeque. Die Tabelle unten gibt einen schnellen Überblick — die Spalte „Lookup-Performance" beschreibt das, was du beim häufigsten Zugriffsmuster erwarten kannst.

Faustregel: Vec und HashMap decken 90 % aller Anwendungen ab. Die anderen Container kommen erst dann ins Spiel, wenn du eine ganz spezifische Anforderung hast, die Vec oder HashMap nicht erfüllen können: deterministische Reihenfolge der Iteration (dann BTreeMap), häufige Push/Pop am Anfang (dann VecDeque), das stets-kleinste-Element-Pattern (dann BinaryHeap). Wer mit dieser klaren Hierarchie ans Design geht, spart sich viel Diskussion über Container-Wahl.

Gemeinsame Patterns

Bevor wir die einzelnen Container im Detail anschauen, lohnt es sich, die gemeinsame Mechanik zu kennen. Die Rust-Stdlib hat ihre Container so entworfen, dass sie sich nach denselben Regeln verhalten — wenn du Vec verstanden hast, wirst du dich bei HashMap und BTreeMap schnell zurechtfinden, weil die API-Konzepte sich wiederholen.

Ownership der Elemente. Wenn du einen Wert in einen Container einfügst (Vec::push(item), HashMap::insert(k, v)), wird er in den Container gemoved — der Container ist von da an der Eigentümer. Beim drop des Containers wird drop für jedes Element automatisch aufgerufen. Das gilt rekursiv: eine HashMap<String, Vec<u8>>, die fällt, droppt erst alle Vecs, jeder Vec dann alle seine Bytes (was bei u8 nichts macht, aber bei verschachtelten Strukturen genau die Kette ist, die du brauchst).

Generizität. Alle Container sind über den Element-Typ generisch. Vec<T> akzeptiert jedes T — primitive Typen genauso wie eigene Structs. Hash-basierte Container (HashMap, HashSet) brauchen zusätzlich T: Hash + Eq, weil sie aus Werten Hashes berechnen und auf Gleichheit prüfen müssen. Geordnete Container (BTreeMap, BTreeSet) brauchen T: Ord. Diese Trait-Anforderungen tauchen in den Compiler-Meldungen auf, wenn du einen eigenen Typ einsetzt und vergisst, das passende derive zu setzen.

Kapazitäts-Modell. Container, die ihre Daten in einem zusammenhängenden Heap-Block halten (Vec, String, VecDeque, HashMap, HashSet), kennen das Konzept der Kapazität: das ist der reservierte Platz, der größer sein kann als die aktuelle Befüllung. Bei Überschreiten wird der Block verdoppelt, was Reallocations auslöst. Mit with_capacity(n) reservierst du vorab und sparst diese Wachstumsschritte. BTreeMap und BTreeSet haben dagegen keine Kapazität, weil sie als Bäume realisiert sind — jeder Knoten ist eine eigene kleine Allokation.

IntoIterator und FromIterator. Beide Traits machen Container zu vollwertigen Iteration-Quellen und -Zielen. for x in container ruft into_iter() auf und konsumiert; for x in &container ruft iter() und liefert Referenzen. Umgekehrt erlaubt iter.collect::<Vec<_>>() (oder jeder andere Container-Typ als Ziel), aus einem Iterator einen neuen Container zu bauen. Diese Symmetrie ist die Grundlage des funktional anmutenden Rust-Stils — ohne sie wäre .iter().filter(...).collect() nicht möglich.

Was dich erwartet

• Vec — der wichtigste Container. Wachsende Sequenz, schneller Index-Zugriff, das Arbeitstier für jede Liste.
• String als Collection — String aus Container-Sicht. Methoden wie push, insert, truncate, clear und die Gemeinsamkeiten mit Vec<u8>.
• HashMap — Key-Value-Lookup mit O(1)-Performance. Entry-API, Default-Hasher, Custom-Hasher.
• HashSet — Unique-Werte-Sammlung. Set-Operationen (union, intersection, difference) und Membership-Tests.
• BTreeMap und BTreeSet — sortierte Alternativen mit O(log n)-Performance. Range-Queries und sortierte Iteration.
• VecDeque und LinkedList — VecDeque als Ring-Buffer für Queue/Deque, LinkedList als Spezialfall.
• Kapazität und Reallocation — wie Container wachsen, with_capacity als Performance-Hebel, shrink_to_fit für Memory.

Was du nach diesem Kapitel kannst

• Den richtigen Container für jede Aufgabe wählen — Vec für Sequenzen, HashMap für Key-Value, BTreeMap für sortierte Daten, VecDeque für Queues.
• Die wichtigsten Methoden jedes Containers nutzen (push/pop, get/insert, iter, filter, collect).
• Kapazitäts-Management beherrschen — vorab with_capacity für Performance, shrink_to_fit für Memory.
• Die Entry-API von HashMap nutzen für „insert-if-missing"-Patterns.
• Set-Operationen für Mengen-Logik einsetzen.
• Eigene Datenstrukturen mit Container-internen Methoden konstruieren.

Im nächsten Kapitel geht's zu Error-Handling im Detail — eigene Error-Typen, thiserror, anyhow, Strategien für Library vs. Application.

Weiterführende Ressourcen

Externe Quellen

• The Rust Book – Common Collections
• std::collections
• Rust API Guidelines – Collections

Verwandte Artikel

• Vec
• String als Collection
• HashMap
• HashSet
• BTreeMap und BTreeSet
• VecDeque und LinkedList
• Kapazität und Reallocation