sortedvec
A pure rust library that exposes macros that generate data structures
on Ord
keys that enables quicker lookups than regular Vec
s (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!
}
let unsorted = vec!;
let sorted = from;
// linear search (slow!)
let unsorted_contains_six: = unsorted.iter.find;
assert!;
// binary search (fast!)
let sorted_contains_six: = sorted.find;
assert!;
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.
- Introduction of the
- 0.4.1: First public release.