A Simple LRU Sample

lru.h

#ifndef LRU_H
#define LRU_H

#include <cassert>
#include <list>
#include <optional>
#include <unordered_map>

#ifdef LRU_DEBUG
#include <iostream>
#include <iterator>
#endif  // LRU_DEBUG

template <class T>
class LRU {
 public:
  LRU() {}
  ~LRU() {}

  std::optional<T> least_recently_used() {
    return list.empty() ? std::nullopt : std::make_optional(list.back());
  }

  std::optional<T> most_recently_used() {
    return list.empty() ? std::nullopt : std::make_optional(list.front());
  }

  void use(const T& item) {
    if (contains(item)) {
      erase(item);
    }
    insert(item);
  }

  void insert(const T& item) {
    assert(!contains(item));
    list.emplace_front(item);
    position[item] = list.begin();
  }

  void erase(const T& item) {
    assert(contains(item));
    list.erase(position[item]);
    position.erase(item);
  }

#ifdef LRU_DEBUG
  void display() {
    for (auto i = list.begin(); i != list.end(); ++i) {
      std::cout << *i;
      if (std::next(i) != list.end()) {
        std::cout << ", ";
      }
    }
    std::cout << std::endl;
  }
#endif  // LRU_DEBUG

 private:
  bool contains(const T& item) { return position.find(item) != position.end(); }

  std::list<T> list;
  std::unordered_map<T, typename std::list<T>::iterator> position;
};

#endif  // LRU_H

Makefile

# Build C++ client example
# Process with GNU make

all: test

check: all
	./test

HEADER := lru.h
CXXFLAGS = -g -Wall -std=c++17 -fsanitize=address -DLRU_DEBUG=1

test: test.cc $(HEADER)
	$(CXX) $(CXXFLAGS) -c $(filter %.cc,$^)
	$(CXX) $(CXXFLAGS) -o $@ *.o

clean:
	$(RM) test
	$(RM) *.a.out
	$(RM) *.o *.a
	$(RM) *.d
	$(RM) -rf *.dSYM

test.cc

// #define LRU_DEBUG 1
#include "lru.h"
#include <cassert>
#include <string>

using std::string;

int main() {
  LRU<string> lru;

  lru.insert("1");  // 1
  lru.insert("2");  // 2, 1
  lru.use("3");     // 3, 2, 1

  lru.use("1");  // 1, 3, 2
  lru.use("3");  // 3, 1, 2
  lru.use("2");  // 2, 3, 1

  lru.erase("3");   // 2, 1
  lru.insert("4");  // 4, 2, 1
  lru.erase("1");   // 4, 2
  lru.insert("5");  // 5, 4, 2
  lru.use("2");     // 2, 5, 4

  assert(lru.most_recently_used().value() == "2");
  assert(lru.least_recently_used().value() == "4");

#ifdef LRU_DEBUG
  lru.display();
#endif  // LRU_DEBUG

  return 0;
}

test.sh

make check && make clean