146. LRU Cache

题目链接：https://leetcode.com/problems/lru-cache/#/description

题目大意：为最近最少访问cache设计和实现一个数据结构，该数据结构应该支持get和put操作。

　　　　　get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
　　　　　put(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.

思路：因为get和set都涉及频繁的插入删除操作，所以需要用一个list来记录key。同时为了在常数时间访问指定值，因此需要用unordered_map来保存每个key对应的value，同时为了更快地找到被删除的节点，unordered_map也需要保存每个key对应的迭代器。

代码：

 1 class LRUCache {
 2 public:
 3     LRUCache(int capacity):_capacity(capacity) {
 4         
 5     }
 6     
 7     int get(int key) {
 8         auto it = cache.find(key);
 9         if (it == cache.end())
10             return -1;
11         touch(it);
12         return it->second.first;
13     }
14     
15     void put(int key, int value) {
16         auto it = cache.find(key);
17         if (it != cache.end())
18             touch(it);
19         else {
20             if (cache.size() == _capacity) {
21                 cache.erase(keys.back());
22                 keys.pop_back();
23             }
24             keys.push_front(key);
25         }
26         cache[key] = {value, keys.begin()};
27     }
28 private:
29     using PII = pair<int, list<int>::iterator>;
30     
31     void touch(unordered_map<int, PII>::iterator it) {
32         keys.erase(it->second.second);
33         keys.push_front(it->first);
34         it->second.second = keys.begin();
35     }
36     
37     list<int> keys;
38     unordered_map<int, PII> cache;
39     int _capacity;
40 };
41 
42 /**
43  * Your LRUCache object will be instantiated and called as such:
44  * LRUCache obj = new LRUCache(capacity);
45  * int param_1 = obj.get(key);
46  * obj.put(key,value);
47  */

评测系统上运行结果：