fork(6) download
copy 
  1. #include<iostream>
  2. #include<map>
  3.  
  4. using namespace std;
  5.  
  6. struct node
  7. {
  8.   int pg;
  9.   struct node *next, *prev;
  10. };
  11.  
  12. class LRUCache
  13. {
  14.   int size;
  15.   int MAXSZ;
  16.   struct node *head,*tail;
  17.   public:
  18.   LRUCache(int maxsize){
  19.     MAXSZ=maxsize;
  20.     size=0;
  21.     head=new node();
  22.     tail=new node();
  23.     head->pg= tail->pg=-99;
  24.     head->next= tail;
  25.     head->prev= tail->next= NULL;
  26.     tail->prev= head;
  27.   }
  28.  
  29.   map<int, struct node *> m;
  30.   void add_to_head(node * );
  31.   void remove_from_list(node *);
  32.  
  33.   public:
  34.   void get();
  35.   void put (int pgno);
  36. };
  37. void LRUCache::add_to_head(struct node *n){
  38.   n->next= head->next;
  39.   n->prev= head;
  40.   n->next->prev= n;
  41.   head->next= n;
  42. }
  43.  
  44. void LRUCache::remove_from_list(node *n){
  45.   if (size==0)
  46.     return;
  47.   n->prev->next= n->next;
  48.   n->next->prev= n->prev;
  49. }
  50.  
  51. void LRUCache::put(int pgno){
  52.   if (m.find(pgno)==m.end()){
  53.     if (size >= MAXSZ)
  54.     {
  55.       m.erase(tail->prev->pg);
  56.       remove_from_list(tail->prev);
  57.     }
  58.     else size++;
  59.     struct node *nn = new node();
  60.     nn->pg=pgno;
  61.     add_to_head(nn);
  62.     m.insert(make_pair(pgno,nn));
  63.   }
  64.   else{
  65.     struct node *n= m[pgno];
  66.     remove_from_list(n);
  67.     add_to_head(n);
  68.   }
  69. }
  70. void LRUCache::get(){
  71.   struct node *temp=head;
  72.   while (temp!=NULL ){
  73.     if(temp->pg != -99)cout << temp->pg << " ";
  74.     temp=temp->next;
  75.   }
  76.   cout << endl;
  77. }
  78.  
  79. int main(){
  80.   LRUCache lru(3);//declare
  81.   //lru.get();
  82.   lru.put(1);
  83.   lru.put(2);
  84.   lru.get();
  85.   lru.put(1);
  86.   lru.get();
  87.   lru.put(3);
  88.   lru.get();
  89.   lru.put(4);
  90.   lru.get();
  91.   return 0;
  92. }
Success #stdin #stdout 0s 4412KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 1 
1 2 
3 1 2 
4 3 1
https://ideone.com/DFql9R
LRU Cache
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!