The Entry API: one lookup, not two

Two classic map tasks: grouping and counting.

pub fn group_words(lines: Vec<String>) -> BTreeMap<String, Vec<String>>
pub fn word_counts(words: Vec<String>) -> BTreeMap<String, u32>

• group_words splits every line on whitespace and groups the words by their first character (as a one-character String key). Words inside a group stay in input order. Empty lines contribute nothing.
• word_counts counts how many times each word appears.

Both return BTreeMap, which iterates in key order — so the output is deterministic and the JSON the harness prints is stable. Use a HashMap here and the answer changes between runs.

The error in the starter is the reason the Entry API exists

The starter contains bucket_for: “give me the vector for this key, creating an empty one if it is missing”. Every language has this helper. Rust rejects it:

error[E0499]: cannot borrow `*map` as mutable more than once at a time
  |
3 |     match map.get_mut(key) {
  |           --- first mutable borrow occurs here
6 |             map.insert(key.to_string(), Vec::new());
  |             ^^^ second mutable borrow occurs here
  |
  |     returning this value requires that `*map` is borrowed for `'a`

Read the last line. The Some(bucket) => bucket arm returns a &mut that the caller keeps, so the borrow taken by get_mut must last for the whole 'a — including inside the None arm, where the key was not found and the borrow is doing nothing useful. The compiler cannot see that the two arms are mutually exclusive with respect to that borrow. This is a known limitation of the borrow checker, not a mistake in your code.

You could get around it with a second contains_key first, paying for two lookups. Or you could use the thing the standard library added because of this exact problem:

map.entry(key).or_default().push(word);

entry(k) performs one hash-and-probe and hands back an Entry — an enum, Occupied or Vacant, holding the position it found. Everything after that operates on that position without searching again:

• .or_insert(v) — &mut V, inserting v if vacant
• .or_insert_with(|| expensive()) — same, but only calls the closure on miss
• .or_default() — same, using V: Default
• .and_modify(|v| ...) — run only if occupied, chainable before or_insert

Counting becomes a one-liner, and the * is where people stumble — or_insert gives you a &mut u32, so you dereference to add:

*map.entry(word).or_insert(0) += 1;

::: question or_insert(compute_default()) versus or_insert_with(|| compute_default()) — when does it matter? Always, if compute_default() does real work. Arguments in Rust are evaluated eagerly, before the call, so or_insert(compute_default()) runs compute_default() on every single iteration — including the millions where the key is already present and the value is thrown away. or_insert_with takes a closure and only calls it on a miss.

clippy’s or_fun_call catches the obvious cases. It stays quiet for cheap constants like or_insert(0), which is correct: a closure there would be noise. :::

map_entry is default-on, and narrower than you think

clippy denies the two-lookup shape:

error: usage of `contains_key` followed by `insert` on a `BTreeMap`

Verified against clippy 0.1.95, it fires on:

if !m.contains_key(&k) { m.insert(k, v); }                       // fires
if m.contains_key(&k) { m.insert(k, a) } else { m.insert(k, b) } // fires

on both HashMap and BTreeMap. And it stays silent on:

if !m.contains_key(&w) { m.insert(w.clone(), 0); }   // silent
*m.get_mut(&w).unwrap() += 1;

because the key expression in the insert (w.clone()) is not syntactically the one in the contains_key (&w). The lint matches a pattern, not a cost. Do not learn “clippy will tell me when I double-look-up” — learn to see the double lookup yourself, and treat the lint as a bonus.

The benchmark, including the part that contradicts the lint

Grouping 300 000 (u32, u32) pairs:

entry().or_default().push()               1.39 ms
contains_key + get_mut + insert           2.46 ms      entry wins 1.77x

Exactly what the lint promises. Now count 200 000 String keys:

entry(w.clone())                          4.78 ms
contains_key + clone only on a miss       4.24 ms      entry LOSES
&str keys, cloning nothing                3.33 ms      the real answer

Why? Because entry demands an owned key up front — it might insert, so it needs something it can store. With Copy keys that costs nothing. With String keys it means a clone() on every iteration, including the 199 000 that hit an existing entry and throw the clone away. The two-lookup version can clone only on the miss, and two lookups of an already-hashed short string are cheaper than an allocation.

So a default-on lint is right for Copy keys and wrong for owned keys, and it cannot tell the difference. That is not a criticism of clippy — it is a lesson about what a lint is. It encodes a good default. The third row is the reminder that the best fix is usually to change the shape of the data, not to pick between two spellings of the same shape.

(For this problem the maps are small and the keys are short; write the entry version. But now you know what you would measure if it mattered.)

Remember the grade is compile + tests + clippy -D warnings.