litemap/
lib.rs

1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5// https://github.com/unicode-org/icu4x/blob/main/documents/process/boilerplate.md#library-annotations
6#![cfg_attr(not(any(test, doc)), no_std)]
7#![cfg_attr(
8    not(test),
9    deny(
10        clippy::indexing_slicing,
11        clippy::unwrap_used,
12        clippy::expect_used,
13        clippy::panic,
14    )
15)]
16// #![warn(missing_docs)]
17
18//! # `litemap`
19//!
20//! `litemap` is a crate providing [`LiteMap`], a highly simplistic "flat" key-value map
21//! based off of a single sorted vector.
22//!
23//! The main goal of this crate is to provide a map that is good enough for small
24//! sizes, and does not carry the binary size impact of [`HashMap`](std::collections::HashMap)
25//! or [`BTreeMap`](alloc::collections::BTreeMap).
26//!
27//! If binary size is not a concern, [`std::collections::BTreeMap`] may be a better choice
28//! for your use case. It behaves very similarly to [`LiteMap`] for less than 12 elements,
29//! and upgrades itself gracefully for larger inputs.
30//!
31//! ## Performance characteristics
32//!
33//! [`LiteMap`] is a data structure with similar characteristics as [`std::collections::BTreeMap`] but
34//! with slightly different trade-offs as it's implemented on top of a flat storage (e.g. Vec).
35//!
36//! * [`LiteMap`] iteration is generally faster than `BTreeMap` because of the flat storage.
37//! * [`LiteMap`] can be pre-allocated whereas `BTreeMap` can't.
38//! * [`LiteMap`] has a smaller memory footprint than `BTreeMap` for small collections (< 20 items).
39//! * Lookup is `O(log(n))` like `BTreeMap`.
40//! * Insertion is generally `O(n)`, but optimized to `O(1)` if the new item sorts greater than the current items. In `BTreeMap` it's `O(log(n))`.
41//! * Deletion is `O(n)` whereas `BTreeMap` is `O(log(n))`.
42//! * Bulk operations like `from_iter`, `extend` and deserialization have an optimized `O(n)` path
43//!   for inputs that are ordered and `O(n*log(n))` complexity otherwise.
44//!
45//! ## Pluggable Backends
46//!
47//! By default, [`LiteMap`] is backed by a [`Vec`]; however, it can be backed by any appropriate
48//! random-access data store, giving that data store a map-like interface. See the [`store`]
49//! module for more details.
50//!
51//! ## Const construction
52//!
53//! [`LiteMap`] supports const construction from any store that is const-constructible, such as a
54//! static slice, via [`LiteMap::from_sorted_store_unchecked()`]. This also makes [`LiteMap`]
55//! suitable for use with [`databake`]. See [`impl Bake for LiteMap`] for more details.
56//!
57//! [`impl Bake for LiteMap`]: ./struct.LiteMap.html#impl-Bake-for-LiteMap<K,+V,+S>
58//! [`Vec`]: alloc::vec::Vec
59
60// for intra doc links
61#[cfg(doc)]
62extern crate std;
63
64#[cfg(feature = "alloc")]
65extern crate alloc;
66
67#[cfg(feature = "databake")]
68#[path = "databake.rs"] // to not conflict with `databake` as used in the docs
69mod databake_impls;
70mod map;
71#[cfg(feature = "serde")]
72mod serde;
73#[cfg(feature = "serde")]
74mod serde_helpers;
75pub mod store;
76
77#[cfg(any(test, feature = "testing"))]
78pub mod testing;
79
80pub use map::{Entry, LiteMap, OccupiedEntry, VacantEntry};
litemap/lib.rs

litemap/
lib.rs
