Struct SmallBTreeMap 

pub struct SmallBTreeMap<K, V, const N: usize> { /* private fields */ }

A sorted map that lives on the stack for up to N entries, then spills to the heap.

Storage strategy

Uses a tagged union ([MapData]) with:

• Stack side: HeaplessBTreeMap<K, V, N> — a sorted heapless::Vec.
• Heap side: std::collections::BTreeMap<K, V>.

Once a spill occurs the struct permanently uses the heap side.

Overflow protocol

When insert is called on a full stack map with a new key, spill_to_heap migrates all entries to a BTreeMap and then re-inserts the new pair.

Generic parameters

Parameter	Meaning
K	Key type; must implement Ord
V	Value type
N	Stack capacity — max entries before spill

Design Considerations

• len tracked separately: instead of accessing the union variant to call .len(), the length is cached in a plain usize field so len() never touches unsafe code.
• Sorted iteration: the stack-side sorted order is preserved during spill, so BTreeMap’s sorted iteration invariant is maintained without re-sorting.
• Entry API: the entry method (in map.rs / SmallMap) can be layered on top; this struct deliberately keeps its API minimal.

Safety

on_stack determines which variant of MapData is active. Only that variant may be accessed. All unsafe union accesses must first check on_stack.

Implementations

impl<K, V, const N: usize> SmallBTreeMap<K, V, N>

where K: Ord,

pub const MAX_STACK_SIZE: usize

A constant parameter.

pub fn new() -> Self

Creates a new empty map on the stack.

pub fn with_capacity(cap: usize) -> Self

Creates an empty map with the specified capacity. If the capacity exceeds the stack limit N, it will be created directly on the heap.

pub fn is_on_stack(&self) -> bool

Returns true if the map is currently storing data on the stack.

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 clear(&mut self)

Clears the map, removing all key-value pairs.

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

Inserts a key-value pair into the map. If the map is on the stack and full, this triggers a transparent spill to the heap.

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

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

Returns a reference to the value corresponding to the key.

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

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

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

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

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

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

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

Returns an iterator over the elements.

Trait Implementations

impl<K: Ord, V, const N: usize> AnyBTreeMap<K, V> for SmallBTreeMap<K, V, N>

fn len(&self) -> usize

Returns the number of key-value pairs.

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

Inserts (key, value), returning the previous value if the key existed.

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

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

Returns a shared reference to the value for key, or None.

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

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

Returns an exclusive reference to the value for key, or None.

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

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

Removes and returns the value for key, or None if absent.

fn clear(&mut self)

Removes all entries.

fn is_empty(&self) -> bool

Returns true if the map is empty.

impl<K, V, const N: usize> Clone for SmallBTreeMap<K, V, N>

where K: Ord + Clone, V: Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Ord + Debug, V: Debug, const N: usize> Debug for SmallBTreeMap<K, V, N>

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

Formats the value using the given formatter.

impl<K: Ord, V, const N: usize> Default for SmallBTreeMap<K, V, N>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, const N: usize> Drop for SmallBTreeMap<K, V, N>

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, const N: usize> Extend<(K, V)> for SmallBTreeMap<K, V, N>

where K: Ord,

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

Extends a collection with the contents of an iterator.

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, V, const N: usize> FromIterator<(K, V)> for SmallBTreeMap<K, V, N>

where K: Ord,

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

Creates a value from an iterator.

impl<K, V, Q, const N: usize> Index<&Q> for SmallBTreeMap<K, V, N>

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

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<K, V, Q, const N: usize> IndexMut<&Q> for SmallBTreeMap<K, V, N>

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

fn index_mut(&mut self, key: &Q) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<K, V, const N: usize> IntoIterator for SmallBTreeMap<K, V, N>

where K: Ord,

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = SmallBTreeMapIntoIter<K, V, N>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Ord, V: Ord, const N: usize> Ord for SmallBTreeMap<K, V, N>

fn cmp(&self, other: &Self) -> 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 + Ord, V: PartialEq, const N: usize, M: AnyBTreeMap<K, V>> PartialEq<M> for SmallBTreeMap<K, V, N>

fn eq(&self, other: &M) -> 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 + Ord, V: PartialOrd, const N: usize> PartialOrd for SmallBTreeMap<K, V, N>

fn partial_cmp(&self, other: &Self) -> 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: Eq + Ord, V: Eq, const N: usize> Eq for SmallBTreeMap<K, V, N>