Struct OrderedHashSet 

pub struct OrderedHashSet<T, S = DefaultHashBuilder> { /* private fields */ }

A hash set which preserves the order of insertion.

Backed by hashbrown and its default hashing algorithm, currently AHash. The hashing algorithm can be changed on a per-map basis with with_hasher and with_capacity_and_hasher. More details on hashing algorithms and why AHash was selected in the hashbrown crate.

To switch to the same hasher as HashMap use RandomState. This will switch to SipHash, a HashDos resistant algorithm but it may be slower in some cases.

Being backed by a HashMap, this container has all the same requirements on its keys as HashMap. Specifically, Keys must implement Eq and Hash. You can typically derive these for types with #[derive(PartialEq, Eq, hash)]. If you implement these yourself you must ensure the following holds:

k1 == k2 -> hash(k1) == hash(k2)

You are also responsible to ensure Keys do not mutate such that their hash can change while in the map. For more information, check HashMap.

This container has some additional memory overhead on top of its backing HashMap. OrderedHashSet holds two pointers to maintain the linked list. Each Value inserted has the overhead of three pointers, one for the key and two for the linked list properties.

Implementations

impl<T> OrderedHashSet<T, DefaultHashBuilder>

pub fn new() -> Self

Create an empty set.

Capacity is 0 so the set will not allocated until inserted into.

use ordered_hash_map::OrderedHashSet;
let set = OrderedHashSet::<i32>::new();

pub fn with_capacity(capacity: usize) -> Self

Create an empty set with at least the specified capacity.

The map will allocate if capacity is nonzero.

use ordered_hash_map::OrderedHashSet;
let set = OrderedHashSet::<i32>::with_capacity(10);
assert!(set.capacity() >= 10)

pub fn drain(&mut self) -> Drain<'_, T>

Returns a draining iterator over the elements in insertion order.

Performance

This iterator visits each element once instead of each bucket once. This iterator is O(len) which a usual map iterator is O(capacity) and may visit empty buckets.

let mut set: OrderedHashSet<i32> = [1i32, 2, 3, 4, 5].iter().collect();
assert_eq!(set.drain().next(), Some(1));
assert!(set.is_empty());

impl<T, S> OrderedHashSet<T, S>

pub const fn with_hasher(hash_builder: S) -> Self

Returns a draining iterator over the elements in insertion order.

Performance

This iterator visits each element once instead of each bucket once. This iterator is O(len) which a usual map iterator is O(capacity) and may visit empty buckets.

use std::collections::hash_map::RandomState;

let rs = RandomState::new();
let set = OrderedHashSet::<i32, _>::with_hasher(rs);

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

Create an empty set with the given capacity and which will use the given hasher.

The map will allocate if capacity is nonzero.

use std::collections::hash_map::RandomState;

let rs = RandomState::new();
let set = OrderedHashSet::<i32, _>::with_capacity_and_hasher(10, rs);
assert!(set.capacity() >= 10)

pub fn hasher(&self) -> &S

Returns a reference to the sets hasher.

use std::collections::hash_map::RandomState;

let rs = RandomState::new();
let set = OrderedHashSet::<i32, _>::with_hasher(rs);
let rs: &RandomState = set.hasher();

pub fn capacity(&self) -> usize

The number of elements the set can hold without reallocating.

pub fn len(&self) -> usize

The number of elements currently held in the set.

pub fn is_empty(&self) -> bool

Returns whether the set is empty.

pub fn clear(&mut self)

Removes all values from the set.

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

Returns an iterator over the elements in insertion order.

Performance

This iterator visits each element once instead of each bucket once. This iterator is O(len) which a usual map iterator is O(capacity) and may visit empty buckets.

impl<T, S> OrderedHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,

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

Insert a new element into the set. Returns whether the key already existed.

let mut set = OrderedHashSet::<i32>::new();
assert!(!set.insert(4));
assert!(set.insert(4));

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

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value stored in the set.

let mut set = OrderedHashSet::<String>::new();
set.insert("A".to_string());
// Stored as String but can use &str to get
assert_eq!(set.get("A"), Some(&String::from("A")));

pub fn remove<Q>(&mut self, value: &Q) -> bool

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Remove an element from the set, returning whether or not the element existed.

pub fn take<Q>(&mut self, value: &Q) -> Option<T>

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Remove and return an element from the set

pub fn contains<Q>(&mut self, value: &Q) -> bool

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Check if the set contains this key.

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

Reserves capacity for at least additional more elements.

Panics

Panics if the new size would overflow a usize.

pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError>

Tries to reserve capacity for at least additional more elements.

Errors

Returns an error if the new size would overflow a usize.

pub fn shrink_to_fit(&mut self)

Shrinks the map as much as possible. May leave some space in accordance with the resize policy.

pub fn shrink_to(&mut self, min_capacity: usize)

Shrinks the map down to a lower limit. May leave some space in accordance with the resize policy.

pub fn pop_back(&mut self) -> Option<T>

Removes and returns the most recently inserted value, if there is one.

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

Returns the most recently inserted value, if there is one

pub fn pop_front(&mut self) -> Option<T>

Remove and return the least recently inserted value, if there is one.

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

Returns the most recently inserted value, if there is one

pub fn move_to_front<Q>(&mut self, key: &Q)

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Move an element to the front of the list

pub fn move_to_back<Q>(&mut self, key: &Q)

where T: Borrow<Q>, Q: Hash + Eq + ?Sized,

Move and element to the back of the list

Trait Implementations

impl<T, S> Clone for OrderedHashSet<T, S>

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

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T, S> Debug for OrderedHashSet<T, S>

where T: Debug,

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

Formats the value using the given formatter.

impl<T, S> Default for OrderedHashSet<T, S>

where S: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<'de, T> Deserialize<'de> for OrderedHashSet<T>

where T: Eq + Hash + Deserialize<'de>,

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl<'a, T, S> Extend<&'a T> for OrderedHashSet<T, S>

where T: 'a + Eq + Hash + Copy, S: BuildHasher,

fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<T, S> Extend<T> for OrderedHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,

fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<'a, T, S> FromIterator<&'a T> for OrderedHashSet<T, S>

where T: 'a + Eq + Hash + Copy, S: BuildHasher + Default,

fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T, S> FromIterator<T> for OrderedHashSet<T, S>

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

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self

Creates a value from an iterator.

impl<T, Q, S> Index<&Q> for OrderedHashSet<T, S>

where T: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, S: BuildHasher,

type Output = T

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, T, S> IntoIterator for &'a OrderedHashSet<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 OrderedHashSet<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 OrderedHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,

fn eq(&self, other: &OrderedHashSet<T, S>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T, S> Serialize for OrderedHashSet<T, S>

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

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

where Ser: Serializer,

Serialize this value into the given Serde serializer.

impl<T, S> Eq for OrderedHashSet<T, S>

where T: Eq + Hash, S: BuildHasher,