Why This Data Structure?
Frequent operations, the lookup you need, order, duplicates, size, churn — a recommendation with what every operation costs in it, why it won, and the answer that would make it lose.
"Use a map, it's O(1)" is the slogan. The falsifiable version: a map wins when the lookup by key is the frequent operation and the collection is large enough for a scan to be felt. A cart of four lines fails both halves, which is why the reference cart is an array. Answer the six questions and watch where the answer flips.
Start from a preset, or answer from scratch
Six questions
0 / 6 answered — the recommendation updates as you go.
Recommendation
Incomplete — the model names the unanswered question that matters most.
- • The simplest structure that keeps insertion order; every language has it and every reader understands it.
- • Appending and walking through are the cheapest operations, and at tens of elements the O(n) lookup is faster than a hash.
- • No answer yet distinguishes the candidates; the array wins by being the simplest.
flips when the lookup by key becomes frequent and the array grows past thousands — every find is now a scan the user waits for.
frequent, lookup, order, duplicates, size, mutation. Answering frequent ("Which operation happens most often?") would change the recommendation most.Map scores 0 against 0 — a tie broken toward the simpler structure: nothing you answered favours it. It wins when the lookup by key becomes frequent and the array grows past thousands — every find is now a scan the user waits for.
Set scores 0 against 0 — a tie broken toward the simpler structure: nothing you answered favours it. It wins when the lookup by key becomes frequent and the array grows past thousands — every find is now a scan the user waits for.
| operation | Array | Map | Set |
|---|---|---|---|
| append | O(1) amortised | O(1) | O(1) |
| lookup by key | O(n) scan | O(1) average | O(1) average membership |
| lookup by position | O(1) | O(n) walk | O(n) walk |
| lookup by predicate | O(n) scan | O(n) scan | O(n) scan |
| remove | O(n) shift | O(1) by key | O(1) |
| iterate in order | O(n), insertion order | O(n), insertion order | O(n), insertion order |
| min / max | O(n) scan | O(n) scan | O(n) scan |
| range query | O(n) scan | O(n) scan | O(n) scan |
8 canonical operations; the scorer reads the same table.
What if?
For each question, every other answer — and whether the primary would change.
Array cart against map cart
impl §59 — the same five operations, two representations; read off the cart concept's own records.
| axis | Array of CartItem | Map from product id to CartItem |
|---|---|---|
| Simplicity | The simplest thing that could work; every language has one. | "One entry per product" becomes structural: the key cannot repeat. |
| Lookup | O(n) scan | O(1) average |
| Ordering | O(n), order preserved | O(n); insertion order only where the language guarantees it |
| Serialisation | Serialises to JSON directly. | Serialising to JSON needs a conversion step in most languages. |
| Memory | one small record per entry, contiguous — nothing beside the data | the entries plus the hash table that indexes them — more per entry, and it only pays back when the lookup is felt |
the reference chose array A cart holds a handful of items and is shown in the order they were added; the O(n) scan is invisible at that size and the array serialises for free. The map is the right answer to a different question — see Why This Data Structure?
The scorer is a sum of small fit tables and a size penalty read off each structure's own complexity row — written down in `src/thinking/sim/structure.ts` so you can check it by hand. It ranks nine in-memory structures and rows; it does not know about tries, skip lists, LSM trees, or the cache line. Beyond memory it stops ranking and says "rows", because that is a different question.