Struct PackedMapBuilder 

pub struct PackedMapBuilder<K, V>
where
    K: ToOwned + ?Sized + Ord + PackedItem,
    K::Owned: Ord,
{ /* private fields */ }

A builder for PackedMap that allows incrementally appending potentially unsorted key-value pairs.

Algorithm

PackedMapBuilder uses an LSM-tree (Log-Structured Merge-tree) inspired approach to handle out-of-order insertions efficiently while maintaining a compact, immutable representation for the final map.

It maintains two structures:

1. packed: A PackedMap containing elements that are already sorted and packed.
2. unpacked: A BTreeMap serving as a buffer for new, potentially out-of-order insertions.

Operations

• Insertion:
  • We first attempt to insert the key-value pair directly into the packed map. PackedMap::insert succeeds if the key already exists (overwriting it) or if the key is greater than or equal to the last key in the map (maintaining sorted order). This fast path takes O(log N) or O(1) time.
  • If the key is out of order, the packed map rejects it. We then insert it into the unpacked buffer (BTreeMap).
• Lookup: To find a key, we check both the packed map and the unpacked buffer.
• Build: When build() is called, any remaining elements in the unpacked buffer are merged with the packed map to produce the final PackedMap.

This design optimizes for the common case where data is mostly sorted, while still supporting full unpacked insertion without severe performance degradation.

Implementations

impl<K, V> PackedMapBuilder<K, V>

where K: ?Sized + Ord + PackedItem + ToOwned, K::Owned: Ord,

pub fn new() -> Self

Creates a new empty PackedMapBuilder.

pub fn with_capacity(element_capacity: usize, buffer_capacity: usize) -> Self

Creates a new PackedMapBuilder with specified capacity.

The element_capacity argument specifies the number of slices that can be stored without reallocating the offsets vector. The buffer_capacity argument specifies the cumulative length of slices that can be stored without reallocating the data vector.

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

Returns true if the builder contains the given key.

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

Returns a reference to the value corresponding to the key.

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

Inserts a key-value pair into the builder.

Complexity

• O(1) if the key is greater than or equal to the last key in the map.
• O(log N) otherwise, where N is the number of elements in the map.

pub fn build(self) -> PackedMap<K, V>

Builds the PackedMap.

Trait Implementations

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

where K: ?Sized + Ord + PackedItem + ToOwned, K::Owned: Ord,

fn default() -> Self

Returns the “default value” for a type.