LRU Cache

Requirements:

• a maximum capacity
• get(key) + mark as recent
• put(key,value) + mark as recent + evict oldest one if inserting ( not updating )at capacity
• both should be average O(1)

high level idea

A hashmap is definitely involed to back as the key value store. You also need a list to maintain the order, a “touch” on an item, pops it from it’s current position and moves it to the top. You insert at top and remove from back. For these arbitrary operation a doubly linked list is ideal. so map(key → *Node( data )) seems to be the way

cpp impl

#include <cassert>
#include <list>
#include <optional>
#include <string>
#include <unordered_map>
#include <utility>
using namespace std;
 
template <typename Key, typename Val>
// I was initilly thinking, do I need a concept to check this
// key is suitable for an unordered map but I was over-engineering
// you don't need that at all as compiler can handled it
class LRUCache {
  private:
    using KV = pair<Key, Val>;
    using Iter = typename std::list<KV>::iterator;
    std::list<KV> ll_; // linked list
    std::unordered_map<Key, Iter> map_;
 
    void move_front(Iter iter) {
        // splice: moving list ranges
        // dst.splice( before what dst iter, src, nothing/single iter/range iter)
        // >>> why both src and src's iterators are needed?
        // iterators don't know their owning list at all
        ll_.splice(ll_.begin(), ll_, iter);
    }
 
    void trim() {
        while (ll_.size() > capacity) {
            map_.erase(ll_.back().first);
            ll_.pop_back();
        }
    }
 
  public:
    // easy getter and no setter
    const std::size_t capacity;
 
    LRUCache(std::size_t capacity) : capacity(capacity) {}
 
    void put(Key k, Val v) {
        auto found = map_.find(k);
        if (found != map_.end()) {
            // a containts then get is a double fetch
            auto iter = found->second;
            iter->second = std::move(v); // this does not invalidate the iterator
            move_front(iter);
        } else {
            // this just prevents a second copy
            ll_.emplace_front(std::move(k), std::move(v));
            // can't use k anymore
            map_[ll_.front().first] = ll_.begin();
            trim();
        }
    }
 
    std::optional<Val> get(const Key &k) {
        // notice the naming, found and then iter
        auto found = map_.find(k);
        if (found == map_.end()) {
            return std::nullopt;
        }
 
        auto iter = found->second;
        move_front(iter);
        // for the compiler, this line is
        // return std::optional<Val>{iter->second};
        // note that we are copying here
        // i'm not making the caller the owner of value here
        return iter->second;
    }
};
 
int main() {
    LRUCache<std::string, int> lru(2);
    lru.put("a", 1);
    lru.put("b", 2);
    assert(lru.get("a") == 1);
    lru.put("c", 3);
    assert(!lru.get("b"));
    lru.put("a", 4);
    assert(lru.get("a") == 4);
}

cpp details

• when do you need typename? If the type is not templated you don’t need it. For example std::list<T>::iterator needs it but std::list<int>::iterator does not need it.
• I had a misconception on the fragility of iterators, they can get invalidated but the conditions are well defined. For an std::list you can go pretty far with iterators.
• REM: if you take the args by copy, any assignemtns for those should almost always be a move
• if you see a if map contains → map(key) that’s two calls, use a find
• don’t forget std::optional instead of just default constructing something