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.
```rust 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 unsortedcontainssix: Option<_> = unsorted.iter().find(|&x| *x == 6); assert!(unsortedcontainssix.is_none());
// binary search (fast!) let sortedcontainssix: Option<_> = sorted.find(&6); assert!(sortedcontainssix.is_none()); ```
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 |