Fast, vector-based map implementation that preserves insertion order.
- Map is implemented as a binary tree over a
Vecfor storage, with only two extra words per entry for book-keeping on 64-bit architectures.
- A fast hash function with good random distribution is used to balance the
tree. Ordnung makes no guarantees that the tree will be perfectly
balanced, but key lookup should be approaching
O(log n)in most cases.
- Tree traversal is always breadth-first and happens over a single continuous block of memory, which makes it cache friendly.
- Iterating over all entries is always
O(n), same as
- There are no buckets, so there is no need to re-bucket things when growing the map.
- You need to preserve insertion order of the map.
- Iterating over the map is very performance sensitive.
- Your average map has fewer than 100 entries.
- You have no a priori knowledge about the final size of the map when you start creating it.
- Removing items from the map is very, very rare.
This is meant to be API compatible drop in replacement for std
An iterator over the entries of a
A mutable iterator over the entries of a
A binary tree implementation of a string ->