LRU Table sample

lru_table.h

#ifndef LRU_TABLE_H
#define LRU_TABLE_H

#include <list>
#include <optional>
#include <unordered_map>
#include <utility>

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

template <class K, class V>
class LRUTable {
  typedef std::list<std::pair<K, V>> List;
  typedef std::unordered_map<K, typename List::iterator> Table;

 public:
  LRUTable() {}
  ~LRUTable() {}

  std::optional<V> lookup(K key) {
    auto search = table.find(key);
    if (search == table.end()) {
      return std::nullopt;
    }

    move_to_front(search);
    typename List::iterator& it = search->second;
    return std::make_optional(it->second);
  }

  std::optional<std::pair<K, V>> recent_used_pair() {
    return list.empty() ? std::nullopt : std::make_optional(list.front());
  }

  std::optional<std::pair<K, V>> least_recent_used_pair() {
    return list.empty() ? std::nullopt : std::make_optional(list.back());
  }

  void insert(K key, V value) {
    auto search = table.find(key);
    if (search == table.end()) {  // Insert a new item in the front
      list.emplace_front(std::make_pair(key, value));
      table[key] = list.begin();
    } else {  // Update the value and move it to the front
      typename List::iterator& it = search->second;
      it->second = value;
      move_to_front(search);
    }
  }

  bool erase(K key) {
    auto search = table.find(key);
    if (search == table.end()) {
      return false;
    }

    list.erase(search->second);
    table.erase(search);
    return true;
  }

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

 private:
  void move_to_front(typename Table::iterator& it) {
    list.splice(list.begin(), list, it->second);
    it->second = list.begin();
  }

  List list;
  Table table;
};

#endif  // LRU_TABLE_H

Makefile

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

all: test

check: all
	./test

HEADER := lru_table.h
CXXFLAGS = -g -Wall -std=c++17 -DLRU_TABLE_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_TABLE_DEBUG 1
#include "lru_table.h"
#include <cassert>
#include <string>

#define assertm(exp, msg) assert(((void)msg, exp))
using std::string;

int main() {
  LRUTable<int, string> table;

  assertm(!table.recent_used_pair().has_value(), "table should be empty");
  assertm(!table.least_recent_used_pair().has_value(), "table should be empty");
  assertm(!table.lookup(1).has_value(), "table[1] should be empty");

  table.insert(1, "this");
  table.insert(2, "world");
  assertm((table.recent_used_pair().value() ==
           std::make_pair<int, string>(2, "world")),
          "table front should be `<2, world>`");
  assertm((table.least_recent_used_pair().value() ==
           std::make_pair<int, string>(1, "this")),
          "table front should be `<1, this>`");

  table.insert(1, "crazy");
  assertm(table.lookup(1).value() == "crazy", "table[1] should be `crazy`");
  assertm((table.recent_used_pair().value() ==
           std::make_pair<int, string>(1, "crazy")),
          "table front should be `<1, crazy>`");
  assertm((table.least_recent_used_pair().value() ==
           std::make_pair<int, string>(2, "world")),
          "table front should be `<2, world>`");

  table.insert(6, "web");
  table.insert(5, "wide");

  assertm(!table.erase(0xdeadbeef), "table should remove nothing");
  assertm(table.erase(1), "table[1] should be removed");
  assertm(table.lookup(2).value() == "world", "table[2] should be `world`");

  assertm((table.recent_used_pair().value() ==
           std::make_pair<int, string>(2, "world")),
          "table front should be `<2, world>`");
  assertm((table.least_recent_used_pair().value() ==
           std::make_pair<int, string>(6, "web")),
          "table front should be `<6, web>`");

#ifdef LRU_TABLE_DEBUG
  table.display();
#endif  // LRU_TABLE_DEBUG

  return 0;
}

test.sh

make check && make clean