Module std::set

A hash set, HashSet, of any K: Hash + Eq (see std::cmp): the keys of a std::map::HashMap with no values. As there, methods that may grow the table ask for Alloc (new, with_capacity, insert), those that destroy keys ask for Free (remove, clear), and lookups need no capability.

Source: std/set.weir; committed interface: std/set.iface. Index

struct HashSet

pub struct HashSet<K> {
    /* private fields */
}

A hash set of K, over std::map::HashMap's table: lookup, insert and remove are expected O(1) (insert amortised), and iteration visits the keys in insertion order until a HashSet::remove, which moves the last key into the hole. Keys are hashed as the map's are: fixed secrets for HashSet::new, a secret seed for HashSet::new_randomized and HashSet::with_seed (for keys an attacker chooses). At most 3 · 2^30 keys.

impl<K> HashSet<K>

method len

pub fn len(&self) -> usize

The number of keys.

Committed interface (std/set.iface): the signature alone.

method is_empty

pub fn is_empty(&self) -> Bool

true when the set has no keys.

Committed interface (std/set.iface): the signature alone.

method for_each

pub fn for_each(&self, f: fn(&K))

Calls f on every key, in key order (see HashSet).

Committed interface (std/set.iface):

holds what may not move at a scheduling point: always
enters the backing of self
callback f: envelope {A, S}; pinned: always; holds self, f
writes regions type K

impl<K: copy> HashSet<K>

method iter

pub fn iter(&self) -> SetIter<K>

An iterator over copies of the keys, in insertion order until a remove. It borrows the set while it lives.

Committed interface (std/set.iface): the signature alone.

impl<K: Hash + Eq> HashSet<K>

method contains

pub fn contains(&self, k: &K) -> Bool

true when the set holds a key equal to k.

Committed interface (std/set.iface):

bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet | Hash not quiet
enters the backing of self, k
writes regions type K
loan of Hash across the backing of k
loan of Eq across the backing of self
loan of Eq across the backing of k

impl<K: Hash + Eq + drops {Free}> HashSet<K>

method remove

pub fn remove(&mut self, k: &K) -> Bool with Free

Removes the key equal to k and answers whether there was one. The stored key is destroyed, hence with Free. The last key moves into the removed one's place.

Committed interface (std/set.iface):

bound Free: Free any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet | Hash not quiet
writes through self: {map} and its shape
destroys values of K
writes regions type K
loan of Hash across the backing of self
loan of Hash across the backing of k
loan of Eq across the backing of self
loan of Eq across the backing of k

method clear

pub fn clear(&mut self) with Free

Destroys every key (with Free) and keeps the table's memory for reuse.

Committed interface (std/set.iface):

bound Free: Free any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
scheduling point: Eq not quiet | Hash not quiet
writes through self: {map} and its shape
destroys values of K

impl<K: Hash + Eq + drops {Alloc}> HashSet<K>

method new

pub fn new() -> HashSet<K> with Alloc

An empty set whose hasher has fixed secrets, as std::map::HashMap::new's: the same layout on every run. It allocates nothing until the first HashSet::insert.

Committed interface (std/set.iface):

bound Alloc: Alloc any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet

method with_seed

pub fn with_seed(seed: u64) -> HashSet<K> with Alloc

An empty set whose hasher is keyed by seed (Hasher::with_seed).

Committed interface (std/set.iface):

bound Alloc: Alloc any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet

method new_randomized

pub fn new_randomized() -> HashSet<K> with Alloc, Random

An empty set keyed by a seed drawn from the caller's Random, as std::map::HashMap::new_randomized: for keys an attacker chooses.

Committed interface (std/set.iface):

bound Alloc: Alloc any
bound Random: Random any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet | Random not quiet

method with_capacity

pub fn with_capacity(n: usize) -> HashSet<K> with Alloc

A set that holds n keys without growing.

Committed interface (std/set.iface):

bound Alloc: Alloc any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet

method insert

pub fn insert(&mut self, k: K) -> Bool with Alloc

Adds k and answers whether it was new: false when the set held an equal key, which k then replaces. with Alloc: it may grow the table and the key buffer.

Committed interface (std/set.iface):

bound Alloc: Alloc any
bound Hash: Hash<K> any row {Diverge}
bound Eq: Eq<K> any row {Diverge}
aborts: Alloc.alloc
scheduling point: Eq not quiet | Hash not quiet
holds what may not move at a scheduling point: Eq not quiet
writes through self: everything and its shape
destroys values of K
writes regions type K
loan of Hash across the backing of self
loan of Hash across the backing of k
loan of Eq across the backing of self
loan of Eq across the backing of k

struct SetIter

pub struct SetIter<K>: forget {
    /* private fields */
}

The iterator HashSet::iter returns: copies of the keys, borrowing the set.

Implementations: