Struct LinkedHashMap

Source

pub struct LinkedHashMap<K, V>where
    K: Hash + Eq,
{ /* private fields */ }

Expand description

A fast and flexible LinkedHashMap that combines a std::collections::HashMap and a LinkedList for O(1) inserts, lookups and deletes along with a predictable iteration order.

All the basic functions - get(), get_mut(), get_key_value(), put(), insert(), remove(), remove_entry() - provide constant time performance which is expected to be lower than that of the Hashmap given the added expense of of maintaining and updating the underlying linked list.

§Getting Started

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

assert_eq!(lhm.get(&1), Some(&"a"));
assert_eq!(lhm.get(&2), Some(&"b"));

if let Some(val) = lhm.get_mut(&1) {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));

§Iteration Order

This map holds a LinkedList of all the elements that defines the iteration order. The order is either InsertionOrder or AccessOrder. InsertionOrder is the order in which the keys were inserted into the map from least recently inserted (oldest) to most recently inserted (newest). ReInserting a key (via the insert or put methods) will change the insertion order to make the re-inserted key the most recently inserted (newest) in the order.

AccessOrder is the order in which the keys in the map were last accessed (via the get(), get_key_value(), get_mut() methods) from least-recently accessed (oldest) to most recently accessed (newest). Iterating over the map using one of the iterators - iter(), iter_mut(), keys(), values(), values_mut() - does not affect the order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. The iteration order of the map is always from oldest entry (accessed or inserted) to the newest entry (accessed or inserted).

The map offers iterators over the elements, keys and values with mutable iterators for elements and values. The iterators can also be reversed.

// Construct a map in InsertionOrder
use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);


// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);
iter = iter.reverse();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), None);

§Evicting Elements

The Map also supports construction with an evict_eldest function that can be provided to implement a policy for removing entries when new elements are added to the map. A LinkedHashMap with AccessOrder and an eviction function is well suited to building an LRU Cache.

use deepmesa_collections::lhmap::Entry;
pub fn evict<K,V>(len: usize, capacity: usize, e: &Entry<K, V>) -> bool {
    if len > capacity {
        return true;
    }
    return false;
}

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(3, Order::AccessOrder, Some(evict));
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

assert_eq!(lhm.get(&2), Some(&"b"));
lhm.put(4, "d");
assert_eq!(lhm.get(&1), None);

§Head/Tail Semantics

This LinkedHashMap uses the following head/tail semantics:

Head: Contains the oldest elements (least recently inserted/accessed)
Tail: Contains the newest elements (most recently inserted/accessed)
Iteration: Always proceeds from head to tail (oldest to newest)
Eviction: Removes elements from the head (oldest elements first)

New elements are added to the tail, and in AccessOrder mode, accessed elements are moved to the tail (marking them as most recently used).

Implementations§

Source §

impl<K, V> LinkedHashMap<K, V>
where K: Hash + Eq,

Source

pub fn new( capacity: usize, order: Order, evict_eldest: Option<fn(len: usize, capacity: usize, e: &Entry<K, V>) -> bool>, ) -> LinkedHashMap<K, V>

Creates an empty LinkedHashMap with the specified capacity and iteration order. The evict_eldest function can be supplied that is called everytime a new entry is inserted into the map with the current length, capacity and the first entry in the linkedlist (least recently inserted or accessed).

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;
let lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);

Source

pub fn with_capacity(capacity: usize) -> LinkedHashMap<K, V>

Creates an empty LinkedHashMap with the specified capacity and InsertionOrder. The underlying list will continue to reallocate additional memory by doubling the capacity everytime the capacity is exceeded. However the list will not deallocate memory when keys are removed.

If the capacity is set to 0, and the underlying list is full, then new memory will be allocated for one new element everytime an element is added to the list.

The underlying hashmap will only allocate memory if the capacity is greater than zero.

§Examples

use deepmesa_collections::LinkedHashMap;
let lhm = LinkedHashMap::<u16, &str>::with_capacity(10);
assert_eq!(lhm.capacity(), 10);
assert_eq!(lhm.len(), 0);

Source

pub fn capacity(&self) -> usize

Returns the number of elements the map can hold before new memory is allocated.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(10, lhm.capacity());
assert_eq!(0, lhm.len());

Source

pub fn len(&self) -> usize

Returns the number or elements in the map.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(lhm.len(), 0);
lhm.insert(1, "a");
assert_eq!(lhm.len(), 1);

Source

pub fn clear(&mut self)

Removes and drops all the key-value pairs this map. This has no effect on the allocated capacity of the map or the underlying list.

This method should complete in O(n) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.clear();
assert!(lhm.is_empty());

Source

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements and false otherwise. This method should complete in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert!(lhm.is_empty());
lhm.insert(1, "a");
assert!(!lhm.is_empty());

Source

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

Returns true if the map contains a value for the specified key. This method should complete in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.contains_key(&1), true);
assert_eq!(lhm.contains_key(&2), false);

Source

pub fn entry_handle(&self, key: &K) -> Option<EntryHandle<K, V>>

Returns a handle to the entry corresponding to the key, or None if the key is not present in the map.

The returned handle can be used to manipulate the position of the entry within the map’s iteration order without affecting the iteration order of access methods like get(), get_mut(), etc.

This method should complete in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");
lhm.insert(3, "c");

// Get handle for key 1
if let Some(handle) = lhm.entry_handle(&1) {
    // Move it to the end of iteration order
    lhm.make_tail(handle);
}

// Now iteration order will be: 2, 3, 1
let keys: Vec<_> = lhm.keys().copied().collect();
assert_eq!(keys, vec![2, 3, 1]);

// Non-existent key returns None
assert_eq!(lhm.entry_handle(&99), None);

Source

pub fn make_tail(&mut self, eh: EntryHandle<K, V>) -> bool

Moves the entry associated with the given handle to the tail of the LinkedHashMap’s iteration order (making it the most recently used).

If the entry is already at the tail of the iteration order, this operation has no effect. This method works regardless of whether the map uses InsertionOrder or AccessOrder.

Returns true if the entry was successfully moved to the tail (or was already at the tail), and false if the handle is invalid.

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

if let Some(handle) = lhm.entry_handle(&1) {
    assert!(lhm.make_tail(handle));
     
    // Now key 1 will be the last in iteration order
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![2, 3, 1]);
}

Source

pub fn make_head(&mut self, eh: EntryHandle<K, V>) -> bool

Moves the entry associated with the given handle to the head of the LinkedHashMap’s iteration order (making it the least recently used).

If the entry is already at the head of the iteration order, this operation has no effect. This method works regardless of whether the map uses InsertionOrder or AccessOrder.

Returns true if the entry was successfully moved to the head (or was already at the head), and false if the handle is invalid.

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

if let Some(handle) = lhm.entry_handle(&3) {
    assert!(lhm.make_head(handle));
     
    // Now key 3 will be the first in iteration order
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![3, 1, 2]);
}

Source

pub fn get_entry(&self, handle: &EntryHandle<K, V>) -> Option<(&K, &V)>

Returns a reference to the key-value pair associated with the given EntryHandle.

This method provides O(1) access to an entry using its handle, without affecting the iteration order (unlike get() which may move accessed entries to the tail in AccessOrder mode).

Returns Some((key, value)) if the handle is valid, or None if the handle is invalid (e.g., the entry was removed from the map).

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

if let Some(handle) = lhm.entry_handle(&2) {
    // Get the entry without affecting iteration order
    assert_eq!(lhm.get_entry(&handle), Some((&2, &"b")));
     
    // Verify order is unchanged
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![1, 2, 3]);
}

// Invalid handle returns None
let invalid_handle = deepmesa_collections::lhmap::EntryHandle::default();
assert_eq!(lhm.get_entry(&invalid_handle), None);

Source

pub fn get_key(&self, handle: &EntryHandle<K, V>) -> Option<&K>

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

This method provides O(1) access to just the key of an entry using its handle, without affecting the iteration order. This is useful when you only need the key and want to avoid destructuring the result of get_entry().

Returns Some(key) if the handle is valid, or None if the handle is invalid (e.g., the entry was removed from the map).

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

if let Some(handle) = lhm.entry_handle(&2) {
    // Get just the key without affecting iteration order
    assert_eq!(lhm.get_key(&handle), Some(&2));
     
    // Verify order is unchanged
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![1, 2, 3]);
}

// Invalid handle returns None
let invalid_handle = deepmesa_collections::lhmap::EntryHandle::default();
assert_eq!(lhm.get_key(&invalid_handle), None);

Source

pub fn get_value(&self, handle: &EntryHandle<K, V>) -> Option<&V>

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

This method provides O(1) access to just the value of an entry using its handle, without affecting the iteration order. This is useful when you only need the value and want to avoid destructuring the result of get_entry().

Returns Some(value) if the handle is valid, or None if the handle is invalid (e.g., the entry was removed from the map).

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

if let Some(handle) = lhm.entry_handle(&2) {
    // Get just the value without affecting iteration order
    assert_eq!(lhm.get_value(&handle), Some(&"b"));
     
    // Verify order is unchanged
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![1, 2, 3]);
}

// Invalid handle returns None
let invalid_handle = deepmesa_collections::lhmap::EntryHandle::default();
assert_eq!(lhm.get_value(&invalid_handle), None);

Source

pub fn get_value_mut(&mut self, handle: &EntryHandle<K, V>) -> Option<&mut V>

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

This method provides O(1) mutable access to the value of an entry using its handle, without affecting the iteration order. This allows you to modify the value in-place while preserving the entry’s position in the map.

Returns Some(value) if the handle is valid, or None if the handle is invalid (e.g., the entry was removed from the map).

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, String>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a".to_string());
lhm.put(2, "b".to_string());
lhm.put(3, "c".to_string());

if let Some(handle) = lhm.entry_handle(&2) {
    // Mutate the value without affecting iteration order
    if let Some(value) = lhm.get_value_mut(&handle) {
        value.push_str("_modified");
    }
     
    // Verify the change
    assert_eq!(lhm.get_value(&handle), Some(&"b_modified".to_string()));
     
    // Verify order is unchanged
    let keys: Vec<_> = lhm.keys().copied().collect();
    assert_eq!(keys, vec![1, 2, 3]);
}

// Invalid handle returns None
let invalid_handle = deepmesa_collections::lhmap::EntryHandle::default();
assert_eq!(lhm.get_value_mut(&invalid_handle), None);

Source

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

Removes and returns the head (oldest) entry from the LinkedHashMap.

The head entry is the least recently inserted or accessed entry depending on the map’s order mode. This is the same entry that would be removed by the eviction policy.

Returns Some((key, value)) if an entry was removed, or None if the map is empty.

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

// Remove the head (oldest entry)
assert_eq!(lhm.remove_head(), Some((1, "a")));
assert_eq!(lhm.remove_head(), Some((2, "b")));
assert_eq!(lhm.remove_head(), Some((3, "c")));
assert_eq!(lhm.remove_head(), None);

Returns a reference to the head (oldest) entry in the LinkedHashMap.

The head entry is the least recently inserted or accessed entry depending on the map’s order mode. This is the entry that would be removed by the eviction policy.

Returns Some((&key, &value)) if the map is not empty, or None if the map is empty.

This operation completes in O(1) time and does not modify the map.

Returns a reference to the entry at the head of the LinkedHashMap.

This method does not change the access order and works the same regardless of whether the map uses InsertionOrder or AccessOrder. Unlike insertion operations, this method is purely a read operation and will not affect the ordering of entries.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
assert_eq!(lhm.head(), None);

lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

// Head is the oldest entry
assert_eq!(lhm.head(), Some((&1, &"a")));

Source

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

Source

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

Removes and returns the tail (newest) entry from the LinkedHashMap.

The tail entry is the most recently inserted or accessed entry depending on the map’s order mode. This is the opposite of the entry that would be removed by the eviction policy.

Returns Some((key, value)) if an entry was removed, or None if the map is empty.

This operation completes in O(1) time.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

// Remove the tail (newest entry)
assert_eq!(lhm.remove_tail(), Some((3, "c")));
assert_eq!(lhm.remove_tail(), Some((2, "b")));
assert_eq!(lhm.remove_tail(), Some((1, "a")));
assert_eq!(lhm.remove_tail(), None);

Returns a reference to the tail (newest) entry in the LinkedHashMap.

The tail entry is the most recently inserted or accessed entry depending on the map’s order mode. This is the opposite of the entry that would be removed by the eviction policy.

Returns Some((&key, &value)) if the map is not empty, or None if the map is empty.

This operation completes in O(1) time and does not modify the map.

Returns a reference to the entry at the tail of the LinkedHashMap.

This method does not change the access order and works the same regardless of whether the map uses InsertionOrder or AccessOrder. Unlike insertion operations, this method is purely a read operation and will not affect the ordering of entries.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
assert_eq!(lhm.tail(), None);

lhm.put(1, "a");
lhm.put(2, "b");
lhm.put(3, "c");

// Tail is the newest entry
assert_eq!(lhm.tail(), Some((&3, &"c")));

Source

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

Source

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

Returns a reference to the value corresponding to the key. If the Map was created with AccessOrder then the key accessed is moved to the tail of the underlying linked list (most recently used).

If the key is not present then this method returns None and the order is unaffected.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

assert_eq!(lhm.get(&1), Some(&"a"));
assert_eq!(lhm.get(&3), None);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);

Source

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

Returns the key-value pair corresponding to the supplied key. the Map was created with AccessOrder then the key accessed is moved to the tail of the underlying linked list (most recently accessed).

If the key is not present then this method returns None and the order is unaffected.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

assert_eq!(lhm.get_key_value(&1), Some((&1, &"a")));
assert_eq!(lhm.get(&3), None);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), None);

Source

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

Returns a mutable reference to the value corresponding to the key. If the Map was created with AccessOrder then the key accessed is moved to the tail of the underlying linked list (most recently used).

If the key is not present then this method returns None and the order is unaffected.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
lhm.insert(2, "b");

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

if let Some(val) = lhm.get_mut(&1) {
    *val = "d";
}

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"d")));
assert_eq!(iter.next(), None);

Source

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

Removes a key from the map, returning the value at the key if the key was previously in the map. If the key was not present then this method returns None. The iteration order is not affected by this method except to remove the specified key from the underlying linked list.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.remove(&1), Some("a"));
assert_eq!(lhm.remove(&1), None);

Source

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

Removes a key from the map, returning the key value pair at the key if the key was previously in the map. If the key was not present then this method returns None. The iteration order is not affected by this method except to remove the specified key from the underlying linked list.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.insert(1, "a");
assert_eq!(lhm.remove_entry(&1), Some((1, "a")));
assert_eq!(lhm.remove(&1), None);

Source

pub fn put(&mut self, k: K, v: V)

Inserts a key-value pair into the map. Unlike the insert method this does not return the old value previously stored. The new value inserted is placed at the tail of the underlying linked list (most recently used).

#Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
assert_eq!(lhm.is_empty(), false);

Source

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

Inserts a key-value pair into the map and returns the old value (if any). If a value was not present for this key then this method returns None. The new value inserted is placed at the tail of the underlying linked list (most recently used).

The key is not updated and only the value corresponding to the key is updated.

#Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
assert_eq!(lhm.insert(1, "a"), None);
assert_eq!(lhm.is_empty(), false);

lhm.insert(2, "b");
assert_eq!(lhm.insert(2, "c"), Some("b"));

Source

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

An Iterator that vists all key value pairs in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is (&’a K, &’a V).

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&1, &"a")));
assert_eq!(iter.next(), Some((&2, &"b")));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.iter();
assert_eq!(iter.next(), Some((&2, &"b")));
assert_eq!(iter.next(), Some((&1, &"a")));

Source

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

An Iterator that vists all key value pairs in a predictable order with mutable references to the values.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed

The iterator element type is (&’a K, &’a mut V).

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

for (_, val) in lhm.iter_mut() {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));
assert_eq!(lhm.get(&2), Some(&"d"));

Source

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

An Iterator that vists all keys in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a K.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.keys();
assert_eq!(iter.next(), Some((&1)));
assert_eq!(iter.next(), Some((&2)));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.keys();
assert_eq!(iter.next(), Some((&2)));
assert_eq!(iter.next(), Some((&1)));

Source

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

An Iterator that vists all values in a predictable order.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a V.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.values();
assert_eq!(iter.next(), Some((&"a")));
assert_eq!(iter.next(), Some((&"b")));

// Construct a map in AccessOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::AccessOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

let mut iter = lhm.values();
assert_eq!(iter.next(), Some((&"b")));
assert_eq!(iter.next(), Some((&"a")));

Source

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

An Iterator that vists all values in a predictable order with mutable references to the values.

Iteration over the map requires time proportional to the length of the map (O(len)) regardless of the capacity because it iterates over the elements of the underlying linked list. If the map is constructed with InsertionOrder then the iteration order is from oldest entry inserted to the newest entry inserted. If the map is constructed with AccessOrder then the iteration order is from oldest entry accessed to the newest entry accessed.

The iterator element type is &’a mut V.

§Examples

use deepmesa_collections::LinkedHashMap;
use deepmesa_collections::lhmap::Order;

// Construct a map in InsertionOrder
let mut lhm = LinkedHashMap::<u16, &str>::new(10, Order::InsertionOrder, None);
lhm.put(1, "a");
lhm.put(2, "b");

lhm.get(&1);

for val in lhm.values_mut() {
    *val = "d";
}

assert_eq!(lhm.get(&1), Some(&"d"));
assert_eq!(lhm.get(&2), Some(&"d"));