Struct rpds::map::red_black_tree_map::RedBlackTreeMap

pub struct RedBlackTreeMap<K, V> { /* fields omitted */ }

A persistent map with structural sharing. This implementation uses a red-black tree.

Complexity

Let n be the number of elements in the map.

Temporal complexity

Operation	Average	Worst case
new()	Θ(1)	Θ(1)
insert()	Θ(log(n))	Θ(log(n))
remove()	Θ(log(n))	Θ(log(n))
get()	Θ(log(n))	Θ(log(n))
contains_key()	Θ(log(n))	Θ(log(n))
size()	Θ(1)	Θ(1)
clone()	Θ(1)	Θ(1)
iterator creation	Θ(log(n))	Θ(log(n))
iterator step	Θ(1)	Θ(log(n))
iterator full	Θ(n)	Θ(n)

Implementation details

This implementation uses a red-black tree as described in "Purely Functional Data Structures" by Chris Okasaki, page 27. Deletion is implemented according to the paper "Red-Black Trees with Types" by Stefan Kahrs (reference implementation)

Methods

impl<K, V> RedBlackTreeMap<K, V> where
    K: Ord, 

#[must_use]

pub fn new() -> RedBlackTreeMap<K, V>

#[must_use]

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Ord, 

#[must_use]

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

#[must_use]

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

#[must_use]

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

pub fn insert_mut(&mut self, key: K, value: V)

#[must_use]

pub fn remove<Q: ?Sized>(&self, key: &Q) -> RedBlackTreeMap<K, V> where
    K: Borrow<Q>,
    Q: Ord, 

pub fn remove_mut<Q: ?Sized>(&mut self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Ord, 

#[must_use]

pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
    K: Borrow<Q>,
    Q: Ord, 

#[must_use]

pub fn size(&self) -> usize

#[must_use]

pub fn is_empty(&self) -> bool

#[must_use]

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

#[must_use]

pub fn keys(&self) -> IterKeys<K, V>

#[must_use]

pub fn values(&self) -> IterValues<K, V>

#[must_use]

pub fn range<Q: ?Sized, RB>(&self, range: RB) -> RangeIter<K, V, RB, Q> where
    K: Borrow<Q>,
    Q: Ord,
    RB: RangeBounds<Q>, 

Trait Implementations

impl<K, V> Default for RedBlackTreeMap<K, V> where
    K: Ord, 

fn default() -> RedBlackTreeMap<K, V>

Returns the "default value" for a type.

impl<K, V: PartialEq> PartialEq<RedBlackTreeMap<K, V>> for RedBlackTreeMap<K, V> where
    K: Ord, 

fn eq(&self, other: &RedBlackTreeMap<K, V>) -> bool

This method tests for self and other values to be equal, and is used by ==.

#[must_use]

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

This method tests for !=.

impl<K: Ord, V: PartialOrd> PartialOrd<RedBlackTreeMap<K, V>> for RedBlackTreeMap<K, V>

fn partial_cmp(&self, other: &RedBlackTreeMap<K, V>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

#[must_use]

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

This method tests less than (for self and other) and is used by the < operator.

#[must_use]

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

This method tests less than or equal to (for self and other) and is used by the <= operator.

#[must_use]

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

This method tests greater than (for self and other) and is used by the > operator.

#[must_use]

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

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<K, V: Eq> Eq for RedBlackTreeMap<K, V> where
    K: Ord, 

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

fn cmp(&self, other: &RedBlackTreeMap<K, V>) -> Ordering

This method returns an Ordering between self and other.

fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

impl<K, V> Clone for RedBlackTreeMap<K, V> where
    K: Ord, 

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, K, V> IntoIterator for &'a RedBlackTreeMap<K, V> where
    K: Ord, 

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<K: Debug, V: Debug> Debug for RedBlackTreeMap<K, V>

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

Formats the value using the given formatter.

impl<K, V> Display for RedBlackTreeMap<K, V> where
    K: Ord + Display,
    V: Display, 

fn fmt(&self, fmt: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<K: Hash, V: Hash> Hash for RedBlackTreeMap<K, V> where
    K: Ord, 

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, 

Feeds a slice of this type into the given [Hasher].

impl<'a, K, Q: ?Sized, V> Index<&'a Q> for RedBlackTreeMap<K, V> where
    K: Ord + Borrow<Q>,
    Q: Ord, 

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

fn from_iter<I: IntoIterator<Item = (K, V)>>(
    into_iter: I
) -> RedBlackTreeMap<K, V>

Creates a value from an iterator.

impl<K, V> Serialize for RedBlackTreeMap<K, V> where
    K: Ord + Serialize,
    V: Serialize, 

fn serialize<S: Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error>

Serialize this value into the given Serde serializer.

impl<'de, K, V> Deserialize<'de> for RedBlackTreeMap<K, V> where
    K: Ord + Deserialize<'de>,
    V: Deserialize<'de>, 

fn deserialize<D: Deserializer<'de>>(
    deserializer: D
) -> Result<RedBlackTreeMap<K, V>, D::Error>

Deserialize this value from the given Serde deserializer.