Rust bounded LRU cache with recency tracking

use std::collections::{HashMap, VecDeque};

struct Lru<K, V> { cap: usize, order: VecDeque<K>, map: HashMap<K, V> }

impl<K: Eq + std::hash::Hash + Clone, V> Lru<K, V> {
    fn new(cap: usize) -> Self { Self { cap, order: VecDeque::new(), map: HashMap::new() } }
    fn get(&mut self, k: &K) -> Option<&V> {
        if self.map.contains_key(k) {
            self.order.retain(|x| x != k);
            self.order.push_back(k.clone());
        }
        self.map.get(k)
    }
    fn put(&mut self, k: K, v: V) {
        self.map.insert(k.clone(), v);
        self.get(&k);
        if self.map.len() > self.cap {
            if let Some(old) = self.order.pop_front() { self.map.remove(&old); }
        }
    }
}