Struct AllocatedBTreeMap 

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

A compressed B-Tree map implementation using the allocated pattern.

This is the low-level “allocated” type that requires manual allocator passing. For most use cases, prefer the CompressedBTreeMap wrapper which owns its allocator and provides a safe, ergonomic API.

This implementation uses ~30% less memory than the naive implementation by using specialized node types:

• Leaf nodes: Store only keys and values (no child pointers)
• Interior nodes: Store keys, values, and child pointers

Type Parameters

• K: Key type, must be PartialOrd + Debug
• V: Value type
• B: Branching factor (defaults to U6 for 6-way tree). Controls the number of keys per node (2*B keys maximum).

Examples

use allocated_btree::AllocatedCompressedBTreeMap;
use allocated::CountingAllocator;

let alloc = CountingAllocator::default();
let mut map = AllocatedCompressedBTreeMap::<u32, String>::new_in(&alloc)?;

unsafe {
    map.insert_in(&alloc, 1, "one".to_string())?;
    map.insert_in(&alloc, 2, "two".to_string())?;
}

assert_eq!(map.len(), 2);

Implementations

impl<K: PartialOrd + Debug, V, B: ArrayLength> AllocatedBTreeMap<K, V, B>

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

pub fn new_in<A: Allocator>(alloc: &A) -> DropGuardResult<Self, &A>

Errors

Will return Err if the allocation fails.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn len(&self) -> usize

Returns the number of elements in the map.

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

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

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

pub unsafe fn insert_in<A: Allocator>( &mut self, alloc: &A, 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.

Safety

alloc MUST be the allocator used to allocate this object.

Errors

Will return Err if the allocation fails.

pub unsafe fn clear_in<A: Allocator>(&mut self, alloc: &A) -> AllocResult<()>

Clears the map, removing all elements.

Safety

alloc MUST be the allocator used to allocate this object.

Errors

Will return Err if the allocation fails.

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

where K: Borrow<Q> + PartialOrd, 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> + PartialOrd, 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> + PartialOrd, Q: PartialOrd + Debug,

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

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

Returns an iterator over the key-value pairs of the map, in sorted order by key.

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

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

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

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

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

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

pub unsafe fn entry_in<'a, 's, A: Allocator>( &'s mut self, alloc: &'a A, key: K, ) -> Entry<'a, 's, A, K, V, B>

Safety

alloc MUST be the allocator used to allocate this object.

pub unsafe fn first_entry_in<'a, 's, A: Allocator>( &'s mut self, alloc: &'a A, ) -> Option<OccupiedEntry<'a, 's, A, K, V, B>>

Safety

alloc MUST be the allocator used to allocate this object.

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

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

Trait Implementations

impl<K: PartialOrd + Debug, V, B: ArrayLength> DropIn for AllocatedBTreeMap<K, V, B>

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

unsafe fn drop_in<A: Allocator>(&mut self, alloc: &A)

Safety

alloc must be the allocator used to allocate this object.

impl<'a, K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator> FromIteratorIn<'a, (K, V), A> for AllocatedBTreeMap<K, V, B>

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

fn from_iter_in<T>(alloc: &'a A, iter: T) -> DropGuardResult<Self, &'a A>

where T: IntoIterator<Item = (K, V)>,

Create a container from elements of an iterator. Any memory that needs to be allocated will be allocated in alloc. The instance of Self MUST be drop_in using the same instance of the allocator.

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

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.

impl<'a, K: PartialOrd + Debug, V, B: ArrayLength, A: Allocator + 'a> IntoIteratorIn<'a, A> for AllocatedBTreeMap<K, V, B>

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

type Item = (K, V)

type IntoIter = IntoIter<'a, K, V, B, A>

unsafe fn into_iter_in(self, alloc: &'a A) -> Self::IntoIter

Safety

impl<K, V, B> RecursiveDropIn for AllocatedBTreeMap<K, V, B>

where K: PartialOrd + Debug + DropIn, V: DropIn, B: ArrayLength, U2: Mul<B>, Prod<U2, B>: ArrayLength, U1: Add<Prod<U2, B>>, Sum<U1, Prod<U2, B>>: ArrayLength,

unsafe fn recursive_drop_in<A: Allocator>(&mut self, alloc: &A)

Safety

alloc must be the allocator used to allocate this object.