Recipe

Choose a collection

Use when: you're about to store more than a handful of values and need to decide which collection holds them

Goal: a collection whose fast operations are the ones your program does most

Taught in Choosing a collection

1. 1

   Write down the two or three operations that will run most often: add at the end, take from the front, look up by key, test membership, walk in order, take the largest.

   Example

   A help desk program holds support tickets. New tickets arrive all day, and staff always take the oldest one still waiting. The list: add a ticket at the end, take the oldest from the front, count how many are waiting.

   Why: a collection is fast at some operations and slow at others, so the choice follows from the operations, not the data.

2. 2

   If you look values up by a name or id, you need a map. If you only ask whether something is present, a set.

   Example

   The staff never look a ticket up by its number, and never ask "is ticket 42 in there?". So no map and no set. If they did look tickets up by number, a HashMap<u32, Ticket> would hold them.

   • lookup by key — HashMap, or BTreeMap if order or ranges matter.
   • "is it in there?" — HashSet, or BTreeSet if order matters.

   Why: maps and sets find by key in constant or logarithmic time, where a Vec would scan.

3. 3

   If values come and go at the ends, pick by which end.

   Example

   Tickets join at the back and leave from the front. That is one end in and the other end out, so the answer is VecDeque<Ticket>: push_back for a new ticket and pop_front for the oldest, both O(1). A Vec with remove(0) would shift every waiting ticket along by one, each time a ticket is served.

   • add and remove at the back only — Vec.
   • add at one end, remove from the other (or both ends) — VecDeque.
   • always remove the largest or smallest — BinaryHeap (with Reverse for smallest).

   Why: each of these makes its common end operations O(1) or O(log n); Vec::remove(0) would be O(n).

4. 4

   If nothing above applies, or the collection stays small, use a Vec.

   Example

   The same program keeps the names of the five staff on shift, and only loops over them to print the day's schedule. No key, no front end, no "largest". It's a Vec<String>.

   Why: its items are contiguous, so small Vecs are fast in practice, and it's the simplest to use.