Struct Lru

pub struct Lru<Key, Value> { /* private fields */ }

A least-recently-used (LRU) cache.

The cache maintains at most capacity entries. When inserting into a full cache, the least recently used entry is automatically evicted. All operations that access values (get, insert, get_or_insert_with) update the entry’s position in the LRU order. Operations that only read without accessing (peek, contains_key, oldest) do not affect LRU ordering.

Time Complexity

• Insert/Get/Remove: O(log n) average, O(n) worst case
• Peek/Contains: O(1) average, O(n) worst case
• Pop (oldest): O(log n)
• Clear: O(1)

Space Complexity

• O(capacity) memory usage
• Pre-allocates space for capacity entries

Examples

use std::num::NonZeroUsize;

use evictor::Lru;

let mut cache = Lru::<i32, String>::new(NonZeroUsize::new(3).unwrap());

cache.insert(1, "one".to_string());
cache.insert(2, "two".to_string());
cache.insert(3, "three".to_string());

assert_eq!(cache.len(), 3);

cache.get(&1);

cache.insert(4, "four".to_string());
assert!(!cache.contains_key(&2));

cache.peek(&3);
let (oldest_key, _) = cache.oldest().unwrap();
assert_eq!(oldest_key, &3);

Implementations

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

pub fn new(capacity: NonZeroUsize) -> Self

Creates a new, empty LRU cache with the specified capacity.

pub fn clear(&mut self)

Removes all entries from the cache.

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

Returns a reference to the value without updating its position in the cache.

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

Returns a reference to the oldest (least recently used) entry. This does not update the entry’s position in the cache.

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

Returns true if the cache contains the given key. This does not update the entry’s position in the cache.

pub fn get_or_insert_with( &mut self, key: Key, or_insert: impl FnOnce(&Key) -> Value, ) -> &Value

Gets the value for a key, or inserts it using the provided function. Returns an immutable reference to existing value (if found) or the newly inserted value. If the cache is full, the least recently used entry is removed on insertion.

pub fn get_or_insert_with_mut( &mut self, key: Key, or_insert: impl FnOnce(&Key) -> Value, ) -> &mut Value

Gets the value for a key, or inserts it using the provided function. Returns a mutable reference to the existing value (if found) or the newly inserted value. If the cache is full, the least recently used entry is removed on insertion.

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

Inserts a key-value pair into the cache. Returns an immutable reference to the inserted value. If the cache is full, the least recently used entry is removed.

pub fn insert_mut(&mut self, key: Key, value: Value) -> &mut Value

Inserts a key-value pair into the cache. Returns a mutable reference to the inserted value. If the cache is full, the least recently used entry is removed.

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

Gets a value from the cache, marking it as recently used. Returns an immutable reference to the value if found.

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

Gets a value from the cache, marking it as recently used. Returns a mutable reference to the value if found.

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

Removes and returns the oldest (least recently used) entry.

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

Removes a specific entry from the cache. Returns the value if the key was present.

pub fn is_empty(&self) -> bool

Returns true if the cache contains no entries.

pub fn len(&self) -> usize

Returns the number of entries in the cache.

pub fn capacity(&self) -> usize

Returns the maximum number of entries the cache can hold.

pub fn retain(&mut self, f: impl FnMut(&Key, &mut Value) -> bool)

Retains only the entries for which the predicate returns true.

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

where I: IntoIterator<Item = (Key, Value)>,

Extends the cache with key-value pairs from an iterator.

pub fn shrink_to_fit(&mut self)

Shrinks the internal storage to fit the current number of entries.

Trait Implementations

impl<Key: Debug, Value: Debug> Debug for Lru<Key, Value>

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

Formats the value using the given formatter.

impl<Key: Hash + Eq, Value> FromIterator<(Key, Value)> for Lru<Key, Value>

fn from_iter<I>(iter: I) -> Self

where I: IntoIterator<Item = (Key, Value)>,

Creates a value from an iterator.