A simple LRU Cache in C++ STL.

LRUCache.hpp

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

using namespace std;

class LRUCache {
  size_t capacity;
  list<pair<int, int>> dlist;
  
  using ListIt = decltype(dlist)::iterator;
  unordered_map<int, ListIt> hash_map;

  void add_to_head(int key, int value) {
    dlist.emplace_front(key, value);
    hash_map[key] = dlist.begin();
  }

  void move_to_head(ListIt it) {
    dlist.splice(dlist.begin(), dlist, it);
  }

  void remove_last() {
    hash_map.erase(dlist.back().first);
    dlist.pop_back();
  }

 public:
  LRUCache(int capacity) : capacity(capacity) {}

  int get(int key) {
    if (hash_map.count(key) == 0) {
      return -1;
    }
    ListIt it = hash_map[key];
    move_to_head(it);
    return it->second;
  }

  void put(int key, int value) {
    if (hash_map.count(key)) {
      ListIt it = hash_map[key];
      move_to_head(it);
      it->second = value;
    } else {
      add_to_head(key, value);
      if (dlist.size() > capacity) {
        remove_last();
      }
    }
  }
};

Verify it with LeetCode: LRU Cache - LeetCode.