问题：

设计类LRUCache，实现LRU Cache

Least Recently Used

优先度为：最近使用优先 的缓存。

• 缓存大小一定，capacity
• get(key)：通过key查找value，若缓存中不存在key，返回-1
• put(key, value)：插入缓存key=value。

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4
 

Constraints:

1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 10^4
At most 3 * 10^4 calls will be made to get and put.

　　

解法：LRU

c++中 利用 list 和 unordered_map 来实现：

• cache：list：存储cache链表。
• kl：unordered_map：存储对应key在list中的位置，方便直接访问。
• kv：另：为了存储value，追加unordered_map保存key：value对应关系。

那么，对于cache，我们有以下两个基本操作：

• 追加key：value对
  • update(key, value)【假设，此操作cache已经不超过最大容量】
    • 若key存在于cache中
      • 在list中找到key（定位：kl[key]），将key从list中删除：list.erase(kl[key])
      • 1. 重新加到list头：list.push_front(key)，更新key在list中的位置：kl[key]=list.begin()
      • 2. 更新 kv[key]=value
    • 若key不存在于cache中
    • 1. 将key加到list头：list.push_front(key)，更新key在list中的位置：kl[key]=list.begin()
    • 2. 更新 kv[key]=value
• 删除最老的元素（当size超出cache容量）
  • outlast()：last = list.back()
  • kl.erase(last)
  • kv.erase(last)
  • list.pop_back()

再看题目所求：

• get(key)：
  • update(key)
  • return kv[key]
• put(key, value)
  • 若cache==最大容量：删除最老元素：outlast()
  • 此时，cache一定不超过最大容量：再进行：update(key, value)

 

代码参考：

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