Struct LfuCache 

pub struct LfuCache<Key: Hash + Eq, Value> { /* private fields */ }

A collection that if limited to a certain capacity will evict based on the least recently used value.

Implementations

impl<Key: Hash + Eq, Value> LfuCache<Key, Value>

pub fn with_capacity(capacity: usize) -> Self

Creates a LFU cache with at least the specified capacity.

When the capacity is reached, then the least frequently used item is evicted. If there are multiple least frequently used items in this collection, the most recently added item is evicted.

let mut cache = LfuCache::with_capacity(2);

// Fill up the cache.
cache.insert("foo", 3);
cache.insert("bar", 4);

// Insert returns the evicted value, if a value was evicted.
let maybe_evicted = cache.insert("baz", 5);

// In the case of a tie, the most recently added value is evicted.
assert!(cache.get(&"bar").is_none());
assert_eq!(maybe_evicted, Some(4));

cache.get(&"baz");
// Otherwise, the least frequently value is evicted.
assert_eq!(cache.pop_lfu(), Some(3));

pub fn unbounded() -> Self

Creates a LFU cache with no bound.

This effectively turns the LFU cache into a very expensive HashMap if the least frequently used item is never removed. This is useful if you want to have fine-grain control over when the LFU cache should evict. If a LFU cache was constructed using this function, users should call pop_lfu to remove the least frequently used item.

Construction of this cache will not heap allocate.

pub fn set_capacity(&mut self, new_capacity: usize)

Sets the new capacity.

If the provided capacity is zero, then this will turn the cache into an unbounded cache. If the new capacity is less than the current capacity, the least frequently used items are evicted until the number of items is equal to the capacity.

If the cache becomes unbounded, then users must manually call pop_lfu to remove the least frequently used item.

If the cache was previously unbounded and is provided a non-zero capacity, then the cache now is bounded and will automatically remove the least frequently used item when the capacity is reached.

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

Inserts a key-value pair into the cache.

If the key already exists, the value is updated without updating the key and the previous value is returned. The frequency of this item is reset.

If the key did not already exist, then what is returned depends on the capacity of the cache. If an entry was evicted, the old value is returned. If the cache did not need to evict an entry or was unbounded, this returns None.

pub fn get(&mut self, key: &Key) -> Option<&Value>

Gets a value and increments the internal frequency counter of that value, if it exists.

pub fn get_mut(&mut self, key: &Key) -> Option<&mut Value>

Gets a mutable value and increments the internal frequency counter of that value, if it exists.

pub fn remove(&mut self, key: &Key) -> Option<Value>

Removes a value from the cache by key, if it exists.

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

Gets the given key’s corresponding entry in the LFU cache for in-place manipulation. If the key refers to an occupied entry, that entry then is immediately considered accessed, even if no reading or writing is performed. This behavior is a limitation of the Entry API.

pub fn pop_lfu(&mut self) -> Option<Value>

Evicts the least frequently used value and returns it. If the cache is empty, then this returns None. If there are multiple items that have an equal access count, then the most recently added value is evicted.

pub fn pop_lfu_key_value(&mut self) -> Option<(Key, Value)>

Evicts the least frequently used key-value pair and returns it. If the cache is empty, then this returns None. If there are multiple items that have an equal access count, then the most recently added key-value pair is evicted.

pub fn pop_lfu_key_value_frequency(&mut self) -> Option<(Key, Value, usize)>

Evicts the least frequently used value and returns it, the key it was inserted under, and the frequency it had. If the cache is empty, then this returns None. If there are multiple items that have an equal access count, then the most recently added key-value pair is evicted.

pub fn clear(&mut self) -> LfuCacheIter<Key, Value>

Clears the cache, returning the iterator of the previous cached values.

pub fn peek_lfu(&self) -> Option<&Value>

Peeks at the next value to be evicted, if there is one. This will not increment the access counter for that value.

pub fn peek_lfu_key(&self) -> Option<&Key>

Peeks at the key for the next value to be evicted, if there is one. This will not increment the access counter for that value.

pub const fn capacity(&self) -> Option<NonZeroUsize>

Returns the current capacity of the cache.

pub const fn len(&self) -> usize

Returns the current number of items in the cache. This is a constant time operation.

pub const fn is_empty(&self) -> bool

Returns if the cache contains no elements.

pub const fn is_unbounded(&self) -> bool

Returns if the cache is unbounded.

pub fn frequencies(&self) -> Vec<usize>

Returns the frequencies that this cache has. This is a linear time operation.

pub fn shrink_to_fit(&mut self)

Sets the capacity to the amount of objects currently in the cache. If no items were in the cache, the cache becomes unbounded.

pub fn keys(&self) -> impl Iterator<Item = &Key> + FusedIterator + '_

Returns an iterator over the keys of the LFU cache in any order.

pub fn peek_values(&self) -> impl Iterator<Item = &Value> + FusedIterator + '_

Returns an iterator over the values of the LFU cache in any order. Note that this does not increment the count for any of the values.

pub fn peek_iter( &self, ) -> impl Iterator<Item = (&Key, &Value)> + FusedIterator + '_

Returns an iterator over the keys and values of the LFU cache in any order. Note that this does not increment the count for any of the values.

Trait Implementations

impl<Key: Hash + Eq + Debug, Value> Debug for LfuCache<Key, Value>

Available on non-tarpaulin_include only.

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

Formats the value using the given formatter.

impl<Key: Hash + Eq, Value> Extend<(Key, Value)> for LfuCache<Key, Value>

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

Inserts the items from the iterator into the cache. Note that this may evict items if the number of elements in the iterator plus the number of current items in the cache exceeds the capacity of the cache.

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<Key: Hash + Eq, Value> FromIterator<(Key, Value)> for LfuCache<Key, Value>

fn from_iter<T: IntoIterator<Item = (Key, Value)>>(iter: T) -> Self

Constructs a LFU cache with the capacity equal to the number of elements in the iterator.

impl<Key: Hash + Eq, Value> IntoIterator for LfuCache<Key, Value>

type Item = (Key, Value)

The type of the elements being iterated over.

type IntoIter = LfuCacheIter<Key, Value>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<Key: PartialEq + Hash + Eq, Value: PartialEq> PartialEq for LfuCache<Key, Value>

fn eq(&self, other: &LfuCache<Key, Value>) -> 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<Key: Eq + Hash + Eq, Value: Eq> Eq for LfuCache<Key, Value>

impl<Key: Hash + Eq, Value> Send for LfuCache<Key, Value>

impl<Key: Hash + Eq, Value> StructuralPartialEq for LfuCache<Key, Value>

impl<Key: Hash + Eq, Value> Sync for LfuCache<Key, Value>