LRU Cache （9）

浏览数：42 / 时间：2015年06月20日

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.

就是实现简单的LRU算法。但是在时间上有限制。首先，我查看了计算机组成原理，知道了在硬件上LRU是这么实现的。每行设置一个计数器，他们的cache每命中一次，命中行计数器清零，其他行计数器增加1。当需要替换时，比较各特定行的计数值，将计数值最大的行换出。

于是，我第一次就利用了这种思路，采用map这一数据结构，每当有一行命中时，这一行计数值清零，其他行计数值加1，每次换出计数值最大的行。但是很不幸，超时了！不能采用这种解法！

我上网找了一些解法，发现他们都是利用list+unordered_map的解法，如果行被命中，就将行移至list的头部，每次替换list尾部的行。算法了然于心，剩下的就是实现了！但是，就算你知道怎么做，其中也可能有各种各样的波折。我想起了刚学数据结构时的窘迫。事后总结，还是双向链表的使用不够熟练，现在已经是22:10了，没有时间来自己实现一个双向链表，改日一定要实操成功！

总之，debug搞得头都疼了！

贴代码了：

 1 struct node {
 2     int key,value;
 3     node(int k,int v):key(k),value(v){
 4     }
 5 
 6 };
 7 class LRUCache{
 8 public:
 9     int size;
10     int capacity;
11     list <node >li;
12     unordered_map <int, list<node>::iterator>mem;
13     LRUCache(int c){
14         capacity=c;
15         size=0;
16     }
17     int get(int key){
18         auto it=mem.find(key);//这里得到的迭代器是const的
19         if(it==mem.end())
20             return -1;
21         auto ok=mem[key];//这里得到的迭代器不是const的
22         li.splice(li.begin(),li,ok);//这里犯了一点糊涂
23         mem[key]=li.begin();
24         return li.begin()->value;
25     }
26     void set(int key,int value){
27         auto it=mem.find(key);
28         if(it==mem.end()){
29             li.push_front(node(key,value));
30             mem[key]=li.begin();
31             size++;
32             if(size>capacity){
33                 mem.erase(li.back().key);
34                 li.pop_back();
35                 size--;
36             }
37         }
38         else{
39             li.splice(li.begin(),li,mem[key]);
40             mem[key]=li.begin();
41             li.begin()->value=value;
42         }
43     }
44 
45 };