Struct CompressedBTreeMap 

pub struct CompressedBTreeMap<K: PartialOrd + Debug, V, B: ArrayLength = U6, A: Allocator = Global>
where
    U2: Mul<B>,
    Prod<U2, B>: ArrayLength,
    U1: Add<Prod<U2, B>>,
    Sum<U1, Prod<U2, B>>: ArrayLength,
{ /* private fields */ }

An ergonomic compressed B-Tree map that owns its allocator.

This is a memory-optimized B-Tree that uses specialized leaf nodes without child pointers, reducing memory usage by approximately 30% compared to the naive implementation.

This is the recommended type for most use cases. It wraps the allocated B-Tree and provides safe methods without requiring unsafe blocks or passing allocators manually.

Example

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert(1, "one").unwrap();
map.insert(2, "two").unwrap();

assert_eq!(map.get(&1), Some(&"one"));
assert_eq!(map.len(), 2);

Implementations

impl<K: PartialOrd + Debug, V> CompressedBTreeMap<K, V>

pub fn new() -> Self

Create a new empty compressed B-Tree using the global allocator.

Panics

Panics if allocation fails.

impl<K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator> CompressedBTreeMap<K, V, B, A>

where U2: Mul<B>, Prod<U2, B>: ArrayLength, U1: Add<Prod<U2, B>>, Sum<U1, Prod<U2, B>>: ArrayLength,

pub fn new_in(alloc: A) -> AllocResult<Self>

Create a new empty compressed B-Tree using the provided allocator.

Errors

Returns an error if allocation fails.

pub fn len(&self) -> usize

Returns the number of elements in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

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

where K: Borrow<Q>, Q: PartialOrd + Debug,

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

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

where K: Borrow<Q>, Q: PartialOrd + Debug,

Returns a reference to the value corresponding to the key.

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

where K: Borrow<Q>, Q: PartialOrd + Debug,

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

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

where K: Borrow<Q>, Q: PartialOrd + Debug,

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

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

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned. If the map did have this key present, the value is updated, and the old value is returned.

Errors

Returns an error if allocation fails during tree rebalancing.

pub fn clear(&mut self) -> AllocResult<()>

Clears the map, removing all key-value pairs.

Errors

Returns an error if allocation fails.

pub fn entry(&mut self, key: K) -> Entry<'_, '_, A, K, V, B>

Gets the given key’s corresponding entry in the map for in-place manipulation.

pub fn entry_ref<Q>( &mut self, key: &Q, ) -> Option<OccupiedEntry<'_, '_, A, K, V, B>>

where K: Borrow<Q>, Q: PartialOrd + Debug + ?Sized,

Gets the given key’s corresponding occupied entry in the map for in-place manipulation.

Returns None if the key is not present 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.

Examples

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert(1, "a").unwrap();

// Get the entry if it exists and modify it
if let Some(mut entry) = map.entry_ref(&1) {
    *entry.get_mut() = "b";
}
assert_eq!(map.get(&1), Some(&"b"));

// Non-existent key returns None
assert!(map.entry_ref(&2).is_none());

Using String keys with &str lookups:

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert("hello".to_string(), 42).unwrap();

if let Some(entry) = map.entry_ref("hello") {
    assert_eq!(entry.key(), &"hello".to_string());
}

pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, '_, A, K, V, B>>

Gets the first entry in the map for in-place manipulation.

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

Returns the first key-value pair in the map.

pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, '_, A, K, V, B>>

Gets the last entry in the map for in-place manipulation.

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

Returns the last key-value pair in the map.

pub fn first(&self) -> Option<&K>

Returns the first key in the map.

pub fn last(&self) -> Option<&K>

Returns the last key in the map.

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

Removes and returns the first key-value pair in the map. The key in this pair is the minimum key that was in the map.

Examples

use allocated_btree::CompressedBTreeMap;

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

assert_eq!(map.pop_first(), Some((1, "a")));
assert_eq!(map.pop_first(), Some((2, "b")));
assert_eq!(map.pop_first(), None);

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

Removes and returns the last key-value pair in the map. The key in this pair is the maximum key that was in the map.

Examples

use allocated_btree::CompressedBTreeMap;

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

assert_eq!(map.pop_last(), Some((2, "b")));
assert_eq!(map.pop_last(), Some((1, "a")));
assert_eq!(map.pop_last(), None);

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

where K: Borrow<Q>, Q: PartialOrd + Debug + ?Sized,

Removes 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.

Examples

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert(1, "a").unwrap();
assert_eq!(map.remove(&1), Some("a"));
assert_eq!(map.remove(&1), None);

Using String keys with &str lookups:

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert("hello".to_string(), 42).unwrap();
assert_eq!(map.remove("hello"), Some(42));  // Note: &str, not &String
assert_eq!(map.remove("hello"), None);

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

where K: Borrow<Q>, Q: PartialOrd + Debug + ?Sized,

Removes a key from the map, returning the stored key and value 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.

Examples

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert(1, "a").unwrap();
assert_eq!(map.remove_entry(&1), Some((1, "a")));
assert_eq!(map.remove_entry(&1), None);

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

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

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

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

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

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

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V, B>

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

Trait Implementations

impl<K: PartialOrd + Debug, V> Default for CompressedBTreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator> Drop for CompressedBTreeMap<K, V, B, A>

where U2: Mul<B>, Prod<U2, B>: ArrayLength, U1: Add<Prod<U2, B>>, Sum<U1, Prod<U2, B>>: ArrayLength,

fn drop(&mut self)

Executes the destructor for this type.

impl<K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator> Extend<(K, V)> for CompressedBTreeMap<K, V, B, A>

where U2: Mul<B>, Prod<U2, B>: ArrayLength, U1: Add<Prod<U2, B>>, Sum<U1, Prod<U2, B>>: ArrayLength,

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends the map with the contents of an iterator.

If the iterator yields duplicate keys, the last value wins.

Panics

Panics if allocation fails during insertion.

Examples

use allocated_btree::CompressedBTreeMap;

let mut map = CompressedBTreeMap::new();
map.insert(1, "a").unwrap();

let more_items = vec![(2, "b"), (3, "c")];
map.extend(more_items);

assert_eq!(map.len(), 3);
assert_eq!(map.get(&2), Some(&"b"));

fn extend_one(&mut self, item: A)

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

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

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

Reserves capacity in a collection for the given number of additional elements.

impl<K: PartialOrd + Debug, V> FromIterator<(K, V)> for CompressedBTreeMap<K, V>

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

Creates a B-tree map from an iterator of key-value pairs.

If the iterator yields multiple values for the same key, the last value wins.

Panics

Panics if allocation fails during construction.

Examples

use allocated_btree::CompressedBTreeMap;

let items = vec![(1, "a"), (2, "b"), (3, "c")];
let map: CompressedBTreeMap<_, _> = items.into_iter().collect();

assert_eq!(map.get(&1), Some(&"a"));
assert_eq!(map.get(&2), Some(&"b"));
assert_eq!(map.get(&3), Some(&"c"));
assert_eq!(map.len(), 3);

impl<'s, K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator> IntoIterator for &'s CompressedBTreeMap<K, V, B, A>

where U2: Mul<B>, Prod<U2, B>: ArrayLength, U1: Add<Prod<U2, B>>, Sum<U1, Prod<U2, B>>: ArrayLength,

type IntoIter = Iter<'s, K, V, B>

Which kind of iterator are we turning this into?

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

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.