Crate ordnung

Ordnung

Ordnung is a simple, Vec-based, insertion order preserving map implementation.

• Mapping 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 as Vec<(K, V)>.
• Growing the map is just one reallocation.

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.

Structs

Iter
IterMut
Map	A binary tree implementation of a string -> JsonValue map. You normally don't have to interact with instances of Object, much more likely you will be using the JsonValue::Object variant, which wraps around this struct.
Vec