Struct rpds::map::hash_trie_map::HashTrieMap

pub struct HashTrieMap<K, V, H: BuildHasher = RandomState> where
    K: Eq + Hash,
    H: Clone,  { /* fields omitted */ }

A persistent map with structural sharing. This implementation uses a hash array mapped trie and supports fast insert(), remove(), and get().

Complexity

Let n be the number of elements in the vector.

Temporal complexity

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

Space complexity

The space complexity is Θ(n).

Implementation details

This implementation is based on Ideal Hash Trees.

See the Node documentation for details.

Methods

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

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

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

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

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

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

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

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

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

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

fn size(&self) -> usize

fn is_empty(&self) -> bool

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

fn keys<'a>(&'a self) -> Map<Iter<K, V>, fn(_: (&'a K, &V)) -> &'a K>

fn values<'a>(&'a self) -> Map<Iter<K, V>, fn(_: (&K, &'a V)) -> &'a V>

Trait Implementations

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

fn fmt(&self, __arg_0: &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, index: &Q) -> &V

Performs the indexing (container[index]) operation.

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<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 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 ==.

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