首页 > 代码库 > LRU Cache （9）
LRU Cache （9）
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=http://www.mamicode.com/value;42 }43 }44 45 };
LRU Cache （9）