146. LRU Cache

I made mistake in first place as following. The OJ complains "Runtime Error". After some debugging, I find I did wrong on line 27. When popping out the last element in the list, we need to erase this element in hash map too. However, here comes the question. To erase the element in the hash map, we need to know the key, but in my design, I don't know the key of the last element in the list.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, list<int>::iterator> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = *mp[key];  
14:        l.erase(mp[key]);  
15:        l.push_front(ret);  
16:        mp[key] = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key]);  
23:        mp.erase(key);  
24:        l.push_front(value);  
25:        mp[key] = l.begin();  
26:      } else {  
27:        if (l.size() == cap) l.pop_back();  
28:        l.push_front(value);  
29:        mp[key] = l.begin();  
30:      }  
31:    }  
32:  };  

So, the right design should be that the list stores the key and and the value corresponding to the key is wrapped in a pair with the list iterator. And the hash map consists of key and the pair of key and list iterator.

1:  class LRUCache{  
2:  private:  
3:    int cap;  
4:    list<int> l;  
5:    unordered_map<int, pair<int, list<int>::iterator>> mp;  
6:  public:  
7:    LRUCache(int capacity) {  
8:      cap = capacity;  
9:    }  
10:    int get(int key) {  
11:      int ret = -1;  
12:      if (mp.find(key) != mp.end()) {  
13:        ret = mp[key].first;  
14:        l.erase(mp[key].second);  
15:        l.push_front(key);  
16:        mp[key].second = l.begin();  
17:      }  
18:      return ret;  
19:    }  
20:    void set(int key, int value) {  
21:      if (mp.find(key) != mp.end()) {  
22:        l.erase(mp[key].second);  
23:        mp.erase(key);  
24:      } else {  
25:        if (l.size() == cap) {  
26:          mp.erase(l.back());  
27:          l.pop_back();  
28:        }  
29:      }  
30:      l.push_front(key);  
31:      mp[key] = make_pair(value, l.begin());  
32:    }  
33:  };