Least Recently Used Cache

Today we’re going to implement a Least Recently Used Cache in C++23.

This structure is basically a fixed-size mapping of keys to values where the least recently used, or oldest, keys are evicted from the cache when adding new keys.

Fetching a value from the cache marks the key as most recently used as do successful insert operations.

First, we’ll add some imports and write a small program to demonstrate our cache:

#include <cstdint>
#include <list>
#include <map>
#include <optional>
#include <print>

int main() {
  LRU<std::string, uint64_t> lru(3);
  lru.set("foo", 23);
  lru.set("bar", 44);
  lru.set("baz", 12);

  std::print("lru capacity: {}\n", lru.capacity());
  std::print("lru size: {}\n", lru.size());

  std::optional<uint64_t> foo = lru.get("foo");
  std::print("foo: {}\n", *foo);

  std::print("adding quz 100\n");
  lru.set("qux", 100);

  std::print("lru capacity: {}\n", lru.capacity());
  std::print("lru size: {}\n", lru.size());

  std::optional<uint64_t> bar = lru.get("bar");
  if (bar.has_value()) {
    std::print("Expected bar to be removed\n");
    return 0;
  } else {
    std::print("bar has been removed\n");
  }

  return 0;
}

Hopefully this program demonstrates what using such a cache might look like. We create a cache with a capacity of 3 elements. We then fill the cache with three elements using the set method on it. We then use the get method to attempt to retrieve an element, "foo", and print it out. We then add another element, check our invariant once again, and validate that the expected key, "bar" is evicted.

Let’s create a definition for LRU:

template <typename K, typename V> struct LRU {
  uint64_t capacity;
  std::map<K, V> cache;
  std::list<K> keys;
};

We’re going to use the standard library as much as we can here. We’re using a map to store our keys and values. And we’re using a list which is usually implemented as a doubly-linked list to keep track of the age of the keys. The most recent keys will go at the front of the list and the oldest at the end.

Next let’s add our constructor and some of accessor methods:

template <typename K, typename V> struct LRU {
  // ... members as before

  LRU(uint64_t cap) : capacity(cap), cache(), keys() {}

  uint64_t capacity() {
    return capacity;
  }

  uint64_t size() {
    return cache.size();
  }
};

This should be standard stuff, next let’s add the get method:

template <typename K, typename V> struct LRU {
  // ...

  std::optional<V> get(K k) {
    if (cache.contains(k)) {
      auto v = cache.at(k);
      keys.remove(k);
      keys.emplace_front(k);
      return v;
    } else {
      return {};
    }
  }

  // ...
};

Here, if the key is found, the keys list is updated so that the accessed key is moved to the head of the list. This does entail traversing the list to remove it first so that we don’t get duplicate entries and we can keep the list bounded in size.

Next we can add the set method which takes a little more work:

template <typename K, typename V> struct LRU {
  // ...

  void set(K k, V v) {
    if (cache.contains(k)) {
      cache[k] = v;
      keys.remove(k);
      keys.emplace_front(k);
    } else {
      if (cache.size() == capacity) {
        auto oldest_k = keys.back();
        cache.erase(oldest_k);

        keys.pop_back();

        cache[k] = v;
        keys.emplace_front(k);
      } else {
        cache[k] = v;
        keys.emplace_front(k);
      }
    }
  }

};

And that’s all we need to compile and run our test program.

The Least Recently Used cache is a great way to implement a cache that is bounded in space with a sensible eviction policy: remove the element that hasn’t been accessed in the most amount of time. This can be done in O(1) time for the cost of O(n) space to have the doubly-linked list keep track of the keys.

If you ever need to keep track of web requests or a long-running process that accesses dynamic resources, you might consider an LRU cache to speed up your read operations!