# Collections

Source: https://codewiki.com/rust/collections/

> - **what**: Rust's standard collections model sequences, double-ended queues, unique values, and key-value mappings; choose by the ordering, uniqueness, and range semantics you need.
> - **trap**: `HashMap` and `HashSet` don't promise iteration order, indexing a `Vec` can panic, and collection mutations can conflict with existing borrows.
> - **fix**: Use `get` for untrusted indices, `entry` for map updates, and either a B-tree collection or explicit boundary sorting when output order must be stable.

## What it is and why it exists

A collection organizes values of the same type when their count may not be known until runtime.
An array includes its length in its type, and a tuple can hold unlike types; a standard collection is an owning container built for growth, removal, key lookup, or queuing.
It manages its elements and drops them when the container goes out of scope.

A collection type describes more than storage. It also describes semantics that callers can rely on.
`Vec` preserves sequence order and supports integer indexing, `HashSet` represents unique membership, and `HashMap<K, V>` maps keys to values.
If key order or range queries are part of the contract, use `BTreeSet` or `BTreeMap<K, V>`; a queue usually calls for `VecDeque`.

`String` also owns a growable buffer, but it maintains a UTF-8 invariant and isn't in the `std::collections` module.
Text indexing and slicing deserve separate treatment; see the related `rust/strings` topic.
`BinaryHeap` retrieves elements by priority. This page includes it in the selection table but doesn't teach heap operations.

You'll meet collections while parsing input, looking up records by ID, removing duplicates, scheduling work, and assembling responses.
State the required semantics first, then choose the type. Picking `HashMap` merely because it looks general-purpose often hides an ordering requirement until output is produced.

| Need | First choice | Guarantee expressed by the type |
|---|---|---|
| Ordered sequence | `Vec` | Elements have sequence order and support indexing and slices |
| Insertion and removal at both ends | `VecDeque` | The sequence has a logical front and back |
| Unique membership | `HashSet` | Each equal value appears at most once |
| Values addressed by key | `HashMap<K, V>` | Each equal key maps to at most one value |
| Ordered keys or key ranges | `BTreeMap<K, V>` / `BTreeSet` | Iteration follows `Ord` and ranges are supported |
| Repeated access to highest priority | `BinaryHeap` | The current greatest element is at the top |

## How it works

`Vec` owns a contiguous element buffer and tracks its length separately from its capacity.
Length is the number of initialized elements. Capacity is how many elements the current allocation can hold before it must be replaced.
`push` increases the length; when there isn't room, the vector may allocate a larger buffer and move its elements.

Maps and sets are organized around key equality.
`HashMap` and `HashSet` use a hash table. Their keys implement `Eq` and `Hash`, and equal keys must produce equal hashes.
`BTreeMap` and `BTreeSet` arrange ordered keys in a B-tree, so their keys implement `Ord`.

Hash collections don't provide stable iteration order.
The same input need not produce the same order in another run, in another collection instance, or after a mutation.
B-tree collections iterate in the key's `Ord` order, which fits range queries and reproducible key sequences.

A collection owns the values inserted into it.
Inserting a `String` into `Vec` moves that string unless you insert a clone; calling `iter()` borrows elements, while `into_iter()` consumes the container and yields owned elements.
The precise item type also depends on whether the receiver is `T`, `&T`, or `&mut T`.

When an iterator builds a collection, `collect()` needs to know the target type.
Sometimes the left side of the assignment supplies it; sometimes you write `collect::<HashSet<_>>()`.
That type decides whether duplicates survive, how key-value pairs are organized, and whether result order is preserved.

`HashMap::entry` represents "present" and "absent" through one Entry API call.
`or_insert`, `or_default`, and `and_modify` operate on that state and return or modify the value inside the map.
Counting and grouping therefore don't need a `contains_key` call followed by a second lookup.

## Examples

### A data pipeline with `Vec`

The first example discards invalid readings, then converts Celsius values to tenths of a degree Fahrenheit.
`into_iter()` consumes the source vector, and the `Vec<i32>` annotation sets the target type for `collect()`.

<!-- quick -->

```rust
// file: normalize_readings.rs
fn main() {
    let readings = vec![20, -99, 24, 18];

    let normalized: Vec<i32> = readings
        .into_iter()
        .filter(|value| *value >= 0)
        .map(|celsius| celsius * 18 + 320)
        .collect();

    println!("tenths Fahrenheit: {normalized:?}");

    let second = normalized.get(1).copied();
    println!("second: {second:?}");
}
```

```text
tenths Fahrenheit: [680, 752, 644]
second: Some(752)
```

<!-- /quick -->

The `filter` closure receives a reference to each candidate, hence the dereference of `value` in its condition.
`map` then takes each accepted `i32`. The result keeps the relative order of valid readings from the input.

`get(1)` returns `Option<&i32>` instead of panicking on an invalid index.
Because this element implements `Copy`, `copied()` turns the result into `Option<i32>`; for a non-`Copy` type such as `String`, keep the borrow or clone deliberately.

### Counting with `HashMap::entry`

The event names are borrowed `&str` keys because every one comes from a static program string.
Each `entry` call describes the key once and returns a mutable reference to its counter.

```rust
// file: count_events.rs
use std::collections::HashMap;

fn main() {
    let events = ["view", "click", "view", "view", "click"];
    let mut counts: HashMap<&str, usize> = HashMap::new();

    for event in events {
        *counts.entry(event).or_insert(0) += 1;
    }

    // HashMap does not promise order; sort explicitly before output.
    let mut summary: Vec<_> = counts.into_iter().collect();
    summary.sort_by_key(|(event, _)| *event);

    for (event, count) in summary {
        println!("{event}: {count}");
    }
}
```

```text
click: 2
view: 3
```

`or_insert(0)` inserts `0` when the key is absent, then returns `&mut usize` in either state.
After the reference is dereferenced, `+= 1` updates the value in the map rather than a temporary copy.

Sorting happens at the output boundary instead of pretending that `HashMap` has an order.
If key order is a program-wide requirement, the `BTreeMap` in the next example usually states that contract more directly.

### Querying a `BTreeMap` range

`BTreeMap` iterators follow key order, and `range` accepts Rust range bounds.
The example reads jobs numbered `20` through `30`, then shows the old value returned by `insert` when a value is replaced.

```rust
// file: job_ranges.rs
use std::collections::BTreeMap;

fn main() {
    let mut jobs = BTreeMap::from([
        (30, "running"),
        (10, "done"),
        (20, "queued"),
        (40, "blocked"),
    ]);

    for (id, state) in jobs.range(20..=30) {
        println!("job {id}: {state}");
    }

    let previous = jobs.insert(20, "running");
    println!("replaced: {previous:?}");
}
```

```text
job 20: queued
job 30: running
replaced: Some("queued")
```

The output order comes from the key's `Ord` implementation, not insertion order.
Both `20` and `30` appear because the range includes its start and end.

`insert` moves the new value and returns `Option`.
The caller can distinguish an initial insert from a replacement; ignoring the result says that the business logic doesn't need the displaced value.

### Expressing a queue with `VecDeque`

A queue receives tasks at the back and takes them from the front.
`VecDeque` exposes both directions directly, so you don't have to remove the first element of a `Vec` repeatedly.

```rust
// file: task_queue.rs
use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::from(["parse", "index", "publish"]);

    if let Some(task) = queue.pop_front() {
        println!("running: {task}");
    }

    queue.push_back("notify");

    while let Some(task) = queue.pop_front() {
        println!("next: {task}");
    }

    println!("empty: {}", queue.is_empty());
}
```

```text
running: parse
next: index
next: publish
next: notify
empty: true
```

`pop_front()` returns `Option` and moves the element out of the queue.
`while let` finishes naturally once the queue is empty, without a separate length check before each pop.

The queue's logical order doesn't mean its storage is always one contiguous slice.
When an API requires contiguous elements, use `make_contiguous()` instead of depending on internal layout.

## Pitfalls

> **Pitfall:** Using `values[index]` with an index derived from external input panics when the index is out of bounds.
> Even if inputs are usually valid, one damaged record can turn a recoverable data error into a process-level failure.

**Fix:** Use `get` or `get_mut`, then return a domain error or skip the record in the `None` branch.
Use direct indexing only when a program invariant has proved the index valid and violating that invariant should stop the current execution.

> **Pitfall:** Tests or serializers iterate a `HashMap` or `HashSet`, then commit the observed order to an assertion or external format.
> That order isn't part of the type's contract, even when consecutive local runs happen to agree.

**Fix:** Use a B-tree collection if order pervades the business logic; if only the boundary needs stable output, collect and sort by an explicit key.
When testing the map itself, compare its key-value relationships instead of its incidental debug string.

> **Pitfall:** To silence a borrow error, generated code often applies `.clone()` to every key and element before lookup.
> This can conceal an ownership design problem and imply that looking up a `HashMap<String, V>` requires allocating another `String`.

**Fix:** Use `iter()` for read-only traversal and `into_iter()` only when consuming the container; string-keyed maps can usually be queried with `&str`.
Clone when a new container truly needs to own independent data, and make that ownership boundary visible in the type signature.

> **Pitfall:** Calling `contains_key` before `get_mut` or `insert` splits one "present or insert" decision into two steps that may drift apart.
> As the function grows, an early return or another mutation of the same map can slip between those steps.

**Fix:** Use `entry(key)` and update through its `Occupied` or `Vacant` state.
Simple counters can use `or_insert`, grouping containers often use `or_default`, and existing values can be handled with `and_modify`.

> **Pitfall:** `or_insert(build_value())` evaluates its argument before `or_insert` runs, so `build_value()` executes even when the key is already present.
> If that constructor logs, performs I/O, or has another side effect, the mistake changes behavior as well as doing needless work.

**Fix:** Use `or_insert_with(build_value)` for lazy construction, or `or_default()` when the desired value is `Default::default()`.
During review, distinguish an already computed argument from a closure that runs only for a missing key.

<!-- deep -->

## Allocation and reference invalidation

An empty `Vec` needn't allocate for elements, while `Vec::with_capacity(n)` requests room for at least `n` elements.
Capacity may be greater than requested, and the growth policy isn't an interface guarantee for callers.
Don't make business logic depend on a capacity sequence observed in one run.

When `len() < capacity()`, another `push` doesn't need a capacity-driven reallocation.
The borrow checker must nevertheless prove that the program is safe in every allowed execution; a test in which storage happened not to move cannot justify using an element reference across a `push`.
End the old borrow before mutation and borrow the element again afterward.

Reallocation isn't the only identity problem.
`Vec::insert`, `remove`, and `swap_remove` change some element indices. Saving an index avoids a dangling reference but doesn't prove that the index still denotes the same domain entity.
When identity comes from a record ID, retain the ID and look it up again instead of treating a position as permanent identity.

`reserve` guarantees room for additional elements in advance. `reserve_exact` merely asks the vector not to reserve deliberately more than requested; it doesn't promise an exact byte count from the allocator.
Derive reservations from a known input bound or format length, not an unvalidated external count that can trigger a huge allocation.

## Key contracts

`HashMap` requires `k1 == k2` to imply `hash(k1) == hash(k2)`.
If a custom key's `Eq` and `Hash` implementations inspect different fields, equal keys can follow inconsistent hash paths. That is a logic error.
Usually, derive `PartialEq`, `Eq`, and `Hash` together, or review hand-written implementations field by field.

`BTreeMap` relies on `Ord` for a total order.
If `cmp` considers two keys equal, `Eq` should do the same; changing hash-relevant or order-relevant contents after insertion also breaks collection logic.
Safe Rust blocks the common direct mutation paths, but interior mutability can still create such errors.

Owned string keys don't require an owned string for every query.
The standard maps support borrowed lookup: a `HashMap<String, V>` can usually be queried with `&str`, and a `BTreeMap<String, V>` also accepts a compatible borrowed key.
Storage remains owned while the read interface stays lightweight.

### Don't discard mutation results

Many collection mutation methods return information that matters to the domain.
`HashSet::insert` returns whether the value was absent, `HashMap::insert` returns the replaced `Option`, and `remove` returns the value moved out.

Those results distinguish an addition, a duplicate, and a replacement without a preliminary lookup.
A caller can deliberately ignore the result, but generated code deserves a check that the discarded information isn't part of a business rule.

Using the returned value also keeps a state transition near one method call.
Compared with "check, then mutate," it makes the duplicate-input, missing-key, and replacement paths easier to see.

## Ordered and unordered boundaries

"Unordered" doesn't mean randomly shuffled, nor does it mean the order must change on every run.
It means the API makes no observational-order promise, so callers cannot assign business meaning to the first or last item they happen to see.
This distinction matters in tests: incidental stability is still not a guarantee.

`BTreeMap::range` returns entries within bounds interpreted in key order.
Half-open, inclusive, and unbounded endpoints use standard range syntax or `Bound`; some internally invalid bound combinations panic, so validate ordering when bounds are built dynamically.

When only the presentation layer needs a stable order, collecting hash-map entries into a `Vec` and sorting there keeps the internal model free of unnecessary ordering semantics.
Conversely, if callers repeatedly ask for key ranges or the smallest key, `BTreeMap` states those operations directly.
Choose from the contract, not from speed claims made without benchmark data.

## `Entry` is one state branch

`entry(key)` mutably borrows the map and returns either `Occupied` or `Vacant`.
An occupied entry can expose, modify, or remove its value; a vacant entry can insert one. Both states retain the context needed to complete that operation.
That is why `entry` can finish an update within one state branch.

`and_modify(f).or_insert(v)` runs `f` when the key exists and inserts `v` otherwise.
But `v` is still an ordinary argument evaluated before the call; use `or_insert_with` for lazy initialization.
When construction needs a reference to the entry's own key, use the corresponding lazy method that provides it.

`Entry` only handles a state branch while one ordinary map is borrowed. It doesn't make cross-thread updates atomic.
A shared mutable map still needs a mutex, a sharded concurrent container, or another synchronization design; the outer mechanism defines the atomic check-and-update boundary.

## `VecDeque`'s logical continuity

`VecDeque` presents one logical sequence, but its ring buffer may occupy two physical memory regions.
`as_slices()` therefore returns two slices whose logical concatenation contains the complete queue.
Code must not assume that the second slice is always empty.

`make_contiguous()` rearranges the current contents so they can be accessed as one mutable slice.
Use it when you actually need a slice API, in-place sorting, or a contiguous region; ordinary queue code can stay with `push_back` and `pop_front`.

## `collect` gets its semantics from the target

An iterator says how to produce items one at a time; it doesn't choose the final container.
Collecting the same items into `Vec` keeps every item and their production order, collecting into `HashSet` merges equal items without promising iteration order, and collecting into `BTreeSet` merges equal items and orders them by `Ord`.

When later use doesn't determine a unique container, the compiler asks for more type information.
You can annotate the variable with a complete type or use `collect::<Vec<_>>()`; the underscore delegates element inference but doesn't omit the container choice.

This is an easy semantic change to miss in generated patches.
Replacing `collect::<Vec<_>>()` with `collect::<HashSet<_>>()` changes the storage, duplicate handling, and ordering contract together.

<!-- /deep -->

[Checkpoint: rust/collections](https://codewiki.com/rust/collections/#checkpoint)

## Further reading

- [Rust standard library: collections](https://doc.rust-lang.org/1.98.0/std/collections/index.html)
- [Rust standard library: `Vec`](https://doc.rust-lang.org/1.98.0/std/vec/struct.Vec.html)
- [Rust standard library: `Entry`](https://doc.rust-lang.org/1.98.0/std/collections/hash_map/enum.Entry.html)
- [Rust standard library: `BTreeMap`](https://doc.rust-lang.org/1.98.0/std/collections/struct.BTreeMap.html)
- [Rust standard library: `VecDeque`](https://doc.rust-lang.org/1.98.0/std/collections/struct.VecDeque.html)