Description

Submission

#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 Cache{
   
   protected: 
   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
   virtual void set(int, int) = 0; //set function
   virtual int get(int) = 0; //get function

};

class LRUCache : public Cache
{
public:
    LRUCache(int capacity)
    {
        Cache::cp = capacity;
    }

      ~LRUCache()
    {
        for(auto n = head; n != NULL;)
        {
            auto t = n;
            n = n->next;
            delete t;
        }
    }

    int get(int key)
    {
        auto res = mp.find(key);
        if(res != mp.end()) {
            // move to front
            if(res->second == tail)
            {
                if(tail != head)
                {
                    tail = tail->prev;
                    tail->next = NULL;
                    res->second->next = head;
                    res->second->prev = NULL;
                    head->prev = res->second;
                    head = res->second;
                }
            } else if(res->second != head) {
                res->second->prev->next = res->second->next;
                res->second->next->prev = res->second->prev;
                res->second->prev = NULL;
                res->second->next = head;
                head->prev = res->second;
                res->second->next = head;
                head = res->second;
            }
            // return the result
            return res->second->value;
        } else {
            return -1;
        }
    }

    void set(int key, int value) {
        auto res = mp.find(key);

        if(res != mp.end()) {
            res->second->value = value;
        } else {
            if(mp.size() == cp) {
                // if the size is not enough
                if(mp.size() == 1) {
                    mp.erase(head->key);
                    mp.insert(make_pair(key, head));
                    head->value = value;
                    head->key = key;
                } else {
                    mp.erase(tail->key);
                    mp.insert(make_pair(key, tail));
                    tail->value = value;
                    tail->key = key;
                    tail = tail->prev;
                    head->prev = tail->next;
                    tail->next->next = head;
                    tail->next->prev = NULL;
                    head = tail->next;
                    tail->next = NULL;
                }
            } else {
                // if the size is enough
                if(mp.size() == 0) {
                    head = new Node(key, value);
                    tail = head;
                    mp.insert(make_pair(key, head));
                } else {
                    Node* node = new Node(NULL, head, key, value);
                    head->prev = node;
                    head = node;
                    mp.insert(make_pair(key, node));
                }

            }
        }
    }
};


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;
}