[][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 as Vec<(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 Vec<T>, but made compact by cramming capacity and length into a single 64bit word.

Structs

Iter

An iterator over the entries of a Map.

IterMut

A mutable iterator over the entries of a Map.

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.