#lookup #table #datastructure #vec #sortedvec

sortedvec

a sorted vector that enables quick lookups

8 releases (4 breaking)

0.5.0 Sep 25, 2020
0.4.1 Jan 23, 2019
0.3.2 Jan 22, 2019
0.2.0 Jan 19, 2019
0.1.0 Jan 17, 2019

#4 in #datastructure

Download history 119/week @ 2021-08-12 74/week @ 2021-08-19 78/week @ 2021-08-26 134/week @ 2021-09-02 183/week @ 2021-09-09 323/week @ 2021-09-16 328/week @ 2021-09-23 346/week @ 2021-09-30 320/week @ 2021-10-07 293/week @ 2021-10-14 321/week @ 2021-10-21 315/week @ 2021-10-28 112/week @ 2021-11-04 15/week @ 2021-11-11 5/week @ 2021-11-18 29/week @ 2021-11-25

233 downloads per month

Apache-2.0

25KB
384 lines

sortedvec

Build Status Docs Crates.io

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.

key type size HashMap SortedVec Vec
int 2 17 2 2
int 6 17 3 2
int 10 18 4 3
int 50 19 5 15
int 100 23 6 28
int 500 18 8 127
int 1000 17 8 231
string 2 25 10 5
string 6 25 20 12
string 10 27 25 21
string 50 30 36 113
string 100 27 42 232
string 500 26 53 1,207
string 1000 26 59 2,324

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.

No runtime deps