Struct coca::collections::list_map::ListMap

pub struct ListMap<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> { /* private fields */ }

A map based on an association list.

Conventionally, this refers to a linked list of key-value pairs, using a linear scan to find the value associated with a given key. This is simple, though inefficient, particularly on modern computer architectures, where traversing each link in the list is likely to cause a cache miss.

For this reason, this implementation uses arrays instead, one for the keys, one for the values. This way, unrelated values need not be fetched into the cache during the key lookup. Nonetheless, this search is O(n), i.e. it takes time linear in the number of entries, which can be problematic for large maps.

Newly inserted entries are appended to the arrays, and a removed entry is replaced by the last one in the list, meaning modifications have constant overhead after the initial lookup. This also means insertion order is not preserved.

As key search is the primary cost of these operations, care should be taken to avoid redundant lookups. Use the Entry API where applicable.

It is required that the keys implement the Eq trait, although this can frequently be achieved using #[derive(PartialEq, Eq)].

It is a logic error for a key to be modified in such a way that its equality, as determined by the Eq trait, changes while it is in the map. This is normally only possible through Cell, RefCell, global state, I/O, or unsafe code. The behavior resulting from such a logic error is not specified, but will not result in undefined behavior. This could include panics, incorrect results, aborts, memory leaks, and non-termination.

Implementations

impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> ListMap<K, V, S, I>

pub fn capacity(&self) -> usize

Returns the number of entries the map can hold.

pub fn keys(&self) -> &[K]

Returns a slice of all keys in the map in arbitrary order.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
for key in map.keys() {
    println!("{}", key);
}

pub fn values(&self) -> &[V]

Returns a slice of all values in the map in arbitrary order.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
for val in map.values() {
    println!("{}", val);
}

pub fn values_mut(&mut self) -> &mut [V]

Returns a mutable slice of all values in the map in arbitrary order.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
for val in map.values_mut() {
    *val = *val * 2;
}
 
assert_eq!(map.get("a"), Some(&2));
assert_eq!(map.get("b"), Some(&4));
assert_eq!(map.get("c"), Some(&6));

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

An iterator visiting all key-value pairs in arbitrary order. The iterator element type is (&'a K, &'a V).

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
for (key, val) in map.iter() {
    println!("{} -> {}", key, val);
}

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

An iterator visiting all key-value pairs in arbitrary order, with mutable references to the values. The iterator element type is (&'a K, &'a mut V).

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
for (_, val) in map.iter_mut() {
    *val *= 2;
}
 
assert_eq!(map.get("a"), Some(&2));
assert_eq!(map.get("b"), Some(&4));
assert_eq!(map.get("c"), Some(&6));

pub fn len(&self) -> usize

Returns the number of entries in the map.

pub fn is_empty(&self) -> bool

Returns true if the map contains no entries, or false otherwise.

pub fn is_full(&self) -> bool

Returns true if the map contains the maximum number of entries it can hold, or false otherwise.

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

Clears the map without taking ownership, and returns all key-value pairs as an iterator.

If the iterator is only partially consumed, or not consumed at all, all remaining key-value pairs will still be removed.

It is unspecified how many pairs will be removed if a panic occurs while dropping an element, or if the Drain value is leaked.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
 
for (k, v) in map.drain().take(1) {
    let a = k == "a" && v == 1;
    let b = k == "b" && v == 2;
    assert!(a || b);
}
 
assert!(map.is_empty());

pub fn drain_filter<F: FnMut(&K, &mut V) -> bool>(
    &mut self,
    pred: F
) -> DrainFilter<'_, K, V, S, I, F>

Creates an iterator which uses a closure to determine if an element should be removed.

If the closure returns true, the element is removed from the map and yielded. If the closure returns false, or panics, the element remains in the map and will not be yielded.

Note that drain_filter lets you mutate every value in the filter closure, regardless of whether you choose to keep or remove it.

If the iterator is only partially consumed, or not consumed at all, all remaining key-value pairs will still be subjected to the closure and removed and dropped if it returns true.

It is unspecified how many pairs will be subjected to the closure if a panic occurs in the closure, or a panic occurs while dropping an element, or if the DrainFilter value is leaked.

Examples

use coca::collections::{InlineListMap, InlineVec};
 
let mut map = InlineListMap::<u32, u32, 8>::new();
(0..8).for_each(|x| { map.insert(x, x); });
let drained = map.drain_filter(|k, v| { *v = *v * *v; k % 2 == 0 });
 
let mut evens = InlineVec::<u32, 4>::new();
let mut odds = InlineVec::<u32, 4>::new();
 
evens.extend(drained.map(|(_x, x_squared)| x_squared));
evens.sort_unstable();
assert_eq!(evens, [0, 4, 16, 36]);
 
odds.extend(map.into_values());
odds.sort_unstable();
assert_eq!(odds, [1, 9, 25, 49]);

pub fn clear(&mut self)

Clears the map, removing all key-value pairs.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
 
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
map.insert("d", 4);
assert!(map.is_full());
 
map.clear();
assert!(map.is_empty());

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

Gets the given key’s corresponding Entry in the map for in-place manipulation.

Panics

Panics if the map is full and does not contain the given key. See try_entry for a checked version that never panics.

pub fn try_entry(&mut self, key: K) -> Result<Entry<'_, K, V, S, I>, K> where
    K: Eq, 

Gets the given key’s corresponding Entry in the map for in-place manipulation.

Returns [Err(key)] if the map is full and does not contain the given key.

Examples

use coca::collections::InlineListMap;
 
let mut letters = InlineListMap::<char, u32, 32>::new();
 
for ch in "i am, therefore i'm coded".chars() {
    let counter = letters.try_entry(ch).unwrap().or_insert(0);
    *counter += 1;
}
 
assert_eq!(letters.get(&'a'), Some(&1));
assert_eq!(letters.get(&'e'), Some(&4));
assert_eq!(letters.get(&'i'), Some(&2));
assert_eq!(letters.get(&'o'), Some(&2));
assert_eq!(letters.get(&'u'), None);

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

Returns a reference to the value associated with the given key.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
assert_eq!(map.get("a"), Some(&1));
assert_eq!(map.get("b"), None);

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

Returns the key-value pair corresponding to the given key.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
assert_eq!(map.get_key_value("a"), Some((&"a", &1)));
assert_eq!(map.get_key_value("b"), None);

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

Returns true if the map contains a value for the given key, or false otherwise.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
assert_eq!(map.contains_key("a"), true);
assert_eq!(map.contains_key("b"), false);

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

Returns a mutable reference to the value associated with the given key.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
if let Some(x) = map.get_mut(&"a") {
    *x = *x + 2;
}
 
assert_eq!(map.get("a"), Some(&3));

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

Inserts a key-value pair into the map.

If the map did not have this key present, None is returned.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated though; this matters for types that can be == without being identical.

Panics

Panics if the map is full and the given key is not present. See try_insert for a checked version that never panics.

pub fn try_insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> where
    K: Eq, 

Inserts a key-value pair into the map.

If the map did not have this key present, Ok(None) is returned if the key-value pair is inserted, or [Err((key, value))] if the map is full.

If the map did have this key present, the value is updated, and the old value is returned. The key is not updated though; this matters for types that can be == without being identical.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
assert_eq!(map.try_insert("a", 37), Ok(None));
assert_eq!(map.try_insert("a", 42), Ok(Some(37)));
 
map.insert("b", 23);
map.insert("c", 19);
map.insert("d", 8);
assert_eq!(map.is_full(), true);
assert_eq!(map.try_insert("e", 0), Err(("e", 0)));

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

Removes a key from the map, returning the value associated with the key if it was previously in the map.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
assert_eq!(map.remove("a"), Some(1));
assert_eq!(map.remove("a"), None);

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

Removes a key from the map, returning the stored key and associated value if the key was previously in the map.

The key may be any borrowed form of the map’s key type, but Eq on the borrowed form must match that for the key type.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
 
assert_eq!(map.remove_entry("a"), Some(("a", 1)));
assert_eq!(map.remove_entry("a"), None);

pub fn retain<F: FnMut(&K, &mut V) -> bool>(&mut self, pred: F)

Retains only the elements specified by the predicate.

In other words, remove all key-value pairs (k, v) such that pred(&k, &mut v) returns false. The elements are visited in arbitrary (and unspecified) order.

Examples

use coca::collections::InlineListMap;
 
let mut map = InlineListMap::<u32, u32, 8>::new();
(0..8).for_each(|x| { map.insert(x, x*10); });
assert_eq!(map.len(), 8);
 
map.retain(|&k, _| k % 2 == 0);
assert_eq!(map.len(), 4);

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

Creates a consuming iterator visiting all keys in arbitrary order. The map cannot be used after calling this. The iterator element type is K.

Examples

use coca::collections::{InlineListMap, InlineVec};
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
let mut vec = InlineVec::<&'static str, 4>::new();
vec.extend(map.into_keys());
// The keys are visited in arbitrary order,
// so they must be sorted for this test.
vec.sort_unstable();
assert_eq!(vec, ["a", "b", "c"]);

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

Creates a consuming iterator visiting all values in arbitrary order. The map cannot be used after calling this. The iterator element type is K.

Examples

use coca::collections::{InlineListMap, InlineVec};
 
let mut map = InlineListMap::<&'static str, u32, 4>::new();
map.insert("a", 1);
map.insert("b", 2);
map.insert("c", 3);
 
let mut vec = InlineVec::<u32, 4>::new();
vec.extend(map.into_values());
// The values are visited in arbitrary order,
// so they must be sorted for this test.
vec.sort_unstable();
assert_eq!(vec, [1, 2, 3]);

impl<K, V, I: Capacity> ListMap<K, V, AllocStorage<ListMapLayout<K, V>>, I>

pub fn with_capacity(capacity: usize) -> Self

This is supported on crate feature alloc only.

Constructs a new, empty AllocListMap with the specified capacity.

impl<K, V, I: Capacity, const N: usize> ListMap<K, V, InlineStorage<K, V, N>, I>

pub fn new() -> Self

Constructs a new, empty InlineListMap.

Trait Implementations

impl<K: Clone, V: Clone, I: Capacity, const N: usize> Clone for ListMap<K, V, InlineStorage<K, V, N>, I>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, S: Storage<ListMapLayout<K, V>>, I: Capacity> Debug for ListMap<K, V, S, I>

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

Formats the value using the given formatter.

impl<K, V, I: Capacity, const N: usize> Default for ListMap<K, V, InlineStorage<K, V, N>, I>

fn default() -> Self

Returns the “default value” for a type.

impl<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> Drop for ListMap<K, V, S, I>

fn drop(&mut self)

Executes the destructor for this type.

impl<'a, K, V, S, I> Extend<(&'a K, &'a V)> for ListMap<K, V, S, I> where
    K: Clone + Eq,
    V: Clone,
    S: Storage<ListMapLayout<K, V>>,
    I: Capacity, 

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, I> Extend<(K, V)> for ListMap<K, V, S, I> where
    K: Eq,
    S: Storage<ListMapLayout<K, V>>,
    I: Capacity, 

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<K, V, S: Storage<ListMapLayout<K, V>>, I: Capacity> From<S> for ListMap<K, V, S, I>

fn from(buf: S) -> Self

Performs the conversion.

impl<Q, K, V, S, I> Index<&'_ Q> for ListMap<K, V, S, I> where
    Q: Eq + ?Sized,
    K: Eq + Borrow<Q>,
    S: Storage<ListMapLayout<K, V>>,
    I: Capacity, 

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: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for &'a ListMap<K, V, S, I>

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

The type of the elements being iterated over.

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

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: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for &'a mut ListMap<K, V, S, I>

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

The type of the elements being iterated over.

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

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: Storage<ListMapLayout<K, V>>, I: Capacity> IntoIterator for ListMap<K, V, S, I>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V, S, I>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, S1, I1, S2, I2> PartialEq<ListMap<K, V, S2, I2>> for ListMap<K, V, S1, I1> where
    K: Eq,
    V: PartialEq,
    S1: Storage<ListMapLayout<K, V>>,
    S2: Storage<ListMapLayout<K, V>>,
    I1: Capacity,
    I2: Capacity, 

fn eq(&self, other: &ListMap<K, V, S2, I2>) -> bool

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

Note that this is O(1) if the two maps have different sizes, but O(n²) if they are the same size.

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

This method tests for !=.

impl<K: Eq, V: Eq, S: Storage<ListMapLayout<K, V>>, I: Capacity> Eq for ListMap<K, V, S, I>