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