首页 > 代码库 > LRU Cache

LRU Cache

2024-07-06 10:55:55   227人阅读

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.

struct Node
{
    int key;
    int value;
    Node* left;
    Node* right;
    Node(){left=NULL;right=NULL;}
};
class LRUCache{
private:
    map<int,Node*> hashmap;
    Node* head;
    Node* tail;
    int capacity;
    int size;
    void remove(Node* p)
    {
        if(p==tail) tail=tail->left;
        if(p==head) head=head->right;
        if(p->left!=NULL)
            p->left->right=p->right;
        if(p->right!=NULL)
            p->right->left=p->left;
        p->left=NULL;
        p->right=NULL;
    }
    void insertfront(Node* p)
    {
        //insert 1st location
        p->left=NULL;
        p->right=head;
        if(head!=NULL) head->left=p;
        head=p;
        if(tail==NULL) tail=head;
    }
    void insertback(Node* p)
    {
        //insert 1st location
        p->left=tail;
        p->right=NULL;
        tail=p;
        if(head==NULL) head=tail;
    }
public:
    LRUCache(int capacity) 
    {
        this->capacity=capacity;
        size=0;
        head=NULL;
        tail=NULL;
    }
    
    int get(int key) 
    {
       map<int ,Node*>::iterator it;
       it=hashmap.find(key);
       if(it==hashmap.end()) return -1;
       
       Node* pnew=it->second;
       remove(pnew);
       insertfront(pnew);
       
       return pnew->value;
    }
    
    void set(int key, int value) 
    {
        map<int ,Node*>::iterator it;
       it=hashmap.find(key);
       Node* pnew;
       if(it!=hashmap.end())
       {
           pnew=it->second;
           pnew->value=http://www.mamicode.com/value;
           remove(pnew);
           insertfront(pnew);
       }
       else
       {
           if(size<capacity)
           {
               pnew=new Node();
               pnew->key=key;
               pnew->value=http://www.mamicode.com/value;
               hashmap.insert(pair<int,Node*>(key,pnew));
               
               insertfront(pnew);
               size++;
           }
           else
           {
               pnew=tail;
               hashmap.erase(hashmap.find(pnew->key));
               
               pnew->key=key;
               pnew->value=http://www.mamicode.com/value;
               hashmap.insert(pair<int,Node*>(key,pnew));
               
               remove(pnew);
               insertfront(pnew);
           }
       }
    }
};

 


联系
我们