Struct BTreeIndexMultiMap 

pub struct BTreeIndexMultiMap<K, V> { /* private fields */ }

BTree-based multi-map with stable entry indices.

Each key may map to any number of values. Entries are stored in a Vec and assigned a stable index equal to their position in that Vec. The index of an entry does not change as long as no entry is removed. A B-tree over the keys provides O(log n) lookup, insertion, and removal, while the Vec backing allows O(1) random access by index.

Example

use btree_indexmap::BTreeIndexMultiMap;

let mut map = BTreeIndexMultiMap::new();

// Multiple values per key, each with its own stable index.
map.push_back("fruit", "apple");
map.push_back("veggie", "carrot");
map.push_back("fruit", "banana");

assert_eq!(map.key_occurences("fruit"), 2);

let fruits: Vec<_> = map.get("fruit").copied().collect();
assert_eq!(fruits, ["apple", "banana"]);

Implementations

impl<K, V> BTreeIndexMultiMap<K, V>

pub fn new() -> Self

Creates a new, empty multi-map.

pub fn with_capacity(cap: usize) -> Self

Creates a new, empty multi-map with space reserved for at least cap entries.

pub fn singleton(key: K, value: V) -> Self

where K: Ord,

Creates a new multi-map containing the single (key, value) entry.

pub fn clear(&mut self)

Removes all entries from the map.

This keeps the capacity allocated for the entries.

pub fn capacity(&self) -> usize

Returns the number of entries the map can hold without reallocating.

pub fn as_entries(&self) -> &[(K, V)]

Returns the entries of the map as a slice, in insertion (index) order.

pub fn is_empty(&self) -> bool

Returns true if the map contains no entries.

pub fn len(&self) -> usize

Returns the total number of entries in the map.

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

Returns the key and value of the first entry in the map (in insertion order), if any.

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

Returns the key and value of the last entry in the map (in insertion order), if any.

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

where Q: ?Sized + Comparable<K>,

Returns true if the map contains at least one entry for key.

pub fn key_occurences<Q>(&self, key: &Q) -> usize

where Q: ?Sized + Comparable<K>,

Returns the number of entries associated with key.

pub fn indexes_of<Q>(&self, key: &Q) -> IndexesIter<'_>

where Q: ?Sized + Comparable<K>,

Returns an iterator over the indexes of every entry associated with key.

pub fn index_of<Q>(&self, key: &Q) -> Option<usize>

where Q: ?Sized + Comparable<K>,

Returns the index of the first entry associated with key.

pub fn get_indexed_entries<Q>(&self, key: &Q) -> GetIndexedEntries<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over (index, &key, &value) for every entry associated with key.

pub fn get_or_insert_indexed_entries_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetIndexedEntries<'_, K, V>

where K: Ord,

Returns an iterator over (index, &key, &value) for every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_indexed_entries( &mut self, key: K, value: V, ) -> GetIndexedEntries<'_, K, V>

where K: Ord,

Returns an iterator over (index, &key, &value) for every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get_entries<Q>(&self, key: &Q) -> GetEntries<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over (&key, &value) for every entry associated with key.

pub fn get_or_insert_entries_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetEntries<'_, K, V>

where K: Ord,

Returns an iterator over (&key, &value) for every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_entries( &mut self, key: K, value: V, ) -> GetEntries<'_, K, V>

where K: Ord,

Returns an iterator over (&key, &value) for every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get<Q>(&self, key: &Q) -> Get<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over a reference to the value of every entry associated with key.

pub fn get_or_insert_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> Get<'_, K, V>

where K: Ord,

Returns an iterator over a reference to the value of every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert(&mut self, key: K, value: V) -> Get<'_, K, V>

where K: Ord,

Returns an iterator over a reference to the value of every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get_indexed<Q>(&self, key: &Q) -> GetIndexed<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over (index, &value) for every entry associated with key.

pub fn get_or_insert_indexed_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetIndexed<'_, K, V>

where K: Ord,

Returns an iterator over (index, &value) for every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_indexed( &mut self, key: K, value: V, ) -> GetIndexed<'_, K, V>

where K: Ord,

Returns an iterator over (index, &value) for every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get_indexed_entries_mut<Q>( &mut self, key: &Q, ) -> GetIndexedEntriesMut<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over (index, &key, &mut value) for every entry associated with key.

pub fn get_or_insert_indexed_entries_mut_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetIndexedEntriesMut<'_, K, V>

where K: Ord,

Returns an iterator over (index, &key, &mut value) for every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_indexed_entries_mut( &mut self, key: K, value: V, ) -> GetIndexedEntriesMut<'_, K, V>

where K: Ord,

Returns an iterator over (index, &key, &mut value) for every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get_entries_mut<Q>(&mut self, key: &Q) -> GetEntriesMut<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over (&key, &mut value) for every entry associated with key.

pub fn get_or_insert_entries_mut_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetEntriesMut<'_, K, V>

where K: Ord,

Returns an iterator over (&key, &mut value) for every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_entries_mut( &mut self, key: K, value: V, ) -> GetEntriesMut<'_, K, V>

where K: Ord,

Returns an iterator over (&key, &mut value) for every entry associated with key, inserting a single new entry with value if key was not already present.

pub fn get_mut<Q>(&mut self, key: &Q) -> GetMut<'_, K, V>

where Q: ?Sized + Comparable<K>,

Returns an iterator over a mutable reference to the value of every entry associated with key.

pub fn get_or_insert_mut_with( &mut self, key: K, f: impl FnOnce() -> V, ) -> GetMut<'_, K, V>

where K: Ord,

Returns an iterator over a mutable reference to the value of every entry associated with key, inserting a single new entry with a value produced by f if key was not already present.

pub fn get_or_insert_mut(&mut self, key: K, value: V) -> GetMut<'_, K, V>

where K: Ord,

Returns an iterator over a mutable reference to the value of every entry associated with key, inserting a single new entry with value if key was not already present.

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

where K: Ord,

Gets the entry associated with key for in-place manipulation.

Example

use btree_indexmap::{BTreeIndexMultiMap, multi_map::Entry};

let mut map: BTreeIndexMultiMap<&str, i32> = BTreeIndexMultiMap::new();

match map.entry("a") {
    Entry::Vacant(e) => {
        e.insert(1);
    }
    Entry::Occupied(_) => unreachable!(),
}

assert_eq!(map.get("a").next(), Some(&1));

pub fn push_back(&mut self, key: K, value: V) -> (usize, bool)

where K: Ord,

Inserts a new entry at the end of the map.

Returns the index of the new entry, and whether key was not already present in the map.

pub fn insert_at(&mut self, index: usize, key: K, value: V) -> bool

where K: Ord,

Inserts a new entry at the given index.

Returns whether key was not already present in the map.

Panics

Panics if index > len.

pub fn push_front(&mut self, key: K, value: V) -> bool

where K: Ord,

Inserts a new entry at the front of the map.

Returns whether key was not already present in the map.

pub fn shift_insert_full( &mut self, key: K, value: V, ) -> (usize, ShiftInsert<'_, K, V>)

where K: Ord,

Inserts a (key, value) entry, keeping only this occurrence of key.

If key was already present, replaces its first occurrence and removes every other one (using shift semantics), returning the index of the kept entry and an iterator over the values it replaced or removed. Otherwise, appends a new entry and returns its index with an empty iterator.

pub fn shift_insert(&mut self, key: K, value: V) -> ShiftInsert<'_, K, V>

where K: Ord,

Inserts a (key, value) entry, keeping only this occurrence of key.

See Self::shift_insert_full.

pub fn swap_insert_full( &mut self, key: K, value: V, ) -> (usize, SwapInsert<'_, K, V>)

where K: Ord,

Inserts a (key, value) entry, keeping only this occurrence of key.

If key was already present, replaces its first occurrence and removes every other one (using swap semantics), returning the index of the kept entry and an iterator over the values it replaced or removed. Otherwise, appends a new entry and returns its index with an empty iterator.

pub fn swap_insert(&mut self, key: K, value: V) -> SwapInsert<'_, K, V>

where K: Ord,

Inserts a (key, value) entry, keeping only this occurrence of key.

See Self::swap_insert_full.

pub fn shift_insert_front( &mut self, key: K, value: V, ) -> ShiftInsertFront<'_, K, V>

where K: Ord,

Inserts a (key, value) entry at the front of the map, replacing every previous occurrence of key.

Returns an iterator over the values of the removed occurrences, removed using shift semantics.

pub fn swap_insert_front( &mut self, key: K, value: V, ) -> SwapInsertFront<'_, K, V>

where K: Ord,

Inserts a (key, value) entry at the front of the map, replacing every previous occurrence of key.

Returns an iterator over the values of the removed occurrences, removed using swap semantics.

pub fn shift_insert_back_full( &mut self, key: K, value: V, ) -> (usize, ShiftInsertBack<'_, K, V>)

where K: Ord,

Inserts a (key, value) entry at the end of the map, replacing every previous occurrence of key.

Returns the index of the new entry and an iterator over the values of the removed occurrences, removed using shift semantics.

pub fn shift_insert_back( &mut self, key: K, value: V, ) -> ShiftInsertBack<'_, K, V>

where K: Ord,

Inserts a (key, value) entry at the end of the map, replacing every previous occurrence of key.

Returns an iterator over the values of the removed occurrences, removed using shift semantics.

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

where K: Ord,

Inserts a (key, value) entry, keeping only this occurrence of key.

This is an alias for Self::shift_insert_back.

pub fn swap_insert_back_full( &mut self, key: K, value: V, ) -> (usize, SwapInsertBack<'_, K, V>)

where K: Ord,

Inserts a (key, value) entry at the end of the map, replacing every previous occurrence of key.

Returns the index of the new entry and an iterator over the values of the removed occurrences, removed using swap semantics.

pub fn swap_insert_back(&mut self, key: K, value: V) -> SwapInsertBack<'_, K, V>

where K: Ord,

Inserts a (key, value) entry at the end of the map, replacing every previous occurrence of key.

Returns an iterator over the values of the removed occurrences, removed using swap semantics.

pub fn shift_remove_at(&mut self, i: usize) -> Option<(K, V)>

where K: Ord,

Removes the entry at the given index, returning its key and value, if it was present.

Shifts every following entry one index down.

pub fn swap_remove_at(&mut self, i: usize) -> Option<(K, V)>

where K: Ord,

Removes the entry at the given index, returning its key and value, if it was present.

Moves the last entry into the removed slot.

pub fn shift_remove_indexed_entries<Q>( &mut self, key: &Q, ) -> ShiftRemoveIndexedEntries<'_, K, V>

where Q: ?Sized + Comparable<K>,

Removes every entry associated with key, returning an iterator over (index, key, value) for each removed entry.

Shifts the remaining entries down to fill the gaps.

pub fn shift_remove_entries<Q>( &mut self, key: &Q, ) -> ShiftRemoveEntries<'_, K, V>

where Q: ?Sized + Comparable<K>,

Removes every entry associated with key, returning an iterator over (key, value) for each removed entry.

Shifts the remaining entries down to fill the gaps.

pub fn shift_remove<Q>(&mut self, key: &Q) -> ShiftRemove<'_, K, V>

where Q: ?Sized + Comparable<K>,

Removes every entry associated with key, returning an iterator over the value of each removed entry.

Shifts the remaining entries down to fill the gaps.

pub fn swap_remove_indexed_entries<Q>( &mut self, key: &Q, ) -> SwapRemoveIndexedEntries<'_, K, V>

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

Removes every entry associated with key, returning an iterator over (index, key, value) for each removed entry.

Moves entries from the end of the map into the gaps.

pub fn swap_remove_entries<Q>(&mut self, key: &Q) -> SwapRemoveEntries<'_, K, V>

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

Removes every entry associated with key, returning an iterator over (key, value) for each removed entry.

Moves entries from the end of the map into the gaps.

pub fn swap_remove<Q>(&mut self, key: &Q) -> SwapRemove<'_, K, V>

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

Removes every entry associated with key, returning an iterator over the value of each removed entry.

Moves entries from the end of the map into the gaps.

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

Returns an iterator over the entries of the map, in insertion (index) order.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Returns an iterator over the entries of the map, with a mutable reference to the value, in insertion (index) order.

pub fn iter_sorted(&self) -> IterSorted<'_, K, V>

Returns an iterator over the entries of the map, sorted by key according to K’s implementation of Ord.

Entries that share the same key are visited in insertion (index) order.

pub fn iter_mut_sorted(&mut self) -> IterMutSorted<'_, K, V>

Returns an iterator over the entries of the map, with a mutable reference to the value, sorted by key according to K’s implementation of Ord.

Entries that share the same key are visited in insertion (index) order.

pub fn into_iter_sorted(self) -> IntoIterSorted<K, V>

Turns this map into an iterator over its entries, sorted by key according to K’s implementation of Ord.

Entries that share the same key are visited in insertion (index) order.

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

Returns an iterator over the keys of the map, in insertion (index) order.

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

Returns an iterator over the values of the map, in insertion (index) order.

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

Returns an iterator over mutable references to the values of the map, in insertion (index) order.

pub fn sort(&mut self)

where K: Ord,

Sort the entries by key name.

The relative order of entries with the same key is unchanged.

Trait Implementations

impl<K: Clone, V: Clone> Clone for BTreeIndexMultiMap<K, V>

fn clone(&self) -> BTreeIndexMultiMap<K, V>

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug> Debug for BTreeIndexMultiMap<K, V>

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<K: Eq, V: Eq> Eq for BTreeIndexMultiMap<K, V>

impl<K: Ord, V> Extend<(K, V)> for BTreeIndexMultiMap<K, V>

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

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: T)

🔬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: Ord, V> FromIterator<(K, V)> for BTreeIndexMultiMap<K, V>

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

Creates a value from an iterator.

impl<K: Hash, V: Hash> Hash for BTreeIndexMultiMap<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, V, Q> Index<&Q> for BTreeIndexMultiMap<K, V>

where Q: ?Sized + Comparable<K>,

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

Panics

Panics if key is not found in the map.

type Output = V

The returned type after indexing.

impl<K, V> IntoIterator for BTreeIndexMultiMap<K, V>

type IntoIter = IntoIter<(K, V)>

Which kind of iterator are we turning this into?

type Item = (K, V)

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a BTreeIndexMultiMap<K, V>

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

Which kind of iterator are we turning this into?

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

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V> IntoIterator for &'a mut BTreeIndexMultiMap<K, V>

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

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

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Ord, V: Ord> Ord for BTreeIndexMultiMap<K, V>

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.

fn clamp_to<R>(self, range: R) -> Self

where Self: Sized, R: ClampBounds<Self>,

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

Restrict a value to a certain range.

impl<K: PartialEq, V: PartialEq> PartialEq for BTreeIndexMultiMap<K, V>

fn eq(&self, other: &Self) -> bool

Equality operator ==.

fn ne(&self, other: &Rhs) -> bool

Inequality operator !=.

impl<K: PartialOrd, V: PartialOrd> PartialOrd for BTreeIndexMultiMap<K, V>

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.