BTreeMap und BTreeSet

BTreeMap — sortierte Key-Value-Sammlung

BTreeMap unterscheidet sich von HashMap in einem zentralen Punkt: alle Operationen pflegen die sortierte Anordnung der Keys. Das hat einen Preis (Lookups sind O(log n) statt O(1)), aber dafür ergeben sich Möglichkeiten, die HashMap überhaupt nicht hat — sortierte Iteration, Range-Queries, schneller Zugriff auf Min/Max. Wenn du eine dieser Eigenschaften brauchst, ist BTreeMap die richtige Wahl, auch wenn der Lookup einen Logarithmus langsamer ist.

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<i32, String> = BTreeMap::new();
    m.insert(3, "drei".into());
    m.insert(1, "eins".into());
    m.insert(2, "zwei".into());

    // Iteration in Key-Reihenfolge!
    for (k, v) in &m {
        println!("{k} → {v}");
    }
    // 1 → eins
    // 2 → zwei
    // 3 → drei
}

Die API ist mit Absicht fast identisch zu HashMap — insert, get, remove, contains_key, entry funktionieren exakt gleich. Wer von HashMap auf BTreeMap umsteigt, muss kaum Code anpassen; oft reicht ein Tausch des Typs in einer einzigen Zeile. Der sichtbare Unterschied liegt in der Iteration: während HashMap die Einträge in unbestimmter Reihenfolge liefert, läuft BTreeMap immer in aufsteigender Key-Reihenfolge. Das ist nicht nur eine Konvention — die Reihenfolge ist garantiert und reproduzierbar, was BTreeMap zur richtigen Wahl macht, wenn deine Anwendung deterministische Ausgaben verlangt (Tests, Snapshots, Hash-Berechnungen über Map-Inhalte).

Intern ist BTreeMap als B-Baum implementiert — ein balancierter Baum, dessen Knoten mehrere Keys halten (typisch 5-11). Diese Knotenstruktur ist anders als ein klassischer binärer Suchbaum: der B-Baum ist gezielt cache-freundlich entworfen, weil mehrere Keys in einem einzigen Knoten zusammen im Speicher liegen und so ein Cache-Line-Lookup viele Vergleiche auf einmal erlaubt. In der Praxis ist BTreeMap deshalb deutlich schneller als ein naiv implementierter binärer Suchbaum, auch wenn beide formal O(log n) sind.

Voraussetzung: K muss Ord sein

Wo HashMap einen Hash + Eq-Key braucht, verlangt BTreeMap stattdessen Ord. Das ist eine stärkere Anforderung — Ord ist ein Total-Ordering, das verlangt, dass für je zwei Werte eindeutig festgestellt werden kann, welcher kleiner ist (oder ob sie gleich sind). Reflexivität, Antisymmetrie, Transitivität müssen erfüllt sein. Diese mathematischen Eigenschaften sind die Grundlage dafür, dass der Baum sortiert bleiben kann.

// OK:
// let m1: BTreeMap<i32, V> = BTreeMap::new();
// let m2: BTreeMap<String, V> = BTreeMap::new();

// Fehler — f64 ist nicht Ord (wegen NaN):
// let m3: BTreeMap<f64, V> = BTreeMap::new();

// Eigene Typen brauchen #[derive(Ord, PartialOrd, Eq, PartialEq)]:
#[derive(PartialEq, Eq, PartialOrd, Ord)]
struct Version { major: u32, minor: u32 }

Alle Standard-Integer-Typen, String, &str, Tuples aus Ord-Typen und die meisten Stdlib-Typen erfüllen Ord direkt. Floats (f32, f64) sind das große Gegenbeispiel: weil NaN mit nichts vergleichbar ist (auch nicht mit sich selbst), erfüllen Floats nur PartialOrd, nicht Ord. Wer dennoch Floats als BTreeMap-Key braucht, benutzt einen Wrapper wie OrderedFloat<f64> aus dem ordered_float-Crate, der NaN verbietet und damit Ord erfüllen kann.

Eigene Typen brauchen das #[derive(...)]-Set mit allen vier Traits — PartialEq, Eq, PartialOrd, Ord. Die abgeleitete Implementation vergleicht die Felder in deklarierter Reihenfolge: erst das erste Feld, bei Gleichheit das zweite, und so weiter. Das ist die lexikographische Ordnung und meist genau das, was man will. Für eigene Vergleichs-Logik kannst du Ord und PartialOrd von Hand implementieren.

Range-Queries

Range-Queries sind die Killer-Feature von BTreeMap — die Eigenschaft, die fast immer den Ausschlag gibt, BTreeMap statt HashMap zu wählen. Die Idee: statt eines einzelnen Keys gibst du einen Bereich an, und bekommst alle Einträge zurück, deren Keys in diesem Bereich liegen. Sortiert, in der Reihenfolge, in der der Baum sie hält. Bei HashMap ist das schlicht nicht möglich — die undefinierte Reihenfolge erlaubt keinen sinnvollen Bereich.

Die Implementation ist effizient: zum Start des Bereichs wird einmalig O(log n) für den Einstieg gerechnet, danach läuft die Iteration durch die Baumknoten in O(1) pro Element. Gesamt O(log n + k), wobei k die Anzahl der Treffer ist. Selbst bei Millionen-Einträge-Maps bleibt das schnell.

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<i32, &str> = BTreeMap::new();
    for i in 0..20 {
        m.insert(i, "x");
    }

    // Alle Keys zwischen 5 und 15 (inklusiv)
    for (k, _) in m.range(5..=15) {
        print!("{k} ");
    }
    // 5 6 7 8 9 10 11 12 13 14 15

    // Alle ab Key 10
    for (k, _) in m.range(10..) {
        print!("{k} ");
    }
    // 10 11 12 13 14 15 16 17 18 19
}

range akzeptiert alle Range-Syntax-Varianten, die Rust kennt: a..b für halboffenes Intervall (inklusive a, exklusive b), a..=b für geschlossenes Intervall (beide inklusive), a.. für „ab a bis Ende", ..b für „vom Anfang bis vor b", und .. für alle Einträge. Diese Konsistenz mit der normalen Slice-Notation macht den Umgang intuitiv.

Diese Operation ist mit HashMap unmöglich — eine HashMap hat keine Reihenfolge, also auch keinen sinnvollen „Bereich". Wenn du in einer HashMap alle Keys zwischen 5 und 15 finden willst, musst du alle Einträge durchgehen und einzeln prüfen — O(n). Mit BTreeMap ist es O(log n + k).

Range mit Mutation

use std::collections::BTreeMap;

fn main() {
    let mut m: BTreeMap<i32, i32> = (1..=10).map(|i| (i, i * 10)).collect();

    // Alle Values im Range 4..=7 verdoppeln
    for (_, v) in m.range_mut(4..=7) {
        *v *= 2;
    }
}

range_mut ist die mutable Variante: sie gibt einen Iterator über (&K, &mut V) zurück. Du kannst die Werte innerhalb eines Schlüssel-Bereichs in-place verändern, ohne den Baum als Ganzes anzufassen. Die Keys bleiben dabei unverändert — das ist auch zwingend, weil das Verändern eines Keys den sortierten Baum invalidieren würde. Anwendungsfälle gibt es genug: alle Records in einem Zeitfenster als „archived" markieren, alle Histogramm-Buckets in einem Range zurücksetzen, alle Cache-Einträge mit Keys in einem Block ablaufen lassen.

First, Last — sortierte Endpoints

Weil BTreeMap intern den kleinsten und größten Key in seinen Endknoten parat hat, sind Zugriffe auf die Extremwerte effizient. Diese vier Methoden — first_key_value, last_key_value, pop_first, pop_last — geben dir den Min- oder Max-Eintrag, optional mit Entfernung. Sie sind alle O(log n), aber in der Praxis sehr schnell, weil sie nur einen geraden Pfad durch den Baum laufen.

use std::collections::BTreeMap;

fn main() {
    let m: BTreeMap<i32, &str> = [(3, "c"), (1, "a"), (2, "b")]
        .into_iter().collect();

    let kleinster = m.first_key_value();        // Some((&1, &"a"))
    let groesster = m.last_key_value();          // Some((&3, &"c"))

    // Mit Mutation
    let mut m2 = m.clone();
    m2.pop_first();      // entfernt (1, "a")
    m2.pop_last();        // entfernt (3, "c")

    assert_eq!(kleinster, Some((&1, &"a")));
}

Bei HashMap wäre dieselbe Operation O(n), weil du den gesamten Map-Inhalt iterieren müsstest, um den Minimum-Key zu finden. Diese vier Methoden machen BTreeMap zur natürlichen Wahl für Algorithmen, die ständig den kleinsten oder größten Wert brauchen — Priority-Queues, Scheduler, expiry-Caches.

pop_first und pop_last sind besonders praktisch: sie geben den entfernten Eintrag zurück und reduzieren die Map gleichzeitig. Damit kannst du BTreeMap als priorisierte Queue verwenden, indem du das kleinste Element herauspoppst und dann verarbeitest.

BTreeSet

Genau wie HashSet zu HashMap verhält sich BTreeSet zu BTreeMap: intern eine BTreeMap<T, ()> mit Wegoptimierung des Unit-Wertes. Alle Eigenschaften der BTreeMap übertragen sich — sortierte Iteration, Range-Queries, schneller Zugriff auf erste/letzte Werte. Was bei HashSet die vier Set-Operationen waren, gilt hier ebenfalls, nur dass die Ergebnisse zusätzlich sortiert sind.

use std::collections::BTreeSet;

fn main() {
    let mut s: BTreeSet<i32> = [3, 1, 4, 1, 5, 9, 2, 6].into_iter().collect();
    // Duplikate weg, sortiert

    for x in &s {
        print!("{x} ");
    }
    // 1 2 3 4 5 6 9

    // Range
    let zwischen: Vec<i32> = s.range(2..6).copied().collect();
    assert_eq!(zwischen, vec![2, 3, 4, 5]);

    // Set-Operations wie bei HashSet:
    let a: BTreeSet<i32> = [1, 2, 3].into_iter().collect();
    let b: BTreeSet<i32> = [2, 3, 4].into_iter().collect();
    let inter: BTreeSet<i32> = a.intersection(&b).copied().collect();
    // {2, 3}
}

Im Beispiel siehst du beides: erstens, dass aus einer Eingabe-Liste mit Duplikaten und unsortierter Reihenfolge automatisch ein sortiertes, dedupliziertes Set wird. Zweitens, dass Range-Queries und Set-Operationen kombiniert werden können — die range(2..6)-Operation läuft direkt auf dem sortierten Set ohne Zusatzkosten.

Praktisch bedeutet das: BTreeSet eignet sich nicht nur für Mengen-Logik, sondern auch als sortierter Index. Wenn du z. B. eine sortierte Liste von Zeitstempeln willst, in der du sowohl ein neues Element einfügen als auch nach einem Range filtern willst, ist BTreeSet besser als ein Vec mit nachträglicher Sortierung.

HashMap vs. BTreeMap — Entscheidungs-Matrix

Die Wahl zwischen HashMap und BTreeMap ist eine der häufigsten Design-Entscheidungen bei Rust-Code, der mit Lookups arbeitet. Die nachfolgende Matrix bündelt die Kriterien, die in der Praxis den Ausschlag geben. Bei den meisten Anwendungen ist die Antwort schnell klar; nur in Grenzfällen lohnt sich Profiling.

Faustregel: Wenn du eine der BTreeMap-spezifischen Eigenschaften brauchst — sortierte Iteration, Range-Queries, schneller First/Last-Zugriff —, ist BTreeMap die richtige Wahl, auch wenn die Lookups dadurch geringfügig langsamer werden. Wenn du keine davon brauchst, ist HashMap die bessere Wahl, weil sie im Average-Case schneller lookups macht und weniger Allokations-Overhead pro Eintrag hat.

In Performance-Tests zeigt sich übrigens, dass die O(log n) bei BTreeMap in der Praxis nicht so dramatisch teuer ist, wie die Theorie suggeriert — der B-Baum ist sehr cache-freundlich, und ein Lookup über zwei oder drei Knoten-Vergleiche kann sogar schneller sein als ein HashMap-Lookup mit Hash-Berechnung und Cache-Miss. Bei kleinen Maps (etwa unter 30 Einträgen) sind beide vergleichbar; bei großen schlägt HashMap im reinen Lookup, aber selten so dramatisch, wie man denken würde.

Praxis: BTreeMap im echten Code

Die Anwendungen von BTreeMap konzentrieren sich auf Szenarien, in denen die Ordnung der Keys eine inhaltliche Rolle spielt. Time-Series-Daten, sortierte Ausgaben, Range-Filter, Top-N-Listen, Prefix-Suchen — überall dort, wo ein Bereich oder eine Reihenfolge die Anfrage definiert, ist BTreeMap meist die elegantere Wahl als HashMap mit nachträglicher Sortierung.

Time-Series-Index

use std::collections::BTreeMap;

pub struct TimeSeries {
    werte: BTreeMap<u64, f64>,
}

impl TimeSeries {
    pub fn neu() -> Self {
        TimeSeries { werte: BTreeMap::new() }
    }

    pub fn record(&mut self, ts: u64, wert: f64) {
        self.werte.insert(ts, wert);
    }

    pub fn range(&self, von: u64, bis: u64) -> Vec<(u64, f64)> {
        self.werte.range(von..=bis)
            .map(|(k, v)| (*k, *v))
            .collect()
    }

    pub fn neueste(&self) -> Option<(u64, f64)> {
        self.werte.last_key_value().map(|(k, v)| (*k, *v))
    }
}

Time-Series-Daten sind der Lehrbuch-Anwendungsfall für BTreeMap. Der Zeitstempel (typisch ein Unix-Timestamp in Sekunden oder Millisekunden) ist die natürliche Ordnungsachse — wenn neue Messwerte ankommen, sind sie typischerweise größer als alle bisherigen, aber gelegentlich kommen auch verspätete Werte aus der Vergangenheit. BTreeMap sortiert sie automatisch ein, ohne dass du selbst eingreifen musst.

Die drei gezeigten Operationen decken die typischen Abfragen ab. record fügt einen Messwert ein. range(von..=bis) holt alle Werte in einem Zeit-Fenster — etwa für eine Chart-Darstellung der letzten Stunde. neueste() greift mit last_key_value auf den aktuellsten Eintrag zu, was bei HashMap eine vollständige Iteration bedeuten würde.

Bei sehr großen Time-Series (Millionen Datenpunkte) gibt es spezialisierte Crates wie timely oder dedicated Time-Series-Datenbanken — aber für mittelgroße Anwendungen und Caches ist BTreeMap eine sehr gute, in der Stdlib vorhandene Lösung.

Sortierte Statistik-Ausgabe

use std::collections::BTreeMap;

pub fn ausgabe_pro_kategorie(daten: &[(String, i64)]) {
    let mut summen: BTreeMap<&str, i64> = BTreeMap::new();
    for (kat, wert) in daten {
        *summen.entry(kat).or_insert(0) += wert;
    }
    // Ausgabe automatisch sortiert nach Kategorie
    for (kat, summe) in &summen {
        println!("{kat}: {summe}");
    }
}

Sobald deine Ausgabe sortiert sein muss — z. B. für reproduzierbare Snapshot-Tests, für ein CLI-Tool mit alphabetischer Reportausgabe, für hash-konsistente Serialisierung —, ist BTreeMap die direkte Wahl. Ohne sie müsstest du die Daten erst in einer HashMap sammeln, dann in einen Vec materialisieren, dann sortieren, dann iterieren. BTreeMap macht das alles in einer Zeile, und das Sortieren passiert kostenlos beim Einfügen.

Bei wenigen Hundert Einträgen ist der Performance-Unterschied zur HashMap-mit-Sortierung-Variante unspürbar. Bei vielen Tausend wird BTreeMap durch ihr inkrementelles Sortieren sogar wettbewerbsfähiger, weil sie keine separate Sortier-Phase braucht.

Latency-Histogramm mit Buckets

use std::collections::BTreeMap;

pub struct LatencyHistogram {
    buckets: BTreeMap<u64, u32>,        // Bucket-Schwelle in ms -> Count
}

impl LatencyHistogram {
    pub fn neu() -> Self {
        let mut buckets = BTreeMap::new();
        for &ms in &[1, 5, 10, 50, 100, 500, 1000, 5000] {
            buckets.insert(ms, 0);
        }
        LatencyHistogram { buckets }
    }

    pub fn record(&mut self, latency_ms: u64) {
        if let Some((_, count)) = self.buckets.range_mut(latency_ms..).next() {
            *count += 1;
        }
    }

    pub fn perzentil(&self, p: f64) -> Option<u64> {
        let gesamt: u32 = self.buckets.values().sum();
        let ziel = (gesamt as f64 * p) as u32;
        let mut sum = 0;
        for (&schwelle, &count) in &self.buckets {
            sum += count;
            if sum >= ziel { return Some(schwelle); }
        }
        None
    }
}

Ein Latency-Histogramm zeigt die Verteilung von Antwortzeiten über vordefinierte Buckets. Klassisch wird ein gemessener Wert in das nächst-größere Bucket einsortiert: 7 ms → Bucket 10, 35 ms → Bucket 50, 250 ms → Bucket 500. Die range_mut(latency_ms..).next()-Operation ist die elegante Form dieser Logik: starte beim ersten Bucket ab oder über dem Messwert, nimm das erste Ergebnis. Bei einem Messwert von 7 mit Buckets [1, 5, 10, 50, ...] ist das erste Bucket im Range 7.. der Wert 10 — und genau dort wird der Counter erhöht.

Die perzentil-Berechnung nutzt die sortierte Iteration. Du läufst von kleinen zu großen Buckets, summierst die Counts auf, und gibst die Bucket-Schwelle zurück, sobald die Summe das Perzentil-Ziel erreicht. Bei einer HashMap müsstest du erst alle Buckets sammeln und sortieren — bei BTreeMap geht das direkt.

Sorted Set für Leaderboard

use std::collections::BTreeMap;

pub struct Leaderboard {
    // Score absteigend als Key — höchste zuerst
    eintraege: BTreeMap<std::cmp::Reverse<u32>, String>,
}

impl Leaderboard {
    pub fn neu() -> Self {
        Leaderboard { eintraege: BTreeMap::new() }
    }

    pub fn add(&mut self, score: u32, name: String) {
        self.eintraege.insert(std::cmp::Reverse(score), name);
    }

    pub fn top_n(&self, n: usize) -> Vec<(u32, &str)> {
        self.eintraege.iter()
            .take(n)
            .map(|(r, name)| (r.0, name.as_str()))
            .collect()
    }
}

Leaderboards brauchen die umgekehrte Sortierung: höchste Scores zuerst. Da BTreeMap aufsteigend sortiert, gibt es zwei Wege: entweder einen negativen Wert als Key benutzen (-score), oder den std::cmp::Reverse-Wrapper. Letzterer ist die saubere Lösung — er ist ein neutraler Newtype, der die Ord-Implementation invertiert. Aus Sicht der BTreeMap ist Reverse(100) „kleiner" als Reverse(50), also kommt der höhere Score zuerst.

Die top_n-Methode nutzt die natürliche Iterations-Reihenfolge: die n ersten Einträge sind automatisch die mit den höchsten Scores. Das r.0 greift in den Reverse-Wrapper hinein und liefert den ursprünglichen Score zurück, damit der Caller den unverpackten Wert bekommt.

Eine kleine Falle: bei gleichen Scores werden Einträge mit den Reverse-Keys überschrieben — wenn zwei Spieler beide 100 Punkte haben und beide eingefügt werden, gewinnt der zweite. In der Praxis löst man das, indem man ein Composite-Key benutzt — etwa (Reverse(score), Spieler-ID), sodass auch bei gleichem Score jeder Eintrag eindeutig bleibt.

Range-Index für Auto-Vervollständigung

use std::collections::BTreeSet;

pub struct WortIndex {
    woerter: BTreeSet<String>,
}

impl WortIndex {
    pub fn aus(woerter: Vec<String>) -> Self {
        WortIndex { woerter: woerter.into_iter().collect() }
    }

    pub fn praefix(&self, p: &str) -> Vec<&str> {
        self.woerter.range(p.to_string()..)
            .take_while(|w| w.starts_with(p))
            .map(|s| s.as_str())
            .collect()
    }
}

fn main() {
    let idx = WortIndex::aus(vec![
        "apple".into(), "application".into(), "apply".into(),
        "banana".into(), "berry".into(),
    ]);
    let app: Vec<&str> = idx.praefix("app");
    assert_eq!(app, vec!["apple", "application", "apply"]);
}

Prefix-Suche auf einem sortierten Set ist eine schöne Anwendung der Range-Query: alle Wörter, die mit einem bestimmten String beginnen, liegen in einem zusammenhängenden Bereich des Sets. Die Implementierung nutzt das aus: range(p.to_string()..) startet beim ersten Wort, das alphabetisch gleich oder größer als das Präfix ist. Danach läuft take_while weiter, solange die Wörter mit dem Präfix beginnen — sobald das nicht mehr der Fall ist, wird abgebrochen.

Die Gesamtkomplexität ist O(log n + k), wobei k die Anzahl der Treffer ist. Bei einem Wörterbuch mit Millionen Wörtern und einer Prefix-Suche, die zehn Treffer liefert, sind das nur etwa zwanzig Schritte. Eine Autocomplete-Funktion in einem CLI oder Editor lässt sich damit ohne externe Trie-Datenstruktur sehr effizient bauen.

Schedule-Manager

use std::collections::BTreeMap;

pub struct Schedule {
    termine: BTreeMap<u64, String>,        // ts -> Beschreibung
}

impl Schedule {
    pub fn naechster(&self, ab: u64) -> Option<(u64, &str)> {
        self.termine.range(ab..).next()
            .map(|(ts, beschr)| (*ts, beschr.as_str()))
    }

    pub fn vergangene_in_letzten(&self, jetzt: u64, sekunden: u64) -> Vec<(u64, &str)> {
        let von = jetzt.saturating_sub(sekunden);
        self.termine.range(von..jetzt)
            .map(|(ts, b)| (*ts, b.as_str()))
            .collect()
    }
}

Ein Scheduler ist eine Standard-Anwendung für sortierte Maps. naechster(ab) fragt: „Gib mir den ersten Termin ab Zeitpunkt X" — das ist range(ab..).next(), also O(log n) für den Range-Einstieg, dann eine einzige Iter-Step für das erste Ergebnis. Bei einem Scheduler mit Millionen geplanten Terminen ist diese Operation immer noch im Mikrosekunden-Bereich.

vergangene_in_letzten zeigt eine subtile, aber wichtige Praxis-Technik: saturating_sub, um Underflow zu vermeiden. Wenn jetzt kleiner als sekunden ist, würde eine normale Subtraktion bei u64 panicken (Debug-Mode) oder wraparound (Release-Mode). saturating_sub gibt stattdessen 0 zurück, was hier die richtige Semantik ist: „beginne beim Zeitnullpunkt".

Sortiertes Logging

use std::collections::BTreeMap;

pub struct OrderedLog {
    eintraege: BTreeMap<u64, String>,       // sequence_id -> message
}

impl OrderedLog {
    pub fn neu() -> Self {
        OrderedLog { eintraege: BTreeMap::new() }
    }

    pub fn add(&mut self, seq: u64, msg: String) {
        self.eintraege.insert(seq, msg);
    }

    pub fn print_alle(&self) {
        for (seq, msg) in &self.eintraege {
            println!("[{seq}] {msg}");
        }
    }
}

In verteilten Systemen kommen Events oft nicht in der Reihenfolge an, in der sie entstanden sind — Netzwerk-Latenzen, Worker-Verzögerungen, Retry-Logik führen dazu, dass Event mit ID 7 vor Event mit ID 5 ankommen kann. Eine BTreeMap mit der Sequence-ID als Key sortiert sie automatisch. Bei der Ausgabe siehst du sie in korrekter Reihenfolge, egal wann sie eingetroffen sind.

Dieser Pattern ist häufig in Audit-Logs, Replay-Mechanismen, Event-Sourcing-Systemen. Die Speicher-Effizienz ist gut genug für Millionen Events; sobald du wirklich große Datenmengen hast, würde man auf eine echte Datenbank wechseln, aber für Caches und Memory-only-Strukturen ist BTreeMap eine sehr gute Wahl.

Set-Difference auf sortierten Mengen

use std::collections::BTreeSet;

pub fn neue_ids(alt: &BTreeSet<u64>, neu: &BTreeSet<u64>) -> Vec<u64> {
    neu.difference(alt).copied().collect()
}

fn main() {
    let alt: BTreeSet<u64> = [1, 2, 3, 5, 8].into_iter().collect();
    let neu: BTreeSet<u64> = [1, 2, 4, 5, 9].into_iter().collect();
    assert_eq!(neue_ids(&alt, &neu), vec![4, 9]);     // sortiert!
}

Set-Operationen auf BTreeSet haben einen schönen Nebeneffekt: das Ergebnis ist automatisch sortiert. Während ein HashSet-Diff dir die fehlenden Elemente in unbestimmter Reihenfolge liefert, kommen sie aus dem BTreeSet sortiert raus. Bei einer „Liste neu hinzugekommener IDs" für ein Logging oder UI ist das oft genau das, was du brauchst — ohne separate Sortier-Phase.

Die algorithmische Komplexität ist gleich gut wie bei HashSet (O(n + m) für die Differenz), aber durch den Cache-Friendliness des B-Baums in der Praxis oft sehr ähnlich schnell.

Weiterführende Ressourcen

Externe Quellen

• std::collections::BTreeMap
• std::collections::BTreeSet
• Performance Comparison

Verwandte Artikel

• HashMap
• HashSet
• Collections – Übersicht