Code Demo · C++ · LRU Cache

#include <iostream>
#include <list>
#include <string>
#include <unordered_map>

class LruCache {
  using Entry = std::pair<std::string, int>;
  const std::size_t capacity;
  std::list<Entry> order;
  std::unordered_map<std::string, std::list<Entry>::iterator> index;

public:
  explicit LruCache(std::size_t size) : capacity(size) {}

  void put(const std::string& key, int value) {
    if (auto found = index.find(key); found != index.end()) {
      order.erase(found->second);
    }
    order.emplace_front(key, value);
    index[key] = order.begin();
    if (index.size() > capacity) {
      index.erase(order.back().first);
      order.pop_back();
    }
  }

  void print() const {
    for (const auto& entry : order) std::cout << entry.first << ":" << entry.second << "\n";
  }
};

int main() {
  LruCache cache(2);
  cache.put("a", 1);
  cache.put("b", 2);
  cache.put("c", 3);
  cache.print();
}