LeetCode #146：LRU Cache(实现 LRU 缓存)

题目描述

考研 OS 和计组的高频考点，当初只会纸上做题手算替换页面和 Cache，现在需要手撸代码了。由于要求 get() 和 put() 函数在 O(1) 的复杂度执行，采用 Hashmap 映射双链表结点的方法，写到一半迭代器的用法忘了还去搜了半天【cai

class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->front = new struct Node(0, 0);
        this->end = new struct Node(0, 0);
        this->front->next = end;
        this->end->prev = front;
    }
    
    int get(int key) {

        unordered_map<int, struct Node*>::iterator it = m.find(key);
        if(it != m.end()) { //检查map中是否已经存在该key
            struct Node* pNode = it->second;

            //把这个结点拆下来放到list头部
            teardownNode(pNode);           
            insertNodeAtFront(pNode);
            
            return pNode->value; //返回该值
        } else {
            return -1;
        }
    }
    
    void put(int key, int value) {

        unordered_map<int, struct Node*>::iterator it = m.find(key);
        if(it != m.end()) { //当key已经存在于map中时，只需修改对应链表结点的值
            struct Node* pNode = it->second;
            pNode->value = value;

            //把这个结点拆下来放到list头部
            teardownNode(pNode);          
            insertNodeAtFront(pNode);
        } else { //否则（仅缓存满时）删去链尾最近最久未使用的结点并插入新值
            if(m.size() >= capacity) { 
                struct Node* d = end->prev;
                m.erase(d->key);
                teardownNode(d);
                delete d;
            }   
            struct Node* pNode = new Node(key, value);
            m[key] = pNode;      
            insertNodeAtFront(pNode);
        }
    }

private:  
    struct Node {
        int key;
        int value;
        struct Node* prev;
        struct Node* next;
        
        Node(int key, int value) {
            this->key = key;
            this->value = value;
            this->prev = NULL;
            this->next = NULL;
        }
    };
    
    int capacity = 0;
    
    struct Node* front = NULL; //指向不存放数据的头结点
    struct Node* end = NULL; //指向不存放数据的末尾结点
    
    unordered_map<int, struct Node*> m;

    void insertNodeAtFront(struct Node* pNode) {
        pNode->next = front->next;
        front->next->prev = pNode;
        front->next = pNode;
        pNode->prev = front;
    }

    void teardownNode(struct Node* pNode) {
        pNode->prev->next = pNode->next;
        pNode->next->prev = pNode->prev;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */