Struct rpds::set::hash_trie_set::HashTrieSet

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

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

Complexity

Let n be the number of elements in the set.

Temporal complexity

Operation	Best case	Average	Worst case
new()	Θ(1)	Θ(1)	Θ(1)
insert()	Θ(1)	Θ(1)	Θ(n)
remove()	Θ(1)	Θ(1)	Θ(n)
contains()	Θ(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)

Implementation details

This is a thin wrapper around a HashTrieMap.

Methods

impl<T> HashTrieSet<T, RandomState> where
    T: Eq + Hash, 

pub fn new() -> HashTrieSet<T>

pub fn new_with_degree(degree: u8) -> HashTrieSet<T>

impl<T, H: BuildHasher> HashTrieSet<T, H> where
    T: Eq + Hash,
    H: Clone, 

pub fn new_with_hasher(hasher_builder: H) -> HashTrieSet<T, H>

pub fn new_with_hasher_and_degree(
    hasher_builder: H,
    degree: u8
) -> HashTrieSet<T, H>

pub fn insert(&self, v: T) -> HashTrieSet<T, H>

pub fn remove<V: ?Sized>(&self, v: &V) -> HashTrieSet<T, H> where
    T: Borrow<V>,
    V: Hash + Eq, 

pub fn contains<V: ?Sized>(&self, v: &V) -> bool where
    T: Borrow<V>,
    V: Hash + Eq, 

pub fn is_disjoint<I: BuildHasher + Clone>(
    &self,
    other: &HashTrieSet<T, I>
) -> bool

pub fn is_subset<I: BuildHasher + Clone>(
    &self,
    other: &HashTrieSet<T, I>
) -> bool

pub fn is_superset<I: BuildHasher + Clone>(
    &self,
    other: &HashTrieSet<T, I>
) -> bool

pub fn size(&self) -> usize

pub fn is_empty(&self) -> bool

pub fn iter(&self) -> Iter<T>

Trait Implementations

impl<T, H> Serialize for HashTrieSet<T, H> where
    T: Eq + Hash + 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, T, H> Deserialize<'de> for HashTrieSet<T, H> where
    T: Eq + Hash + Deserialize<'de>,
    H: BuildHasher + Clone + Default, 

fn deserialize<D: Deserializer<'de>>(
    deserializer: D
) -> Result<HashTrieSet<T, H>, D::Error>

Deserialize this value from the given Serde deserializer.

impl<T: Debug, H: Debug + BuildHasher> Debug for HashTrieSet<T, H> where
    T: Eq + Hash,
    H: Clone, 

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

Formats the value using the given formatter.

impl<T, H: BuildHasher> Clone for HashTrieSet<T, H> where
    T: Eq + Hash,
    H: Clone, 

fn clone(&self) -> HashTrieSet<T, H>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T, H: BuildHasher> Default for HashTrieSet<T, H> where
    T: Eq + Hash,
    H: Default + Clone, 

fn default() -> HashTrieSet<T, H>

Returns the "default value" for a type.

impl<T: Eq, H: BuildHasher> PartialEq for HashTrieSet<T, H> where
    T: Hash,
    H: Clone, 

fn eq(&self, other: &HashTrieSet<T, 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<T: Eq, H: BuildHasher> Eq for HashTrieSet<T, H> where
    T: Hash,
    H: Clone, 

impl<T, H: BuildHasher> Display for HashTrieSet<T, H> where
    T: Eq + Hash + Display,
    H: Clone, 

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

Formats the value using the given formatter.

impl<'a, T, H: BuildHasher> IntoIterator for &'a HashTrieSet<T, H> where
    T: Eq + Hash,
    H: Default + Clone, 

type Item = &'a T

The type of the elements being iterated over.

type IntoIter = Iter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Iter<'a, T>

Creates an iterator from a value.

impl<T, H> FromIterator<T> for HashTrieSet<T, H> where
    T: Eq + Hash,
    H: BuildHasher + Clone + Default, 

fn from_iter<I: IntoIterator<Item = T>>(into_iter: I) -> HashTrieSet<T, H>

Creates a value from an iterator.