vec_collections/lib.rs
1//! This crate provides collections (sets and maps) that wrap [SmallVec].
2//!
3//! # Use cases
4//!
5//! ## Small collections
6//!
7//! It happens very frequently that you have collections that have on average just a very small number of elements. If you know
8//! the maximum size or even the maximum _typical_ size in advance, you can use this crate to store such collections without allocations.
9//! For a larger number of elements, the underlying [SmallVec] will allocate the elements on the heap as a single allocation.
10//!
11//! ## Read-heavy collections
12//!
13//! Another very frequent pattern is that you have a possibly large collection that is being created once and then used readonly for
14//! a long time. E.g. lookup tables. In these cases, ease of adding individual new elements is less important than compact in-memory
15//! representation and lookup performance. This crate provides succinct collections that have only a very small constant overhead over
16//! the contents of the collections.
17//!
18//! # Performance
19//!
20//! Performance for bulk creation as well as lookup is better than [BTreeMap]/[BTreeSet] and comparable with [HashMap]/[HashSet] for
21//! types with a cheap [Ord] instance, like primitive types, and small to medium sizes. Performance for insertion or removal of
22//! individual elements to/from large collections is bad, however. This is not the intended use case.
23//!
24//! # Collections overview
25//!
26//! ## [VecSet]
27//!
28//! Provides a set backed by a [SmallVec] of elements.
29//!
30//! ## [VecMap]
31//!
32//! Provides a map backed by a [SmallVec] of key value pairs.
33//!
34//! ## [RadixTree]
35//!
36//! A [RadixTree] that comes in different flavours.
37//!
38//! ## [TotalVecSet]
39//!
40//! A [VecSet] with an additional flag so it can support negation. This way it is possible to represent e.g. the set of all u64 except 1.
41//!
42//! ## [TotalVecMap]
43//!
44//! A [VecMap] with an additional default value, so lookup is a total function.
45//!
46//! # Unsafe
47//!
48//! The in place operations use unsafe code. If that is a problem for you, let me know and I can hide them behind a feature.
49//!
50//! [SmallVec]: https://docs.rs/smallvec/1.4.1/smallvec/struct.SmallVec.html
51//! [VecSet]: struct.VecSet.html
52//! [VecMap]: struct.VecMap.html
53//! [TotalVecSet]: struct.TotalVecSet
54//! [TotalVecMap]: struct.TotalVecMap
55//! [RadixTree]: radix_tree/struct.RadixTree.html
56//! [Ord]: https://doc.rust-lang.org/std/cmp/trait.Ord.html
57//! [BTreeSet]: https://doc.rust-lang.org/std/collections/struct.BTreeSet.html
58//! [BTreeMap]: https://doc.rust-lang.org/std/collections/struct.BTreeMap.html
59//! [HashSet]: https://doc.rust-lang.org/std/collections/struct.HashSet.html
60//! [HashMap]: https://doc.rust-lang.org/std/collections/struct.HashMap.html
61#[cfg_attr(docsrs, doc(cfg(feature = "rkyv_validated", feature = "radixtree")))]
62#[cfg(test)]
63extern crate quickcheck;
64
65#[cfg(test)]
66#[macro_use(quickcheck)]
67extern crate quickcheck_macros;
68
69#[cfg(test)]
70extern crate maplit;
71
72extern crate sorted_iter;
73pub use sorted_iter::{SortedIterator, SortedPairIterator};
74
75mod merge_state;
76
77mod vec_map;
78mod vec_set;
79
80#[cfg(feature = "radixtree")]
81pub mod radix_tree;
82
83#[cfg(feature = "total")]
84pub mod total_vec_map;
85
86#[cfg(feature = "total")]
87pub mod total_vec_set;
88
89#[cfg(feature = "std_support")]
90pub mod btree_map;
91
92mod dedup;
93mod iterators;
94
95mod macros;
96
97pub use dedup::{sort_dedup, sort_dedup_by_key};
98pub use macros::*;
99pub use smallvec::Array;
100pub use vec_map::*;
101pub use vec_set::*;