Leetcode--LRU Cache

http://oj.leetcode.com/problems/lru-cache/

参考了这篇文章，是用双向链表和unordered_map来实现的，难点在于复杂的指针操作，以及每次get，set之后都要考虑map是否要改变，还有，要同步更新size，这也容易遗忘

最后，我从中抽象出一个moveToHead的函数，简化了代码

 

本来想用单链表实现的，到中途发现似乎不行

事后的思考：也许有单独的不存储数据的头结点和尾节点会使得真正操作简单一点，可以避免考虑很多边界情况，NULL指针问题

 

//seems that single linked list is not enough
#include <cstdio>
#include <cstdlib>
#include <unordered_map>
using namespace std;
class Node{
public:
    int key;
    int value;
    Node *next;
    Node *prev;
    Node(int k, int v, Node* n, Node *pre):key(k),value(v),next(n), prev(pre){}
};
class LRUCache{
public:
    LRUCache(int capacity) {
        if(capacity < 0){
            printf("error");
            exit(-1);
        }
        _head = _tail = NULL;
        _size = 0;
        _cap = capacity;
    }
    ~LRUCache(){
        if(_head == NULL) return;
        Node *p = _head, *q = _head->next;
        while(q){
            delete p;
            p = q;
            q = q->next;
        }
        delete p;
    }
    int get(int key) {
        auto it = _map.find(key);
        if(it == _map.end()){
            return -1;
        } else {
            moveToHead(it->second);
            return it->second->value;
        }
    }
    
    void set(int key, int value) {
        if(_cap == 0) return;
        if(_cap == 1){
            if(_size == 1){
                _map.erase(_head->key);
                _map[key] = _head;
                _head->key = key;
                _head->value = value;
                return;
            } else {//_size==0
                _head = _tail = new Node(key,value,NULL,NULL);
                _map[key] = _head;
                _size++;
                return;
            }
        }
        //_cap >= 2
        auto it = _map.find(key);
        if(it == _map.end()){
            if(_size < _cap){
                Node *p = new Node(key,value,_head, NULL);
                if(_head == NULL){
                    _head = _tail = p;
                    _map[key] = _head;
                    _size++;
                    return;
                }
                _head->prev = p;
                _head = p;
                _map[key] = p;
                _size++;
            } else {//_size >= _cap >= 0, actually, we always ensure that _cap >= _size, so _size must equal to _cap
                //_size == _cap >= 2
                Node *p = _tail;
                _map.erase(_tail->key);
                p->key = key;
                p->value = value;
                
                _map[key] = p;
                moveToHead(p);
            }
        } else {
            it->second->value = value;
            moveToHead(it->second);
        }
    }
    void moveToHead(Node* p){
        if(p==_head) return;
        p->prev->next = p->next;
        if(p == _tail){
            _tail = p->prev;
        } else {
            p->next->prev = p->prev;
        }
        p->next = _head;
        p->prev = NULL;
        _head->prev = p;
        _head = p;
    }
private:
    unordered_map<int,Node*> _map;
    Node *_head, *_tail;
    int _size;
    int _cap;
};

编译要指定C++11（当然，你还要提供一个main函数才行），对于g++来说，添加 -std=c++11