VecDeque und LinkedList

VecDeque — die idiomatische Queue

VecDeque hat ihren Namen von „Double-ended Queue" — einer Datenstruktur, bei der du an beiden Enden gleichermaßen schnell einfügen und entfernen kannst. Bei Vec ist das Anhängen am Ende billig (O(1)), aber alles, was vorne passiert, ist teuer (O(n) wegen Verschiebungen). VecDeque löst dieses Problem mit einer kleinen, aber wirkungsvollen Designentscheidung: statt einem geraden Heap-Block mit einem Anfang ist die Speicherung als Ring-Buffer organisiert, der gedanklich „rundum" läuft. Damit sind beide Enden symmetrisch billig.

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::new();

    // Push an beiden Enden
    q.push_back(1);
    q.push_back(2);
    q.push_back(3);
    q.push_front(0);
    // q: [0, 1, 2, 3]

    // Pop an beiden Enden
    let v = q.pop_front();      // Some(0)
    let l = q.pop_back();       // Some(3)
    assert_eq!(v, Some(0));
    assert_eq!(l, Some(3));
    // q: [1, 2]
}

Im Beispiel siehst du den symmetrischen Charakter der API. push_back(x) und push_front(x) fügen am jeweiligen Ende ein, pop_back() und pop_front() entfernen am jeweiligen Ende — beide letzteren geben einen Option<T> zurück (None bei leerer Queue). Alle vier Operationen sind O(1) amortisiert: in den meisten Fällen kostet jede Operation nur einen Schreibvorgang, und nur gelegentlich (beim Wachstum des Buffers) wird umkopiert.

Der Unterschied zu Vec ist genau bei den Front-Operationen entscheidend. Vec::insert(0, x) muss alle bestehenden Elemente um einen Slot nach hinten kopieren — bei einer 10 000-Elemente-Liste sind das 10 000 Memmoves. Vec::remove(0) macht dasselbe in umgekehrter Richtung. Beide sind O(n). Genau für diesen Fall existiert VecDeque: sie ist die richtige Wahl, sobald du regelmäßig vorne einfügst oder entfernst.

Ein häufiger Anfänger-Fehler ist, Vec für klassische FIFO-Queues zu nehmen und dabei remove(0) als Dequeue zu verwenden. Bei kleinen Queues unauffällig, bei großen ein performance-Killer. VecDeque hat dieses Problem schlicht nicht.

Wie es intern funktioniert

Das Verstehen des Ring-Buffer-Modells ist der Schlüssel, um VecDeque richtig einzusetzen. Anders als bei Vec, wo das erste Element immer an Speicher-Position 0 liegt und Wachstum nach hinten geht, kann der „Anfang" eines VecDeque irgendwo im Heap-Block stehen. Du musst dir das Heap-Array als Kreis vorstellen: nach dem letzten Slot kommt wieder der erste. Zwei Indizes — head für den Anfang und tail für hinter dem Ende — markieren den belegten Bereich. Sie laufen mit jedem push/pop weiter, mit Modulo gegen die Kapazität.

Ring-Buffer der Kapazität 8:
    [_, _, A, B, C, D, _, _]
          ^head        ^tail (exklusiv)

push_back: tail += 1
push_front: head -= 1 (mit Modulo)
pop_back: tail -= 1
pop_front: head += 1

Die ASCII-Skizze zeigt einen Buffer mit Kapazität 8 und vier belegten Slots in der Mitte. Wenn ein push_front kommt, läuft head nach links — beim Erreichen von Index 0 springt er gemäß Modulo zurück auf Index 7. Wenn ein push_back kommt, läuft tail nach rechts. Wenn die beiden sich treffen würden (Buffer voll), wird umgesetzt: ein neuer, doppelt so großer Heap-Block wird alloziert, alle Elemente werden in geordneter Reihenfolge umkopiert, danach steht head bei 0 und tail bei len. Erst dann sind die nächsten Operationen wieder günstig.

Diese Mechanik erklärt auch, warum Index-Zugriff auf VecDeque etwas anders funktioniert als bei Vec: q[i] ist intern eine (head + i) % capacity-Rechnung. Das ist immer noch O(1), aber mit einer zusätzlichen Modulo-Operation pro Zugriff — minimal teurer als bei Vec, in der Praxis nicht messbar.

Speicher-Layout

use std::collections::VecDeque;
use std::mem::size_of;

fn main() {
    println!("{}", size_of::<VecDeque<i32>>());      // 32
    // 8 ptr + 8 cap + 8 head + 8 len
}

VecDeque belegt im Stack 32 Bytes — acht mehr als Vec. Der zusätzliche Speicher steckt im head-Index, den Vec nicht braucht, weil dort der Anfang immer bei Position 0 liegt. Bei tausend kleinen VecDeques in einer Anwendung sind das also 8 KB Stack-Overhead — vernachlässigbar in den meisten Fällen, aber gut zu wissen für sehr speicherkritische Programme.

Die eigentlichen Elemente leben wie bei Vec auf dem Heap. Bei einem VecDeque mit 100 i32-Werten sind das 100 * 4 = 400 Bytes Heap-Speicher (plus eventuelle Reserve durch die Kapazitätspolitik), unabhängig vom Element-Typ.

Die wichtigsten Methoden

Neben den vier zentralen Operationen (push_front/back, pop_front/back) hat VecDeque die übliche Container-API: Lesen ohne Entfernen, Index-Zugriff, Iteration, Längenabfrage. Der gesamte Werkzeugkasten unterscheidet sich kaum von Vec — was den Wechsel zwischen den Containern erleichtert, wenn du im Nachhinein merkst, dass du die andere Charakteristik gebraucht hättest.

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::from([1, 2, 3, 4, 5]);

    // Front / Back lesen ohne Entfernen
    let f = q.front();           // Some(&1)
    let b = q.back();            // Some(&5)

    // Index-Zugriff
    let x = q[2];                // 3
    let y = q.get(99);           // None

    // Iteration
    for v in &q {
        print!("{v} ");
    }

    // Längen
    assert_eq!(q.len(), 5);
    assert!(!q.is_empty());
}

front() und back() sind die nicht-konsumierenden Pendants zu pop_front und pop_back — sie geben dir eine Option<&T> auf den ersten oder letzten Eintrag, ohne ihn zu entfernen. Praktisch, wenn du eine Queue „beobachten" willst, bevor du tatsächlich aus ihr entnimmst.

Index-Zugriff (q[i] und q.get(i)) ist O(1) — der Modulo-Trick aus dem Ring-Buffer-Modell macht das möglich. Das unterscheidet VecDeque deutlich von LinkedList, wo Index-Zugriff O(n) wäre, weil die Liste durchwandert werden müsste.

Die Iteration über for v in &q durchläuft alle Elemente in logischer Reihenfolge (also vom head zum tail), nicht in der physischen Heap-Reihenfolge. Damit musst du dich um den Ring-Buffer nie kümmern; die Iteration tut so, als wäre VecDeque eine ganz normale Sequenz.

Konvertierung

Zwischen Vec und VecDeque kannst du ohne hohe Kosten wechseln. Beide nutzen denselben heap-basierten Speicher, also lassen sich Daten oft direkt übernehmen, ohne eine teure Kopier-Operation. Das ist nützlich, wenn deine Verarbeitung in zwei Phasen abläuft: Phase eins braucht Front/Back-Operationen (VecDeque), Phase zwei nur Iteration (Vec wäre da etwas schneller).

use std::collections::VecDeque;

fn main() {
    // Aus Vec
    let v = vec![1, 2, 3];
    let q: VecDeque<i32> = v.into();
    // oder: VecDeque::from(v)

    // Zurück zu Vec
    let v2: Vec<i32> = q.into_iter().collect();
    // oder: Vec::from(q)
}

Bei Vec -> VecDeque ist die Operation typischerweise O(1) — der gesamte Heap-Block wird übernommen, head wird auf 0 gesetzt, tail auf len. Keine Element-Bewegung nötig. Bei VecDeque -> Vec muss eventuell umsortiert werden, falls der Ring-Buffer-Inhalt nicht zusammenhängend an Position 0 beginnt. Im Worst Case ist das eine O(n)-Operation, aber immerhin in-place und ohne Heap-Realloc.

Diese Konvertierungen sind ein Grund, in der API-Design-Phase nicht zu verkrampft an einem Typ festzuhalten. Wenn du nicht sicher bist, was du brauchst, kannst du später wechseln, ohne dass die Daten umgepackt werden müssen.

VecDeque vs. Vec

Die Faustregel ist einfach: Vec für sequenzielle Verarbeitung und LIFO-Stack-Verhalten, VecDeque für FIFO-Queues und Operationen an beiden Enden. Vec ist die Default-Wahl — wenn nicht klar ist, dass du Front-Operationen brauchst, nimm Vec. VecDeque ist die spezialisierte Wahl, sobald „push vorne" oder „pop vorne" zum Anwendungsfall gehören.

Ein Sonderfall ist die Slice-Conversion: Vec lässt sich direkt zu &[T] coercen (Standard-Pattern für Funktions-Parameter), VecDeque dagegen nicht, weil ihre Daten möglicherweise im zwei Stücken im Heap liegen. Wenn du VecDeque oft als Slice brauchen würdest, ist Vec wahrscheinlich die bessere Wahl, oder du nutzt VecDeque's make_contiguous (siehe nächster Abschnitt).

as_slices und make_contiguous

Eine direkte Folge des Ring-Buffer-Modells ist, dass der logisch zusammenhängende Inhalt physisch in zwei Stücken im Heap liegen kann. Stell dir einen Buffer mit Kapazität 8 vor, in den du erst sechs Elemente am Ende einfügst, dann zwei am Anfang — die Daten sind dann „A B _ _ _ C D E F" verteilt, also einmal in den Slots 0-1 und einmal in 4-8. Die Stdlib bietet dir zwei Wege, mit dieser Situation umzugehen.

use std::collections::VecDeque;

fn main() {
    let mut q: VecDeque<i32> = VecDeque::with_capacity(8);
    for i in 0..5 { q.push_back(i); }

    // Zwei Slice-Teile
    let (a, b) = q.as_slices();
    // a hat Inhalt, b ist leer oder hat den Rest

    // Erzwinge kontiguierlichen Speicher
    let slice: &mut [i32] = q.make_contiguous();
    // Jetzt ist alles in einem Slice
}

as_slices() ist die ehrliche Variante: sie gibt ein (&[T], &[T])-Tupel zurück — die zwei Teilsegmente. Wenn der Inhalt zusammenhängend ist, ist das zweite Slice leer. Du musst beide Teile getrennt verarbeiten, was bei Algorithmen, die mit einer einzigen &[T]-Sequenz arbeiten, unhandlich werden kann.

make_contiguous() ist die teure Lösung: sie verschiebt intern die Elemente so, dass sie wieder zusammenhängend in einem Slice liegen — anschließend gibt sie genau diesen Slice zurück. Im Worst Case ist das O(n), aber danach ist der Buffer aufgeräumt, und alle folgenden Slice-Zugriffe sind wieder O(1). Wenn du eine VecDeque einmalig in ein Slice-konsumierendes Stück Code übergeben willst, lohnt sich der einmalige Aufwand.

Eine kleine Stolperfalle: make_contiguous braucht &mut self, weil es den Inhalt umstellt. Du brauchst also eine mutable Bindung — auch wenn du danach nur lesen willst.

LinkedList — selten gebraucht

Eine doppelt verkettete Liste klingt in der Theorie interessant: jeder Knoten ist eine eigene Heap-Allocation mit zwei Pointern (zum Vorgänger und Nachfolger). Insertion und Deletion an einer beliebigen Position sind formal O(1), wenn du einen Iterator-Cursor an dieser Position hast. Du musst nichts umkopieren wie bei Vec/VecDeque, du hängst einfach neue Knoten in die Kette ein.

Die Praxis sieht jedoch anders aus, und in Rust wird LinkedList<T> deshalb auffallend selten genutzt. Die theoretischen Vorteile werden von ganz konkreten Nachteilen erdrückt.

use std::collections::LinkedList;

fn main() {
    let mut l: LinkedList<i32> = LinkedList::new();
    l.push_back(1);
    l.push_back(2);
    l.push_front(0);
    // l: 0 → 1 → 2
}

Vier Gründe, warum LinkedList in der Praxis selten die richtige Wahl ist:

Schlechte Cache-Lokalität. Jeder Knoten wird einzeln auf dem Heap alloziert, oft in völlig unterschiedlichen Speicher-Bereichen. Beim Iterieren springt die CPU von Knoten zu Knoten — jeder Sprung kann ein Cache-Miss sein, der hundert Takte kostet. Bei einem Vec oder VecDeque liegen alle Elemente eng beieinander; eine Iteration läuft fast vollständig im L1- oder L2-Cache.

Höherer Memory-Overhead. Pro Element brauchst du nicht nur den Wert, sondern auch zwei Pointer (für die Verkettung) plus Allocator-Header-Bytes. Bei einem LinkedList<u8> zahlst du also für jeden einzelnen u8-Wert mindestens 17 Bytes — ein Vielfaches des Nutzwerts. Bei Vec<u8> ist es genau ein Byte pro Element.

Asymptotische Komplexität gleicht VecDeque für die meisten Operationen. Push/Pop an beiden Enden ist bei beiden O(1). Lookup ist bei beiden O(n). Der einzige Vorteil der LinkedList wäre Insertion-in-Middle, aber:

Insert in der Mitte ist nur dann O(1), wenn du schon einen Cursor an der richtigen Stelle hast. In der Praxis braucht man fast immer erst eine Suche, um die Stelle zu finden — und die ist O(n). Das eliminiert den theoretischen Vorteil komplett.

Faustregel: Wenn du an LinkedList denkst, nimm zuerst VecDeque. Erst wenn du dann immer noch echte Vorteile aus der LinkedList ziehen kannst (z. B. Cursor-basierte Algorithmen, die häufig mitten in der Sequenz Knoten einfügen oder herausnehmen), ist sie die richtige Wahl. In der Stdlib-Doku selbst steht der Hinweis, dass VecDeque „fast immer eine bessere Wahl" sei.

Praxis: VecDeque im echten Code

VecDeque taucht überall dort auf, wo Werte am einen Ende reinkommen und am anderen rausgehen müssen. Die folgenden Beispiele zeigen die häufigsten Patterns — Queues, Sliding-Windows, Buffer mit fester Größe, Undo-Stacks. Bei allen liegt die Stärke von VecDeque darin, dass die O(1)-Operationen an beiden Enden den Algorithmus erst praktikabel machen.

BFS-Traversal

use std::collections::{HashSet, VecDeque};

pub fn bfs_kuerzeste(graph: &[(u32, u32)], start: u32, ziel: u32) -> Option<u32> {
    let mut queue: VecDeque<(u32, u32)> = VecDeque::new();
    let mut visited: HashSet<u32> = HashSet::new();
    queue.push_back((start, 0));
    visited.insert(start);

    while let Some((node, distanz)) = queue.pop_front() {
        if node == ziel { return Some(distanz); }
        for &(a, b) in graph {
            if a == node && visited.insert(b) {
                queue.push_back((b, distanz + 1));
            }
        }
    }
    None
}

Die Breitensuche (BFS) ist der Lehrbuch-Anwendungsfall für VecDeque. Der Algorithmus arbeitet in „Ringen" — zuerst alle Nachbarn des Startknotens, dann deren Nachbarn, und so weiter. Damit die Reihenfolge stimmt, brauchst du eine echte FIFO-Queue: neue Knoten werden hinten angehängt (push_back), als nächstes zu verarbeitende Knoten kommen vorne raus (pop_front).

Würdest du das mit Vec und remove(0) machen, wäre der Algorithmus O(n²) bei einem Graphen mit n Knoten — jedes Dequeue müsste alle übrigen Elemente nach vorne kopieren. Mit VecDeque bleibt die Gesamtkomplexität O(V + E), also linear in der Anzahl Knoten und Kanten.

Der HashSet als Visited-Tracker stellt sicher, dass jeder Knoten höchstens einmal in die Queue kommt. Das ist die zweite Voraussetzung dafür, dass BFS korrekt arbeitet — ohne die Markierung würden Knoten in Zyklen unendlich oft verarbeitet.

Sliding-Window-Aggregator

use std::collections::VecDeque;

pub struct SlidingAverage {
    werte: VecDeque<f64>,
    max_size: usize,
    summe: f64,
}

impl SlidingAverage {
    pub fn neu(window_size: usize) -> Self {
        SlidingAverage {
            werte: VecDeque::with_capacity(window_size),
            max_size: window_size,
            summe: 0.0,
        }
    }

    pub fn record(&mut self, wert: f64) {
        self.werte.push_back(wert);
        self.summe += wert;
        if self.werte.len() > self.max_size {
            if let Some(alt) = self.werte.pop_front() {
                self.summe -= alt;
            }
        }
    }

    pub fn mittel(&self) -> Option<f64> {
        if self.werte.is_empty() { None }
        else { Some(self.summe / self.werte.len() as f64) }
    }
}

Ein Sliding-Window-Durchschnitt muss bei jedem neuen Wert den ältesten verwerfen und einen neuen aufnehmen — und dabei den Mittelwert effizient halten. Die naive Implementation würde bei jedem record-Aufruf den gesamten Window summieren (O(window_size)). Diese Variante macht es mit O(1): die Gesamtsumme wird gepflegt, beim Hinzufügen wird der neue Wert dazu addiert, beim Entfernen der alte abgezogen.

VecDeque ist hier die natürliche Wahl, weil neue Werte hinten reinkommen und alte vorne rausfallen. Mit einem Vec und remove(0) wäre die Operation wieder O(n), und der Performance-Gewinn der Summenpflege wäre dahin.

Anwendungsfälle: Latenz-Monitoring (Durchschnitt der letzten N Requests), Sensor-Daten-Glättung (kein einzelner Ausreißer dominiert), Finanz-Indikatoren (gleitender Durchschnitt eines Kurses). Bei sehr großen Windows lohnen sich Spezial-Datenstrukturen wie Reservoir-Sampling oder t-digest, aber für moderate Window-Größen ist VecDeque ideal.

Worker-Queue

use std::collections::VecDeque;

pub struct JobQueue<T> {
    jobs: VecDeque<T>,
}

impl<T> JobQueue<T> {
    pub fn neu() -> Self {
        JobQueue { jobs: VecDeque::new() }
    }

    pub fn enqueue(&mut self, job: T) {
        self.jobs.push_back(job);
    }

    pub fn dequeue(&mut self) -> Option<T> {
        self.jobs.pop_front()
    }

    pub fn priorisieren(&mut self, job: T) {
        self.jobs.push_front(job);      // an den Anfang — höchste Priorität
    }
}

Eine Worker-Queue mit Prioritäts-Mechanik in der einfachsten Form. Normale Jobs gehen hinten rein (enqueue mit push_back), priorisierte Jobs werden vorne reingesetzt (priorisieren mit push_front). Der Worker holt sich Jobs vorne raus (dequeue mit pop_front) — damit werden priorisierte Jobs als erstes verarbeitet.

Das ist natürlich noch keine echte Priority-Queue mit beliebigen Prioritäten — dafür wäre BinaryHeap die richtige Wahl. Aber für „normal/dringend"-Zweiteilung reicht VecDeque und ist deutlich effizienter, weil die beiden Operationen jeweils O(1) sind.

Event-Log mit fester Größe

use std::collections::VecDeque;

pub struct BoundedLog {
    eintraege: VecDeque<String>,
    max: usize,
}

impl BoundedLog {
    pub fn neu(max: usize) -> Self {
        BoundedLog { eintraege: VecDeque::with_capacity(max), max }
    }

    pub fn add(&mut self, eintrag: String) {
        if self.eintraege.len() == self.max {
            self.eintraege.pop_front();
        }
        self.eintraege.push_back(eintrag);
    }

    pub fn alle(&self) -> impl Iterator<Item = &String> {
        self.eintraege.iter()
    }
}

Ein Log mit beschränkter Größe — sobald max Einträge erreicht sind, fallen die ältesten beim nächsten add raus. Das ist das Ring-Buffer-Muster für „behalte die letzten N", typisch für Audit-Trails, Debug-Logs, Rolling-Window-Statistiken. Bei jedem neuen Eintrag prüfen wir die Größe und werfen ggf. vorne einen weg.

VecDeque::with_capacity(max) reserviert den Buffer einmalig in der richtigen Größe — danach läuft das Add ohne weitere Reallocations. Die max-Größe ist die effektive Obergrenze; der Buffer wächst nie über sie hinaus.

Undo/Redo-Stack

use std::collections::VecDeque;

pub struct History<T> {
    done: VecDeque<T>,
    undone: VecDeque<T>,
    limit: usize,
}

impl<T: Clone> History<T> {
    pub fn neu(limit: usize) -> Self {
        History { done: VecDeque::new(), undone: VecDeque::new(), limit }
    }

    pub fn add(&mut self, item: T) {
        self.done.push_back(item);
        if self.done.len() > self.limit {
            self.done.pop_front();
        }
        self.undone.clear();
    }

    pub fn undo(&mut self) -> Option<T> {
        let item = self.done.pop_back()?;
        self.undone.push_back(item.clone());
        Some(item)
    }

    pub fn redo(&mut self) -> Option<T> {
        let item = self.undone.pop_back()?;
        self.done.push_back(item.clone());
        Some(item)
    }
}

Undo/Redo ist die Domain-Anwendung schlechthin für zwei verbundene Stacks. Jede neue Aktion landet auf dem done-Stack (mit push_back). Bei undo wird das letzte Element von done auf undone umgehängt — und der Aufrufer bekommt das ursprüngliche Item zurück, damit er es rückgängig machen kann. Bei redo wandert es zurück.

add löscht den undone-Stack, weil eine neue Aktion nach einem Undo die Redo-Kette zerstört — das ist Standard-Verhalten in jeder Text-Editor-Undo-Logik. Mit dem limit wird die History auf maximal limit Einträge beschränkt; bei Überschreitung fällt der älteste Eintrag vorne raus.

Hier nutzen wir VecDeque eigentlich nur für push_back, pop_back und das pop_front zum Limit-Einhalten. Mit einem reinen Vec würde das fast funktionieren, aber das pop_front für den Limit-Verfall wäre O(n) — VecDeque macht es O(1).

Token-Pipeline

use std::collections::VecDeque;

pub struct TokenStream {
    buffer: VecDeque<String>,
}

impl TokenStream {
    pub fn neu() -> Self { TokenStream { buffer: VecDeque::new() } }

    pub fn push(&mut self, tokens: Vec<String>) {
        self.buffer.extend(tokens);
    }

    pub fn peek_n(&self, n: usize) -> Vec<&String> {
        self.buffer.iter().take(n).collect()
    }

    pub fn consume(&mut self) -> Option<String> {
        self.buffer.pop_front()
    }
}

Token-Streams in Parsern und Lexern profitieren von der VecDeque-API. Der Producer (z. B. ein Lexer) drückt mehrere Tokens auf einmal in den Buffer (extend ist effizienter als viele einzelne Pushes). Der Consumer (z. B. ein Parser) zieht sie einzeln vorne raus.

Die peek_n-Methode ist ein typisches Lexer/Parser-Pattern: schau dir die nächsten n Tokens an, ohne sie zu konsumieren. Damit kann der Parser Lookahead machen, etwa um zwischen unterschiedlichen Grammatikregeln zu unterscheiden, bevor er sich entscheidet. Bei einem klassischen Vec mit Anfangs-Index wäre das umständlicher; bei einer LinkedList wäre peek_n O(n), wegen der Knoten-Navigation.

LRU-Cache-Skeleton

use std::collections::{HashMap, VecDeque};

pub struct LruCache<K, V> {
    capacity: usize,
    data: HashMap<K, V>,
    order: VecDeque<K>,
}

impl<K: std::hash::Hash + Eq + Clone, V> LruCache<K, V> {
    pub fn neu(capacity: usize) -> Self {
        LruCache {
            capacity,
            data: HashMap::with_capacity(capacity),
            order: VecDeque::with_capacity(capacity),
        }
    }

    pub fn put(&mut self, key: K, wert: V) {
        if self.data.len() == self.capacity && !self.data.contains_key(&key) {
            if let Some(oldest) = self.order.pop_front() {
                self.data.remove(&oldest);
            }
        }
        if !self.data.contains_key(&key) {
            self.order.push_back(key.clone());
        }
        self.data.insert(key, wert);
    }

    pub fn get(&self, key: &K) -> Option<&V> {
        self.data.get(key)
    }
}

Ein vereinfachter LRU-Cache (Least Recently Used): wenn die Kapazität voll ist und ein neuer Eintrag kommt, wird der älteste rausgeworfen. Die HashMap dient als Datenspeicher mit O(1)-Lookup, die VecDeque als Reihenfolge-Tracker — vorne stehen die ältesten Keys, hinten die jüngsten.

Diese Implementation ist intentional simpel: bei jedem put wird geprüft, ob die Kapazität voll ist; wenn ja, wird der älteste Key sowohl aus der VecDeque als auch aus der HashMap entfernt. Was sie nicht macht: einen vorhandenen Key beim Zugriff in der Reihenfolge nach hinten verschieben — eine echte LRU würde das tun, um „recently used" korrekt zu verfolgen.

Für produktive LRU-Caches lohnt sich das lru-Crate, das eine HashMap-Plus-LinkedList-Kombination intern nutzt und Move-to-Back in O(1) macht (das wäre mit einer reinen VecDeque-Plus-HashMap nicht trivial möglich). Aber als Lehrbuch-Beispiel zeigt diese Variante schön, wie HashMap und VecDeque sich ergänzen.

Async-Channel-Buffer

use std::collections::VecDeque;
use std::sync::Mutex;

pub struct SimpleChannel<T> {
    buffer: Mutex<VecDeque<T>>,
}

impl<T> SimpleChannel<T> {
    pub fn neu() -> Self {
        SimpleChannel { buffer: Mutex::new(VecDeque::new()) }
    }

    pub fn send(&self, item: T) {
        self.buffer.lock().unwrap().push_back(item);
    }

    pub fn recv(&self) -> Option<T> {
        self.buffer.lock().unwrap().pop_front()
    }
}

Eine minimalistische Channel-Implementation für Producer/Consumer-Kommunikation. Der Mutex macht die VecDeque thread-safe — mehrere Sender können gleichzeitig send aufrufen, der Receiver liest mit recv. Wirklich gute Channels (wie std::sync::mpsc oder das crossbeam-Crate) haben deutlich mehr Features (Blocking-Wait, Bounded-Capacity, Multi-Receiver), aber die Grundstruktur ist exakt diese: ein Mutex um eine VecDeque.

Beachtenswert ist die Effizienz: push_back und pop_front sind beide O(1), und durch den Ring-Buffer-Mechanismus bleibt die Speicher-Nutzung über lange Lebenszeiten stabil. Mit einem Vec würde der Buffer entweder durch remove(0) permanent O(n) kosten oder durch nicht-aufgeräumtes Anwachsen Speicher verschlingen.

Weiterführende Ressourcen

Externe Quellen

• std::collections::VecDeque
• std::collections::LinkedList
• std::collections – Performance Comparison

Verwandte Artikel

• Vec
• Kapazität und Reallocation
• Collections – Übersicht