Step 6 of 6

Choosing a collection

You now know every collection in std::collections. Choosing one is about how you'll access the data. Here's the cheat sheet teams actually use:

Questions to ask:

1. How will I look things up? By position (Vec), by key (a map), by "the best one" (BinaryHeap), by range (BTreeMap)?
2. Does order matter? Insertion order (Vec, VecDeque), sorted order (BTree*), or none (Hash*)? Output that people or tests read must be deterministic, which rules out iterating a HashMap directly.
3. How big will it get? For a handful of items a Vec with a linear search often beats a HashMap, because hashing has a cost. Start with Vec and change when the access pattern or a profile says so.

Combining collections

Real systems often keep the same data in two shapes, one per kind of question. This order summary uses three collections, each for what it's good at:

use std::collections::{BTreeMap, BinaryHeap, HashMap};

fn main() {
    // (day, customer, amount in cents)
    let orders = [(3, "ana", 1250), (1, "ben", 830), (3, "ben", 4999), (2, "ana", 300), (1, "cy", 2100)];

    let mut by_customer: HashMap<&str, Vec<u32>> = HashMap::new();
    let mut per_day: BTreeMap<u32, u32> = BTreeMap::new();
    let mut biggest = BinaryHeap::new();
    for &(day, customer, cents) in &orders {
        by_customer.entry(customer).or_default().push(cents);
        *per_day.entry(day).or_insert(0) += cents;
        biggest.push((cents, customer));
    }
    println!("ben's orders: {:?}", by_customer["ben"]);
    for (day, total) in &per_day {
        println!("day {day}: {total}");
    }
    println!("largest: {:?}", biggest.pop());
}

ben's orders: [830, 4999]
day 1: 2930
day 2: 300
day 3: 6249
largest: Some((4999, "ben"))

• The HashMap answers "everything about one customer" in O(1).
• The BTreeMap answers "totals per day, in day order" without sorting.
• The BinaryHeap answers "the biggest order" (and the next biggest, and so on).
• entry(key).or_default() creates an empty Vec the first time a customer appears: the idiomatic way to group.

Common mistakes

• One collection for every question, then sorting or scanning it on every request. If a question is asked often, give it its own index.
• Keeping two collections out of sync. When data lives in two places, update both in the same method so nobody can forget one. That's a good reason to wrap them in a struct with methods.
• Choosing by habit. "HashMap because it's fast" is wrong when you need sorted output, and "BTreeMap for safety" costs O(log n) when you never need order.

Your task

An API gateway needs a rate limiter: each user may make at most limit requests in any window of window seconds. Write:

• fn new(limit: usize, window: u64) -> Self
• fn allow(&mut self, user: &str, now: u64) -> bool

A request at time now counts the user's earlier allowed requests at times t with now - t < window. If there are fewer than limit, allow it (and remember now); otherwise reject it. Rejected requests don't count. Times never go backwards.

Use a HashMap<String, VecDeque<u64>>: for each user, a queue of their recent allowed times. Before deciding, pop the times that have left the window off the front. The tests make 200,000 requests from one user with a limit of 50,000, so don't rescan the whole history on every call.

Challenge 2

Marketing wants a page report from the web server's access log. Each line of standard input is PAGE USER, like /home ana. For every page, in alphabetical order, print how many different users visited it and how many views it had in total:

/cart: 1 visitors, 1 views
/home: 2 visitors, 3 views

Pick collections that make this easy: a BTreeMap from page to a pair of a HashSet of users and a view count. Skip blank lines.

Challenge 3

Build an LRU cache (least recently used): a fixed-capacity key-value store that, when full, evicts the entry that was used longest ago. Caches like this sit in front of slow databases everywhere.

fn new(capacity: usize) -> Self            // capacity is at least 1
fn get(&mut self, key: &str) -> Option<i32> // a hit counts as a use
fn put(&mut self, key: &str, value: i32)    // insert or update (also a use), then evict if over capacity

Combine two collections: a HashMap<String, (i32, u64)> from key to (value, time of last use), and a BTreeMap<u64, String> from time of last use to key. A counter tick goes up by one on every use. The least recently used key is then by_age.pop_first(), in O(log n). When a key is used again, remove its old time from by_age and insert the new one. The tests run 120,000 operations on a cache of 5,000 entries.

Previous: LinkedList, and why it's rare