[−][src]Crate ordnung
Ordnung
Fast, vector-based map implementation that preserves insertion order.
- Map is implemented as a binary tree over a
Vec
for 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 asVec<(K, V)>
. - There are no buckets, so there is no need to re-bucket things when growing the map.
When should you use this?
- 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.
Re-exports
pub use compact::Vec; |
Modules
compact | This is meant to be API compatible drop in replacement for std |
Structs
Iter | An iterator over the entries of a |
IterMut | A mutable iterator over the entries of a |
Map | A binary tree implementation of a string -> |