Struct more_collections::small_map::SmallMap

pub struct SmallMap<K, V, const C: usize, S = RandomState> { /* private fields */ }

A map-like container that can store a specified number of elements inline.

SmallMap shares most of its API with, and behaves like IndexMap. It can store a limited amount of data inline, backed by SmallVec. If the data exceeds the limit C, SmallMap will move all its data over to the heap in the form of an IndexMap. For performance reasons, transitions between heap and inline storage should generally be avoided.

The SmallMap datastructure is meant for situations where the data does not exceed C most of the time but it still needs to support cases where the data does exceed C.

Example

use more_collections::SmallMap;

let mut map = SmallMap::<usize, String, 3>::new();
// The map can hold up to three items inline
map.insert(0, "zero".to_string());
map.insert(1, "one".to_string());
map.insert(2, "two".to_string());
assert_eq!(3, map.len());
assert!(map.is_inline());

// Adding the fourth item will move the map to the heap
map.insert(3, "three".to_string());
assert_eq!(4, map.len());
assert!(!map.is_inline());

Implementations

impl<K, V, const C: usize> SmallMap<K, V, C>

pub fn new() -> Self

Create a new map.

impl<K, V, const C: usize, S> SmallMap<K, V, C, S>

pub fn len(&self) -> usize

The number of key-values stored in the map.

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

pub const fn inline_capacity(&self) -> usize

The memory capacity that will be allocated inline. If the nubmer of values exceeds the inline capacity, the map will move to the heap.

pub const fn is_inline(&self) -> bool

Is the data contained by this map stored inline (true) or on the heap (false).

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

Returns an iterator over the key-values in insertion order.

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

Returns an iterator over the key-values in insertion order.

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

impl<K, V, const C: usize, S> SmallMap<K, V, C, S>

where K: Hash + Eq, S: BuildHasher,

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where Q: Hash + Equivalent<K> + ?Sized,

Return a reference to the value stored for key, if it is present, else None.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where Q: Hash + Equivalent<K> + ?Sized,

Return a mutable reference to the value stored for key, if it is present, else None.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn get_index(&self, index: usize) -> Option<(&K, &V)>

Get a key-value pair by index, if it is present, else None.

Computational complexity: O(1)

pub fn get_index_mut(&mut self, index: usize) -> Option<(&K, &mut V)>

Get a mutable key-value pair by index, if it is present, else None.

Computational complexity: O(1)

pub fn get_index_of<Q>(&self, key: &Q) -> Option<usize>

where Q: Hash + Equivalent<K> + ?Sized,

Return the item index, if it exists in the map, else None.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn entry(&mut self, key: K) -> Entry<'_, K, V, C, S>

Get the given key’s corresponding entry in the map for insertion and/or in-place manipulation.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn contains_key<Q>(&self, key: &Q) -> bool

where Q: Hash + Equivalent<K> + ?Sized,

Return true if an equivalent to key exists in the map.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn from_map(map: IndexMap<K, V, S>) -> Self

Convert the specified map and turn it into a SmallMap.

If the map len is smaller or equal the inline capacity, the data will be moved inline.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where Q: Hash + Equivalent<K> + ?Sized,

Remove the key-value pair equivalent to key and return its value.

If key is not present None is returned.

If an existing key is removed that causes the size of the SmallMap to be equal to or below the inline capacity, all remaining data after removal of the specified key-value pair is moved to the heap.

The behavior of this method is equivalent to .swap_remove(key) on HashMaps and Vecs, order is not preserved.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn swap_remove_full<Q>(&mut self, key: &Q) -> Option<(usize, K, V)>

where Q: Hash + Equivalent<K> + ?Sized,

Remove the key-value pair equivalent to key and return its index, key, and value.

If key is not present None is returned.

If an existing key is removed that causes the size of the SmallMap to be equal to or below the inline capacity, all remaining data after removal of the specified key-value pair is moved to the heap.

The behavior of this method is equivalent to .swap_remove(key) on HashMaps and Vecs, order is not preserved.

Computational complexity:

• inline: O(n)
• heap: O(1)

pub fn binary_search_by<'a, F>(&'a self, f: F) -> Result<usize, usize>

where F: FnMut((&'a K, &'a V)) -> Ordering,

Binary searches this map with a comparator function.

The comparator function should implement an order consistent with the sort order of the underlying slice, returning an order code that indicates whether its argument is Less, Equal or Greater the desired target.

If the value is found then Result::Ok is returned, containing the index of the matching element. If there are multiple matches, then any one of the matches could be returned.

Errors

If the value is not found then Result::Err is returned, containing the index where a matching element could be inserted while maintaining sorted order.

impl<K, V, const C: usize, S> SmallMap<K, V, C, S>

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

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

Inserts the specified key-value pair into this map.

If a value for the specified key already exists, the new value will overwrite the existing value. The iteration order of the key-value pair will remain in the original position.

If a new key is added that causes the size of the SmallMap to exceed the inline capacity, all existing data and the new key-value pair is moved to the heap.

Computational complexity:

• inline: O(n)
• heap: O(1)

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

Inserts the specified key-value pair into this map, and get their index.

If a value for the specified key already exists, the new value will overwrite the existing value. The iteration order of the key-value pair will remain in the original position.

If a new key is added that causes the size of the SmallMap to exceed the inline capacity, all existing data and the new key-value pair is moved to the heap.

Computational complexity:

• inline: O(n)
• heap: O(1)

Trait Implementations

impl<K: Clone, V: Clone, const C: usize, S: Clone> Clone for SmallMap<K, V, C, S>

fn clone(&self) -> SmallMap<K, V, C, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K, V, const C: usize, S> Debug for SmallMap<K, V, C, S>

where K: Debug, V: Debug,

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

Formats the value using the given formatter.

impl<K, V, const C: usize, S> Default for SmallMap<K, V, C, S>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, const C: usize, S> FromIterator<(K, V)> for SmallMap<K, V, C, S>

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

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

Creates a value from an iterator.

impl<K, V, const C: usize, S> Hash for SmallMap<K, V, C, S>

where K: Hash + Eq, V: Hash + Eq,

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<K, V, Q, const C: usize, S> Index<&Q> for SmallMap<K, V, C, S>

where K: Eq + Hash, Q: Hash + Equivalent<K> + ?Sized, S: BuildHasher,

type Output = V

The returned type after indexing.

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

Performs the indexing (container[index]) operation.

impl<K, V, const C: usize, S> Index<usize> for SmallMap<K, V, C, S>

where K: Eq + Hash, S: BuildHasher,

type Output = V

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<K, V, Q, const C: usize, S> IndexMut<&Q> for SmallMap<K, V, C, S>

where K: Eq + Hash, Q: Hash + Equivalent<K> + ?Sized, S: BuildHasher,

fn index_mut(&mut self, key: &Q) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<K, V, const C: usize, S> IndexMut<usize> for SmallMap<K, V, C, S>

where K: Eq + Hash, S: BuildHasher,

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<'a, K, V, const C: usize, S> IntoIterator for &'a SmallMap<K, V, C, S>

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

Which kind of iterator are we turning this into?

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

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, const C: usize, S> IntoIterator for &'a mut SmallMap<K, V, C, S>

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

Which kind of iterator are we turning this into?

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

The type of the elements being iterated over.

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, const C: usize, S> IntoIterator for SmallMap<K, V, C, S>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, C>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, const C: usize, S> PartialEq for SmallMap<K, V, C, S>

where K: Hash + PartialEq, V: PartialEq,

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<K, V, const C: usize, S> Eq for SmallMap<K, V, C, S>

where K: Hash + Eq, V: Eq,