Struct rpds::map::hash_trie_map::HashTrieMap

pub struct HashTrieMap<K, V, H: BuildHasher = RandomState> { /* fields omitted */ }

A persistent map with structural sharing. This implementation uses a hash array mapped trie.

Complexity

Let n be the number of elements in the map.

Temporal complexity

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

Implementation details

This implementation uses a hash array mapped trie. Details can be found in Ideal Hash Trees.

See the Node documentation for details.

Methods

impl<K, V> HashTrieMap<K, V, RandomState> where
    K: Eq + Hash, 

#[must_use]

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

#[must_use]

pub fn new_with_degree(degree: u8) -> HashTrieMap<K, V>

impl<K, V, H: BuildHasher> HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Clone, 

#[must_use]

pub fn new_with_hasher(hasher_builder: H) -> HashTrieMap<K, V, H>

#[must_use]

pub fn new_with_hasher_and_degree(
    hasher_builder: H,
    degree: u8
) -> HashTrieMap<K, V, H>

#[must_use]

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

#[must_use]

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

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

#[must_use]

pub fn remove<Q: ?Sized>(&self, key: &Q) -> HashTrieMap<K, V, H> where
    K: Borrow<Q>,
    Q: Hash + Eq, 

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

#[must_use]

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

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

Trait Implementations

impl<K, V, H: BuildHasher> Default for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Default + Clone, 

fn default() -> HashTrieMap<K, V, H>

Returns the "default value" for a type.

impl<K: Eq, V: PartialEq, H: BuildHasher> PartialEq<HashTrieMap<K, V, H>> for HashTrieMap<K, V, H> where
    K: Hash,
    H: Clone, 

fn eq(&self, other: &HashTrieMap<K, V, H>) -> 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: Eq, V: Eq, H: BuildHasher> Eq for HashTrieMap<K, V, H> where
    K: Hash,
    H: Clone, 

impl<K, V, H: BuildHasher> Clone for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Clone, 

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, K, V, H: BuildHasher> IntoIterator for &'a HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: Default + Clone, 

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, H: Debug + BuildHasher> Debug for HashTrieMap<K, V, H>

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

Formats the value using the given formatter.

impl<K, V, H: BuildHasher> Display for HashTrieMap<K, V, H> where
    K: Eq + Hash + Display,
    V: Display,
    H: Clone, 

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

Formats the value using the given formatter.

impl<'a, K, Q: ?Sized, V, H: BuildHasher> Index<&'a Q> for HashTrieMap<K, V, H> where
    K: Eq + Hash + Borrow<Q>,
    Q: Hash + Eq,
    H: Clone, 

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<K, V, H> FromIterator<(K, V)> for HashTrieMap<K, V, H> where
    K: Eq + Hash,
    H: BuildHasher + Clone + Default, 

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

Creates a value from an iterator.

impl<K, V, H> Serialize for HashTrieMap<K, V, H> where
    K: Eq + Hash + Serialize,
    V: Serialize,
    H: BuildHasher + Clone + Default, 

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

Serialize this value into the given Serde serializer.

impl<'de, K, V, H> Deserialize<'de> for HashTrieMap<K, V, H> where
    K: Eq + Hash + Deserialize<'de>,
    V: Deserialize<'de>,
    H: BuildHasher + Clone + Default, 

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

Deserialize this value from the given Serde deserializer.