LeetCode LRU Cache

 1 class LRUCache{
 2 private:
 3     int max_size;
 4     unordered_map<int, list<pair<int, int> >::iterator> hash;
 5     list<pair<int, int> > lru_stack;
 6 public:
 7     LRUCache(int capacity) {
 8         if (capacity < 1) capacity = 0;
 9         max_size = capacity;
10     }
11 
12     int get(int key) {
13         unordered_map<int, list<pair<int, int> >::iterator>::iterator miter = hash.find(key);
14         list<pair<int, int> >::iterator liter;
15         if (miter == hash.end()) {
16             return -1;
17         } else {
18             liter = miter->second;
19             int val = liter->second;
20             lru_stack.erase(liter);
21             miter->second = liter = lru_stack.insert(lru_stack.begin(), make_pair(key, val));
22             return liter->second;
23         }
24     }
25 
26     void set(int key, int value) {
27         if (max_size == 0) return;
28         unordered_map<int, list<pair<int, int> >::iterator>::iterator miter = hash.find(key);
29         list<pair<int, int> >::iterator liter;
30         if (miter == hash.end()) {   // key not exists in the cache
31             if (hash.size() == max_size) {
32                 // invalidate LRU item to avoid overflow
33                 hash.erase(lru_stack.back().first);
34                 lru_stack.pop_back();
35             }
36             liter = lru_stack.insert(lru_stack.begin(), make_pair(key, value));
37             hash.insert(make_pair(key, liter));
38         } else {    // key already exists, so replace the value with new one
39             liter = miter->second;
40             lru_stack.erase(liter);
41             miter->second = lru_stack.insert(lru_stack.begin(), make_pair(key, value));
42         }
43     }
44 };