Untitled

struct Node {
  int key;
  int value;
};

class LRUCache {
 public:
  LRUCache(int capacity) : capacity(capacity) {}
  int get(int key) {
    const auto it = keyToIterator.find(key);
    if (it == keyToIterator.cend()){
      return -1;
    }
    const auto& listIt = it->second;
    cache.splice(cache.begin(), cache, listIt);
    return listIt->value;
  }
  void put(int key, int value) {
    if (const auto it = keyToIterator.find(key); it != keyToIterator.cend()) {
      const auto& listIt = it->second;
      cache.splice(cache.begin(), cache, listIt);
      listIt->value = value;
      return;
    }
    if (cache.size() == capacity) {
      const Node& lastNode = cache.back();
      keyToIterator.erase(lastNode.key);
      cache.pop_back();
    }
    cache.emplace_front(key, value);
    keyToIterator[key] = cache.begin();
  }

 private:
  const int capacity;
  list<Node> cache;
  unordered_map<int, list<Node>::iterator> keyToIterator;
};