Struct RedBlackTreeMap 

pub struct RedBlackTreeMap<K, V, P = RcK>
where
    P: SharedPointerKind,
{ /* private fields */ }

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, ArcTK>

where K: Ord,

pub fn new_sync() -> RedBlackTreeMap<K, V, ArcTK>

impl<K, V> RedBlackTreeMap<K, V>

where K: Ord,

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

impl<K, V, P> RedBlackTreeMap<K, V, P>

where K: Ord, P: SharedPointerKind,

pub fn new_with_ptr_kind() -> RedBlackTreeMap<K, V, P>

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

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

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

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

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

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

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

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

pub fn remove<Q>(&self, key: &Q) -> RedBlackTreeMap<K, V, P>

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

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

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

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

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

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

where PO: SharedPointerKind,

Test whether the two maps refer to the same content in memory.

This would return true if you’re comparing a map to itself, or if you’re comparing a map to a fresh clone of itself.

pub fn size(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn iter( &self, ) -> Map<IterPtr<'_, K, V, P>, fn(&SharedPointer<Entry<K, V>, P>) -> (&K, &V)>

pub fn keys( &self, ) -> Map<Map<IterPtr<'_, K, V, P>, fn(&SharedPointer<Entry<K, V>, P>) -> (&K, &V)>, fn((&K, &V)) -> &K>

pub fn values( &self, ) -> Map<Map<IterPtr<'_, K, V, P>, fn(&SharedPointer<Entry<K, V>, P>) -> (&K, &V)>, fn((&K, &V)) -> &V>

pub fn range<Q, RB>( &self, range: RB, ) -> Map<RangeIterPtr<'_, K, V, RB, Q, P>, fn(&SharedPointer<Entry<K, V>, P>) -> (&K, &V)>

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

impl<K, V, P> RedBlackTreeMap<K, V, P>

where K: Ord + Clone, V: Clone, P: SharedPointerKind,

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

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

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 duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V, P> Debug for RedBlackTreeMap<K, V, P>

where K: Debug, V: Debug, P: Debug + SharedPointerKind,

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

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: D, ) -> Result<RedBlackTreeMap<K, V, P>, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

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<(), Error>

Formats the value using the given formatter.

impl<K, V, P> FromIterator<(K, V)> for RedBlackTreeMap<K, V, P>

where K: Ord, P: SharedPointerKind,

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

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

Creates a value from an iterator.

impl<K, V, P> Hash for RedBlackTreeMap<K, V, P>

where K: Hash + Ord, V: Hash, P: SharedPointerKind,

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

where H: Hasher,

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, P> Index<&Q> for RedBlackTreeMap<K, V, P>

where K: Ord + Borrow<Q>, Q: Ord + ?Sized, 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 = Map<IterPtr<'a, K, V, P>, fn(&'a SharedPointer<Entry<K, V>, P>) -> (&'a K, &'a V)>

Which kind of iterator are we turning this into?

fn into_iter( self, ) -> Map<IterPtr<'a, K, V, P>, fn(&'a SharedPointer<Entry<K, V>, P>) -> (&'a K, &'a V)>

Creates an iterator from a value.

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

where K: Ord, V: Ord, P: SharedPointerKind,

fn cmp(&self, other: &RedBlackTreeMap<K, V, P>) -> 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, V, P, PO> PartialEq<RedBlackTreeMap<K, V, PO>> for RedBlackTreeMap<K, V, P>

where V: PartialEq, K: Ord, P: SharedPointerKind, PO: SharedPointerKind,

fn eq(&self, other: &RedBlackTreeMap<K, V, PO>) -> 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, V, P, PO> PartialOrd<RedBlackTreeMap<K, V, PO>> for RedBlackTreeMap<K, V, P>

where K: Ord, V: PartialOrd, 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.

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, V, P> Serialize for RedBlackTreeMap<K, V, P>

where K: Ord + Serialize, V: Serialize, P: SharedPointerKind,

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

where S: Serializer,

Serialize this value into the given Serde serializer.

impl<K, V, P> Eq for RedBlackTreeMap<K, V, P>

where V: Eq, K: Ord, P: SharedPointerKind,