Choosing#
The operator’s cheat-sheet for picking the right container.
Need |
Lookup |
Insert |
Order |
Dup |
Pick |
|---|---|---|---|---|---|
Indexed access |
O(1) |
O(n) |
yes |
yes |
|
Immutable, hashable |
O(1) by index |
n/a |
yes |
yes |
|
Membership / unique |
O(1) avg |
O(1) avg |
no |
no |
|
Key-value |
O(1) avg |
O(1) avg |
insertion |
keys unique |
|
Auto-init values |
O(1) |
O(1) |
insertion |
keys unique |
|
Frequency / multiset |
O(1) |
O(1) |
insertion |
n/a |
|
Both-end queue |
n/a |
O(1) ends |
yes |
yes |
|
Priority extract |
n/a |
O(log n) |
by key |
yes |
|
Layered lookup |
O(n_chains) |
O(1) |
chain |
across |
|
Fixed record |
n/a |
n/a |
field |
n/a |
|
The general decision rule: start with list or dict;
switch to a specialised container when a profile shows the
specific operation (front-pop, top-N, frequency, etc.) is the
bottleneck.
References#
Data Structures for the catalogue.
Big-O for the underlying complexities.