Struct ordered_hash_map::OrderedHashMap

pub struct OrderedHashMap<K, V, S = DefaultHashBuilder> { /* private fields */ }

A hash map which preserved 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 overhead on top of its backing HashMap. OrderedHashMap 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<K, V> OrderedHashMap<K, V, DefaultHashBuilder>

pub fn new() -> Self

Create an empty map.

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

pub fn with_capacity(capacity: usize) -> Self

Create an empty map with at least the specified capacity.

The map will allocate if capacity is nonzero.

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

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.

impl<K, V, S> OrderedHashMap<K, V, S>

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

Create an empty map which will use the given hasher.

Capacity is 0 so the map will not allocate until inserted into.

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

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

The map will allocate if capacity is nonzero.

pub fn hasher(&self) -> &S

Returns a reference to the maps hasher.

pub fn capacity(&self) -> usize

The number of elements the map can hold without reallocating.

pub fn len(&self) -> usize

The number of elements currently held in the map.

pub fn is_empty(&self) -> bool

Returns whether the map is empty.

pub fn clear(&mut self)

Removes all key-value pairs from the map.

pub fn keys(&self) -> Keys<'_, K, V>

Returns an iterator over the keys 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.

pub fn into_keys(self) -> IntoKeys<K, V>

Returns an iterator over the keys 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.

pub fn values(&self) -> Values<'_, K, V>

Returns an iterator over the values 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.

pub fn into_values(self) -> IntoValues<K, V>

Returns an iterator over the values 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.

pub fn values_mut(&mut self) -> ValuesMut<'_, K, V>

Returns a mutable value iterator over the values 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.

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

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.

pub fn iter_mut(&mut self) -> IterMut<'_, K, V>

Returns a mutable value 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<K, V, S> OrderedHashMap<K, V, S>where K: Eq + Hash, S: BuildHasher,

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Insert a new element into the map. If that key was associated with a value, returns the old element, otherwise None.

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

Returns a reference to the value stored in the map.

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

Returns a mutable reference to the value stored in the map.

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

Returns a reference to the key and value stored in the map

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

Returns a reference to key and mutable reference to value stored in the map

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

Remove an element from the map, retuning the stored value if there is one.

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

Remove an element from the map, returning the key and value if here is one.

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

Check if the map 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_entry(&mut self) -> Option<(K, V)>

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

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

Removed and returns the most recently inserted element, if there is one.

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

Get the element at the back

pub fn back_mut(&mut self) -> Option<&mut V>

Get a mutable reference to the element at the back

pub fn pop_front_entry(&mut self) -> Option<(K, V)>

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

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

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

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

Get the element at the front

pub fn front_mut(&mut self) -> Option<&mut V>

Get a mutable reference to the element at the front

pub fn move_to_front<Q>(&mut self, key: &Q)where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Move an element to the front of the list

Trait Implementations

impl<K, V, S> Clone for OrderedHashMap<K, V, S>where K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone,

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, S> Debug for OrderedHashMap<K, V, S>where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V, S> Default for OrderedHashMap<K, V, S>where S: Default,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, S> Drop for OrderedHashMap<K, V, S>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V, S> Extend<(&'a K, &'a V)> for OrderedHashMap<K, V, S>where K: Eq + Hash + Copy, V: Copy, S: BuildHasher,

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

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<K, V, S> Extend<(K, V)> for OrderedHashMap<K, V, S>where K: Eq + Hash, S: BuildHasher,

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

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, K, V, S> FromIterator<(&'a K, &'a V)> for OrderedHashMap<K, V, S>where K: Eq + Hash + Copy, V: Copy, S: BuildHasher + Default,

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

Creates a value from an iterator.

impl<K, V, S> FromIterator<(K, V)> for OrderedHashMap<K, V, S>where K: Eq + Hash, S: BuildHasher + Default,

fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self

Creates a value from an iterator.

impl<K, Q, V, S> Index<&Q> for OrderedHashMap<K, V, S>where K: Eq + Hash + Borrow<Q>, Q: Eq + Hash + ?Sized, S: BuildHasher,

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<'a, K, V, S> IntoIterator for &'a OrderedHashMap<K, V, S>

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

Creates an iterator from a value.

impl<'a, K, V, S> IntoIterator for &'a mut OrderedHashMap<K, V, S>

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S> IntoIterator for OrderedHashMap<K, V, S>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S> PartialEq<OrderedHashMap<K, V, S>> for OrderedHashMap<K, V, S>where K: Eq + Hash, V: PartialEq, S: BuildHasher,

fn eq(&self, other: &OrderedHashMap<K, V, S>) -> 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<K, V, S> Eq for OrderedHashMap<K, V, S>where K: Eq + Hash, V: Eq, S: BuildHasher,

impl<K: Send, V: Send, S: Send> Send for OrderedHashMap<K, V, S>

impl<K: Sync, V: Sync, S: Sync> Sync for OrderedHashMap<K, V, S>