sortedvec

Documentation

A pure rust library that exposes macros that generate data structures on Ord keys that enables quicker lookups than regular Vecs (O(log(n)) vs O(n)) and is simpler and more memory efficient than hashmaps. It is ideal for small lookup tables where insertions and deletions are infrequent.

Note: sortedvec is still experimental and its interface may change.

Example

use sortedvec::sortedvec;

sortedvec! {
    struct SortedVec {
        fn derive_key(x: &u32) -> u32 { *x }
    }
}

let unsorted = vec![3, 5, 0, 10, 7, 1];
let sorted = SortedVec::from(unsorted.clone());

// linear search (slow!)
let unsorted_contains_six: Option<_> = unsorted.iter().find(|&x| *x == 6);
assert!(unsorted_contains_six.is_none());

// binary search (fast!)
let sorted_contains_six: Option<_> = sorted.find(&6);
assert!(sorted_contains_six.is_none());

Benchmarks

The table below displays how lookups scale on the standard library's HashMap, SortedVec and Vec for string and integer keys.

Change log

• 0.5.0:
  • Introduction of the sortedvec_slicekey! macro.
  • Introduction of the position method.
  • Resolved key derivation function naming collisions by associating them to the data structure. This fixes the key derivation names to derive_key. This is a breaking change.
• 0.4.1: First public release.