Struct BTreeIndexMap 

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

BTree-based map with stable entry indices.

Each key maps to exactly one value. 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::BTreeIndexMap;

let mut map = BTreeIndexMap::new();

// Entries are stored in insertion order and assigned a stable index.
map.insert("banana", 3);
map.insert("apple", 5);

// O(1) access by index (insertion order).
assert_eq!(map.as_entries()[0], ("banana", 3));
assert_eq!(map.as_entries()[1], ("apple", 5));

// O(log n) lookup by key, returning the stable index alongside the value.
assert_eq!(map.get_full("apple"), Some((1, &"apple", &5)));

Implementations

impl<K, V> BTreeIndexMap<K, V>

pub fn new() -> Self

Creates a new, empty map.

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

where K: Ord,

Creates a new 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 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 number of entries in the map.

pub fn get_full<Q>(&self, key: &Q) -> Option<(usize, &K, &V)>

where Q: ?Sized + Comparable<K>,

Returns the index, key, and value of the entry matching key, if any.

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

where Q: ?Sized + Comparable<K>,

Returns the key and value of the entry matching key, if any.

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

where Q: ?Sized + Comparable<K>,

Returns a reference to the value associated with key, if any.

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

where Q: ?Sized + Comparable<K>,

Returns the index, key, and a mutable reference to the value of the entry matching key, if any.

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

where Q: ?Sized + Comparable<K>,

Returns the key and a mutable reference to the value of the entry matching key, if any.

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

where Q: ?Sized + Comparable<K>,

Returns a mutable reference to the value associated with key, if any.

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::{BTreeIndexMap, map::Entry};

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

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

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

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

where K: Ord,

Inserts a key-value pair in the map, returning the index of the entry and, if key was already present, its previous value.

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

where K: Ord,

Inserts a key-value pair in the map, returning the previous value associated with key, if any.

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

where Q: ?Sized + Comparable<K>,

Removes the entry matching key, returning its former index, key, and value, if it was present.

Shifts every following entry one index down.

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

where Q: ?Sized + Comparable<K>,

Removes the entry matching key, returning its key and value, if it was present.

Shifts every following entry one index down.

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

where Q: ?Sized + Comparable<K>,

Removes the entry matching key, returning its value, if it was present.

Shifts every following entry one index down.

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

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

Removes the entry matching key, returning its former index, key, and value, if it was present.

Moves the last entry into the removed slot.

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

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

Removes the entry matching key, returning its key and value, if it was present.

Moves the last entry into the removed slot.

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

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

Removes the entry matching key, returning its value, if it was present.

Moves the last entry into the removed slot.

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 according to K’s implementation of Ord.

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 according to K’s implementation of Ord.

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

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

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.

Trait Implementations

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

fn clone(&self) -> BTreeIndexMap<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 BTreeIndexMap<K, V>

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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

impl<K: Ord, V> Extend<(K, V)> for BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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 BTreeIndexMap<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.