Least Recently Used cache mechanic, cache recently used value

lru_cache.cpp

/*
A cache is a component that stores data so future requests for that data can be served faster. The data stored in a cache might be the results of an earlier computation, or the duplicates of data stored elsewhere. A cache hit occurs when the requested data can be found in a cache, while a cache miss occurs when it cannot. Cache hits are served by reading data from the cache which is faster than recomputing a result or reading from a slower data store. Thus, the more requests that can be served from the cache, the faster the system performs.

One of the popular cache replacement policies is: "least recently used" (LRU). It discards the least recently used items first.
*/

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

struct Node{
   Node* next;
   Node* prev;
   int value;
   int key;
   Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
   Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
};

class LRUCache {
private:
  map<int,Node*> mp; //map the key to the node in the linked list
  int cp;  //capacity
  Node* tail; // double linked list tail pointer
  Node* head; // double linked list head pointer
  void insert(int key, int value) {
    auto node = new Node(key, value);
    node->next = head;
    head->prev = node;
    head = node;
    mp[key] = node;
    if(mp.size() > cp) {
      auto tail_it = mp.find(tail->key);
      mp.erase(tail_it);
      tail = tail->prev;
      delete tail->next;
      tail->next = 0;
    }
  }
  void pop(Node* node) {
    if(!node->prev) {
      return;
    }
    node->prev->next = node->next;
    node->next = head;
    head->prev = node;
    head = node;
  }
  void init(int key, int value) {
    auto node = new Node(key, value);
    head = tail = node;
    mp[key] = node;
  }
public:
  LRUCache(int cap) {
    cp = cap;
    head = 0;
    tail = 0;
  }
  virtual void set(int key, int value) override {
    auto it = mp.find(key);
    if(it == mp.end()) {
      if(!head) {
        return init(key, value);
      }
      return insert(key, value);
    }
    auto node = (*it).second;
    node->value = value;
  }
  virtual int get(int key) override {
    auto it = mp.find(key);
    if(it == mp.end()) {
      return -1;
    }
    auto node = (*it).second;
    pop(node);
    return node->value;
  }
};

int main() {
   int n, capacity,i;
   cin >> n >> capacity;
   LRUCache l(capacity);
   for(i=0;i<n;i++) {
      string command;
      cin >> command;
      if(command == "get") {
         int key;
         cin >> key;
         cout << l.get(key) << endl;
      } 
      else if(command == "set") {
         int key, value;
         cin >> key >> value;
         l.set(key,value);
      }
   }
   return 0;
}

test_case.txt

500000 644
get 3
get 19
get 8
set 1 1195
set 5 1404
get 6
set 15 1020
set 7 1010
get 8
set 7 1628
set 16 1498
get 11
get 14
get 19
get 8
set 12 267
set 19 125
get 8
set 15 1241
set 8 1936
get 1
set 17 1162
set 13 151
get 19
get 20
get 14
get 16
get 7
set 2 1305
set 12 287
set 9 160
get 16
get 17
set 5 1524
set 16 81
set 4 312
set 9 89
set 19 1306
set 18 1041
set 16 237
get 8
set 11 387
get 1
get 8
set 7 1733
set 1 1652
get 17
get 8
set 20 1992
set 5 1290
set 13 270
set 3 1236
set 5 1441
set 15 743
set 19 165
get 18
get 17
set 16 193
set 14 1146
get 1
get 9
set 9 831
set 5 444
set 3 302
set 12 1973
get 19

test_result.txt

-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
1195
125
-1
-1
1498
1628
1498
1162
1936
1195
1936
1162
1936
1041
1162
1652
89
165