|0.2.4||Apr 19, 2023|
|0.2.3||Apr 16, 2023|
|0.1.0||Mar 14, 2023|
#1645 in Data structures
29 downloads per month
This crate provides the
PrefixArraySet datastructures that implement some Map-like and Set-like interfaces, while also being capable of querying data based on what it starts with (its prefix).
prefix_array boasts zero memory overhead,
log n searching, and searching on subsets of the main array. This crate also has the advantage of cache locality over a tree type datastructure.
This crate is no_std capable, but has the
std feature enabled by default (currently this adds From impls for
This crate is licensed under MPL-2.0 (less common for rust crates), broadly this implies that you may use this crate in a closed source project, and statically link it, but any modifications to the crate itself must be made public. This is not legal advice.
prefix_array is a crate consisting of datastructures that aid in querying data based on prefixes of string keys,
the main feature being searching and refining on subgroups with common prefixes.
PrefixArray] when you want a HashMap-like structure, and [
PrefixArraySet] for a HashSet-like structure.
Creating a PrefixArray(Set)
For creating a new collection, ideally you can use the
FromIterator implementation, this has
O(n log n) complexity and with an
ExactSizeIterator will allocate once.
If you cannot use
FromIterator it is recommended to use
PrefixArray(Set)::from_vec_lossy instead, as this is what
FromIterator calls under the hood.
It is ill advised to use
insert in a loop to create a
PrefixArray(Set), as this has
For an already partially filled
PrefixArray(Set) that you wish to insert multiple items into, consider the
Extend implementation, which is specifically designed for this purpose.
use prefix_array::PrefixArray; // construct a new prefix array from an iterator let arr = PrefixArray::from_iter([("abcde", 123), ("absgh", 1234)]); // borrow a subslice of all data with the prefix 'ab' let mut subslice = arr.find_all_with_prefix("ab"); assert_eq!(subslice.len(), 2); // we can refine the subslice subslice = subslice.find_all_with_prefix("abc"); assert_eq!(subslice.len(), 1); // and find when something doesn't exist assert!(subslice.find_all_with_prefix("ba").is_empty());