Struct Map 

pub struct Map<K: Indexable, V> { /* private fields */ }

An owned map optimized for read-heavy workloads, backed by a PGM-index.

This is a BTreeMap-like container that owns its data and provides efficient lookups using a learned index. Mutations are supported but trigger O(n) index rebuilds; for frequent updates use crate::Dynamic.

Works with any key type that implements Indexable:

• Numeric types (u64, i32, etc.) are indexed directly
• String/bytes types use prefix extraction

Example

use pgm_extra::Map;

// Numeric keys
let entries: Vec<(u64, &str)> = vec![(1, "one"), (2, "two"), (3, "three")];
let map = Map::from_sorted_unique(entries, 64, 4).unwrap();
assert_eq!(map.get(&2), Some(&"two"));

// String keys
let entries = vec![("apple", 1), ("banana", 2), ("cherry", 3)];
let map = Map::from_sorted_unique(entries, 64, 4).unwrap();
assert_eq!(map.get(&"banana"), Some(&2));

Implementations

impl<K: Indexable + Ord, V> Map<K, V>

where K::Key: Ord,

pub fn from_sorted_unique( entries: Vec<(K, V)>, epsilon: usize, epsilon_recursive: usize, ) -> Result<Self, Error>

Create a map from pre-sorted, unique key-value pairs.

Panics

Debug builds will panic if keys are not sorted or contain duplicates.

pub fn build<I>( iter: I, epsilon: usize, epsilon_recursive: usize, ) -> Result<Self, Error>

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

Create a map from an unsorted iterator of key-value pairs.

If duplicate keys exist, the last value wins (like BTreeMap::from_iter).

pub fn empty(epsilon: usize, epsilon_recursive: usize) -> Self

pub fn new(entries: Vec<(K, V)>) -> Result<Self, Error>

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

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

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

pub fn lower_bound(&self, key: &K) -> usize

Find the index of the first key >= the given key.

pub fn upper_bound(&self, key: &K) -> usize

Find the index of the first key > the given key.

pub fn range<R>(&self, range: R) -> impl DoubleEndedIterator<Item = (&K, &V)>

where R: RangeBounds<K>,

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

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

pub fn iter( &self, ) -> impl ExactSizeIterator<Item = (&K, &V)> + DoubleEndedIterator

pub fn keys(&self) -> impl ExactSizeIterator<Item = &K> + DoubleEndedIterator

pub fn values(&self) -> impl ExactSizeIterator<Item = &V> + DoubleEndedIterator

pub fn values_mut( &mut self, ) -> impl ExactSizeIterator<Item = &mut V> + DoubleEndedIterator

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

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn segments_count(&self) -> usize

Get the number of segments in the underlying index.

pub fn height(&self) -> usize

Get the height of the underlying index.

pub fn epsilon(&self) -> usize

Get the epsilon value.

pub fn epsilon_recursive(&self) -> usize

Get the epsilon_recursive value.

pub fn size_in_bytes(&self) -> usize

Approximate memory usage in bytes.

pub fn keys_slice(&self) -> &[K]

Get a reference to the underlying keys slice.

pub fn values_slice(&self) -> &[V]

Get a reference to the underlying values slice.

pub fn into_vec(self) -> Vec<(K, V)>

Consume the map and return the underlying key-value pairs.

pub fn index(&self) -> Option<&Static<K>>

Get a reference to the underlying index.

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

Insert a key-value pair into the map.

Returns the old value if the key already existed, or None if it was newly inserted.

Note: This rebuilds the entire index, making it O(n) per insertion. For bulk insertions, prefer collecting into a new map. For frequent mutations, consider using index::owned::Dynamic directly.

Trait Implementations

impl<K: Indexable, V> Archive for Map<K, V>

where Vec<K>: Archive, Vec<V>: Archive, Option<Static<K>>: Archive, usize: Archive,

type Archived = ArchivedMap<K, V>

The archived representation of this type.

type Resolver = MapResolver<K, V>

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output.

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize.

impl<K: Indexable + Clone, V: Clone> Clone for Map<K, V>

where K::Key: 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: Indexable + Debug, V: Debug> Debug for Map<K, V>

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

Formats the value using the given formatter.

impl<'de, K, V> Deserialize<'de> for Map<K, V>

where K: Serialize + DeserializeOwned + Indexable, V: Serialize + DeserializeOwned, K::Key: Serialize + DeserializeOwned,

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<__D: Fallible + ?Sized, K: Indexable, V> Deserialize<Map<K, V>, __D> for Archived<Map<K, V>>

where Vec<K>: Archive, <Vec<K> as Archive>::Archived: Deserialize<Vec<K>, __D>, Vec<V>: Archive, <Vec<V> as Archive>::Archived: Deserialize<Vec<V>, __D>, Option<Static<K>>: Archive, <Option<Static<K>> as Archive>::Archived: Deserialize<Option<Static<K>>, __D>, usize: Archive, <usize as Archive>::Archived: Deserialize<usize, __D>,

fn deserialize( &self, deserializer: &mut __D, ) -> Result<Map<K, V>, <__D as Fallible>::Error>

Deserializes using the given deserializer

impl<K: Indexable + Ord, V> Extend<(K, V)> for Map<K, V>

where K::Key: Ord,

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

Extends the map with key-value pairs from an iterator.

If duplicate keys exist, the last value wins.

Note: This rebuilds the entire index, making it O(n) per call. For bulk insertions, prefer collecting into a new map. For frequent mutations, consider using index::owned::Dynamic directly.

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: Indexable + Ord, V> FromIterator<(K, V)> for Map<K, V>

where K::Key: Ord,

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

Creates a Map from an iterator.

Returns an empty map if the iterator is empty.

impl<K: Indexable + Hash, V: Hash> Hash for Map<K, V>

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

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<K: Indexable + Ord, V> Index<&K> for Map<K, V>

where K::Key: Ord,

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

Returns a reference to the value corresponding to the key.

Panics

Panics if the key is not present in the map.

type Output = V

The returned type after indexing.

impl<'a, K: Indexable, V> IntoIterator for &'a Map<K, V>

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

The type of the elements being iterated over.

type IntoIter = Zip<Iter<'a, K>, Iter<'a, V>>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Indexable + Ord, V> IntoIterator for Map<K, V>

where K::Key: Ord,

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) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Indexable + Ord + PartialEq, V: PartialEq> PartialEq for Map<K, V>

fn eq(&self, other: &Self) -> 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<__S: Fallible + ?Sized, K: Indexable, V> Serialize<__S> for Map<K, V>

where Vec<K>: Serialize<__S>, Vec<V>: Serialize<__S>, Option<Static<K>>: Serialize<__S>, usize: Serialize<__S>,

fn serialize( &self, serializer: &mut __S, ) -> Result<<Self as Archive>::Resolver, <__S as Fallible>::Error>

Writes the dependencies for the object and returns a resolver that can create the archived type.

impl<K, V> Serialize for Map<K, V>

where K: Serialize + DeserializeOwned + Indexable, V: Serialize + DeserializeOwned, K::Key: Serialize + DeserializeOwned,

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

where __S: Serializer,

Serialize this value into the given Serde serializer.

impl<K: Indexable + Ord + Eq, V: Eq> Eq for Map<K, V>