Struct BoundedBTreeMap

pub struct BoundedBTreeMap<K, V, S>(/* private fields */);

Re-export this since it’s part of the API of this crate. A bounded map based on a B-Tree.

B-Trees represent a fundamental compromise between cache-efficiency and actually minimizing the amount of work performed in a search. See BTreeMap for more details.

Unlike a standard BTreeMap, there is an enforced upper limit to the number of items in the map. All internal operations ensure this bound is respected.

Implementations

impl<K, V, S> BoundedBTreeMap<K, V, S>

where S: Get<u32>,

pub fn bound() -> usize

Get the bound of the type in usize.

impl<K, V, S> BoundedBTreeMap<K, V, S>

where K: Ord, S: Get<u32>,

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &mut V) -> bool,

Exactly the same semantics as BTreeMap::retain.

The is a safe &mut self borrow because retain can only ever decrease the length of the inner map.

pub fn new() -> BoundedBTreeMap<K, V, S>

Create a new BoundedBTreeMap.

Does not allocate.

pub fn into_inner(self) -> BTreeMap<K, V>

Consume self, and return the inner BTreeMap.

This is useful when a mutating API of the inner type is desired, and closure-based mutation such as provided by try_mutate is inconvenient.

pub fn try_mutate( self, mutate: impl FnMut(&mut BTreeMap<K, V>), ) -> Option<BoundedBTreeMap<K, V, S>>

Consumes self and mutates self via the given mutate function.

If the outcome of mutation is within bounds, Some(Self) is returned. Else, None is returned.

This is essentially a consuming shorthand Self::into_inner -> ... -> Self::try_from.

pub fn clear(&mut self)

Clears the map, removing all elements.

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

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

Return a mutable reference to the value corresponding to the key.

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

pub fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)>

Exactly the same semantics as BTreeMap::insert, but returns an Err (and is a noop) if the new length of the map exceeds S.

In the Err case, returns the inserted pair so it can be further used without cloning.

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

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

Remove a key from the map, returning the value at the key if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

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

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

Remove a key from the map, returning the value at the key if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

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

See BTreeMap::iter_mut for more information.

pub fn map<T, F>(self, f: F) -> BoundedBTreeMap<K, T, S>

where F: FnMut((&K, V)) -> T,

Consume the map, applying f to each of it’s values and returning a new map.

pub fn try_map<T, E, F>(self, f: F) -> Result<BoundedBTreeMap<K, T, S>, E>

where F: FnMut((&K, V)) -> Result<T, E>,

Consume the map, applying f to each of it’s values as long as it returns successfully. If an Err(E) is ever encountered, the mapping is short circuited and the error is returned; otherwise, a new map is returned in the contained Ok value.

Methods from Deref<Target = BTreeMap<K, V>>

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.

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), None);

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

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

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

The supplied key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.get_key_value(&1), Some((&1, &"a")));
assert_eq!(map.get_key_value(&2), None);

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

where K: Ord,

Returns the first key-value pair in the map. The key in this pair is the minimum key in the map.

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
assert_eq!(map.first_key_value(), None);
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.first_key_value(), Some((&1, &"b")));

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

where K: Ord,

Returns the last key-value pair in the map. The key in this pair is the maximum key in the map.

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "b");
map.insert(2, "a");
assert_eq!(map.last_key_value(), Some((&2, &"a")));

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.

The key may be any borrowed form of the map’s key type, but the ordering on the borrowed form must match the ordering on the key type.

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(1, "a");
assert_eq!(map.contains_key(&1), true);
assert_eq!(map.contains_key(&2), false);

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 elements in the map. The simplest way is to use the range syntax min..max, thus range(min..max) will yield elements from min (inclusive) to max (exclusive). The range may also be entered as (Bound<T>, Bound<T>), so for example range((Excluded(4), Included(10))) will yield a left-exclusive, right-inclusive range from 4 to 10.

Panics

Panics if range start > end. Panics if range start == end and both bounds are Excluded.

Examples

use std::collections::BTreeMap;
use std::ops::Bound::Included;

let mut map = BTreeMap::new();
map.insert(3, "a");
map.insert(5, "b");
map.insert(8, "c");
for (&key, &value) in map.range((Included(&4), Included(&8))) {
    println!("{key}: {value}");
}
assert_eq!(Some((&5, &"b")), map.range(4..).next());

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

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

Examples

use std::collections::BTreeMap;

let mut map = BTreeMap::new();
map.insert(3, "c");
map.insert(2, "b");
map.insert(1, "a");

for (key, value) in map.iter() {
    println!("{key}: {value}");
}

let (first_key, first_value) = map.iter().next().unwrap();
assert_eq!((*first_key, *first_value), (1, "a"));

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

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

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(2, "b");
a.insert(1, "a");

let keys: Vec<_> = a.keys().cloned().collect();
assert_eq!(keys, [1, 2]);

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

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

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
a.insert(1, "hello");
a.insert(2, "goodbye");

let values: Vec<&str> = a.values().cloned().collect();
assert_eq!(values, ["hello", "goodbye"]);

pub fn len(&self) -> usize

Returns the number of elements in the map.

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert_eq!(a.len(), 0);
a.insert(1, "a");
assert_eq!(a.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

Examples

use std::collections::BTreeMap;

let mut a = BTreeMap::new();
assert!(a.is_empty());
a.insert(1, "a");
assert!(!a.is_empty());

pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>

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

🔬This is a nightly-only experimental API. (btree_cursors)

Returns a Cursor pointing at the gap before the smallest key greater than the given bound.

Passing Bound::Included(x) will return a cursor pointing to the gap before the smallest key greater than or equal to x.

Passing Bound::Excluded(x) will return a cursor pointing to the gap before the smallest key greater than x.

Passing Bound::Unbounded will return a cursor pointing to the gap before the smallest key in the map.

Examples

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let map = BTreeMap::from([
    (1, "a"),
    (2, "b"),
    (3, "c"),
    (4, "d"),
]);

let cursor = map.lower_bound(Bound::Included(&2));
assert_eq!(cursor.peek_prev(), Some((&1, &"a")));
assert_eq!(cursor.peek_next(), Some((&2, &"b")));

let cursor = map.lower_bound(Bound::Excluded(&2));
assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
assert_eq!(cursor.peek_next(), Some((&3, &"c")));

let cursor = map.lower_bound(Bound::Unbounded);
assert_eq!(cursor.peek_prev(), None);
assert_eq!(cursor.peek_next(), Some((&1, &"a")));

pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V>

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

🔬This is a nightly-only experimental API. (btree_cursors)

Returns a Cursor pointing at the gap after the greatest key smaller than the given bound.

Passing Bound::Included(x) will return a cursor pointing to the gap after the greatest key smaller than or equal to x.

Passing Bound::Excluded(x) will return a cursor pointing to the gap after the greatest key smaller than x.

Passing Bound::Unbounded will return a cursor pointing to the gap after the greatest key in the map.

Examples

#![feature(btree_cursors)]

use std::collections::BTreeMap;
use std::ops::Bound;

let map = BTreeMap::from([
    (1, "a"),
    (2, "b"),
    (3, "c"),
    (4, "d"),
]);

let cursor = map.upper_bound(Bound::Included(&3));
assert_eq!(cursor.peek_prev(), Some((&3, &"c")));
assert_eq!(cursor.peek_next(), Some((&4, &"d")));

let cursor = map.upper_bound(Bound::Excluded(&3));
assert_eq!(cursor.peek_prev(), Some((&2, &"b")));
assert_eq!(cursor.peek_next(), Some((&3, &"c")));

let cursor = map.upper_bound(Bound::Unbounded);
assert_eq!(cursor.peek_prev(), Some((&4, &"d")));
assert_eq!(cursor.peek_next(), None);

Trait Implementations

impl<K, V, S> AsRef<BTreeMap<K, V>> for BoundedBTreeMap<K, V, S>

where K: Ord,

fn as_ref(&self) -> &BTreeMap<K, V>

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

impl<K, V, S> Clone for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Clone,

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, S> Debug for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Debug, S: Get<u32>,

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

Formats the value using the given formatter.

impl<K, V, S> Decode for BoundedBTreeMap<K, V, S>

where K: Decode + Ord, V: Decode, S: Get<u32>,

fn decode<I>(input: &mut I) -> Result<BoundedBTreeMap<K, V, S>, Error>

where I: Input,

Attempt to deserialise the value from input.

fn skip<I>(input: &mut I) -> Result<(), Error>

where I: Input,

Attempt to skip the encoded value from input.

fn decode_into<I>( input: &mut I, dst: &mut MaybeUninit<Self>, ) -> Result<DecodeFinished, Error>

where I: Input,

Attempt to deserialize the value from input into a pre-allocated piece of memory.

fn encoded_fixed_size() -> Option<usize>

Returns the fixed encoded size of the type.

impl<K, V, S> DecodeLength for BoundedBTreeMap<K, V, S>

fn len(self_encoded: &[u8]) -> Result<usize, Error>

Return the number of elements in self_encoded.

impl<K, V, S> Default for BoundedBTreeMap<K, V, S>

where K: Ord, S: Get<u32>,

fn default() -> BoundedBTreeMap<K, V, S>

Returns the “default value” for a type.

impl<K, V, S> Deref for BoundedBTreeMap<K, V, S>

where K: Ord,

type Target = BTreeMap<K, V>

The resulting type after dereferencing.

fn deref(&self) -> &<BoundedBTreeMap<K, V, S> as Deref>::Target

Dereferences the value.

impl<'de, K, V, S> Deserialize<'de> for BoundedBTreeMap<K, V, S>

where S: Get<u32>, K: Deserialize<'de> + Ord, V: Deserialize<'de>,

fn deserialize<D>( deserializer: D, ) -> Result<BoundedBTreeMap<K, V, S>, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<K, V, S> Encode for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Encode, PhantomData<S>: Encode,

fn size_hint(&self) -> usize

If possible give a hint of expected size of the encoding.

fn encode_to<__CodecOutputEdqy>( &self, __codec_dest_edqy: &mut __CodecOutputEdqy, )

where __CodecOutputEdqy: Output + ?Sized,

Convert self to a slice and append it to the destination.

fn encode(&self) -> Vec<u8>

Convert self to an owned vector.

fn using_encoded<R, F>(&self, f: F) -> R

where F: FnOnce(&[u8]) -> R,

Convert self to a slice and then invoke the given closure with it.

fn encoded_size(&self) -> usize

Calculates the encoded size.

impl<K, V, S> From<BoundedBTreeMap<K, V, S>> for BTreeMap<K, V>

where K: Ord,

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

Converts to this type from the input type.

impl<K, V, S> Hash for BoundedBTreeMap<K, V, S>

where K: Hash, V: Hash,

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

where H: Hasher,

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<'a, K, V, S> IntoIterator for &'a BoundedBTreeMap<K, V, S>

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) -> <&'a BoundedBTreeMap<K, V, S> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<'a, K, V, S> IntoIterator for &'a mut BoundedBTreeMap<K, V, S>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter( self, ) -> <&'a mut BoundedBTreeMap<K, V, S> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<K, V, S> IntoIterator for BoundedBTreeMap<K, V, S>

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) -> <BoundedBTreeMap<K, V, S> as IntoIterator>::IntoIter

Creates an iterator from a value.

impl<K, V, S> MaxEncodedLen for BoundedBTreeMap<K, V, S>

where K: MaxEncodedLen, V: MaxEncodedLen, S: Get<u32>,

fn max_encoded_len() -> usize

Upper bound, in bytes, of the maximum encoded size of this item.

impl<K, V, S> Ord for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Ord, S: Get<u32>,

fn cmp(&self, other: &BoundedBTreeMap<K, V, S>) -> 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, V, S> PartialEq<BTreeMap<K, V>> for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: PartialEq,

fn eq(&self, other: &BTreeMap<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, V, S1, S2> PartialEq<BoundedBTreeMap<K, V, S1>> for BoundedBTreeMap<K, V, S2>

where BTreeMap<K, V>: PartialEq, S1: Get<u32>, S2: Get<u32>,

fn eq(&self, other: &BoundedBTreeMap<K, V, S1>) -> 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, V, S> PartialOrd for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: PartialOrd, S: Get<u32>,

fn partial_cmp(&self, other: &BoundedBTreeMap<K, V, S>) -> 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, S> Serialize for BoundedBTreeMap<K, V, S>

where K: Serialize, V: Serialize,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, V, S> TryFrom<BTreeMap<K, V>> for BoundedBTreeMap<K, V, S>

where K: Ord, S: Get<u32>,

type Error = ()

The type returned in the event of a conversion error.

fn try_from( value: BTreeMap<K, V>, ) -> Result<BoundedBTreeMap<K, V, S>, <BoundedBTreeMap<K, V, S> as TryFrom<BTreeMap<K, V>>>::Error>

Performs the conversion.

impl<K, V, S> TypeInfo for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: TypeInfo + 'static, PhantomData<S>: TypeInfo + 'static, K: TypeInfo + 'static, V: TypeInfo + 'static, S: 'static,

type Identity = BoundedBTreeMap<K, V, S>

The type identifying for which type info is provided.

fn type_info() -> Type

Returns the static type identifier for Self.

impl<K, V, S> EncodeLike<BTreeMap<K, V>> for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Encode,

impl<K, V, S> EncodeLike for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Encode, PhantomData<S>: Encode,

impl<K, V, S> Eq for BoundedBTreeMap<K, V, S>

where BTreeMap<K, V>: Eq, S: Get<u32>,