LRU Cache

• For Buffer Replacement policy in database

LRU = Least Recently Used

• It defines the policy to evict elements from the cache to make room for new elements when the cache is full, therefore it discards the least recently used items first.

• refer = pass

Example Below:

#include<iostream>
#include<list>
#include<unordered_map>

using namespace std;
 
class LRUCache {
    
  protected:

    list<int> dq;
    unordered_map<int, list<int>::iterator> map_;
    int csize; 
 
  public:
      LRUCache(int);
      void refer(int);
      void display();
};
 

LRUCache::LRUCache(int n)
{
    csize = n;
}
 
void LRUCache::refer(int x)
{
    if (map_.find(x) == map_.end()) {
        if (dq.size() == csize) {
            // if full, delete least recently used element
            int last = dq.back();
            
            dq.pop_back();
            map_.erase(last);
        }
    }
    else{
        dq.erase(map_[x]);
    }
        
    dq.push_front(x);
    map_[x] = dq.begin();
}

void LRUCache::display()
{   
    for (auto it = dq.begin(); it != dq.end();
         it++)
        cout << (*it) << " ";
 
    cout << endl;  
}
 
// Driver Code
int main()
{
    LRUCache cac(4);
 
    cac.refer(1);
    cac.refer(2);
    cac.refer(3);
    cout << "Cache: ";
    cac.display();
    cac.refer(1); // 1 is already in our LRU
    cout << "Cache: ";
    cac.display();
    cout << "The Cache Will be full now"<< endl;
    cac.refer(4);
    cout << "Cache: ";
    cac.display();
    cac.refer(5);
    cout << "Cache: ";
    cac.display();
    cac.refer(9);
    cout << "Cache: ";
    cac.display();
    cac.refer(7);
    cout << "Cache: ";
    cac.display();
    cac.refer(4);
    cout << "Cache: ";
    cac.display();

    
}

Output:

Cache: 3 2 1 
Cache: 1 3 2 
The Cache Will be full now
Cache: 4 1 3 2 
Cache: 5 4 1 3 
Cache: 9 5 4 1 
Cache: 7 9 5 4 
Cache: 4 7 9 5 

updating