LRU设计

  1 //leetcode 146.LRU缓存 
  2 #include 
  3 #include 
  4 using namespace std;
  5 struct DlinkedNode{
  6     int key,value;
  7     DlinkedNode* pre;
  8     DlinkedNode* next;
  9     DlinkedNode():key(0),value(0),pre(nullptr),next(nullptr){}
 10     DlinkedNode(int _key,int _value):key(_key),value(_value),pre(nullptr),next(nullptr){}
 11 };
 12 class LRUCache{
 13     private:
 14         unordered_map<int,DlinkedNode*> cache;
 15         DlinkedNode* head;//虚拟头 
 16         DlinkedNode* tail;//虚拟尾 
 17         int size;
 18         int capacity;
 19     public:
 20     //LRUCache():default;
 21     LRUCache(int _capacity):capacity(_capacity),size(0){
 22         head = new DlinkedNode();
 23         tail = new DlinkedNode();
 24         head->next = tail;
 25         tail->pre = head;
 26     }
 27     int get(int key){
 28         if(!cache.count(key))//key不存在 
 29         {
 30             return -1;
 31         }
 32         //如果key存在，先通过哈希表定位，再移到头部
 33         DlinkedNode* node = cache[key];
 34         moveToHead(node);
 35         return node->value; 
 36     }
 37     void put(int key,int value){
 38         if(!cache.count(key)){//元素不存在 
 39             DlinkedNode* node= new DlinkedNode(key,value);//创建一个新节点 
 40             cache[key] = node;//插入哈希表 
 41             addToHead(node);//添加到双链表头部 
 42             ++size;//当前哈希表中元素个数 
 43             if(size > capacity) 
 44             {
 45                 //超出容量，删除双向链表尾部节点 
 46                 DlinkedNode* removed = removeTail();
 47                 //删除哈希表中对应的项 
 48                 cache.erase(removed->key);
 49                 //防止内存泄漏
 50                 delete removed;
 51                 --size; 
 52             } 
 53         }
 54         else{//如果哈希表中存在key，更新value，再把它移到头部 
 55             DlinkedNode* node = cache[key];
 56             node->value=value;
 57             moveToHead(node); 
 58         }
 59     }
 60     void addToHead(DlinkedNode* node){
 61         node->pre = head;//虚拟头节点
 62         node->next = head->next;
 63         head->next->pre= node;
 64         head->next = node; 
 65     }    
 66     void removeNode(DlinkedNode* node)//断开某个节点 
 67     {
 68         node->pre->next = node->next;
 69         node->next->pre = node->pre;
 70     }
 71     void moveToHead(DlinkedNode* node)//移动某个节点到头部 
 72     {
 73         removeNode(node);
 74         addToHead(node);
 75     } 
 76     DlinkedNode* removeTail(){//删除最久未使用的节点 
 77         DlinkedNode* node = tail->pre;//实际上是最后一个节点 
 78         removeNode(node);
 79         return node;
 80         
 81     }
 82     void lru_print()
 83     {
 84         unordered_map<int,DlinkedNode*>::iterator it=cache.begin();
 85         while(it!=cache.end())
 86         {
 87             cout<<"key: "<first<<" value: "<second->value<<" "<<endl;
 88             ++it;
 89         }
 90         /*for(const auto it:cache)//基于范围for循环 
 91         {
 92             cout<value<<" "< 93         }*/
 94     }
 95 };
 96 int main(int argc, char *argv[])
 97 {
 98     LRUCache lruCache(2);//容量设为2 
 99      lruCache.put(1,1);
100     lruCache.put(2,2);
101     lruCache.get(1);
102     lruCache.put(3,3);
103     lruCache.get(2);
104     lruCache.put(4,4);
105     lruCache.get(1);
106     lruCache.get(3);
107     lruCache.get(4); 
108     lruCache.lru_print();
109     return 0;
110 }