skip to content

Owned Collection Types

std ships Vec, String, HashMap, BTreeMap, VecDeque and BinaryHeap, each with ownership rules on top of its data structure. Interviewers ask which to choose and what it costs.

on this pageshow

explore

questions

26

In Rust, why does printing a BTreeMap<&str, usize> list keys in sorted order when a HashMap does not, and what must its key type implement?

level: juniorimportance: must knowfreq 60%

answer

  1. where the order comes from
  2. which comparison trait the methods need
  3. the bound sits on insert, not new
  4. f64 keys and E0277
  5. a randomly seeded hasher

basics

~20 s

BTreeMap keeps entries sorted by key, so iteration and Debug output walk them in ascending order, and its key type must implement Ord. HashMap places entries by a randomly seeded hash, so its order is arbitrary, and it needs Hash + Eq instead.

solid answer

~40 s

A `BTreeMap<K, V>` is an ordered map. Every insert puts the key at its sorted position, and `iter`, `keys`, `values`, `into_iter` and the `{:?}` output all yield entries in ascending key order, on every run. That is why its methods carry a `K: Ord` bound: `insert`, `get`, `range` and `entry` all compare keys. `BTreeMap::new` has no bound, so a float key fails at the first `insert` with E0277 ("the trait bound `f64: Ord` is not satisfied"). A `HashMap` needs `Hash + Eq` and uses a randomly seeded hasher, so its order is arbitrary and can change between runs. Choose `BTreeMap` for sorted output, range queries or reproducible iteration in snapshot tests and diffs. As a bonus, `BTreeMap` and `BTreeSet` implement `Hash` and `Ord` themselves, so they can serve as keys, which `HashMap` cannot.

code

rust · 17 lines
rust
use std::collections::{BTreeMap, HashMap};

fn main() {
    let words = ["pear", "apple", "fig", "kiwi", "banana"];

    let mut hashed: HashMap<&str, usize> = HashMap::new();
    let mut sorted: BTreeMap<&str, usize> = BTreeMap::new();
    for w in words {
        hashed.insert(w, w.len());
        sorted.insert(w, w.len());
    }

    // Order depends on this map's random hasher seed: can differ run to run.
    println!("{hashed:?}");
    // Always ascending by key, because &str implements Ord.
    println!("{sorted:?}");
}

go deeper

for a junior

Recall that BTreeMap iterates in ascending key order and needs Ord keys, while HashMap order is arbitrary and needs Hash plus Eq.

for a middle

Explain that the Ord bound lives on insert, get and range rather than on new, and read the E0277 that a float key produces.

for a senior

Show when determinism matters in production: snapshot tests, serialized diffs and reproducible logs, and why a hashed map's order must never be relied on.

for a principal

Frame the choice as an API decision: exposing a BTreeMap gives callers ordering and hashability, which becomes part of the contract you cannot quietly withdraw.

## What "ordered" means for `BTreeMap` A **`BTreeMap<K, V>`** (in `std::collections`) is an **ordered map**. Every `insert` places the key at its sorted position, so the map is always ordered by key. Whatever order you insert in, these all yield entries in **ascending key order**: - `iter`, `iter_mut`, `keys`, `values` and `into_iter`; - a `for (k, v) in &map` loop, which calls `iter` under the hood; - the `{:?}` output, because the `Debug` impl walks the same iterator. The std docs state that these iterators produce items in key order. That is why a `BTreeMap<&str, usize>` printed twice gives the same output on every run and every machine. **`BTreeSet<T>`** is the same structure with keys only: its `iter` yields elements in ascending order. ## The `Ord` bound and where rustc enforces it To keep keys sorted, the map has to compare any two of them and get a definite `Ordering` (`Less`, `Equal` or `Greater`). That is what the **`Ord`** trait promises: a total order. So the methods that place or find a key carry a `K: Ord` bound. That includes `insert`, `get`, `contains_key`, `remove`, `entry` and `range`. One detail surprises people: **`BTreeMap::new` has no bound** (it is even a `const fn`). The error appears at the first call that needs to compare: ```rust let mut prices = BTreeMap::new(); prices.insert(19.99_f64, "widget"); // error[E0277]: the trait bound `f64: Ord` is not satisfied ``` rustc points at the `K: Ord` clause on `BTreeMap::insert`. Floats are the classic case because `NaN` breaks a total order, so `f64` implements only `PartialOrd`. How to order such a type is covered with the comparison traits. For a price, the usual fix is an integer number of cents or ticks. ## Why `HashMap` prints in a different order A **`HashMap<K, V>`** needs `K: Hash + Eq`, not `Ord`. It files each entry under a bucket chosen from the key's hash. By default the hasher is `RandomState`, which is seeded randomly, so two maps holding the same keys can lay them out differently. The std docs describe its iterators as visiting entries in **arbitrary order**. The order can change between runs of the same program; two runs of one binary printed the same map's keys in two different orders. How the hasher works and why it is randomised belongs with the hash map material. ## Choosing between them | Need | `BTreeMap` | `HashMap` | |---|---|---| | Key bound | `Ord` | `Hash + Eq` | | Iteration order | ascending by key, every run | arbitrary, may differ per run | | Range queries (`range`) | yes | no | | Smallest or largest key | `first_key_value`, `last_key_value` | a full scan | | Map usable as a key itself | yes: it implements `Hash` and `Ord` | no: no `Hash` impl | | Hasher to choose or tune | none | `RandomState` by default | Reach for `BTreeMap` when: 1. output must be **sorted** (a report, a CLI listing, a config dump); 2. you need **reproducible iteration**: snapshot tests, diffs of serialized state, deterministic logs; 3. you query **ranges** or the **ends** of the key space; 4. the map itself must be **hashed or compared**, for example a `BTreeSet<u32>` stored inside a `HashSet`. For plain lookups by key, with no need for order, a `HashMap` is the common default. ## The same rules for `BTreeSet` `BTreeSet<T>` wraps a `BTreeMap` whose values are a zero-sized placeholder, a set of keys with nothing attached, and it follows the same rules: - `insert` requires `T: Ord` and returns `true` only when the value was not already present; - `iter` and the `{:?}` output are in ascending order, so `BTreeSet::from([3, 1, 2])` prints `{1, 2, 3}`; - set operations such as `union`, `intersection` and `difference` also yield their results in sorted order. That makes a `BTreeSet` the quickest way to get a **sorted, deduplicated** list of values, such as tags, user ids or file names, without a separate sort and dedup pass. ## Mistakes interviewers listen for - Thinking `BTreeMap` keeps **insertion order**. It keeps key order. Insertion order needs something else, such as a `Vec` of keys kept alongside the map. - Assuming a `HashMap` with integer keys prints sorted. It may look sorted on a small map by accident, and that proves nothing. - Expecting `BTreeMap::new()` itself to reject a non-`Ord` key. The bound sits on the methods. - Believing `BTreeMap` needs `Hash`. It never hashes anything.

  • How do you key a Rust BTreeMap by a price when f64 does not implement Ord?
    The usual fix is to store the price as an integer, such as cents or exchange ticks in a `u64`. Exact integer keys are what money needs anyway. If you must keep the float, wrap it in a newtype whose `Ord` uses `f64::total_cmp`. Writing that impl correctly is covered with the comparison traits.
  • Why can a BTreeSet<u32> be an element of a HashSet when a HashSet<u32> cannot?
    `BTreeSet<T>` implements `Hash` (when `T: Hash`) and `Ord`. Its elements always iterate in sorted order, so equal sets feed the hasher the same sequence. `HashSet` and `HashMap` implement neither `Hash` nor `Ord`, so using one as a key fails with a missing-trait error. A sorted set is the standard way to key by a set of values.

  • BTreeMap keeps keys in the order they were inserted.
  • A BTreeMap key only needs Eq, the same as a HashMap key.
  • BTreeMap::new() refuses to compile when the key type lacks Ord.
  • A HashMap with integer keys always iterates in ascending order.
  • BTreeMap hashes its keys, so they must implement Hash.
open as a page

In Rust, which std collection fits a sliding-window rate counter that appends new timestamps and expires old ones, and which methods do the work?

level: juniorimportance: must knowfreq 62%

basics

~10 s

Use std::collections::VecDeque: push_back each new timestamp, then pop_front while front() is older than the window. Both ends are amortised O(1), unlike Vec::remove(0), which shifts every remaining element.

open as a page

In a Rust session cache `HashMap<String, u32>`, what do `insert`, `get` and `map[key]` return when a key is new, present or missing?

level: juniorimportance: must knowfreq 72%

basics

~20 s

insert returns None for a new key and Some(old value) when it overwrites one; get returns Option<&V>, None when the key is missing; map[key] returns the value directly and panics with "no entry found for key" when it is absent.

open as a page

In Rust, why does `let first = name[0];` fail to compile when `name` is a `String`, and how do you get its first character?

level: juniorimportance: must knowfreq 75%

basics

~20 s

A String holds UTF-8 bytes and a character takes one to four of them, so str can be indexed only by byte ranges. name[0] fails with E0277; name.chars().next() gives the first char, name.as_bytes()[0] the first byte.

open as a page

In Rust, when should a value be a fixed `[f32; 3]` array rather than a `Vec<f32>`, and what does each one cost?

level: juniorimportance: must knowfreq 72%

basics

~20 s

A [f32; 3] stores exactly three floats inline, with the length fixed in its type and no allocation; a Vec<f32> is a pointer, capacity and length pointing at a heap buffer that can grow at run time.

open as a page

For a Rust order book in a BTreeMap<u64, u32>, how do you query a price band with range, and when does range panic?

level: middleimportance: must knowfreq 50%

basics

~20 s

Call range with any RangeBounds value (a..b, ..=b, a.., or a Bound tuple like (Excluded(a), Unbounded)) to iterate only those keys, in order, from either end. It panics when start exceeds end, or when equal bounds are both Excluded.

open as a page

Rust's std::collections::BinaryHeap always pops the largest element; how do you make a job scheduler pop the earliest deadline first?

level: middleimportance: must knowfreq 58%

basics

~10 s

Wrap each entry in std::cmp::Reverse, as in heap.push(Reverse((deadline, id))). Reverse flips Ord, so BinaryHeap's max-heap pops the smallest deadline first; an Ord impl that compares backwards also works.

open as a page

In a Rust word counter, what does `*counts.entry(word.to_string()).or_insert(0) += 1` do, and why prefer it to `contains_key` then `insert`?

level: middleimportance: must knowfreq 70%

basics

~20 s

entry hashes the key once and returns an Entry, Occupied or Vacant; or_insert(0) stores 0 only when vacant and returns &mut usize to the value either way, so the increment costs one lookup instead of two.

open as a page

A Rust signup form caps display names at 12 characters with `name.len() <= 12`; why does it reject "Zoë Šimićová", and what should it count?

level: middleimportance: must knowfreq 60%

basics

~10 s

str::len counts UTF-8 bytes, and that 12-character name is 16 bytes. name.chars().count() counts Unicode scalar values; for what a reader sees as letters, count grapheme clusters, which std does not provide.

open as a page

For a Rust `Vec<T>`, how do `len` and `capacity` differ, and when do `with_capacity`, `reserve` and `shrink_to_fit` pay off?

level: middleimportance: must knowfreq 66%

basics

~20 s

len counts the elements a Vec holds; capacity counts the slots its buffer has room for. A push reallocates, possibly moving the buffer, only when len equals capacity, and a Vec never shrinks on its own: shrink_to_fit or shrink_to returns the memory.

open as a page

In Rust, why does `s1 + &s2` move `s1`, why can two `&str` values not be added, and when is `format!` better?

level: juniorimportance: should knowfreq 55%

basics

~20 s

+ on strings calls Add<&str> for String, whose add takes self by value and appends with push_str, so s1 is moved. Two &str values have no owned buffer to append into, giving E0369. format! borrows all its arguments and builds a new String.

open as a page

In a Rust leaderboard stored as BTreeMap<u32, String> keyed by score, why do tied players vanish, and how do you read the top and bottom?

level: middleimportance: should knowfreq 42%

basics

~20 s

Each key holds one value, so inserting a second player with an equal score replaces the first. Store unique (score, player) tuples in a BTreeSet instead, then read last() for the top, first() for the bottom, and pop_first() to evict the lowest.

open as a page

In a Rust order book held as BTreeMap<u64, u32>, how do you remove empty or out-of-band price levels without hitting E0502?

level: middleimportance: should knowfreq 35%

basics

~20 s

Removing inside a for loop over &map fails with E0502. Use retain for a predicate over every entry, split_off to cut the map at a key, or extract_if, stable since Rust 1.91, to remove and collect matches inside one key range.

open as a page

Why is std::collections::LinkedList rarely the right choice in Rust, even for a queue that removes items from the middle?

level: middleimportance: should knowfreq 40%

basics

~20 s

LinkedList allocates a node per element and walks scattered memory, and std's docs say Vec or VecDeque is almost always better. On stable Rust its cursor and remove-at methods are unstable, so middle removal walks the list anyway.

open as a page

In Rust, why do two `HashMap<String, u32>` maps built from the same keys, in the same order, iterate in different orders?

level: middleimportance: should knowfreq 45%

basics

~20 s

Each HashMap gets its own RandomState: SipHash 1-3 keys taken from OS randomness once per thread and incremented for every new RandomState, so the same keys land in different buckets and iteration order usually differs between maps and runs.

open as a page

In Rust, how do `String::from_utf8`, `String::from_utf8_lossy` and `String::from_utf8_unchecked` differ when turning bytes read from a socket into text?

level: middleimportance: should knowfreq 45%

basics

~10 s

from_utf8 validates a Vec<u8> and returns Result<String, FromUtf8Error>. from_utf8_lossy replaces invalid sequences with U+FFFD and returns Cow<str>. The unsafe from_utf8_unchecked skips the check, and invalid bytes then break every later string operation's assumption.

open as a page

When compacting a Rust `Vec<T>` buffer in place, when do you reach for `drain`, `retain`, `dedup`, `extract_if` or `swap_remove`?

level: middleimportance: should knowfreq 48%

basics

~10 s

drain(range) removes a range and yields it; retain keeps what a predicate accepts; dedup removes consecutive duplicates; extract_if (Rust 1.87) removes and yields predicate matches; swap_remove removes one element in O(1) by breaking order.

open as a page

A Rust BTreeSet holds keys whose Ord reads a Cell, and one key is changed in place; why do lookups start missing, and is it undefined behaviour?

level: seniorimportance: should knowfreq 30%

basics

~20 s

The tree placed the key by its old ordering and never re-sorts, so searches for either value take the wrong path and miss. std calls this a logic error: results are unspecified (wrong answers, panics, leaks, non-termination) but never undefined behaviour.

open as a page

Why is Rust's std BTreeMap built as a B-tree with multi-key nodes rather than a binary search tree, and when does HashMap still beat it?

level: seniorimportance: should knowfreq 38%

basics

~20 s

A binary tree allocates one node per entry and risks a cache miss at every comparison. std's B-tree currently packs up to 11 keys per node in contiguous arrays and scans them linearly. HashMap still wins on large, lookup-only workloads with costly-to-compare keys.

open as a page

Why does calling `sort()` on a Rust VecDeque fail to compile, and what do `as_slices` and `make_contiguous` give you instead?

level: seniorimportance: should knowfreq 35%

basics

~20 s

A VecDeque's elements can wrap past the end of its buffer, so it cannot deref to one slice and has no sort method (E0599). as_slices returns the two halves; make_contiguous rearranges them in place into one &mut [T].

open as a page

How does Rust's BinaryHeap::peek_mut let you change the top element in place, and when is the heap invariant restored?

level: seniorimportance: should knowfreq 30%

basics

~20 s

peek_mut returns a PeekMut guard that derefs to the top element. If you write through it, the guard's Drop sifts that element down, so the heap is repaired once, when the guard goes out of scope.

open as a page

A Rust game loop profile shows SipHash dominating lookups in a `HashMap<u64, Entity>` keyed by engine-assigned IDs; how do you swap the hasher, and what changes?

level: seniorimportance: should knowfreq 38%

basics

~10 s

Set HashMap's third type parameter to a faster BuildHasher, such as rustc-hash's FxBuildHasher, and build maps with default() or with_hasher; HashMap::new stops applying, and functions taking HashMap<K, V> must become generic over S: BuildHasher.

open as a page

A Rust backup tool panics at `path.to_str().unwrap()` on a Latin-1 file name; why, and how should it carry paths using `OsString` and `PathBuf`?

level: seniorimportance: should knowfreq 35%

basics

~20 s

File names on Unix can be arbitrary non-zero bytes and on Windows arbitrary 16-bit units, while str must be UTF-8. Path::to_str returns None for such a name, so unwrap panics. Keep paths as &Path and PathBuf end to end, and convert only for display.

open as a page

A Rust service cuts display names to a 32-byte limit with `name.truncate(32)`; why does it panic on some names, and how do you cut safely?

level: seniorimportance: should knowfreq 40%

basics

~10 s

String::truncate takes a byte length and panics when it falls inside a multi-byte character, because a String must stay valid UTF-8. Cut at name.floor_char_boundary(32), stable since Rust 1.91, or step down with is_char_boundary.

open as a page

In Rust, when do you pick `sort` over `sort_unstable` for a `Vec<T>`, and why does `values.sort()` on a `Vec<f32>` fail with E0277?

level: seniorimportance: should knowfreq 42%

basics

~20 s

sort is stable and may allocate a scratch buffer; sort_unstable may reorder equal elements but sorts in place without allocating. Both need T: Ord, which f32 lacks because NaN breaks total order, so float vectors use sort_by(f32::total_cmp).

open as a page

As a Rust lead, what rule do you set for when code may replace HashMap's default SipHash hasher with a faster one?

level: principalimportance: should knowfreq 30%

basics

~20 s

Keep RandomState wherever an outsider can choose or influence keys, such as words from uploaded documents; allow a fast hasher only for internal keys, after a profile shows hashing matters, behind named types that clippy's disallowed_types enforces.

open as a page