Struct rpds::map::red_black_tree_map::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, ArcK>where K: Ord,

pub fn new_sync() -> RedBlackTreeMapSync<K, V>

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) -> boolwhere K: Borrow<Q>, Q: Ord + ?Sized,

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

pub fn size(&self) -> usize

pub fn is_empty(&self) -> bool

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

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

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

pub fn range<Q, RB>(&self, range: RB) -> RangeIter<'_, K, V, RB, Q, P>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 copy of the value.

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

Performs copy-assignment from source.

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

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, 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, V: Hash, P: SharedPointerKind> Hash for RedBlackTreeMap<K, V, P>where K: Ord + Hash,

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<'a, K, Q, V, P> Index<&'a 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) -> 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.

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

Compares and returns the maximum of two values.

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

Compares and returns the minimum of two values.

fn clamp(self, min: Self, max: Self) -> Selfwhere Self: Sized + PartialOrd<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 ==.

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

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

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.

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

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

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

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

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

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

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.

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