#include <iostream>
#include <list>
#include <unordered_map>
#include <vector>

using namespace std;

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

  int get(int key) {
    auto it = key_to_it_.find(key);
    if (it == key_to_it_.end()) {
      return -1;
    }
    pair<int, int> p = *(it->second);
    // bump priority.
    key_values_.erase(it->second);
    key_to_it_[key] = key_values_.insert(key_values_.begin(), p);
    return p.second;
  }

  void put(int key, int value) {
    auto it = key_to_it_.find(key);
    if (it != key_to_it_.end()) {
      // erase from key_values_
      key_values_.erase(it->second);
    }
    // Purge old entries.
    if (key_values_.size() >= capacity_) {
      const pair<int, int>& p = key_values_.back();
      auto it2 = key_to_it_.find(p.first);
      __glibcxx_assert(it2 != key_to_it_.end());
      key_to_it_.erase(it2);
      key_values_.pop_back();
    }
    key_to_it_[key] = key_values_.insert(key_values_.begin(), {key, value});
  }

private:
  list<pair<int, int>> key_values_;
  unordered_map<int, list<pair<int, int>>::iterator> key_to_it_;
  int capacity_;
};

int main() {
  LRUCache cache(2 /* capacity */);

  cache.put(1, 1);
  cache.put(2, 2);
  cache.get(1);    // returns 1
  cache.put(3, 3); // evicts key 2
  cache.get(2);    // returns -1 (not found)
  cache.put(4, 4); // evicts key 1
  cache.get(1);    // returns -1 (not found)
  cache.get(3);    // returns 3
  cache.get(4);    // returns 4
  return 0;
}