2 unstable releases

0.2.0 May 7, 2024
0.1.0 Jun 11, 2020

#334 in Data structures

Download history 6610/week @ 2024-02-25 6260/week @ 2024-03-03 7595/week @ 2024-03-10 8252/week @ 2024-03-17 8069/week @ 2024-03-24 6808/week @ 2024-03-31 5736/week @ 2024-04-07 8168/week @ 2024-04-14 5204/week @ 2024-04-21 5661/week @ 2024-04-28 5103/week @ 2024-05-05 6817/week @ 2024-05-12 4657/week @ 2024-05-19 4713/week @ 2024-05-26 6978/week @ 2024-06-02 6613/week @ 2024-06-09

23,266 downloads per month
Used in 13 crates (5 directly)

MIT/Apache

75KB
2K SLoC

sorted_vector_map

sorted_vector_map is an implementation of an ordered map and set (like std::collections::BTreeMap and std::collections::BTreeSet) using a sorted vector as the backing store.

Sorted vector maps are appropriate when data is frequently loaded from an ordered source, queried a small number of times, and infrequently modified through insertion or removal.

Loading from an ordered sequence is O(n) through an optimization to insert that handles in-order insertions specially. Extension of the sequence is also optimized, where extending a map or set of size n with m elements in a single operation is O(n + m log m). Otherwise, loading from an unordered sequence is O(n^2).

Look-up is O(log n) through binary search. Insertion and removal are both O(n), as are set operations like intersection, union and difference.

sorted_vector_map is part of rust-shed. See the rust-shed repository for more documentation, including the contributing guide.

License

sorted_vector_map is both MIT and Apache License, Version 2.0 licensed, as found in the LICENSE-MIT and LICENSE-APACHE files.

Dependencies

~1MB
~19K SLoC