LRU Cache Implementation.

LRU Cache Implementation.

We use two data structures to implement an LRU Cache.

1. The queue is implemented using a doubly-linked list. The maximum size of the queue will be equal to the total number of frames available (cache size). The most recently used pages will be near the front end and the least recent pages will be near the rear end.
2. A Hash with page number as key and address of the corresponding queue node as value.
3. When a page is referenced, the required page may be in the memory. If it is in the memory, we need to detach the node of the list and bring it to the front of the queue.
   If the required page is not in memory, we bring that in memory. In simple words, we add a new node to the front of the queue and update the corresponding node address in the hash. If the queue is full, i.e. all the frames are full, we remove a node from the rear of the queue, and add the new node to the front of the queue.

 //Our code here
 #include<bits/stdc++.h>

 using namespace std;
 class LRUCache {
     public:
         LRUCache(int);

     int get(int);

     void set(int, int);
 };
 int main() {
     int t;
     cin >> t;
     while (t--) {
         int n;
         cin >> n;
         LRUCache * l = new LRUCache(n);
         int q;
         cin >> q;
         for (int i = 0; i < q; i++) {
             string a;
             cin >> a;
             if (a == "SET") {
                 int aa, bb;
                 cin >> aa >> bb;
                 l - > set(aa, bb);
             } else if (a == "GET") {
                 int aa;
                 cin >> aa;
                 cout << l - > get(aa) << " ";
             }
         }
         cout << endl;
     }
 }

 }


 int maxSize;
 list < pair < int, int >> dq;
 unordered_map < int, list < pair < int, int >> ::iterator > ma;
 LRUCache::LRUCache(int N) {
     maxSize = N;
     dq.clear();
     ma.clear();
 }

 /*Sets the key x with value y in the LRU cache */
 void LRUCache::set(int x, int y) {
     //Your code here
     if (ma.find(x) == ma.end()) {
         if (dq.size() == maxSize) {
             int Lx = dq.back().first;
             int Ly = dq.back().second;
             dq.pop_back();
             dq.push_front({ x, y });
             ma.erase(Lx);
             ma[x] = dq.begin();
         } else {
             dq.push_front({ x, y });

             ma[x] = dq.begin();
         }
     } else {
         auto it = ma.find(x);
         dq.erase(it - > second);
         dq.push_front({ x, y });

         ma[x] = dq.begin();
     }
 }
 /*Returns the value of the key x if
 present else returns -1 */
 int LRUCache::get(int x) {
     //Your code here
     if (ma.find(x) == ma.end()) {
         return -1;
     }
     auto it = ma.find(x);
     int d = ( * (it - > second)).second;
     dq.erase(it - > second);
     dq.push_front({ x, d });
     ma[x] = dq.begin();
     return d;
 }