Struct BTreeMap 

pub struct BTreeMap<K, V, A: Tuning = DefaultTuning> { /* private fields */ }

BTreeMap similar to std::collections::BTreeMap.

General guide to implementation:

BTreeMap has a length and a Tree, where Tree is an enum that can be Leaf or NonLeaf.

The Entry API is implemented using CursorMut.

CursorMut is implemented using CursorMutKey which has a stack of raw pointer/index pairs to keep track of non-leaf positions.

Roughly speaking, unsafe code is limited to the vecs module and the implementation of CursorMut and CursorMutKey.

Implementations

impl<K, V> BTreeMap<K, V>

pub const fn new() -> Self

Returns a new, empty map.

pub const fn new_in<AL>(a: AL) -> BTreeMap<K, V, CustomTuning<AL>>

where AL: Allocator + Clone,

Returns a new, empty map with specified allocator.

Example

use pstd::{ alloc::Global, collections::btree_map::{BTreeMap,CustomTuning} };
let a = Global;
let mut map = BTreeMap::new_in(a);
map.insert("England", "London");

impl<K, V, A: Tuning> BTreeMap<K, V, A>

pub const fn with_tuning(atune: A) -> Self

Returns a new, empty map with specified allocation tuning.

Example

    use pstd::collections::btree_map::{BTreeMap,DefaultTuning};
    let mut mymap = BTreeMap::with_tuning(DefaultTuning::new(8,2));
    mymap.insert("England", "London");
    mymap.insert("France", "Paris");
    println!("The capital of France is {}", mymap["France"]);

pub fn tuning(&self) -> &A

Get ref to tuning.

pub fn tuning_mut(&mut self) -> &mut A

Get mut ref to tuning.

pub fn clear(&mut self)

Clear the map.

pub const fn len(&self) -> usize

Get number of key-value pairs in the map.

pub const fn is_empty(&self) -> bool

Is the map empty?

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

where K: Ord,

Get Entry for map key.

pub fn first_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>

where K: Ord,

Get first Entry.

pub fn last_entry(&mut self) -> Option<OccupiedEntry<'_, K, V, A>>

where K: Ord,

Get last Entry.

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

where K: Ord,

Insert key-value pair into map, or if key is already in map, replaces value and returns old value.

pub fn try_insert( &mut self, key: K, value: V, ) -> Result<&mut V, OccupiedError<'_, K, V, A>>

where K: Ord,

Tries to insert a key-value pair into the map, and returns a mutable reference to the value in the entry.

If the map already had this key present, nothing is updated, and an error containing the occupied entry and the value is returned.

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

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

Does the map have an entry for the specified key.

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

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

Remove key-value pair from map, returning just the value.

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

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

Remove key-value pair from map.

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

Remove first key-value pair from map.

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

Remove last key-value pair from map.

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &mut V) -> bool, K: Ord,

Remove all key-value pairs, visited in ascending order, for which f returns false.

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

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

Get reference to the value corresponding to the key.

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

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

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

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

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

Get references to the corresponding key and value.

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

Get references to first key and value.

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

Gets references to last key and value.

pub fn append(&mut self, other: &mut BTreeMap<K, V, A>)

where K: Ord,

Moves all elements from other into self, leaving other empty.

If a key from other is already present in self, the respective value from self will be overwritten with the respective value from other.

pub fn split_off<Q: ?Sized + Ord>(&mut self, key: &Q) -> Self

where K: Borrow<Q> + Ord,

Splits the collection into two at the given key. Returns everything after the given key, including the key.

pub fn extract_if<F>(&mut self, pred: F) -> ExtractIf<'_, K, V, F, A>

where K: Ord, F: FnMut(&K, &mut V) -> bool,

Returns iterator that visits all elements (key-value pairs) in ascending key order and uses a closure to determine if an element should be removed.

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

Get iterator of references to key-value pairs.

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

Get iterator of mutable references to key-value pairs.

pub fn range<T, R>(&self, range: R) -> Range<'_, K, V>

where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>,

Get iterator for range of references to key-value pairs.

pub fn range_mut<T, R>(&mut self, range: R) -> RangeMut<'_, K, V>

where T: Ord + ?Sized, K: Borrow<T> + Ord, R: RangeBounds<T>,

Get iterator for range of mutable references to key-value pairs.

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

Get iterator of references to keys.

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

Get iterator of references to values.

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

Get iterator of mutable references to values.

pub fn into_keys(self) -> IntoKeys<K, V, A>

Get consuming iterator that returns all the keys, in sorted order.

pub fn into_values(self) -> IntoValues<K, V, A>

Get consuming iterator that returns all the values, in sorted order.

pub fn lower_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V, A>

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

Get cursor positioned just after bound.

pub fn upper_bound<Q>(&self, bound: Bound<&Q>) -> Cursor<'_, K, V, A>

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

Get cursor positioned just before bound.

pub fn lower_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>

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

Get a cursor positioned just after bound that permits map mutation.

pub fn upper_bound_mut<Q>(&mut self, bound: Bound<&Q>) -> CursorMut<'_, K, V, A>

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

Get a cursor positioned just before bound that permits map mutation.

Trait Implementations

impl<K: Clone, V: Clone, A: Tuning> Clone for BTreeMap<K, V, A>

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, A: Tuning> Debug for BTreeMap<K, V, A>

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

Formats the value using the given formatter.

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

fn default() -> Self

Creates an empty BTreeMap.

impl<K, V, A: Tuning> Drop for BTreeMap<K, V, A>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K: Ord + Copy, V: Copy, A: Tuning> Extend<(&'a K, &'a V)> for BTreeMap<K, V, A>

fn extend<I>(&mut self, iter: I)

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

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: Ord, V, A: Tuning> Extend<(K, V)> for BTreeMap<K, V, A>

fn extend<T>(&mut self, iter: T)

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

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: Ord, V, const N: usize> From<[(K, V); N]> for BTreeMap<K, V>

fn from(arr: [(K, V); N]) -> BTreeMap<K, V>

Converts to this type from the input type.

impl<K: Ord, V> FromIterator<(K, V)> for BTreeMap<K, V>

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

Creates a value from an iterator.

impl<K: Hash, V: Hash, A: Tuning> Hash for BTreeMap<K, V, A>

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, Q, V, A: Tuning> Index<&Q> for BTreeMap<K, V, A>

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

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

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

Panics if the key is not present in the BTreeMap.

type Output = V

The returned type after indexing.

impl<'a, K, V, A: Tuning> IntoIterator for &'a BTreeMap<K, V, A>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, K, V>

Creates an iterator from a value.

impl<'a, K, V, A: Tuning> IntoIterator for &'a mut BTreeMap<K, V, A>

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

fn into_iter(self) -> IterMut<'a, K, V>

Creates an iterator from a value.

impl<K, V, A: Tuning> IntoIterator for BTreeMap<K, V, A>

fn into_iter(self) -> IntoIter<K, V, A>

Convert BTreeMap to IntoIter.

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, A>

Which kind of iterator are we turning this into?

impl<K: Ord, V: Ord, A: Tuning> Ord for BTreeMap<K, V, A>

fn cmp(&self, other: &BTreeMap<K, V, A>) -> 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, V: PartialEq, A: Tuning> PartialEq for BTreeMap<K, V, A>

fn eq(&self, other: &BTreeMap<K, V, A>) -> 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, V: PartialOrd, A: Tuning> PartialOrd for BTreeMap<K, V, A>

fn partial_cmp(&self, other: &BTreeMap<K, V, A>) -> 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, V: Eq, A: Tuning> Eq for BTreeMap<K, V, A>