Struct rpds::map::red_black_tree_map::RedBlackTreeMap

pub struct RedBlackTreeMap<K, V, P = RcK> where
    P: SharedPointerKind,  { /* 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)

Implementations

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

#[must_use]pub fn new_sync() -> RedBlackTreeMapSync<K, V>

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

#[must_use]pub fn new() -> RedBlackTreeMap<K, V>

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

#[must_use]pub fn new_with_ptr_kind() -> RedBlackTreeMap<K, V, P>

#[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, P>

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

#[must_use]pub fn remove<Q: ?Sized>(&self, key: &Q) -> RedBlackTreeMap<K, V, P> 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, P>

#[must_use]pub fn keys(&self) -> IterKeys<'_, K, V, P>

#[must_use]pub fn values(&self) -> IterValues<'_, K, V, P>

#[must_use]pub fn range<Q: ?Sized, RB>(&self, range: RB) -> RangeIter<'_, K, V, RB, Q, P> where
    K: Borrow<Q>,
    Q: Ord,
    RB: RangeBounds<Q>, 

impl<K, V, P> RedBlackTreeMap<K, V, P> where
    K: Ord + Clone,
    V: Clone,
    P: SharedPointerKind, 

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

Trait Implementations

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, P: Debug> Debug for RedBlackTreeMap<K, V, P> where
    P: SharedPointerKind, 

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

Formats the value using the given formatter.

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

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

Returns the "default value" for a type.

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

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

Deserialize this value from the given Serde deserializer.

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

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

Formats the value using the given formatter.

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

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

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

Creates a value from an iterator.

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

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

Feeds this value into the given Hasher.

pub 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, P> Index<&'a Q> for RedBlackTreeMap<K, V, P> where
    K: Ord + Borrow<Q>,
    Q: Ord,
    P: SharedPointerKind, 

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

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

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

The type of the elements being iterated over.

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

Which kind of iterator are we turning this into?

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

Creates an iterator from a value.

impl<K: Ord, V: Ord, P> Ord for RedBlackTreeMap<K, V, P> where
    P: SharedPointerKind, 

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

This method returns an Ordering between self and other.

#[must_use]pub fn max(self, other: Self) -> Self

Compares and returns the maximum of two values.

#[must_use]pub fn min(self, other: Self) -> Self

Compares and returns the minimum of two values.

#[must_use]pub fn clamp(self, min: Self, max: Self) -> Self

Restrict a value to a certain interval.

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

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

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

#[must_use]pub fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<K: Ord, V: PartialOrd, P, PO> PartialOrd<RedBlackTreeMap<K, V, PO>> for RedBlackTreeMap<K, V, P> where
    P: SharedPointerKind,
    PO: SharedPointerKind, 

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

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

#[must_use]pub fn lt(&self, other: &Rhs) -> bool

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

#[must_use]pub 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]pub fn gt(&self, other: &Rhs) -> bool

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

#[must_use]pub 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, P> Serialize for RedBlackTreeMap<K, V, P> where
    K: Ord + Serialize,
    V: Serialize,
    P: SharedPointerKind, 

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

Serialize this value into the given Serde serializer.