Choosing Specialized Collections

When a workload moves beyond a plain growable array (Vec<T>) or key-value table (HashMap<K, V>), selecting the right specialized collection or adapter ensures optimal time complexity and cache behavior.

Quick Selection Guide for Specialized Collections

Workload / Access Pattern	Best Specialized Choice	Key Reason
FIFO queue, BFS traversal, or sliding window buffer	`VecDeque<T>`	Amortized $O(1)$ `push_back` and $O(1)$ `pop_front` in a contiguous ring buffer
In-memory byte pipe (`Read + Write`)	`VecDeque<u8>`	Implements `std::io::Read` (front) and `std::io::Write` (back) directly
Max-priority queue (highest priority first)	`BinaryHeap<T>`	$O(1)$ `peek`, $O(\log n)$ `push`/`pop` inside a single `Vec<T>` allocation
Min-priority queue or streaming Top-$K$ largest	`BinaryHeap<Reverse<T>>`	Zero-cost `Reverse<T>` wrapper inverts `Ord` without custom comparator boilerplate
Double-ended priority queue (pop both min and max)	`BTreeSet<T>` (or `BTreeMap<T, usize>`)	$O(\log n)$ `pop_first` and `pop_last`
Priority queue with $O(\log n)$ cancel / reprioritize by ID	`BTreeSet<(Prio, Id)>` + `HashMap<Id, Prio>`	Direct $O(\log n)$ removal of `(old_prio, id)`
$O(1)$ concatenation of two huge independent lists	`LinkedList<T>`	`list_a.append(&mut list_b)` relinks four pointers in $O(1)$ time

Combining Specialized Collections: Rate-Limited Priority Dispatcher

A practical event dispatcher often combines VecDeque (for tracking timestamps in a sliding rate-limit window) with BinaryHeap (for dispatching the highest-priority pending message whenever capacity is available in the window):

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

struct RateLimitedDispatcher {
    window_ms: u64,
    max_per_window: usize,
    sent_timestamps: VecDeque<u64>,
    pending_jobs: BinaryHeap<(u8, &'static str)>, // (priority, job_name)
}

impl RateLimitedDispatcher {
    fn new(window_ms: u64, max_per_window: usize) -> Self {
        Self {
            window_ms,
            max_per_window,
            sent_timestamps: VecDeque::with_capacity(max_per_window),
            pending_jobs: BinaryHeap::new(),
        }
    }

    fn enqueue(&mut self, priority: u8, job: &'static str) {
        self.pending_jobs.push((priority, job));
    }

    fn poll(&mut self, now_ms: u64) -> Option<(&'static str, u8)> {
        // 1. Evict expired timestamps from the front of the VecDeque in O(1) each:
        while let Some(&oldest) = self.sent_timestamps.front() {
            if now_ms.saturating_sub(oldest) >= self.window_ms {
                self.sent_timestamps.pop_front();
            } else {
                break;
            }
        }

        // 2. If under the rate limit, pop the highest-priority job from BinaryHeap:
        if self.sent_timestamps.len() < self.max_per_window {
            let (prio, job) = self.pending_jobs.pop()?;
            self.sent_timestamps.push_back(now_ms);
            Some((job, prio))
        } else {
            None
        }
    }
}

fn main() {
    // Allow at most 2 jobs per 1000ms window:
    let mut dispatcher = RateLimitedDispatcher::new(1_000, 2);
    dispatcher.enqueue(10, "low_prio_sync");
    dispatcher.enqueue(90, "critical_alert");
    dispatcher.enqueue(50, "user_webhook");

    println!("@100ms:  {:?}", dispatcher.poll(100));
    println!("@200ms:  {:?}", dispatcher.poll(200));
    println!("@300ms:  {:?} (rate limited!)", dispatcher.poll(300));
    println!("@1150ms: {:?} (100ms slot expired)", dispatcher.poll(1_150));
}

@100ms:  Some(("critical_alert", 90))
@200ms:  Some(("user_webhook", 50))
@300ms:  None (rate limited!)
@1150ms: Some(("low_prio_sync", 10)) (100ms slot expired)