Struct lfu_cache::LfuCache

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

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>

#[must_use]pub fn with_capacity(capacity: usize) -> Self

Creates a LFU cache with a capacity bound. 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 provided 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));

#[must_use]pub fn unbounded() -> Self

Creates a LFU cache with no bound. This 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 Self::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 Self::pop_lfu to remove the least frequently used item.

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

Inserts a value into the cache using the provided key. If the value already exists, then the value is replace with the provided value and the frequency is reset.

The returned Option will return an evicted value, if a value needed to be evicted. This includes the old value, if the previously existing value was present under the same key.

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

Gets a value and incrementing 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 incrementing 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 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.

#[must_use]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.

#[must_use]pub fn capacity(&self) -> Option<NonZeroUsize>

Returns the current capacity of the cache.

#[must_use]pub fn len(&self) -> usize

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

#[must_use]pub fn is_empty(&self) -> bool

Returns if the cache contains no elements.

#[must_use]pub fn is_unbounded(&self) -> bool

Returns if the cache is unbounded.

#[must_use]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: Debug + Hash + Eq, Value: Debug> Debug for LfuCache<Key, Value>

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

Formats the value using the given formatter.

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

fn drop(&mut self)

Executes the destructor for this type.

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

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.

pub fn extend_one(&mut self, item: A)

🔬 This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

pub 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<LfuCache<Key, Value>> for LfuCache<Key, Value>

fn eq(&self, other: &LfuCache<Key, Value>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &LfuCache<Key, Value>) -> bool

This method tests for !=.

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

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

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

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