Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get
and set
.get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.In the list, we should be able to track the key in map, so that when it's reached the cap, we can delete the entry in map.
class LRUCache{ struct LRUEntry { int val,key; LRUEntry(int k, int v) :val(v), key(k){} }; //save value list<LRUEntry> cache; //save key unordered_map<int, list<LRUEntry>::iterator> map; int cap; public: LRUCache(int capacity) { cap = capacity; } void moveToHead(int key) { auto it = map[key]; cache.push_front(LRUEntry(key, it->val)); cache.erase(it); map[key] = cache.begin(); } int get(int key) { if(map.find(key) == map.end()) return -1; moveToHead(key); return map[key]->val; } void set(int key, int value) { if(map.find(key) != map.end()) { *map[key] = LRUEntry(key, value); moveToHead(key); return; } if(cache.size() == cap) { map.erase(cache.rbegin()->key); cache.pop_back(); } cache.push_front(LRUEntry(key,value)); map[key] = cache.begin(); } };