Struct FrozenMap 

pub struct FrozenMap<K, V> { /* private fields */ }

A compact frozen (immutable) ordered map backed by a sorted boxed slice.

This is a read-only map that stores key-value pairs in a contiguous, sorted array. It provides efficient sorted iteration and binary search lookups, but cannot be modified after construction.

Construction

If you’re building a new map, and you don’t expect many overlapping keys, consider pushing entries into a Vec<(K, V)> and calling FrozenMap::from. It is typically cheaper to collect into a Vec and sort the entries once at the end than it is to maintain a temporary map data structure.

If you already have a map, need to perform lookups during construction, or you have many overlapping keys that you don’t want to temporarily hold onto, you can use the provided From trait implementations to create a FrozenMap from one of many common collections. You should prefer using a BTreeMap, as it matches the sorted iteration order of FrozenMap and avoids a sort operation during conversion.

If you don’t have an existing collection, you can use the FromIterator<(K, V)> trait implementation to .collect() tuples into a FrozenMap.

Finally, if you have a list of pre-sorted tuples with unique keys, you can use the advanced FrozenMap::from_unique_sorted_box or FrozenMap::from_unique_sorted_box_unchecked constructors, which provide the cheapest possible construction.

Overlapping keys encountered during construction preserve the last overlapping entry, matching similar behavior for other maps in the standard library.

Implementations

impl<K, V> FrozenMap<K, V>

pub fn new() -> Self

Creates an empty FrozenMap. Does not perform any heap allocations.

impl<K, V> FrozenMap<K, V>

where K: Ord,

pub fn from_unique_sorted_box(entries: Box<[(K, V)]>) -> Self

Creates a FrozenMap from a pre-sorted boxed slice with unique keys.

Panics if the keys in entries are not unique and sorted.

pub fn from_unique_sorted_box_unchecked(entries: Box<[(K, V)]>) -> Self

Creates a FrozenMap from a pre-sorted boxed slice with unique keys.

Correctness

The caller must ensure that:

• The entries are sorted by key in ascending order according to K: Ord
• There are no overlapping keys

If these invariants are not upheld, the map will behave incorrectly (e.g., FrozenMap::get may fail to find keys that are present), but no memory unsafety will occur.

When debug_assertions is enabled, this will panic if an invariant is not upheld.

impl<K, V> FrozenMap<K, V>

pub const fn len(&self) -> usize

Returns the number of elements in the map.

pub const fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub const fn as_slice(&self) -> &[(K, V)]

Returns a reference to the underlying sorted slice.

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns a reference to the value corresponding to the key.

pub fn get_key_value<Q>(&self, key: &Q) -> Option<(&K, &V)>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns the key-value pair corresponding to the supplied key.

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

Returns true if the map contains a value for the specified key.

pub fn first_key_value(&self) -> Option<(&K, &V)>

Returns the first key-value pair in the map.

pub fn last_key_value(&self) -> Option<(&K, &V)>

Returns the last key-value pair in the map.

pub fn iter(&self) -> Iter<'_, K, V>

Gets an iterator over the entries of the map, sorted by key.

pub fn keys(&self) -> Keys<'_, K, V>

Gets an iterator over the keys of the map, in sorted order.

pub fn values(&self) -> Values<'_, K, V>

Gets an iterator over the values of the map, in order by key.

pub fn into_keys(self) -> IntoKeys<K, V>

Creates a consuming iterator visiting all the keys, in sorted order.

pub fn into_values(self) -> IntoValues<K, V>

Creates a consuming iterator visiting all the values, in order by key.

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>

where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>,

Constructs a double-ended iterator over a sub-range of entries in the map.

pub fn extend(&self, entries: impl IntoIterator<Item = (K, V)>) -> Self

where K: Clone + Ord, V: Clone,

Extend this FrozenMap by constructing a new map with the additional entries. New entries with overlapping keys will overwrite existing ones.

Trait Implementations

impl<K, V> AsRef<[(K, V)]> for FrozenMap<K, V>

fn as_ref(&self) -> &[(K, V)]

Converts this type into a shared reference of the (usually inferred) input type.

impl<'__de, K, V, __Context> BorrowDecode<'__de, __Context> for FrozenMap<K, V>

where K: BorrowDecode<'__de, __Context> + '__de, V: BorrowDecode<'__de, __Context> + '__de,

fn borrow_decode<__D: BorrowDecoder<'__de, Context = __Context>>( decoder: &mut __D, ) -> Result<Self, DecodeError>

Attempt to decode this type with the given BorrowDecode.

impl<K: Clone, V: Clone> Clone for FrozenMap<K, V>

fn clone(&self) -> FrozenMap<K, V>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for FrozenMap<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K, V, __Context> Decode<__Context> for FrozenMap<K, V>

where K: Decode<__Context> + 'static, V: Decode<__Context> + 'static,

fn decode<__D: Decoder<Context = __Context>>( decoder: &mut __D, ) -> Result<Self, DecodeError>

Attempt to decode this type with the given Decode.

impl<K, V> Default for FrozenMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<'de, K, V> Deserialize<'de> for FrozenMap<K, V>

where K: Deserialize<'de>, V: Deserialize<'de>,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V> Encode for FrozenMap<K, V>

where K: Encode, V: Encode,

fn encode<__E: Encoder>(&self, encoder: &mut __E) -> Result<(), EncodeError>

Encode a given type.

impl<K, V> From<&[(K, V)]> for FrozenMap<K, V>

where K: Ord + Clone, V: Clone,

fn from(entries: &[(K, V)]) -> Self

Creates a FrozenMap from a slice of key-value pairs. Keys and values are cloned.

If there are overlapping keys, the last entry for each key is kept.

impl<K: Ord, V, const N: usize> From<[(K, V); N]> for FrozenMap<K, V>

fn from(entries: [(K, V); N]) -> Self

Creates a FrozenMap from an owned array of key-value pairs.

If there are overlapping keys, the last entry for each key is kept.

impl<K, V> From<BTreeMap<K, V>> for FrozenMap<K, V>

fn from(map: BTreeMap<K, V>) -> Self

Creates a FrozenMap from a BTreeMap.

This is more efficient than From<HashMap<K, V>> because BTreeMap already iterates in sorted order, so no re-sorting is needed.

impl<K: Ord, V> From<Box<[(K, V)]>> for FrozenMap<K, V>

fn from(entries: Box<[(K, V)]>) -> Self

Creates a FrozenMap from a boxed slice of key-value pairs.

If there are overlapping keys, the last entry for each key is kept.

impl<K, V> From<FrozenMap<K, V>> for Box<[(K, V)]>

fn from(map: FrozenMap<K, V>) -> Self

Converts to this type from the input type.

impl<K, V, S> From<HashMap<K, V, S>> for FrozenMap<K, V>

where K: Ord, S: BuildHasher,

fn from(map: HashMap<K, V, S>) -> Self

Creates a FrozenMap from a HashMap.

The entries are sorted by key during construction.

impl<K, V, S> From<IndexMap<K, V, S>> for FrozenMap<K, V>

where K: Ord, S: BuildHasher,

fn from(map: IndexMap<K, V, S>) -> Self

Creates a FrozenMap from an [IndexMap].

The entries are sorted by key during construction.

impl<K: Ord, V> From<Vec<(K, V)>> for FrozenMap<K, V>

fn from(entries: Vec<(K, V)>) -> Self

Creates a FrozenMap from a Vec of key-value pairs.

If there are overlapping keys, the last entry for each key is kept.

impl<K: Ord, V> FromIterator<(K, V)> for FrozenMap<K, V>

fn from_iter<T: IntoIterator<Item = (K, V)>>(entries: T) -> Self

Creates a FrozenMap from an iterator of key-value pairs.

If there are overlapping keys, the last entry for each key is kept.

impl<K: Hash, V: Hash> Hash for FrozenMap<K, V>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<K, Q, V> Index<&Q> for FrozenMap<K, V>

where K: Borrow<Q> + Ord, Q: Ord + ?Sized,

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &V

Performs the indexing (container[index]) operation.

impl<'a, K, V> IntoIterator for &'a FrozenMap<K, V>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V>

Creates an iterator from a value.

impl<K, V> IntoIterator for FrozenMap<K, V>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> IntoIter<K, V>

Creates an iterator from a value.

impl<K: Ord, V: Ord> Ord for FrozenMap<K, V>

fn cmp(&self, other: &FrozenMap<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

where Self: Sized,

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

where Self: Sized,

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Self

where Self: Sized,

Restrict a value to a certain interval.

impl<K: PartialEq, V: PartialEq> PartialEq for FrozenMap<K, V>

fn eq(&self, other: &FrozenMap<K, V>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: PartialOrd, V: PartialOrd> PartialOrd for FrozenMap<K, V>

fn partial_cmp(&self, other: &FrozenMap<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

Tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

Tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

Tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

Tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K, V> Serialize for FrozenMap<K, V>

where K: Serialize, V: Serialize,

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<K: Eq, V: Eq> Eq for FrozenMap<K, V>

impl<K, V> StructuralPartialEq for FrozenMap<K, V>