#lookup #table #datastructure #vec #sortedvec

sortedvec

a sorted vector that enables quick lookups

7 unstable releases (3 breaking)

✓ Uses Rust 2018 edition

0.4.1 Jan 23, 2019
0.4.0 Jan 23, 2019
0.3.2 Jan 22, 2019
0.2.0 Jan 19, 2019
0.1.0 Jan 17, 2019

#259 in Data structures

Download history 8/week @ 2019-04-07 1/week @ 2019-04-14 8/week @ 2019-04-21 8/week @ 2019-04-28 9/week @ 2019-05-05 10/week @ 2019-05-12 24/week @ 2019-05-19 49/week @ 2019-05-26 7/week @ 2019-06-02 7/week @ 2019-06-09 10/week @ 2019-06-16 79/week @ 2019-06-23 28/week @ 2019-06-30 22/week @ 2019-07-07

54 downloads per month

Apache-2.0

12KB
186 lines

sortedvec

A pure rust library that exposes a single macro, [sortedvec]. It generates a lookup table on Ord keys that has quicker lookups than regular Vecs, O(log(n)) vs O(n), and is simpler and more memory efficient than hashmaps. It is ideal for (very) small lookup tables where insertions and deletions are infrequent.

Note: sortedvec is still highly experimental and likely to change significantly.

Example

use sortedvec::sortedvec;

sortedvec! {
    struct SortedVec {
        fn key_deriv(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

No runtime deps