Struct strudel::StHashSet

pub struct StHashSet<T, S = RandomState> { /* private fields */ }

An insertion-ordered hash set implemented as an StHashMap where the value is ().

As with the StHashMap type, a StHashSet requires that the elements implement the Eq and Hash traits.

Implementations

impl<T> StHashSet<T, RandomState>

pub fn new() -> Self

Creates an empty StHashSet.

The hash set is initially created with a capacity of 0, so it will not allocate until it is first inserted into.

Examples

use strudel::StHashSet;
let mut set: StHashSet<i32> = StHashSet::new();
assert_eq!(0, set.capacity());

pub fn with_capacity(capacity: usize) -> Self

Creates an empty StHashSet with the specified capacity.

The hash set will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash set will not allocate.

Examples

use strudel::StHashSet;
let mut set: StHashSet<i32> = StHashSet::with_capacity(10);
assert!(set.capacity() >= 10);

impl<T, S> StHashSet<T, S>

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty StHashSet which will use the given hash builder to hash keys.

The created set has the default initial capacity.

Warning: hash_builder is normally randomly generated, and is designed to allow StHashSets to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hash_builder passed should implement the BuildHasher trait for the StHashSet to be useful, see its documentation for details.

Examples

use strudel::StHashSet;
use std::collections::hash_map::RandomState;

let s = RandomState::new();
let mut set = StHashSet::with_hasher(s);
assert_eq!(0, set.capacity());
set.insert(1);

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

Creates an empty StHashSet with the specified capacity, using the given hash builder to hash keys.

The hash set will be able to hold at least capacity elements without reallocating. If capacity is 0, the hash set will not allocate.

Warning: hash_builder is normally randomly generated, and is designed to allow StHashSets to be resistant to attacks that cause many collisions and very poor performance. Setting it manually using this function can expose a DoS attack vector.

The hash_builder passed should implement the BuildHasher trait for the StHashSet to be useful, see its documentation for details.

Examples

use strudel::StHashSet;
use std::collections::hash_map::RandomState;

let s = RandomState::new();
let mut set = StHashSet::with_capacity_and_hasher(10, s);
assert!(set.capacity() >= 10);
set.insert(1);

pub fn capacity(&self) -> usize

Returns the number of elements the set can hold without reallocating.

This number is a lower bound; the StHashSet might be able to hold more, but is guaranteed to be able to hold at least this many.

Examples

use strudel::StHashSet;
let mut set: StHashSet<i32> = StHashSet::with_capacity(100);
assert!(set.capacity() >= 100);

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

An iterator for visiting all elements in insertion order. The iterator element type is &'a T.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");

for elem in set.iter() {
    println!("element: {}", elem);
}

pub fn insert_ranks_from(&self, rank: usize) -> InsertRanks

An iterator for visiting all insertion counters in insertion order starting from the given rank. The iterator element type is usize.

This iterator may return insertion counters to dead elements.

The yielded elements may be passed to get_nth to retrieve the element in the nth insertion slot.

This API can be used to build a mutable iterator over the set that can safely be invalidated. This is safe because new inserts always have higher insert rank. See api::st_foreach.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");

set.remove(&"a");
set.insert("b");

let insert_ranks = set.insert_ranks_from(0).collect::<Vec<_>>();
assert_eq!(vec![0, 1, 2], insert_ranks);

assert_eq!(None, set.get_nth(0));
assert_eq!(Some(&"b"), set.get_nth(1));
assert_eq!(Some(&"c"), set.get_nth(2));
assert_eq!(None, set.get_nth(4));

assert_eq!(0, set.insert_ranks_from(100).count());

pub fn first(&self) -> Option<&T>

Returns the first element in the set. The element is equal to the element inserted earliest into the set.

Elements are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to elements maintain the same insertion position.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");
assert_eq!(Some(&"a"), set.first());

set.remove(&"a");
set.insert("b");
assert_eq!(Some(&"b"), set.first());

pub fn last(&self) -> Option<&T>

Returns the last element in the set. The element is equal to the element inserted most recently into the set.

Elements are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to elements maintain the same insertion position.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");
assert_eq!(Some(&"c"), set.last());

set.remove(&"a");
set.insert("b");
assert_eq!(Some(&"c"), set.last());

pub fn get_nth(&self, n: usize) -> Option<&T>

Returns the nth element in the set. The element is equal to the element inserted nth earliest into the set.

Elements are ordered by insertion order. Insertion order is maintained if there are deletions. Insertion order is by slot, so in-place updates to elements maintain the same insertion position.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert("a");
set.insert("b");
set.insert("c");

set.remove(&"a");
set.insert("b");

let insert_ranks = set.insert_ranks_from(0).collect::<Vec<_>>();
assert_eq!(vec![0, 1, 2], insert_ranks);

assert_eq!(None, set.get_nth(0));
assert_eq!(Some(&"b"), set.get_nth(1));
assert_eq!(Some(&"c"), set.get_nth(2));
assert_eq!(None, set.get_nth(4));

assert_eq!(0, set.insert_ranks_from(100).count());

pub fn min_insert_rank(&self) -> usize

Insertion counter for the first element in the set.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
assert_eq!(0, set.min_insert_rank());

set.insert("a");
set.insert("b");
set.insert("c");
assert_eq!(0, set.min_insert_rank());

set.remove(&"a");
set.insert("b");
assert_eq!(1, set.min_insert_rank());

pub fn max_insert_rank(&self) -> usize

Insertion counter for the last element in the set.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
assert_eq!(0, set.max_insert_rank());

set.insert("a");
set.insert("b");
set.insert("c");
assert_eq!(2, set.max_insert_rank());

set.remove(&"a");
set.insert("b");
assert_eq!(2, set.max_insert_rank());

pub fn len(&self) -> usize

Returns the number of elements in the set.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
assert_eq!(0, set.len());
set.insert(1);
assert_eq!(1, set.len());

pub fn is_empty(&self) -> bool

Returns true if the set contains no elements.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
assert!(set.is_empty());
set.insert(1);
assert!(!set.is_empty());

pub fn clear(&mut self)

Clears the set, removing all elements. Keeps the allocated memory for reuse.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert(1);
set.clear();
assert!(set.is_empty());

pub fn hasher(&self) -> &S

Returns a reference to the set’s BuildHasher.

Examples

use strudel::StHashSet;
use std::collections::hash_map::RandomState;

let hasher = RandomState::new();
let set: StHashSet<i32> = StHashSet::with_hasher(hasher);
let hasher: &RandomState = set.hasher();

pub fn estimated_memsize(&self) -> usize

Return an estimate of the byte size of memory allocted for this set.

Examples

use strudel::StHashSet;
let empty: StHashSet<i32> = StHashSet::with_capacity(0);
let set: StHashSet<i32> = StHashSet::with_capacity(100);
assert!(set.estimated_memsize() > empty.estimated_memsize());

impl<T, S> StHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more elements to be inserted in the StHashSet. The collection may reserve more space to avoid frequent reallocations.

Panics

Panics if the new allocation size overflows usize.

Examples

use strudel::StHashSet;
let mut set: StHashSet<&str> = StHashSet::new();
assert_eq!(0, set.capacity());
set.reserve(10);
assert!(set.capacity() >= 10);

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the set as much as possible. It will drop down as much as possible while maintaining the internal rules and possibly leaving some space in accordance with the resize policy.

Examples

use strudel::StHashSet;
let mut set: StHashSet<i32> = StHashSet::with_capacity(100);
set.insert(1);
set.insert(3);
assert!(set.capacity() >= 100);
set.shrink_to_fit();
assert!(set.capacity() >= 2);

pub fn contains(&self, element: &T) -> bool

Returns true if the set contains the specified element.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert(1);
assert_eq!(set.contains(&1), true);
assert_eq!(set.contains(&2), false);

pub fn get(&self, element: &T) -> Option<&T>

Returns a reference to the element in the set corresponding to the given value.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert(1);
assert_eq!(set.get(&1), Some(&1));
assert_eq!(set.get(&2), None);

impl<T, S> StHashSet<T, S>

where T: Eq + Hash + Clone, S: BuildHasher,

pub fn insert(&mut self, element: T) -> bool

Adds an element into the set.

If the set did not have this element present, false is returned.

If the set did have this element present, true is returned. The element is not updated, though. To update the element in-place, use StHashSet::update.

pub fn update(&mut self, element: T)

Inserts an element into the set and update the element in place if an entry is already present.

This function maintains the insertion rank of the element.

If you do not wish to update the element in-place, use StHashSet::insert.

pub fn remove(&mut self, element: &T) -> bool

Removes an element from the set, returning the stored element if the element was previously in the set.

Examples

use strudel::StHashSet;

let mut set = StHashSet::new();
set.insert(1);
assert!(set.remove(&1));
assert!(!set.remove(&1));

Trait Implementations

impl<T: Clone, S: Clone> Clone for StHashSet<T, S>

fn clone(&self) -> StHashSet<T, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, S: Debug> Debug for StHashSet<T, S>

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

Formats the value using the given formatter.

impl<T: Default, S: Default> Default for StHashSet<T, S>

fn default() -> StHashSet<T, S>

Returns the “default value” for a type.

impl<'a, T, S> IntoIterator for &'a StHashSet<T, S>

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) -> Self::IntoIter

Creates an iterator from a value.

impl<T, S> IntoIterator for StHashSet<T, S>

type Item = T

The type of the elements being iterated over.

type IntoIter = IntoIter<T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<T, S> PartialEq for StHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,

fn eq(&self, other: &Self) -> 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<T, S> Eq for StHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,