LRU cache

// author: Tecker Yu
// time: 92 ms, 99.55%
// mem: 38 M, 84.45% 
class LRUCache {
public:
    struct Node {
        int key;
        int val;
        Node* prev;
        Node* next;
        Node(int k, int v) {
            key = k;
            val = v;
        }
    };
    
    LRUCache(int capacity) {
        cap = capacity;
        head = NULL;
        tail = NULL;
        //op = 0;
    }
    
    void print() {
        Node* h = head;
        //cout<<"OP:"<<op<<endl;
        assert(head->prev == NULL);
        while(h) {
            if (h->next) assert(h->next->prev == h);
            cout<<h->key<<":"<<h->val<<endl;
            h=h->next;
        }
    }
    
    int get(int key) {
        //++op;
        if (!m.count(key)) return -1;
        
        Node* n = m[key];
        if (n == head) {
            //print();
            return n->val;
        }
		// 是尾部节点
        if (n == tail) {
            tail = tail->prev;
        }
		// 不是尾部节点需要将前继和后继进行连接
        else {
            n->next->prev = n->prev;
        }
        n->prev->next = n->next;
        n->prev = NULL;
        n->next = head;
        head->prev = n;
        head = n;
        
        //print();
        return n->val;
    }
    
    void put(int key, int value) {
        //++op;
        if (m.count(key)) {
            Node* n = m[key];
            n->val = value;
            if (n == head) return;
            if (n == tail) tail = n->prev;
            else {
                n->next->prev = n->prev;
            }
            n->prev->next = n->next;
            n->prev = NULL;
            n->next = head;
            head->prev = n;
            head = n;
            return;
        }
        Node* n = new Node(key, value);
        if (head!=NULL) {
            n->next = head;
            head->prev = n;
            if (tail == NULL) {
                tail = head;
                tail->next = NULL;
            }
        }
        head = n;
        head->prev = NULL;
        m.insert({key, n});
        if (m.size() > cap) {
            m.erase(tail->key);
            Node* n = tail->prev;
            tail->prev->next = NULL;
            //delete tail;
            tail = n;
        }
    }
    
    int cap;
    //int op;
    Node* head;
    Node* tail;
    unordered_map<int, Node*> m;
};

#include <bits/stdc++.h> 
using namespace std; 
  
class LRUCache { 
    // store keys of cache 
    list<int> dq; 
  
    // store references of key in cache 
    unordered_map<int, list<int>::iterator> ma; 
    int csize; // maximum capacity of cache 
  
public: 
    LRUCache(int); 
    void refer(int); 
    void display(); 
}; 
  
// Declare the size 
LRUCache::LRUCache(int n) 
{ 
    csize = n; 
} 
  
// Refers key x with in the LRU cache 
void LRUCache::refer(int x) 
{ 
    // not present in cache 
    if (ma.find(x) == ma.end()) { 
        // cache is full 
        if (dq.size() == csize) { 
            // delete least recently used element 
            int last = dq.back(); 
  
            // Pops the last elmeent 
            dq.pop_back(); 
  
            // Erase the last 
            ma.erase(last); 
        } 
    } 
  
    // present in cache 
    else
        dq.erase(ma[x]); 
  
    // update reference 
    dq.push_front(x); 
    ma[x] = dq.begin(); 
} 
  
// Function to display contents of cache 
void LRUCache::display() 
{ 
  
    // Iterate in the deque and print 
    // all the elements in it 
    for (auto it = dq.begin(); it != dq.end(); 
         it++) 
        cout << (*it) << " "; 
  
    cout << endl; 
}