Struct TotalOrderMultiMap

pub struct TotalOrderMultiMap<K, V>
where
    V: StableDeref + DerefMut,
    K: Hash + Eq + Copy,
{ /* private fields */ }

A multi map with keeps the total ordering of inserted elements

The map is meant to contain values implementing StableDeref, methods like get and iter will iterate over the inner values referred to when dereferencing the values.

The key is currently limited to values implementing Copy.

See the module/crate level documentation for more details.

Unwind Safety

This type is unwind + resume safe. Through in the unlikely case that a panic happens inside of a function like insert,get the resulting state might be inconsistent in a safe way, i.e. some values might be in the map, accessible during iteration but hey won’t appear when using get.

Note that this can only happen in a few rare cases:

1. Vec::pop/Vec::reserve panics
2. HashMap::insert/HashMap::reserve panics
3. for some reason oom does panic instead of aborting

Which mainly can happen in mainly following cases:

• the vector of key-value pairs tries to contain more then isize::MAX bytes
• you use zero-sized values and overflow usize (which can’t really happen as we store at last some data per inserting, i.e. you would overflow the vec first)

Generally speaking you won’t run into any of this in normal circumstances and if you do it’s likely that you are close to a system wide oom anyway.

Implementations

impl<K, V> TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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

Returns a iterator over the key value pairs in insertion order.

As this is a multi map a key can appear more than one time.

Examples found in repository

examples/from_readme.rs (line 25)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

impl<K, V> TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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

impl<K, V> TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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

return a entry for a given key

impl<K, V> TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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

Return an iterator the keys of this multi map.

each key will only be returned once, there is no specific order in which they keys are returned

pub fn group_iter(&self) -> GroupedValues<'_, K, V::Target>

Returns a iterator over all values grouped by key.

pub fn group_iter_mut(&mut self) -> GroupedValuesMut<'_, K, V::Target>

Returns a iterator over all values grouped by key

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

Returns a iterator over the inner-values in this multi map.

Inner-Values are returned in the order they where inserted into the map. Note that

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

Returns a iterator over the values in this multi map.

impl<K, V> TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

pub fn new() -> Self

Create a new empty map.

Examples found in repository

examples/from_readme.rs (line 16)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

pub fn with_capacity(capacity: usize) -> Self

Crate a new map with a given capacity.

Note that this method will reserve the given capacity for the internal Vec and HashMap, but as it’s a multi map it can not know how elements will be distributed, as such using with_capacity does not guarantee that there are no allocations if less than capacity elements are inserted. Through it still can reduce the number of allocations needed.

pub fn capacity(&self) -> usize

Returns the capacity (unreliable).

This is not reliable as it only returns the capacity of the underlying Vec not considering the underlying HashMap or the Vec used to turn the map into a multi map.

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

Reserves space for n additional elements.

The reservation is done in both the internal Vec and HashMap but as the map is a multi map this method is less helpful as e.g. on a pure Vec or HashMap

Panics

if the new allocation size overflows usize

pub fn reverse(&mut self)

Reverses insertion order.

After calling this the map will contains values as if they had been inserted in reversed order.

This will affect both the iteration order of the fill map as well as the iteration order of values returned by get.

pub fn shrink_to_fit(&mut self)

Shrinks all internal containers to not contains any additional capacity.

Whether or not memory is freed depends in the dens on the shrink_to_fit implementation of Vec and HashMap

pub fn len(&self) -> usize

Returns the total number of elements.

pub fn key_count(&self) -> usize

Returns the total number of different keys.

pub fn is_empty(&self) -> bool

Returns true if the map is empty.

pub fn clear(&mut self)

Empties this map.

pub fn contains_key(&self, k: K) -> bool

Returns true if the key is contained in the map.

Does not state how many values are associated with it.

pub fn get(&self, k: K) -> EntryValues<'_, V::Target>

Returns values associated with the given key.

If the key is not in the map this will return None. This also means that EntryValues has at last one element.

Examples found in repository

examples/from_readme.rs (line 45)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

pub fn get_mut(&mut self, k: K) -> EntryValuesMut<'_, V::Target>

Returns mutable references associated with the given key.

If the key is not in the map this will return None. This means the EntryValuesMut has at last one element.

pub fn add(&mut self, key: K, value: V) -> EntryValuesMut<'_, V::Target>

Adds a value for a given key to the multi map.

Returns access the all values already added to the key previously and this now added value through EntryValuesMut

Examples found in repository

examples/from_readme.rs (line 18)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

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

Sets the value associated with the given key.

Values previously associated with the key are removed and returned.

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

Remove and return the element last inserted.

Examples found in repository

examples/from_readme.rs (line 55)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

pub fn truncate(&mut self, to_len: usize)

Keeps the first to_len inserted headers, removing the remaining ones.

If to_len is equal or larger the current length nothing will happen.

This won’t affect the capacity.

Which headers are keeps/removed depends on the insertion order of the headers in the map and is independent of the headers name or if there had been other headers with the same name inserted before/after.

pub fn remove_all(&mut self, key_to_remove: K) -> bool

removes all values associated with the given key

I.e. this removes all key-value pairs which key is equal to the given key.

Returns true if at last one value was removed

Examples found in repository

examples/from_readme.rs (line 60)

fn main() {
    let mut map = TotalOrderMultiMap::<Key, Value>::new();

    map.add("key1", mk_box_str("val1"));
    map.add("key1", mk_my_thingy("val2"));
    map.add("key2", mk_box_str("val3"));
    map.add("key1", mk_my_thingy("val4"));
    map.add("key0", mk_box_str("val5"));

    let stringed = map
        .iter()
        // val is of type `&Display`
        .map(|(key, val)| format!("{}:{}", key, val))
        .collect::<Vec<_>>();

    // as it can be seen the total insertion order was kept
    assert_eq!(stringed, &[
        "key1:val1".to_owned(),
        "key1:val2".to_owned(),
        "key2:val3".to_owned(),
        "key1:val4".to_owned(),
        "key0:val5".to_owned()
    ]);

    // It's also still a multi map.
    // Note that the get operation has roughly the same
    // performance as in a hash map (through you then
    // iterate over the elements associated with the key
    // roughly with the speed of iterating over an `Vec`).
    {
        let values = map.get("key1");
        let stringed = values
            .map(|val| format!("{}", val))
            .collect::<Vec<_>>();

        assert_eq!(stringed, &[ "val1", "val2", "val4" ]);
    }

    // but as we have an order we can remove
    // "the last inserted" element
    let (key, val) = map.pop().unwrap();
    assert_eq!(format!("{}:{}", key, val), "key0:val5");

    // or remove all for an specific key as it's
    // an multi map
    map.remove_all("key1");
    assert_eq!(0, map.get("key1").len(), "expected no values for key1");

    println!("DONE (I only contain asserts)")
}

pub fn retain<FN>(&mut self, func: FN)

where FN: FnMut(K, &V::Target) -> bool,

retains only key value pairs for which func returns true

All key-value pairs for with the predicate func returns false will be removed.

Trait Implementations

impl<K, V> Clone for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut + Clone,

fn clone(&self) -> Self

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<K, V> Debug for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy + Debug, V: StableDeref + DerefMut + Debug,

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

Formats the value using the given formatter.

impl<K, V> Default for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> Extend<(K, V)> for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

fn extend<I>(&mut self, src: I)

where I: IntoIterator<Item = (K, V)>,

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> FromIterator<(K, V)> for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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

Creates a value from an iterator.

impl<K, V> IntoIterator for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut,

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> PartialEq for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut + PartialEq<V>,

Compares for equality which does consider the insertion order

fn eq(&self, other: &Self) -> 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<K, V> Eq for TotalOrderMultiMap<K, V>

where K: Hash + Eq + Copy, V: StableDeref + DerefMut + Eq,

Compares for equality which does consider the insertion order

impl<K, V> Send for TotalOrderMultiMap<K, V>

where SyncSendHelper<K, V>: Send, V: StableDeref + DerefMut, K: Hash + Eq + Copy,

see SendSyncHelper

impl<K, V> Sync for TotalOrderMultiMap<K, V>

where SyncSendHelper<K, V>: Sync, V: StableDeref + DerefMut, K: Hash + Eq + Copy,

see SendSyncHelper